Синхронизация процессов на основе семафорных операций

Для устранения активного ожидания процесса CPU может быть использован так называемый аппарат событий. С помощью этого средства могут решаться не только проблемы взаимного исключения, но и более общие задачи синхронизации процессов. В разных операционных системах аппарат событий реализуется по-своему, но в любом случае используются системные функции аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x - идентификатор некоторого события. На рис. 4 показан фрагмент алгоритма процесса, использующего эти функции. Если ресурс занят, то процесс не выполняет циклический опрос, а вызывает системную функцию WAIT(D), здесь D обозначает событие, заключающееся в освобождении ресурса D. Функция WAIT(D) переводит активный процесс в состояние ОЖИДАНИЕ и делает отметку в его дескрипторе о том, что процесс ожидает события D. Процесс, который в это время использует ресурс D, после выхода из критической секции выполняет системную функцию POST(D), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события D, в состояние ГОТОВНОСТЬ.

Обобщающее средство синхронизации процессов предложил Дейкстра, который ввел два новых примитива. В абстрактной форме эти примитивы, обозначаемые P и V, оперируют над целыми неотрицательными переменными, называемыми семафорами. Пусть S такой семафор. Операции определяются следующим образом:

V(S) : переменная S увеличивается на 1 одним неделимым действием; выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время выполнения этой операции.

P(S) : уменьшение S на 1, если это возможно. Если S=0, то невозможно уменьшить S и остаться в области целых неотрицательных значений, в этом случае процесс, вызывающий P-операцию, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также является неделимой операцией.

В частном случае, когда семафор S может принимать только значения 0 и 1, он превращается в блокирующую переменную. Операция P заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания, в то время как V-операция может при некоторых обстоятельствах активизировать другой процесс, приостановленный операцией P (сравните эти операции с системными функциями WAIT и POST).

Рассмотрим использование семафоров для взаимоисключения процессов.

Двоичный семафор

С каждым семафором связывается список процессов, ожидающих разрешения пройти семафор.

ОС может выполнить три действия над процессами:

1) может назначить для исполнения готовый процесс;

2) может заблокировать исполняющийся процесс и поместить его в список, связанный с конкретным семафором;

3) может деблокировать процесс, тем самым переводя его в готовое к исполнению состояние и позволяя ему когда-нибудь возобновить исполнение.

Находясь в списке заблокированных, ожидающий процесс не проверяет семафор непрерывно, как в случае активного ожидания. Вместо него на процессоре может исполняться другой процесс (рис. 5, 6).

Рис.5. Временная диаграмма для двоичного семафора (S)

До момента t₁ ресурс был не занят. В момент t₁ процесс Pr1, выполняет операцию P(S) и входит в критический участок (CS). В момент t₂ процесс Pr2 выполняет операцию P(S) – занять ресурс, это приводит к изменению: S = -1 – означает, что Pr2 в состоянии блокирования.В момент t₃ – конец критического участка для процесса Pr1. Выполняется операция V(S) – освободить, это приводит к увеличению значения S на единицу (т.е. S=0). Для процесса блокированного (Pr2) это сигнал на разблокировку и предоставления ему ресурса. В момент t₄ процесс Pr2 освобождает ресурс, выполняется операция V(S), которая изменяет значение S на 1 (т.е. S=1).

Достоинство синхронизации на основе семафорных операций – отсутствие активного ожидания представления ресурса.

Рис. 6. Временная диаграмма для двоичного семафора (семафоры - S1 и S2)

Б – блокировано, СS1 и CS2 – критические участки 1 и 2, идентифицированные семафорами S1 и S2.