Синтаксис и семантика

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

132                                               Часть 1. Программирование с разделяемыми переменными

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

Семафор объявляется так: sem s ;

По умолчанию начальным значением является 0, но семафор можно инициализировать лю­бым положительным значением, например:

sem lock =  1; Массивы семафоров можно объявлять и при необходимости инициализировать обычным образом:

sem  forks[5]   =   ([5]   1);

Если бы в этой декларации не было инициализации, то начальным значением каждого сема­фора в массиве forks был 0.

После объявления и инициализации семафор можно обрабатывать только с помощью операций р и V. Каждая из них является неделимым действием с одним аргументом. Пусть s — семафор. Тогда операции р (s) и V (s) определяются следующим образом.

P(s):   (await   (s>0)s=s-l;> V(s) :   (s   =   s   +   1;>

Операция V увеличивает значение s на единицу неделимым образом. Операция Р уменьшает значение s, но, чтобы после вычитания значение s не стало отрицательным, она сначала ожидает, пока s не станет положительным.

Приостановка выполнения и вычитание в операции р являются единым неделимым дейст-.вием. Предположим, что s — семафор с текущим значением 1. Если два процесса пытаются одновременно выполнить операцию Р (s), то это удастся сделать только одному из них. Но если один процесс пытается выполнить операцию Р (s), а другой — V (s), то обе операции будут ус­пешно выполнены в непредсказуемом порядке, а конечным значением семафора s станет 1.

Обычный семафор может принимать любые неотрицательные значения, двоичный семафор — только значения 1 или 0. Это значит, что операция V для двоичного семафора может быть вы­полнена, только когда его значение 0. (Операцию V для двоичного семафора можно опреде­лить как ожидание, пока значение семафора станет меньше 1, и затем его увеличение на 1.)
Поскольку операции с семафором определяются в терминах операторов await, их фор­мальная семантика следует непосредственно из применения правила оператора await (см. раздел 2.6). Правила вывода для операций Р и V получаются непосредственно из правила опе­ратора await, примененного к конкретным операторам в определении Р и V.
Свойства справедливости для операций с семафорами тоже следуют из их определения с по­мощью оператора await. Используем терминологию раздела 2.8. Если условие s > 0 стано­вится и далее остается истинным, выполнение операции Р (s) завершится при справедливой в слабом смысле стратегии планирования. Если условие s > 0 становится истинным бесконеч­но часто, то выполнение операции Р (s) завершится при справедливой в сильном смысле стра­тегии планирования. Операция V для обычного семафора является безусловным неделимым действием, поэтому она завершится, если стратегия планирования безусловно справедлива.


Как будет показано в главе 6, при реализации семафоров обычно обеспечивается, что, ес­ли процессы приостанавливаются, выполняя операции р, они возобновляются в том же по-
' Буквы Р и V взяты от голландских слов (это описано в исторической справке в конце главы). Мож­но считать, что буква Р связана со словом "пропустить" (pass), а форма буквы V, расширяющаяся к вер­ху, обозначает увеличение значения. Некоторые авторы вместо Р и V используют названия wait и sig­nal, но здесь эти команды оставлены для главы о мониторах.
Глава 4 Семафоры                                                                                                                         133


рядке, в котором были приостановлены. Следовательно, процесс, ожидающий выполнения операции р, сможет в конце концов продолжить работу, если другие процессы выполнят со­ответствующее число операций V.
4.2. Основные задачи и методы
Семафоры непосредственно поддерживают реализацию взаимного исключения, необходи­мого, например, в задаче критической секции. Кроме того, они обеспечивают поддержку про­стых форм условной синхронизации, где они используются для сигнализации о событиях. Для решения более сложных задач эти два способа применения семафоров можно комбинировать.
В данном разделе иллюстрируется применение семафоров для взаимного исключения и ус­ловной синхронизации на примере решения четырех задач: критических секций, барьеров, про­изводителей и потребителей, ограниченных (кольцевых) буферов. В решении последних двух задач применяется метод, разделенных двоичных семафоров. В дальнейших разделах показано, как использовать представленные здесь методы для решения более сложных задач синхронизации.
4.2.1. Критические секции: взаимное исключение
Напомним, что в задаче критической секции каждый из п процессов многократно выпол­няет критическую секцию кода, в которой требуется исключительный доступ к некоторому разделяемому ресурсу, а затем некритическую секцию кода, в которой он работает только слокальными объектами. Каждому процессу, находящемуся в своей критической секции, нужен взаимоисключающий доступ к разделяемому ресурсу.
Семафоры были придуманы отчасти, чтобы облегчить решение задачи критической сек­ции В листинге 3.2 представлено решение, использующее переменные для блокировки, в ко­тором переменная lock имеет значение "истина", когда ни один процесс не находится в сво­ей критической секции, и значение "ложь" в противном случае. Пусть значение "истина" представлено как 1, а "ложь" — как 0. Тогда процесс перед входом в критическую секцию должен подождать, пока значение переменной lock не станет равным 1, и присвоить ей значе­ние 0.


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

134                                               Часть 1 Программирование с разделяемыми переменными
4.2.2. Барьеры: сигнализирующие события
В разделе 3.4 барьерная синхронизация была представлена в качестве средства синхрони­зации алгоритмов, параллельных по данным (раздел 3.5). В реализациях барьеров с активным ожиданием использованы переменные-флаги, которые устанавливаются приходящими к барьеру процессами и сбрасываются покидающими его. Как при решении задачи критиче­ской секции, семафоры облегчают реализацию барьерной синхронизации. Основная идея — использовать семафор в качестве флага синхронизации. Выполняя операцию V, процесс ус­танавливает флаг, а при операции Р — ждет установки флага и сбрасывает его. (Если каждому процессу параллельной программы выделен собственный процессор, то задержки на барьерах должны быть реализованы с помощью циклов активного ожидания, а не блокировки процес­сов. Таким образом, желательна реализация семафоров с активным ожиданием.)
Вначале рассмотрим задачу реализации барьера для двух процессов. Напомним, что необ­ходимо выполнить два требования. Во-первых, ни один процесс не должен перейти барьер, пока к нему не подошли оба процесса. Во-вторых, барьер должен допускать многократное использование, поскольку обычно одни и те же процессы синхронизируются после каждого этапа вычислений. Для решения задачи критической секции достаточно лишь одного сема­фора для блокировки, поскольку нужно просто определить, находится ли процесс в критиче­ской секции.


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

Глава 4. Семафоры                                                                                                                         135
прибытии, выполняя операцию V(arrive[i]), а затем ожидает прибытия остальных про­цессов, выполняя Р для их элементов массива arrive. В отличие от ситуации с переменны­ми-флагами здесь нужен только один массив семафоров arrive, поскольку действие опера­ции V "запоминается", тогда как значение флаговой переменной может быть перезаписано.
Семафоры можно использовать и в качестве сигнальных флагов в реализации барьерной синхронизации для п процессов с управляющим процессом (см. листинг 3.12) или комбини­рующим деревом (см. листинг 3.13). Операции V запоминаются, поэтому используется мень­ше семафоров, чем флаговых переменных. В управляющем процессе Coordinator (см. лис­тинг 3.12), например, нужен всего один семафор.
4.2.3. Производители и потребители: разделенные двоичные семафоры


В данном разделе вновь рассматривается задача о производителях и потребителях, постав­ленная в разделе 1.6 и пересмотренная в разделе 2.5. Там предполагалось, что есть только один про­изводитель и один потребитель. Здесь рассматривается общий случай, когда есть несколько произ­водителей и несколько потребителей. Приводимое ниже решение демонстрирует еще одно приме­нение семафоров в качестве сигнальных флагов и знакомит с важным понятием разделенного двоичного семафора, обеспечивающего еще один способ защиты критических секций кода.
В задаче о производителях и потребителях производители посылают сообщения, получае­мые потребителями. Процессы общаются с помощью разделяемого буфера, управляемого двумя операциями: deposit (поместить) и fetch (извлечь). Выполняя операцию deposit, производители помещают сообщения в буфер; потребители получают сообщения с помощью операции fetch. Чтобы сообщения не перезаписывались и каждое из них могло быть полу­чено только один раз, выполнение операций deposit и fetch должно чередоваться, причем первой должна быть deposit.
Запрограммировать необходимое чередование операций можно с помощью семафоров. Такие семафоры используются либо для сообщения о том, что процессы достигают критиче­ских точек выполнения, либо для отображения состояния разделяемых переменных. Здесь критические точки выполнения— это начало и окончание операций deposit и fetch. Соот­ветствующие изменения разделяемого буфера состоят в том, что он заполняется или опустоша­ется. Поскольку производителей и потребителей может быть много, проще связать семафор с каждым из двух возможных состояний буфера, а не с точками выполнения процессов.
Пусть empty (пустой) и full (полный) — два семафора, отображающие состояние буфе­ра. В начальном состоянии буфер пуст, поэтому семафор empty имеет значение 1 (т.е. про­изошло событие "опустошить буфер"), a full — 0. Перед выполнением операции deposit производитель сначала ожидает опустошения буфера.


Когда производитель помещает в буфер сообщение, буфер становится заполненным. И, наоборот, перед выполнением операции fetch потребитель сначала ожидает заполнения буфера, а затем опустошает его. Процесс ожидает события, выполняя операцию Р для соответствующего семафора, и сообщает о собы­тии, выполняя V. Полученное таким образом решение показано в листинге 4.3.
Переменные empty и full в листинге 4.3 являются двоичными семафорами. Вместе они образуют так называемый разделенный двоичный семафор, поскольку в любой момент времени только один из них может иметь значение 1. Термин "разделенный двоичный семафор" объ­ясняется тем, что переменные empty и full могут рассматриваться как единый двоичный семафор, разделенный на две части. В общем случае разделенный двоичный семафор может быть образован любым числом двоичных семафоров.
Роль разделенных двоичных семафоров особенно важна в реализации взаимного исклю­чения. Предположим, что один из двоичных семафоров инициализирован значением 1
136                                               Часть 1. Программирование с разделяемыми переменными
(соответственно, остальные имеют значение 0). Допустим, что в процессах, использующих семафоры, каждая выполняемая ветвь начинается операцией Р для одного из семафоров и заканчивается операцией V (для одного из семафоров). Тогда все операторы между Р и бли­жайшей V выполняются со взаимным исключением, т.е. если процесс находится между опе­рациями Р и V, то все семафоры равны 0, и, следовательно, ни один процесс не сможет за­вершить операцию Р, пока первый процесс не выполнит V.

Решение задачи производителей и потребителей (см. листинг 4.3) иллюстрирует именно такое применение семафоров. Каждый процесс-производитель Producer попеременно вы­полняет операции Р (empty) и V(full), а каждый процесс-потребитель Consumer — P(full) и V(empty). В разделе4.4 это свойство разделенного двоичного семафора будет использовано для создания общего метода реализации операторов await.


4.2.4. Кольцевые буферы: учет ресурсов
Из последнего примера видно, как синхронизировать доступ к одному буферу обмена. Если данные производятся и потребляются примерно с одинаковой частотой, то процессу не прихо­дится долго ждать доступа к буферу. Однако обычно потребитель и производитель работают нерав­номерно. Например, производитель может быстро создать сразу несколько элементов, а затем долго вычислять до следующей серии элементов. В таких случаях увеличение емкости буфера мо­жет существенно повысить производительность программы, уменьшая число блокировок процес­сов. (Это пример классического противоречия между временем вычислений и объемом памяти.)
Здесь решается так называемая задача о кольцевом буфере, который используется в качест­ве многоэлементного коммуникационного буфера. Решение основано на решении задачи из предыдущего раздела. Оно также демонстрирует применение обычных семафоров в качестве счетчиков ресурсов.
Предположим пока, что есть только один производитель и только один потребитель. Про­изводитель помещает сообщения в разделяемый буфер, потребитель извлекает их оттуда. Бу­фер содержит очередь уже помещенных, но еще не извлеченных сообщений. Эта очередь мо-
Глава 4 Семафоры                                                                                                                         137
жет быть представлена связанным списком или массивом. Здесь используется массив, более простой для программирования. Итак, представим буфер массивом buf [n], где п > 1. Пусть переменная front является индексом первого сообщения очереди, a rear — индек­сом первой пустой ячейки после сообщения в конце очереди. Вначале переменные front и rear имеют одинаковые значения, скажем, 0.
При таком представлении буфера производитель помещает в него сообщение со значени­ем data, выполнив следующие действия:
buf[rear]   = data;   rear =   (rear+1)   % n;
Аналогично потребитель извлекает сообщение в свою локальную переменную result, вы­полняя действия:


result  =  buf[front];   front  =   (front+1)   %  n;
Оператор взятия остатка (%) используется для того, чтобы значения переменных front и rear всегда были в пределах от о до п-1. Очередь буферизованных сообщений хранится в ячейках от buf [front] до buf [rear] (не включительно). Переменная buf интерпретируется как коль­цевой массив, в котором за buf [п-1] следует buf [0]. Вот пример конфигурации массива buf.

Затемненные ячейки заполнены, белые — пусты.
Если используется только один буфер (как в задаче "производитель—потребитель"), то выпол­нение операций deposit и fetch должно чередоваться. При наличии нескольких буферов опера­цию deposit можно выполнить, если есть пустая ячейка, a fetch — если сохранено хотя бы одно сообщение. Фактически, если есть пустая ячейка и сохраненное сообщение, операции deposit и fetch могут выполняться одновременно, поскольку обращаются к разным ячейкам и, следова­тельно, не влияют друг на друга. Однако требования синхронизации для одноэлементного и коль­цевого буфера одинаковы. В частности, операции Р и V применяются одним и тем же образом. Единственное отличие состоит в том, что семафор empty инициализируется значением n, а не 1, поскольку в начальном состоянии есть n пустых ячеек. Решение показано в листинге 4.4.

138                                               Часть 1. Программирование с разделяемыми переменными
V(empty);
}
_}________________________________________________________________________________
В листинге 4.4 семафоры играют роль счетчиков ресурсов: каждый учитывает количество элементов ресурса: empty — число пустых ячеек буфера, a full — заполненных. Когда ни один процесс не выполняет deposit или fetch, сумма значений обоих семафоров равна общему числу ячеек п. Семафоры, учитывающие ресурсы, полезны в случаях, когда процессы конкури­руют за доступ к таким многоэлементным ресурсам, как ячейки буфера или блоки памяти.
В программе (см. листинг 4.4) предполагалось, что есть только один производитель и один потребитель.


