Неделимость Р и V гарантирует целостность значений семафоров

Такой способ поддержки целостности Р и V операций реализуется аппаратно.

Семафорные примитивы Дейкстры

Семафор – переменная специального вида, которая доступна параллельным процессам для проведения только двух операций

P (от голанд. Proberen(проверить) – закрытие семафора

V (от голанд. Verboten(увеличить) – открытие семафора

Обращение к семафору и изменение его состояния осуществляется с помощью единого механизма, реализуемого одной непрерываемой командой.

Семафорные операции:

1. P(S)(закрытие семафора):

if S>0 S=S-1 и переход к следующей после примитива операции

if S=0 then {остановить процесс и поместить его в очередь ожидания к семафору S}

2. V(S)(открытие семафора):

if S=0 then {поместить один из ожидающих процессов очереди семафора S в очередь готовности}

else S=S+1

Если несколько процессов одновременно запрашивают Р или V операции над одним и тем же семафором, то эти операции будут выполняться последовательно в произвольном порядке.

Аналогично, если более одного процесса ждут после выполнения Р-операции и изменяемый семафор становится положительным, то конкретный ожидающий процесс, который выбирается для завершения операции, произволен и неизвестен.

Семафорные переменные могут быть использованы для синхронизации процессов:

• Р-примитив заключает в себе потенциальное ожидание вызывающих процессов,
• в то время как V-примитив может, возможно, активизировать некоторый ждущий процесс.

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

В простейшем случае семафор имеет один двоичный разряд, в который записывается текущий сигнал семафора 0 или 1.

Если на время работы программы с некоторым ресурсом доступ к нему со стороны других программ нужно запретить, то программа выполняет Р-операцию над семафором, устанавливая его сигнальный разряд в 0 и запрещая тем самым доступ к ресурсу.

По окончании работы с ресурсом программа выполняет V-операцию, устанавливая сигнальный разряд в 1 и тем самым снимая запрет.

Мютексы (mutex)

mutual exelusion semaphore (семафор взаимного исключения)

Мьютексы реализованы во многих ОС, их основное назначение - организация взаимного исключения для задач (потоков) из одного и того же или из разных процессов.

Мьютексы - это простейшие двоичные семафоры, которые могут находиться в одном из двух состояний — отмеченном или неотмеченном (открыт и закрыт соответственно).

• Когда процесс становится владельцем объекта mutex, последний переводится в неотмеченное состояние.
• Если процесс освобождает мьютекс, его состояние становится отмеченным.

Организация последовательного (а не параллельного) доступа к ресурсам с использованием мьютексов становится несложной, поскольку в каждый конкретный момент только одна задача может владеть этим объектом.

Для того чтобы объект mutex стал доступен задачам (потокам), принадлежащим разным процессам, при создании ему необходимо присвоить имя.

Потом это имя нужно передать «по наследству» задачам, которые должны его использовать для взаимодействия.

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

Если начальное значение мьютекса равно true, то считается, что процесс, создающий этот объект, будет им сразу владеть.

Можно указать в качестве начального значение false — в этом случае мьютекс не принадлежит ни одной из задач и только специальным обращением к нему можно изменить его состояние.

Для работы с мьютексом имеется несколько функций

функции создания такого объекта (CreateMutex),

функции открытия (Ореn Mutex),

ожидания событий (WaitForSingleObject и WaitForMultipleObjects)

и, наконец, освобождение этого объекта (ReleaseMutex).

Конкретные обращения к этим функциям и перечни передаваемых и получаемых параметров нужно смотреть в документации на соответствующую ОС.

Достоинства семафоров:

• простота
• независимость от количества процессов
• отсутствие «активнее: ожидания»)

Недостатки семафоров:

• слишком примитивны (не указывают непосредственно на синхронизирующее условие, с которым он связан или на критический ресурс)
• поэтому при построении сложных схем синхронизации алгоритмы решения задач получаются сложными, ненаглядными, затруднительными для доказательства их правильности.

Во многих ОС предусматриваются специальные системные вызовы для работы с критическими интервалами.

На рис. 5.1 показано, как с помощью этих функций реализовано взаимное исключение в операционных системах семейства Windows NT.

• Перед тем как начать изменение критических данных, поток выполняет системный вызов EnterCriticalSection().
• В рамках этого вызова сначала выполняется, как и в предыдущем случае, проверка блокирующей переменной, отражающей состояние критического ресурса.
• Если системный вызов определил, что ресурс занят (F(D) = 0), он в отличие от предыдущего случая не выполняет циклический опрос, а переводит поток в состояние ожидания (D) и делает отметку о том, что данный поток должен быть активизирован, когда соответствующий ресурс освободится.
• Поток, который в это время использует данный ресурс, после выхода из критической секции должен выполнить системную функцию LeaveCriticalSection(), в результате чего блокирующая переменная принимает значение, соответствующее свободному состоянию ресурса (F(D) = 1), а операционная система просматривает очередь ожидающих этот ресурс потоков и переводит первый поток из очереди в состояние готовности.