Семафоры Дейкстры

Семафор – это переменная специального типа, над которым процесс может выполнить только две операции: закрытия Р и открытия V. Они являются примитивами в отношении семафора, который указывается в качестве параметра операций. Семафор выполняет в данном случае роль вспомогательного критического ресурса. P- и V-операции неделимы при своем выполнении и взаимно исключают друг друга. При этом попытка нескольких параллельных процессов (например, в мультипроцессорной системе) одновременно выполнить примитив над одним и тем же семафором будет успешной только у одного процесса (неизвестно, у какого именно), а остальные процессы будут исключены на время выполнения примитива.

При использовании семафорного механизма сначала проверяется состояние вспомогательного критического ресурса (значение семафора), а затем производится доступ к основному ресурсу или отказ от него на время. При отказе доступа используется режим пассивного ожидания, что повысит эффективность работы системы.

На практике используются различные виды семафорных механизмов и их модификаций. Они отличаются начальным значением и диапазоном изменения значений семафора, логикой действий над семафорами, количеством семафоров, доступных для обработки при исполнении отдельного примитива. В простейшем случае допустимыми значениями семафора являются целые числа. Диапазон их изменения может быть ограничен только неотрицательными значениями. Семафор, допустимыми значениями которого являются только числа 0 и 1, называют двоичным.

Операция P(S) – проверка значения семафора, если 1, то переход к следующей за примитивом операции, иначе процесс снимается с выполнения и переводится в состояние пассивного ожидания.

Операция V(S) - увеличение значения семафора на 1 и перевод одного или несколких процессов в состояние готовности.