Операции P и V над семафорами
В 1968 г. Э. Дейкстра предложил удобную форму механизма захвата/освобождения ресурсов, которую он назвал операциями P и V над считающими семафорами. Считающим семафором называют целочисленную переменную, выполняющую те же функции, что и байт блокировки. Однако в отличие от последнего она может принимать кроме "0" и "1" и другие целые положительные значения.
Семафоры – это часть абстракции, поддерживающая очередь постоянно ожидающих процессов.
Операции P и V над семафором S могут быть определены следующим образом.
P(S):
1. Уменьшить значение S на 1, т. е. S: = S – 1.
2. Если S < 0, выполнить ОЖИДАНИЕ (S).
V(S):
1. Увеличить значение S на 1, т. е. S : = S + 1.
2. Если S ³ 0, выполнить ОПОВЕЩЕНИЕ (S).
Операция ОЖИДАНИЕ (S) (WAIT) блокирует обслуживание процесса, делает соответствующую отметку об этом и связывает процесс со значением переменной S.
Операция ОПОВЕЩЕНИЕ (S) (SIGNAL) просматривает связанный с переменной S список блокированных процессов. Если в списке есть процессы, ожидающие освобождения некоторого ресурса, управляемого (сигнализируемого) S, один из них переводится в состояние готовности, а в соответствующей ему записи делается отметка. С этого момента процесс становится опять доступным планировщику.
По определению, ожидание, связанное с операцией P(S), не является ожиданием "зависания", так как ожидающие процессы не используют центральный процессор. Так как несколько процессов могут ожидать операцию P(S) над отдельным семафором, во время приращения должен быть осуществлен выбор, какую контрольную точку процесса сделать доступной. Алгоритм выбора не определен, за исключением требования равнодоступности процессов, т. е. никакой процесс не может быть "забыт".
Типичным примером использования алгоритма семафоров является задача производитель/потребитель. Задается максимальная емкость хранилища. Производитель не должен переполнять его, а потребитель не должен пытаться брать продукцию из пустого хранилища.
Наиболее употребительные операции над семафорами:
· создать семафор;
· запросить состояние семафора;
· изменить состояние семафора;
· уничтожить семафор.
Операции над семафорами в силу своей неделимости позволяют блокировать или активизировать процессы при освобождении или запросах ресурсов любого типа (памяти, процессоров, устройств ввода-вывода и т. п.).
Наиболее показательно аппарат семафоров можно применить на следующей задаче.
Три курильщика сидят за столом. У одного есть табак, у другого – бумага, у третьего – спички. На столе могут появиться извне два из трех упомянутых предмета. Появившиеся предметы забирает тот курильщик, у которого будет полный набор предметов. Он сворачивает папиросу, раскуривает ее и курит. Новые два предмета могут появиться на столе только после того, как он кончит курить. Другие курильщики в это время не могут начать курение.
Задание. Описать с помощью P и V – операций над семафорами – систему процессов, которая моделирует взаимодействия этих курильщиков.
Указание. Выделить шесть процессов, три из которых соответствуют трем курильщикам X, Y, Z, а три других имеют следующее назначение: А – поставляет спички и бумагу, В – табак и спички, С – бумагу и табак.
Требование. Процессы-поставщики не знают, какие предметы находятся у курильщиков.
Проблема взаимоисключения включает в себя нахождение протокола, который может использоваться отдельными процессами в момент входа в критический раздел или выхода из него.
Рассмотренные приемы синхронизации просты и сравнительно эффективны, однако их использование приводит порой к сложным и труднопостижимым конструкциям, которые чувствительны к незначительным изменениям. Рассмотрим более простые в реализации приемы, которые дают уверенность программисту в правильности написанной программы. Но сначала рассмотрим еще один способ представления процессов.
