Механизмы синхронизации: блокирующие переменные, семафоры, мониторы. Блокирующие переменные (мьютексы):
С каждым разделяемым ресурсом связывается двоичная переменная, которая принимает значение 1, если ресурс свободен, и значение 0, если ресурс занят.
Неделимая операция обеспечивает принцип взаимного исключения:
Т.е. исключает случай, когда процесс 1 определил, что ресурс свободен, но, не успев установить переменную в 0, был прерван;
Процесс 2 сделал то же самое и был прерван, после чего управление возвращено процессу 1 для выполнения своей критической секции.
«Неделимая операция» может быть реализована использованием неделимой команды анализа и присвоения значения логической переменной (например, команды BTC, BTR, BTS процессора Pentium) или с помощью специальных системных примитивов – базовых функций ОС, которые бы запрещали прерывания на протяжении всей операции проверки и установки.
«-»:
В течение времени, когда один процесс находится в критической секции, другой процесс, которому требуется тот же ресурс, будет выполнять рутинные действия по опросу блокирующей переменной, бесполезно растрачивая процессорное время.
Семафоры
Для устранения этого недостатка во многих ОС предусматриваются специальные системные вызовы (аппарат для работы с критическими секциями.
В разных ОС аппарат событий реализован по своему, но в любом случае используются системные функции, которые условно называют WAIT(x) и POST(x), где x – идентификатор некоторого события (например, освобождение ресурса).
Обобщающее средство синхронизации процессов предложил Дейкстра, который ввел новые примитивы, обозначаемые V (“открытие”) и P (“закрытие”), оперирующие над целыми неотрицательными переменными, называемыми семафорами.
Доступ любого процесса к семафору, за исключением момента его инициализации, может осуществляться только через эти две атомарные операции. Смысл P(S) заключается в проверке текущего значения семафора S, и если S>0, то осуществляется переход к следующей за примитивом операции, иначе процесс переходит в состояние ожидания.
P(S):
Пока S==0
Процесс блокируется;
S=S-1;
Операция V(S) связана с увеличением значения S на 1 и переводом одного или нескольких процессов из состояния готовности к исполнению процессором.
V(S):
S=S+1;
В простом случае, когда семафор работает в режиме 2-х состояний (S>0 и S=0), его алгоритм работы полностью совпадает с алгоритмом работы мьютекса и S выполняет роль блокирующей переменной.
“+”: пассивное ожидание (постановка в очередь и автоматическая выдача ресурсов)
возможность управления группой однородных ресурсов
“-”: не указывают непосредственно на критический ресурс
некорректное использование операций может привести к нарушению работоспособности (например, переставив местами операции P(e) и P(b) в функции Writer()).
Мониторы (условные переменные)
Для облегчения работы программистов при создании параллельных программ без усилий на доказательства правильности алгоритмов и отслеживание взаимосвязанных объектов (что характерно при использовании семафоров) предложено высокоуровневое средство синхронизации, называемое мониторами.
Мониторы – тип данных, обладающий собственными переменными, значения которых могут быть изменены только с помощью вызова функций-методов монитора.
Функции-методы могут использовать в работе только данные, находящиеся внутри монитора, и свои параметры.
Доступ к мониторам в каждый момент времени имеет только один процесс.
Для организации не только взаимоисключений, но и очередности процессов, подобно семафорам f(full) и e(empty), было введено понятие условных переменных, над которыми можно совершать две операции wait и signal, отчасти похожие на операции P и V над семафорами.
Функция монитора выполняет операцию wait над какой-либо условной переменной. При этом процесс, выполнивший операцию wait, блокируется, становится неактивным, и другой процесс получает возможность войти в монитор.
Когда ожидаемое событие происходит, другой процесс внутри функции совершает операцию signal над той же самой условной переменной. Это приводит к пробуждению ранее заблокированного процесса, и он становится активным.
Исключение входа нескольких процессов в монитор реализуется компилятором, а не программистом, что делает ошибки менее вероятными.
Требуются специальные языки программирования и компиляторы (встречаются в языках, “параллельный Евклид”,”параллельный Паскаль”,Java).
Следует отметить, что условные переменные мониторов не запоминают предысторию, поэтому операцию signal всегда должна выполняться после операции wait(иначе выполнение операции wait всегда будет приводить к блокированию процесса).