Механизмы синхронизации. Семафоры Дейкстры

S: semaphore

P(s) - close

V(s) - open

Семафор относится к низкоуровневым средствам синхронизации, работает по двуступенчатой схеме в режиме пассивного ожидания.

Семафор — целочисленная переменная в отношении которой выполняется операции двух видов: открытие и закрытие. Операция открытия увеличивает значение семафора на 1, операция закрытия — уменьшает на 1. Если значение семафора больше 0, то он считается открытым, а если равен 0, то закрытым.

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

Неделимость операций

Примитивы — это неделимые операции. При попытке выполнить примитив над семафором из разных процессов приведет к успеху только одного действия, выполняемого потоком, причем неизвестно каким.

Механизмы синхронизации. Решение задачи реактивации

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

Возможны 2 варианта:

- процесс должен повторно выполнить операцию закрытия (считая попытку неуспешной)

- процесс при перемещении в очередь готовности отмечается как успешно выполненный т е его выполнение начнётся со следующей команды.

Возможны ситуации тупика.

1)Пусть процесс 2 успешно выполнил операцию закрытия, значение семафора = 0, далее процесс 1 пытается выполнить операцию закрытия (не удается), т.е., 1 процесс останавливается на семафоре. Знач. семафора = -1. При выходе из крит. обл, процесс 2 открывает семафор, знач семафора = 0. Процесс 1 переходит в очередь готовности. Если он повторно выполнит операцию закрытия, значение семафора = -1, а 1-ый процесс остановится. Соответсвтенно, попытка 2-ого процесса войти в крит. область также будет заблокирована.

2) Пусть процесс 2 открывает семафор, т.е. значение семафора =0. Если 2 процесс повторно пытается закрыть семафор, он остановится, а значение семафора станет равным -1. 1-ый процесс при переходе в активное состояние входит в крит. обл. и при выходе устанавливает значение семафора = 0. "Освобожденный" 2-ой процесс также повтороно попадает в крит. обл., открывает семафор, значение семафора =1.