15 Двоичный семафор. Считающий семафор. Алгоритмы. Временные диаграммы. Двоичный семафор. Мьютексы.

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

ОС может выполнить три действия над процессами: 1) может назначить для исполнения готовый процесс; 2) может заблокировать исполняющийся процесс и поместить его в список, связанный с конкретным семафором; 3) может деблокировать процесс, тем самым переводя его в готовое к исполнению состояние и позволяя ему когда-нибудь возобновить исполнение.

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

Замечание: все CS должны быть одинаковы по длительности, поэтому чтобы упростить временные диаграммы здесь и далее применено сокращение -

До момента t1 ресурс был не занят. В момент t1 процесс Pr1, выполняет операцию P(S) и входит в критический участок (CS).

В момент t2 процесс Pr2 выполняет операцию P(S) - занять ресурс, это приводит к изменению: S = -1 - означает, что Pr2 в состоянии блокирования.

В момент t3 - конец критического участка для процесса Pr1. Выполняется операция V(S) - освободить, это приводит к увеличению значения S на единицу (т.е. S=0). Для процесса блокированного (Pr2) это сигнал на разблокировку и предоставления ему ресурса. В момент t4 процесс Pr2 освобождает ресурс, выполняется операция V(S), которая изменяет значение S на 1 (т.е. S=1).

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

Универсальный семафор (считающий семафор)- это пара операций - примитив и аргумент-семафор, имеющий диапазон целых чисел. Числовые семафоры могут принимать отрицательные значения: если S отрицательно, то |S| - это число процессов, заблокированных по S.

Начальное значение S - количество процессов, которые могут пройти семафор до первой операции V(S) (например у двоичного - начальное значение S=1). Пример временной диагра-ммы считающего семафора
(1 ресурс, семафор - S, 5 процессов)

Mutex неспособен считать, может только управлять взаимоисключаю-щим  доступом к совместно использу-емому ресурсу. Mutex – переменная, которая может находиться в одном из двух состояний (БЛОК и НЕБЛОК), для этого требуется всего один бит. Значение Mutex устанавливается 2 процедурами: Если процесс собирается войти в CS, он вызывает Mutex_lock, если вход в CS разрешен, запрос выполняется , если запрещен, то вызывающий процесс блокирован пока другой не выйдет из CS, вызывя  Mutex_unlock.