если 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. Характеристики очередей – следующие:

I1= 50 мкс, N1= 6; I2= 150 мкс, N2= 12; I3= 400 мкс, N3 > 12

Блок

управления

задачей

и т. д.

…

Блок

управления

процессом

и т. д.

…

процессом

Блок

управления

процессом

и т. д.

…

и имеется программа, которой требуется для выполнения 5000 мкс времени. В этом случае при наличии только одной первой очереди процессу потребовалось 100 перезагрузок в ОП. В случае трех вышеуказанных очередей ей потребовалось бы всего 26 перезагрузок.

При таком алгоритме планирования процессорного времени преимущественное право обслуживания получают более время емкие процессы. Пусть имеются те же три очереди и в каждой из них находится 6 заданий. Задания 1 – очереди в сумме получат 300 мкс, 2 – й очереди – 900 мкс, а 3 –й – 2400 мкс. На однократный просмотр и обслуживание всех заданий уйдет 3600 мкс. Итак 66% времени будет выделено на обслуживание самых крупных заданий. Для мелких заданий промежутки между интервалами обслуживания составят 3550 мкс.