Это гарантировало неделимое выполнение операций deposit и fetch. Теперь предположим, что есть несколько процессов-производителей. При наличии хотя бы двух сво­бодных ячеек два из них могли бы выполнить операцию deposit одновременно. Но тогда оба попытались бы поместить свои сообщения в одну и ту же ячейку! (Если бы они присваивали но­вое значение ячейке buf [rear] до увеличения значения переменной rear.) Аналогично, если есть несколько потребителей, два из них одновременно могут выполнить fetch и получить од­но и то же сообщение. Таким образом, deposit и fetch становятся критическими секциями. Одинаковые операции должны выполняться со взаимным исключением, но разные могут вы­полняться одновременно, поскольку при работе семафоров empty и full производители и по­требители обращаются к разным ячейкам буфера. Необходимое исключение можно реализо­вать, используя решение задачи критической секции (см. листинг 4.1) с отдельными семафора­ми для защиты каждой критической секции. Законченное решение приведено в листинге 4.5.

Глава 4. Семафоры                                                                                                                                 139
Итак, отдельно решены две задачи синхронизации — сначала между одним производите­лем и одним потребителем, затем между несколькими производителями и несколькими по­требителями. В результате оказалось легко объединить решения двух подзадач для получения полного решения задачи. Такая же идея будет использована в решении задачи о читателях и писателях в разделе 4.3. Таким образом, везде, где присутствуют несколько типов синхро­низации, полезно реализовать их отдельно и затем объединить решения.

Содержание раздела

---

---