14 Взаимоисключение
процессов на основе P,V операций над семафором S. Алгоритмы P,V
операций.
Для устранения
активного ожидания процесса CPU может быть использован так называемый аппарат
событий. С помощью этого средства могут решаться не только проблемы взаимного
исключения, но и более общие задачи синхронизации процессов. В разных
операционных системах аппарат событий реализуется по своему, но в любом случае
используются системные функции аналогичного назначения, которые условно назовем
WAIT(x) и POST(x), где x - идентификатор некоторого события. На рисунке показан
фрагмент алгоритма процесса, использующего эти функции. Если ресурс занят, то
процесс не выполняет циклический опрос, а вызывает системную функцию 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
Алгоритмы P,V операций
Для P(S)
Запрет прерываний
S:=S-1
IF (S<0)
Блокировать процесс по S
Выбрать след. готовый
процесс
FI
Разрешить прерывание
|
Для V(S)
Запрет прерываний
S:=S+1
IF (S<=0)
деблокировать любой процесс
ожидающий S
FI
Разрешить прерывание
|
Вообще, семафор – это переменная,
которая исключает доступ к ресурсу, который уже занят.
Если S>0,
то ресурс был свободен, не нужно деблокировать люб. процесс. Начальное значение
S – это количество процессов,
которые могут пройти семафор до операции V(S), у двоичного <=1.
Нарисовать врем.диагр. двоич.
симафора (2 процесса,ядро,1 ресурс)