Избыточность общего семафора
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" критический интервал потребителя динамически распадается на две части: это исключительно важно, так как иначе производитель никогда не получит возможность добавить новую порцию, которую уже ждет потребитель.
(Только что приведенная программа известна под названием "Спящий парикмахер". Имеется парикмахерская с отдельной комнатой ожидания. Входная дверь в комнату ожидания расположена рядом с дверью в комнату, где находится кресло парикмахера. Вход и выход прикрываются одной и той же скользящей дверью, так что или вход, или выход закрыт. Кроме того, вход настолько узок, что посетители могут входить только по одному, тем самым фиксируется очередность входа. Взаимные исключения поэтому обеспечиваются.
 |
Две предложенные программы дают убедительное свидетельство, что применение общего семафора действительно избыточно. Тем не менее, мы не будем от него отказываться: выраженная с его помощью односторонняя синхронизация имеет очень простой вид, и сравнение решений с использованием общего семафора и без него показывает, что это средство очень удобно.
