4.1. Типичное использование общего семафора
Рассмотрим два процесса, которые назовем "производитель" и "потребитель". Производитель является циклическим процессом, и при каждом циклическом повторении участка программы он производит отдельную порцию информации, которая должна быть обработана потребителем. Потребитель также является циклическим процессом, и при каждом повторении он обрабатывает следующую порцию информации, выработанную производителем. Простой пример представляет вычислительный процесс, производящий в качестве "порций информации" образы перфокарт, которые должны быть отперфорированы карточным перфоратором, играющим роль потребителя.
Отношение производитель - потребитель подразумевает односторонний канал связи, по которому могут передаваться порции информации. Предположим, что с этой целью процессы связаны через буфер неограниченной емкости, т. е. произведенные порции не обязательно должны немедленно потребляться, а могут образовывать в буфере очередь. Тот факт, что не установлено верхней границы для емкости буфера, делает пример отчасти нереальным, но это не должно нас сейчас слишком волновать.
(Причина появления названия "буфер" станет ясной, когда мы посмотрим, что произойдет при его отсутствии, а именно, если производитель может предложить следующую порцию только после того, как предыдущая порция действительно потреблена. В примере с вычислительной машиной и карточным перфоратором можно считать, что перфоратор перфорирует карты с постоянной скоростью, например, 4 карты в секунду. Давайте предположим, что эта скорость вывода хорошо согласуется со скоростью образования данных для перфорации, т. е. вычислительная машина выполняет выработку образа карты с той же средней скоростью. Если передача данных между вычислительным процессом и перфорацией карт не буферизована, то работа каждого из процессов будет протекать непрерывно с полной скоростью только в том случае, когда образ карты вырабатывается через каждую четвертую часть секунды. Если, однако, природа вычислительного процесса такова, что после одной или двух секунд энергичных вычислений вырабатывается от 4 до 8 образов карт сразу, то безбуферная связь приведет к тому, что за периодом времени, в течение которого перфоратор будет простаивать (из-за отсутствия информации), последует период, когда должен будет стоять вычислительный процесс, потому что он не сможет избавиться от следующего произведенного образа карты, прежде чем предыдущий не будет отперфорирован. Такая нестабильность в скорости выработки образов карт может быть, однако, сглажена с помощью буфера надлежащего размера. Вот почему такое приспособление с очередью получило название "буфер".)
В этом параграфе мы не будем касаться различных методов реализации буферов. Буфер должен обеспечить размещение последовательных порций информации, поэтому он должен располагаться в подходящей запоминающей среде, доступной обоим процессам. Кроме того, буфер не только должен содержать сами порции информации, но также отражать их линейную упорядоченность. (В литературе описаны, например, два хорошо известных метода: "циклическая буферизация" и "цепная".) Когда подготовлена очередная порция информации, мы будем называть последующее действие, не вдаваясь в детали, "добавление порции к буферу"; подобным образом, "взятие порции из буфера" описывает поведение потребителя, при этом имеется в виду самая старая порция, еще находящаяся в буфере (т. е. буфер работает по принципу "первый вошел - первый вышел").
Опуская во внешнем блоке все связанные с буфером описания, мы можем теперь построить два процесса с помощью единственного общего семафора, названного "число порций в буфере".
begin integer число порций в буфере;
число порций в буфере := 0;
parbegin
производитель: begin
снова 1: производство новой порции;
добавление порции к буферу;
V(число порций в буфере);
goto снова 1
end;
потребитель: begin
снова 2: P(число порций в буфере);
взятие порции из буфера;
обработка взятой порции;
goto снова 2
end;
parend
end
Вторая строка части программы производителя представляет процесс формирования следующей порции информации; подразумевается полная независимость от буфера, для которого предназначена эта порция; когда этот оператор выполнен, очередная порция окончательно образована и ее вид больше не зависит от каких-либо неупомянутых здесь обстоятельств. Третья строка программы производителя описывает добавление сформированной порции к буферу, но так, что потребитель еще не знает об этом. V-операция окончательно подтверждает ее наличие, т. е. сообщает об этом потребителю. Чрезвычайно существенным является то, что V-операции предшествует окончательное добавление порции. О структуре потребителя можно сделать аналогичные замечания.
Операции "добавление порции к буферу" и "взятие порции из буфера", работающие с общей управляющей информацией о состоянии буфера, особенно в случае организации буфера в виде цепи, могут мешать друг другу, если только мы не позаботимся о том, чтобы они взаимно исключали друг друга во время выполнения. Этого можно добиться с помощью двоичного семафора, названного "работа с буфером", который принимает следующие значения:
- =0: имеет место добавление к буферу или взятие из буфера;
- =1: ни добавление, ни взятие не имеют места.
Программа становится такой:
begin integer число порций в буфере, работа с буфером;
число порций в буфере := 0;
работа с буфером := 1;
parbegin
производитель: begin
снова 1: производство новой порции;
P(работа с буфером);
добавление порции к буферу;
V(работа с буфером);
V (число порций в буфере);
goto снова 1
end;
потребитель: begin
снова 2: P(число порций в буфере);
P(работа с буфером);
взятие порции из буфера;
V(работа с буфером);
обработка взятой порции;
goto снова 2
end
parend
end
Читателю предоставляется убедиться самостоятельно в следующем:
а) порядок двух V-операций в производителе несуществен;
б) порядок двух P-операций в потребителе существен.
Замечание. Наличие двоичного семафора "работа с буфером" имеет еще одно следствие. Мы составили программу для одного производителя и одного потребителя. Однако теперь расширение ее до большего числа производителей и (или) потребителей очевидно: этот же семафор заботится о том, чтобы два или более добавлений новых порций никогда не осуществлялись вместе; то же относится к взятию порций различными потребителями. От читателя требуется проверить, что порядок двух V-операций в производителе по-прежнему несуществен.
4.2. Избыточность общего семафора
В этом параграфе мы покажем избыточность общего семафора и для этого перепишем последнюю программу из предыдущего параграфа, используя только двоичные семафоры. (Я умышленно говорю "мы покажем", а не "мы докажем". У нас нет математического аппарата, который позволил бы это доказывать, и я не склонен развивать такой аппарат теперь. Тем не менее, я надеюсь, что мои рассуждения будут убедительными!) Сначала мы приведем решение, а обсуждение проведем позже.
begin integer числопорцбуф, работа с буфером, задержка потребителя;
числопорцбуф:= 0; работа с буфером:= 1;
задержка потребителя:= 0;
parbegin
производитель: begin
снова 1: производство новой порции;
P(работа с буфером);
добавление порции к буферу;
числопорцбуф := числопорцбуф + 1;
if числопорцбуф = 1 then V(задержка потребителя);
V(работа с буфером);
goto снова 1
end;
потребитель: begin integer старчислопорцбуф;
ждать: P(задержка потребителя),
продолжать: P(работа с буфером);
взятие порции из буфера;
числопорцбуф := числопорцбуф - 1;
старчислопорцбуф:= числопорцбуф;
V(работа с буфером);
обработка взятой порции;
if старчислопорцбуф = 0 then goto ждать
else goto продолжать
end
parend
end
В динамическом поведении этой программы представляют интерес промежутки времени, в течение которых буфер пуст. (Пока буфер не пуст, потребитель может продолжать работу с максимальной скоростью.) Такой промежуток времени может наступить только как следствие работы потребителя (который берег из буфера последнюю имеющуюся там порцию информации), а закончиться такой промежуток времени может только с помощью производителя (который добавляет к пустому буферу порцию информации). При обнаружении этих событий ошибки возникнуть не может благодаря двоичному семафору "работа с буфером", который обеспечивает взаимное исключение выполнения процессов производителя и потребителя, необходимое при фиксации этих событий. Каждый такой промежуток времени, связанный с пустым буфером, сопровождается P- и V-операциями над новым двоичным семафором "задержка потребителя". И наконец, остановимся на локальной переменной потребителя "старчислопорцбуф" - старое число порций в буфере: ее значение устанавливается при взятии порции из буфера и оно фиксирует, не была ли эта порция последней. (Более искушенные в АЛГОЛе читатели понимают, что для этих целей нам достаточно единственного бита информации, который говорит, а не стало ли значение переменной "числопорцбуф" - число порций в буфере - после уменьшения равным "0". В таком случае можно было бы воспользоваться переменной типа Boolean). Когда потребитель решает "ждать", т. е. обнаруживает, что "старчислопорцбуф = 0", в этот момент значение "числопорцбуф" уже опять может быть больше нуля!
В предыдущей программе все внимание было сосредоточено на промежутке времени, когда буфер пуст. Однако можно заметить, что пустота буфера сама по себе значения не имеет: она важна только тогда, когда потребителю хотелось бы взять новую порцию, которой еще нет в буфере. Мы запрограммируем также и этот вариант. В динамическом поведении такой программы можно ожидать выполнения меньшего числа P- и V-операций над семафором "задержка потребителя": их не будет, если буфер пустовал короткое время, но снова заполнялся своевременно, не вызывая задержки потребителя. Мы опять сначала дадим программу, а затем прокомментируем ее.
begin integer числопорцбуф, работа с буфером, задержка
потребителя; числопорцбуф := 0; работа с буфером := 1;
задержка потребителя := 0;
parbegin
производитель: begin
снова 1: производство новой порции;
P(работа с буфером);
добавление порции к буферу;
числопорцбуф := числопорцбуф+1;
if числопорцбуф = 0 then
begin V(работа с буфером);
V(задержка потребителя) end
else V(работа с буфером);
goto снова 1
end;
потребитель: begin
снова 2: P(работа с буфером);
числопорцбуф := числопорцбуф -1;
if числопорцбуф = - 1 then
begin V(работа с буфером);
P(задержка потребителя);
P(работа с буфером) end;
взятие порции из буфера;
V(работа с буфером);
обработка взятой порции;
goto снова 2
end
parend
end
Снова семафор "работа с буфером" предназначен для взаимного исключения критических интервалов. Последние шесть строк программы производителя можно было бы записать так:
if числопорцбуф = 0 then V(задержка потребителя);
V(работа с буфером); goto снова 1
Я не воспользовался такой записью, так как мне не нравится применять P- и V-операции внутри критических интервалов; читатель может не обращать на это внимания.
Область допустимых значений для "числопорцбуф" была расширена значением "-1", которое означает (вне выполнения критического интервала): "буфер не только пуст, нечего пустота уже обнаружена потребителем, который решил ждать". Этот факт может быть установлен производителем по значению "числопорцбуф = 0" после добавления единицы.
Заметим, что в случае "числопорцбуф = -1" критический интервал потребителя динамически распадается на две части: это исключительно важно, так как иначе производитель никогда не получит возможность добавить новую порцию, которую уже ждет потребитель.
(Только что приведенная программа известна под названием "Спящий парикмахер". Имеется парикмахерская с отдельной комнатой ожидания. Входная дверь в комнату ожидания расположена рядом с дверью в комнату, где находится кресло парикмахера. Вход и выход прикрываются одной и той же скользящей дверью, так что или вход, или выход закрыт. Кроме того, вход настолько узок, что посетители могут входить только по одному, тем самым фиксируется очередность входа. Взаимные исключения поэтому обеспечиваются.
Когда парикмахер заканчивает обслуживание, он открывает дверь в комнату ожидания и осматривает ее. Если комната не пуста, то он приглашает следующего посетителя, в противном случае он устраивается спать в одном из кресел комнаты ожидания. Поведение посетителей определяется следующим образом: если они видят "нуль или более" посетителей в комнате ожидания, то ждут своей очереди; если они видят спящего парикмахера, - "числопорцбуф = -1", - то будят его.)
Две предложенные программы дают убедительное свидетельство, что применение общего семафора действительно избыточно. Тем не менее, мы не будем от него отказываться: выраженная с его помощью односторонняя синхронизация имеет очень простой вид, и сравнение решений с использованием общего семафора и без него показывает, что это средство очень удобно.
4.3. Ограниченный буфер
Я приведу последний пример для иллюстрации использования общего семафора. В ?4.1 мы изучали производителя и потребителя, связанных через буфер неограниченной емкости. Это типичное одностороннее ограничение: производитель может находиться сколь угодно впереди потребителя; однако потребитель никогда не может быть впереди производителя. Их отношения становятся симметричными, если они связываются через буфер ограниченной емкости, скажем в N порций. Программа дается без обсуждения; читателю предоставляется убедиться в ее полной симметрии. ("Потребитель производит, а производитель потребляет пустые порции в буфере".) Значение N, так же, как и буфер, предполагаются определенными во внешних блоках.
begin integer число порций в буфере, число пустых позиций,
работа с буфером;
число порций в буфере := 0;
число пустых позиций := N;
работа с буфером := 1;
parbegin
производитель: begin
снова 1: производство новой порции;
P(число пустых позиций);
P(работа с буфером);
добавление порции к буферу;
V(работа с буфером);
V(число порций в буфере);
goto снова 1;
end;
потребитель: begin
снова 2: P(число порций в буфере);
P(работа с буфером);
взятие порции из буфера;
V(работа с буфером);
V(число пустых позиций);
обработка взятой порции;
goto снова 2;
end
parend
end
