Основные задачи и методы

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

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

Критические секции: взаимное исключение

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

Семафоры были придуманы отчасти, чтобы облегчить решение задачи критической сек­ции. В листинге 1 представлено решение, использующее переменные для блокировки, в ко­тором переменная lock имеет значение "истина", когда ни один процесс не находится в сво­ей критической секции, и значение "ложь" в противном случае. Пусть значение "истина" представлено как 1, а "ложь" – как 0. Тогда процесс перед входом в критическую секцию должен подождать, пока значение переменной lock не станет равным 1, и присвоить ей значе­ние 0. Выходя из критической секции, процесс должен присвоить переменной lock значение 1.

Листинг 1 –Решение задачи критической секции

Именно эти операции и поддерживаются семафорами. Пусть mutex – семафор с началь­ным значением 1. Выполнение операции Р (mutex) – это то же, что и ожидание, пока зна­чение переменной lock не станет равным 1, и последующее присвоение ей значения 0. Ана­логично выполнение операции V (mutex) – это то же, что присвоение lock значения 1 (при условии, что это можно сделать, только когда она имеет значение 0). Эти рассуждения приво­дят к решению задачи критической секции, показанному в листинге 1.

Барьеры: сигнализирующие события

В реализациях барьеров с активным ожиданием использованы переменные-флаги, которые устанавливаются приходящими к барьеру процессами и сбрасываются покидающими его. Как при решении задачи критиче­ской секции, семафоры облегчают реализацию барьерной синхронизации. Основная идея – использовать семафор в качестве флага синхронизации. Выполняя операцию V, процесс ус­танавливает флаг, а при операции Р – ждет установки флага и сбрасывает его. (Если каждому процессу параллельной программы выделен собственный процессор, то задержки на барьерах должны быть реализованы с помощью циклов активного ожидания, а не блокировки процес­сов. Таким образом, желательна реализация семафоров с активным ожиданием.)

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

Сигнализирующий семафор s – это семафор с нулевым (как правило) начальным значени­ем. Процесс сигнализирует о событии, выполняя операцию V (s); другие процессы ожидают события, выполняя Р (s). Для двухпроцессного барьера два существенных события состоят в том, что процессы прибывают к барьеру. Следовательно, поставленную задачу можно ре­шить с помощью двух семафоров arrivel и arrive2. Каждый процесс сообщает о своем прибытии к барьеру, выполняя операцию V для своего семафора, и затем ожидает прибытия другого процесса, выполняя для его семафора операцию р. Это решение приведено в лис­тинге 2. Поскольку барьерная синхронизация симметрична, процессы действуют одинаково – каждый из них просто сигнализирует о прибытии и ожидает на других семафо­рах. Используемые таким образом семафоры похожи на флаговые переменные, поэтому их применение должно следовать принципам синхронизации флагами.

Листинг 2 – Барьерная синхронизация с помощью семафоров

На каждом этапе процесс i сначала сообщает о своём прибытии, выполняя операцию V(arrive[i]), а затем ожидает прибытия остальных про­цессов, выполняя Р для их элементов массива arrive. В отличие от ситуации с переменны­ми-флагами здесь нужен только один массив семафоров arrive, поскольку действие опера­ции V "запоминается", тогда как значение флаговой переменной может быть перезаписано.

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