Все описанные выше ключевые понятия, относящиеся к взаимоисключению, Дейкстра суммировал в своей концепции семафоров. Семафор – это защищенная переменная, значение которой можно опрашивать и менять только при помощи специальных операций P и V и операции инициализации, которую мы будем называть «инициализациясемафора». Двоичные семафоры могут принимать только значения 0 и 1. Считающие семафоры (семафоры со счетчиками) могут принимать неотрицательные целые значения. Операция P над семафором записывается, как P(S) и выполняется следующим образом:
если S > 0
то S := S – 1
иначе (ожидать на S).
Операция V над семафором записывается, как V(S) и выполняется следующим образом:
если (один или более процессов ожидают на S) то (разрешить одному из этих процессов продолжить работу) иначе S := S + 1.
Предполагается, что очередь процессов, ожидающих на S, обслуживается в соответствии с дисциплиной «первый пришедший обслуживается первым». Как и операция testandset, операции P и V являются неделимыми. Участки взаимоисключения по семафору S в процессах обрамляются операциями P(S) и V(S). Если одновременно несколько процессов попытаются выполнить операцию P(S), это будет разрешено только одному из них, а остальным придется ждать.
Семафоры и операции над ними могут быть реализованы как программно, так и аппаратно. Как правило они реализуются в ядре ОС, где производится управление сменой состояния процессов.
Ниже приводится пример того, каким образом можно обеспечить взаимоисключение при помощи семафоров. Здесь примитив P(активный) – эквивалент для «входвзаимоисключения», а примитив V(активный) – для «выходвзаимоисключения».
program примерсемафораодин;
var активный: семафор;
procedure процессодин;
begin
while истина do
begin
предшествующиеоператорыодин;
P(активный);
критическийучастокодин;
V(активный);
прочиеоператорыодин
end
end;
procedure процессдва;
begin
while истина do
begin
предшествующиеоператорыдва;
P(активный);
критическийучастокдва;
V(активный);
прочиеоператорыдва
end
end;
begin
инициализациясемафора(активный,1);
parbegin
процессодин;
процессдва
parend
end.
Синхронизация процессов при помощи семафоров
Когда процесс выдает запрос ввода – вывода, он блокирует себя в ожидании завершения соответствующей операции ввода – вывода. Заблокированный процесс должен быть активизирован каким – то другим процессом. Подобное взаимодействие может служить примером функций, относящихся к протоколу блокирования/возобновления.
Рассмотрим более общий случай, когда одному процессу необходимо, например, чтобы он получал уведомление о наступлении некоторого события. Предположим, что какой либо другой процесс может обнаружить, что данное событие произошло.
Программа показывает, каким образом при помощи семафора можно реализовать простой механизм синхронизации (блокирования/возобновления) для двух процессов.
program блокированиевозобновление;
var событие: семафор;
procedure процессодин;
/* этот процесс ожидает P(событие) наступления к-либо события */
/* P(событие) переводит его в состояние ожидания */
begin
предшествующиеоператорыодин;
P(событие);
прочиеоператорыодин
end;
procedure процессдва;
/* этот процесс активизирует V(событие) ждущий процесс */
/* V(событие) переводит ждущий процесс в активный */
begin
предшествующиеоператорыдва;
V(событие);
прочиеоператорыдва
end;
begin
инициализациясемафора(событие,0);
parbegin
процессодин;
процессдва
parend
end.
Здесь «процессодин» выполняет некоторые «предшествующиеоператорыодин», а затем операцию P(событие). Ранее при инициализации семафор был установлен в нуль, поэтому «процессодин» будет ждать. Со временем «процессдва» выполнит операцию V(событие), сигнализируя о том, что данное событие произошло (например завершилась операция ввода/вывода). Тем самым «процессодин» получает возможность продолжить свое выполнение. Отметим, что подобный механизм будет выполнять свои функции даже в том случае, если «процессдва» обнаружит наступление события и просигнализирует об этом еще до того, как «процессодин» выполнит операцию P(событие); при этом семафор переключится из 0 в 1, так что операция P(событие) просто произведет обратное переключение из, 1 в 0, и «процессодин» продолжит свое выполнение без ожидания. Пара «производитель – потребитель» Когда в последовательной программе одна процедура вызывает другую и передает ей данные, обе эти процедуры вызываются частями единого процесса – они не выполняются параллельно. Если, однако, один процесс передает данные другому процессу, возникают определенные проблемы. Подобная передача может служить примером взаимодействия, или обмена информацией между процессами.
program парапроизводительпотребитель;
var исключительный доступ: семафор;
procedure процессодин;
begin
while истина do
begin
предшествующиеоператорыодин;
P(активный);
критическийучастокодин;
V(активный);
прочиеоператорыодин
end
end;
procedure процессдва;
begin
while истина do
begin
предшествующиеоператорыдва;
P(активный);
критическийучастокдва;
V(активный);
прочиеоператорыдва
end
end;
begin
инициализациясемафора(активный,1);
parbegin
процессодин;
процессдва
parend
end.
Квантование времени.
(Г. Лорин Х. М. Дейтел Операционные системы. «Ф и С» 1984г.)
Квантование – это выделение для выполнения каждой программы установленного временного интервала (кванта). По завершении этого интервала данная программа приостанавливается и начинает выполняться следующая. ОС (супервизор, диспетчер, координатор) циклически просматривает свою очередь, предоставляя всем программам по очереди фиксированные кванты времени.
Это наиболее простой способ управления более или менее однотипными задачами в системе разделения времени, которые запускаются с пользовательских терминалов, где каждому терминалу поставлена в соответствие некоторая фиксированная область оперативной памяти, и, где каждая задача запрашивает выполнение примерно одинаковых пользовательских функций. Как уже отмечалось ранее, начав выполнятся, задача становится процессом. В любом случае, ОС должна чем-то руководствоваться для определения момента времени для первого запуска процесса. Этот момент определяется на основании приоритета.
Приоритет – это число, характеризующее степень привилегированности процесса (потока) при использовании ресурсов компьютера, в частности процессорного времени. Чем выше приоритет, тем выше привилегии, тем меньше времени процесс (поток) будет проводить в очередях. Изначально приоритет может присваиваться операционной системой, а точнее, ее компонентой – планировщиком задач. В соответствии с приоритетом из процессов, готовых выполнению, образуется очередь. Процессы с более высоким приоритетом располагаются ближе к началу очереди. Для равноприоритетных процессов используется принцип FIFO (первый пришедший, первым обслуживается). В зависимости от предыстории времменных потребностей процесса его приоритет, может измененяться, может быть и неявно.
Циклические очереди с обратной связью. Циклические подочереди с обратной связью состоят из n подочередей.
Подочередь 1 Подочередь 2 ... Подочередь n
Процесс начинает выполняться в подочереди 1. Он становится в ней первым и получает I1 интервалов времени обслуживания. Затем этот процесс перемещается в конец той же подочереди, со временем снова становится первым и получает очередные I1 интервалов. Это повторяется N1 раз, после чего процесс попадает в подочередь 2. Далее, находясь в подочереди 2, он получает N2 по I2 интервалов обслуживания и перемещается в подочередь 3, и т. д. Попав в самую последнюю подочередь, процесс находится в ней до полного завершения выполнения. Находясь в подочереди х, процесс может получить управление только в том случае, если ни в одной из подочередей с меньшими номерами нет готовых выполнению процессов. Обычно соблюдаются следующие соотношения: Ni>Nj и Ii>Ij при i>j. Величины: n, Ni и Ii можно задавать при генерации ОС.
Стрелки означают, что по завершении некоторого фиксированного интервала обслуживания процесс может либо оставаться в своей подочереди, либо – переместиться в другую. Правила перемещения программ в подочередях иногда окончательно устанавливаются при создании системы, а иногда допускают параметризацию в процессе ее установки.
Такая структура может применяться в системах разделения времени (СРВ), где процесс подлежащий выполнению, всякий раз перегружается (подкачивается) в ОП, а по окончании выделенного интервала изгоняется из ОП во внешнюю память. В подобных системах загрузка / выгрузка процессов происходит довольно часто, и значит процессор подолгу простаивает. Можно разделив всю ОП на три раздела: «предыдущий», «текущий» и следующий, и на основании регулярности смены выполняющихся процессов, обеспечиваемой режимом квантования, в процессе выполнения «текущего» процесса, «загружать» следующий и выгружать - «предыдущий». Это вообще говоря возможно, если компьютер допускает параллельные операции.
Пример: пусть n = 3. Характеристики очередей – следующие:
и имеется программа, которой требуется для выполнения 5000 мкс времени. В этом случае при наличии только одной первой очереди процессу потребовалось 100 перезагрузок в ОП. В случае трех вышеуказанных очередей ей потребовалось бы всего 26 перезагрузок.
При таком алгоритме планирования процессорного времени преимущественное право обслуживания получают более время емкие процессы. Пусть имеются те же три очереди и в каждой из них находится 6 заданий. Задания 1 – очереди в сумме получат 300 мкс, 2 – й очереди – 900 мкс, а 3 –й – 2400 мкс. На однократный просмотр и обслуживание всех заданий уйдет 3600 мкс. Итак 66% времени будет выделено на обслуживание самых крупных заданий. Для мелких заданий промежутки между интервалами обслуживания составят 3550 мкс.
