Алгоритм банкира
6.1. Алгоритм банкира
Банкир обладает конечным капиталом во флоринах. Он решает принимать клиентов, которые могут занимать у него флорины на следующих условиях:
Клиент делает заем для совершения сделки, которая будет завершена за конечный промежуток времени. Клиент должен заранее указать максимальную "потребность" во флоринах для этой сделки. Пока "заем" не превышает заранее установленную "потребность", клиент может увеличивать или уменьшать свой заем флорин за флорином. Клиент, который просит увеличить его текущий заем, обязуется принимать без недовольства следующий ответ: "Если бы я дал вам запрашиваемый флорин, вы еще не превысили бы свою установленную потребность, и поэтому вы имеете право на следующий флорин. Однако в настоящий момент мне, по некоторым причинам, неудобно его дать, но я обещаю вам флорин в должное время". Гарантия для клиента в том, что этот момент действительно наступит, основана на предусмотрительности банкира и на том факте, что остальные клиенты подчиняются тем же условиям, что и он сам: как только клиент получает флорин, он приступает к своей сделке с ненулевой скоростью, т. е. в конечный промежуток времени он или запросит новый флорин, или возвратит флорин, или закончит сделку, что означает возвращение всего займа (флорин за флорином).
Основными вопросами здесь являются:
а) при каких условиях банкир может заключить контракт с новым клиентом?
б) при каких условиях банкир может выплатить (следующий) запрашиваемый флорин клиенту, не опасаясь попасть в тупик?
Ответ на вопрос (а) прост: он может принять любого клиента, чья максимальная потребность не превышает капитал банкира.
Для ответа на вопрос (б) введем следующую терминологию.
Банкир имеет в своем распоряжении фиксированный "капитал"; каждый новый клиент устанавливает свою максимальную "потребность" и для любого клиента выполняется условие:
"потребность[i] < капитал" (для всех i).
Текущая обстановка для каждого клиента характеризуется его "заемом".
Каждый заем первоначально равен "0" и будет в любой момент удовлетворять соотношению:
"0 < заем[i] < потребность[i]" (для всех i).
Отсюда может быть получена полезная величина, представляющая максимальное дальнейшее "требование":
"требование[i] = потребность[i] - заем[i]" (для всех i).
Наконец, "наличные" банкира составляют:
"наличные = капитал - сумма всех займов".
Очевидно, что должно выполняться условие:
"0 < наличные < капитал".
Для того чтобы решить, выплачивать ли запрашиваемый флорин клиенту, банкир по существу оценивает положение, которое сложилось бы, если бы он произвел выплату. Если это положение "безопасно", он выплачивает флорин; если положение не "безопасно", он должен сказать: "Извиняюсь, но вы должны подождать".
Проверка того, является ли положение безопасным, равнозначна проверке, могут ли быть с гарантией завершены все сделки. Алгоритм начинается с исследования, имеет ли по крайней мере один клиент "требование", не превосходящее "наличные". Если так, то этот клиент сможет завершить свою сделку, и поэтому исследуются оставшиеся клиенты в предположении, что первый завершил сделку и возвратил свой заем полностью. Безопасность положения означает, что могут быть закончены все сделки, т.е. банкир видит путь получения обратно всех своих денег.
Если клиенты пронумерованы от 1 до N, то стандартную программу проверки положения можно составить так:
integer свободные деньги; Boolean безопасно; Boolean array завершение под сомнением[1 : N]; свободные деньги := наличные; for i := 1 step 1 until N do завершение под сомнением[i] := true; L: for i := 1 step 1 until N do
begin if завершение под сомнением[i] and требование[i] свободные деньги then
begin завершение под сомнением[i] := false; свободные деньги := свободные деньги + заем[i]; goto L end
end;
if свободные деньги = капитал then безопасно := true
else безопасно := false
Приведенная стандартная программа проверяет любое положение. Улучшение алгоритма банкира было предложено Цваненбургом, который принял во внимание, что подлежат исследованию только те положения, которые возникают, когда при безопасном положении выдается флорин некоторому клиенту [i]. Как только при работе программы выполнится условие "завершение под сомнением[i] := false", можно прямо сделать вывод о безопасности нового положения, так как тогда, очевидно, эта планируемая выплата будет обратима. Это усовершенствование реализовано в программе следующего параграфа.
Избыточность общего семафора
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" критический интервал потребителя динамически распадается на две части: это исключительно важно, так как иначе производитель никогда не получит возможность добавить новую порцию, которую уже ждет потребитель.
(Только что приведенная программа известна под названием "Спящий парикмахер". Имеется парикмахерская с отдельной комнатой ожидания. Входная дверь в комнату ожидания расположена рядом с дверью в комнату, где находится кресло парикмахера. Вход и выход прикрываются одной и той же скользящей дверью, так что или вход, или выход закрыт. Кроме того, вход настолько узок, что посетители могут входить только по одному, тем самым фиксируется очередность входа. Взаимные исключения поэтому обеспечиваются.
Две предложенные программы дают убедительное свидетельство, что применение общего семафора действительно избыточно. Тем не менее, мы не будем от него отказываться: выраженная с его помощью односторонняя синхронизация имеет очень простой вид, и сравнение решений с использованием общего семафора и без него показывает, что это средство очень удобно.
Необходимость в более реалистическом решении
3.1. Необходимость в более реалистическом решении
Метод, описанный в ¬2.2, интересен постольку, поскольку он показывает, что даже рассмотренных ограниченных средств связи между процессами достаточно для решения задачи. С других точек зрения, которые на мой взгляд так же важны, предложенное решение является безнадежно несовершенным.
Прежде всего, оно приводит к громоздкому описанию отдельных процессов. В этом описании есть все что угодно, но нет ясности в том, что общее поведение процесса на самом деле соответствует (умозрительно весьма простому) требованию взаимного исключения. Другими словами, так или иначе, это решение есть просто крупная мистификация. Давайте попытаемся отчетливо представить, в каком отношении это решение действительно представляет собой мистификацию. Это могло бы дать ключ к дальнейшему усовершенствованию метода.
Рассмотрим отрезок времени, в течение которого один из процессов находится в критическом интервале. Мы знаем, что на протяжении этого времени никакой другой процесс не может войти в свой критический интервал, и даже если он хочет это сделать, то должен ждать, пока не завершится выполнение текущего критического интервала. В этот период от ждущих процессов вряд ли требуется какая-то активность, и относительно них можно сказать, что "они могли бы быть приостановлены".
Наше решение совсем этого не отражает: мы сохраняем процессы в состоянии постоянной занятости, устанавливая и проверяя все время общие переменные, как будто за такую активность ничего не нужно платить. Но если наша реализация, т.е. средства, с помощью которых процессы выполняются, такова, что "приостановка" есть менее дорогостоящее состояние, чем этот активный способ ожидания, то мы вправе (теперь и с экономической точки зрения) назвать наше решение вводящим в заблуждение. В современных вычислительных машинах есть по меньшей мере две особенности, из-за которых такой активный способ ожидания может оказаться очень дорогим. Позвольте коротко на них остановиться.
Вычислительные машины имеют две четко различающиеся части, обычно называемые "процессор" и "память". Процессор является активной частью, где выполняются арифметические и логические операции; он "активен и мал". В памяти, которая "пассивна и велика", размещается в каждый момент времени информация, которая в этот самый момент не обрабатывается, а только хранится для будущего обращения к ней. В общем вычислительном процессе информация передается из памяти в процессор, как только она должна играть активную роль, а информация в памяти может быть изменена передачей в обратном направлении.
Такая вычислительная машина представляет собой исключительно гибкое средство для реализации последовательных процессов. Даже обладая одним единственным процессором, вычислительная машина может использоваться для реализации некоторого числа совместно действующих процессов. С макроскопической точки зрения будет казаться, что все эти процессы выполняются одновременно. Более тщательное наблюдение покажет, однако, что в каждый "микроскопический" момент времени процессор обслуживает только одну единственную программу, а общее впечатление является лишь результатом того, что в некоторые вполне определенные моменты процессор переключается с одного процесса на другой. При такой реализации различные процессы "делят" один и тот же процессор, и активность (т. е. ненулевая скорость) любого процесса означает нулевую скорость для других; в таком случае нежелательно, чтобы драгоценное процессорное время расходовалось процессами, которые по тем или иным причинам не могут продолжать выполнение.
Помимо разделения процессора, разделение памяти также может сделать нежелательным ненужную активность ожидающего процесса. Предположим, что проверка или присваивание "общей переменной" означает обращение к единице информации - так называемому "слову", - расположенному в памяти на ферритовых сердечниках. Доступ к слову в ферритовой памяти занимает ненулевое время, и, кроме того, по техническим причинам в каждый момент можно обратиться только к одному слову.Если более чем один активный процесс пожелает обратиться к той же самой ферритовой памяти, то обычный механизм доступа работает так, что близкие по времени запросы к памяти от различных активных процессов удовлетворяются согласно встроенному правилу: процесс с меньшим приоритетом автоматически задерживается. (В литературе эта ситуация известна как "захват процессором информационного канала на цикл памяти".) В результате этого частая проверка общих переменных может замедлить выполнение тех процессов, для которых в той же самой ферритовой памяти хранятся их локальные величины.
Новый подход к задаче взаимного исключения
3. НОВЫЙ ПОДХОД К ЗАДАЧЕ ВЗАИМНОГО ИСКЛЮЧЕНИЯ
Мы возвращаемся к задаче взаимного исключения во время выполнения критических интервалов процессов, которую мы первоначально рассмотрели в ¬2.1 и затем обобщили в ¬2.2. Настоящий параграф посвящен более эффективному методу решения задачи взаимного исключения. Освоив его, мы получим средства для описания примеров, с помощью которых я надеюсь убедить читателя в фундаментальном значении проблемы взаимного исключения; другими словами, я временно призываю к терпению заинтересованного читателя (как и я, страдающего от последовательного характера средств человеческого общения!).
Обобщенная задача взаимного исключения
2.2. Обобщенная задача взаимного исключения
Задача из ¬2.1 допускает естественное обобщение: даны N циклических процессов, каждый со своим критическим интервалом; можем ли мы так построить их, чтобы в любой момент самое большее один процесс находился в критическом интервале? Предположим, что в нашем распоряжении имеются те же самые средства связи, т. е. набор переменных общего доступа. Кроме того, наше решение должно удовлетворять тем же требованиям, а именно: остановка процесса вне его критического интервала не может никаким образом ограничивать продвижение других процессов, если более чем один процесс находится перед входом в свой критический интервал, то должно быть выполнено требование о невозможности подобрать для них такие конечные скорости, при которых решение о том, какому из них первому войти в свой критический интервал, откладывается до бесконечности.
Чтобы записать решение на языке АЛГОЛ-60, необходимо ввести понятие массива. В ¬2.1 мы вводили для каждого из процессов свои "с" с помощью описания
integer cl, с2
Вместо прямого перечисления величин, мы можем использовать (в предположении, что "N" имеет соответствующее положительное значение) следующее описание:
integer array с[1 : N]
которое означает, что мы вводим N целых переменных, к которым обращаются по именам
с[индекс],
где "индекс" может принимать значения 1, 2, . . ., N.
Следующей конструкцией языка АЛГОЛ-60, которую мы используем, является так называемый оператор цикла:
for j:=l step 1 until N do оператор S;
Он дает нам возможность очень удобно задать повторение "оператора S". В принципе эта конструкция означает, что "оператор S" будет выполнен N раз с "j", принимающим последовательно значения, равные 1, 2, . . ., N. (Мы добавили "в принципе", так как с помощью оператора goto, являющегося частью оператора S и передающего управление вне оператора S, повторное выполнение может быть прекращено раньше.)
Наконец, нам нужна логическая операция, которая в пределах этой главы будет обозначаться "and".
Мы уже встречали условное предложение в форме:
if условие then оператор
Теперь мы будем использовать такую форму:
if условие 1 and условие 2 then оператор
которая означает, что оператор S будет выполнен, если только "условие 1" и "условие 2" удовлетворяются оба. (Хотелось бы еще раз подчеркнуть, что эта глава не является руководством по программированию на АЛГОЛе и приведенные выше (нестрогие!) объяснения элементов АЛГОЛа даются только для того, чтобы сделать излагаемый материал возможно более самостоятельным.) С помощью только что бегло очерченных изобразительных средств мы можем записать наше решение для фиксированного значения N следующим образом:
begin integer array b, с[0 : N], integer очередь; for очередь := 0 step 1 until N do
begin b[очередь] := 1; с[очередь] :=1 end; очередь := 0; parbegin
процесс 1: begin ............... end; процесс 2: begin ............... end; . . . процесс N: begin ............... end; parend
end
В первой строчке вводится два массива с N + 1 элементом каждый; во второй вводится простая переменная "очередь". При выполнении следующего далее цикла переменная "очередь" принимает последовательно значения 0, 1, 2, 3, ..., N, так что элементы обоих массивов получают начальные значения, равные "1". Затем "очередь" устанавливается в "0" (т. е. ни один из процессов, пронумерованных от 1 до N, не поставлен в особые условия). После этого все N процессов начинают одновременно выполняться.
Все N процессов подобны. Структура i-го процесса такова (1 i N) :
процесс i: begin integer 3; Ai: b[i] := 0; Li: if очередь i then
begin с[i] := 1; if b[очередь] = 1 then очередь := i; goto Li end; c[i] :=0; for j:= 1 step 1 until N do
begin if j=/=1 and с[j] = 0 then goto Li end; критический интервал i; очередь :=0; с[i]:=1; b[i]:=l; остаток цикла i; goto Ai end
Ограниченный буфер
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
Определение
Определение
. V-операция есть операция с одним аргументом, который должен быть семафором. (Если "S1" и "S2" обозначают семафоры, то мы можем написать "V(S1)" и "V(S2)".) Назначение этой операции состоит в увеличении значения аргумента на 1; это действие должно рассматриваться как неделимая операция.
Заметим, что, согласно последнему предложению, "V(81)" не эквивалентно "S1 := S1 + 1"- Предположим, что два процесса А и В содержат оператор "V(S1)", и что оба они хотят выполнить этот оператор в момент, когда, скажем, "S1 = 6". Если исключить влияние на S1 других процессов, то А и В выполнят свои V-операции в некотором неопределенном порядке (во всяком случае, вне нашего контроля), и после завершения второй V-операции окончательное значение S1 будет равно "8". Если S1 не семафор, а только обычная общая целая переменная, и если процессы А и В оба содержат оператор "S1 := S1 + 1" вместо V-операции над S1, то могло бы случиться следующее. Процесс А вычисляет "S1 + 1" и получает "7"; до осуществления, однако, присваивания этого нового значения, процесс В достигает той же точки в программе и вычисляет "S1 + 1", также получая "7". После этого оба процесса присваивают значение "7" переменной S1, и одно из необходимых приращений, таким образом, потеряно. Требование "неделимости операции" предназначено для того, чтобы исключить подобный случай при использовании V-операции.
Определение
. P-операция есть операция с одним аргументом, который должен быть семафором. (Если "S1" и "S2" обозначают семафоры, то мы можем написать "P(S1)" и "P(S2)".) Ее назначение - уменьшить величину аргумента-семафора на 1, если только результирующее значение не становится отрицательным. Завершение P-операции, т. е. решение о том, что настоящий момент является подходящим для выполнения уменьшения, и последующее собственно уменьшение значения аргумента должно рассматриваться как неделимая операция.
P-операция как раз и представляет потенциальную задержку; а именно, если процесс инициирует P-операцию над семафором, который в этот момент равен "0", то в этом случае данная P-операция не может завершиться, пока другой процесс не выполнит V-операцию над тем же семафором и не присвоит ему значение "1". Несколько процессов могут одновременно начать P-операцию над одним и тем же семафором. Тогда утверждение о том, что завершение P-операции есть неделимое действие, означает, что когда семафор получит значение "1", только одна из начавшихся P-операций над семафором завершится. Какая именно - это опять не определено, т.е., во всяком случае, остается вне нашего контроля.
Мы будем считать, что P- и V-операции можно реализовать да вычислительной машине.
Применение алгоритма банкира
6.2. Применение алгоритма банкира
Этот пример также связан с флоринами. (Каждому флорину можно поставить в соответствие магнитную ленту; тогда заем флорина будет означать разрешение на использование одной из лент.)
Предположим, что клиенты пронумерованы от 1 до N, и что флорины пронумерованы от 1 до M. С каждым клиентом связывается переменная "номер флорина", значение которой после очередной выдачи флорина клиенту определяет номер только что выделенного флорина. В свою очередь с каждым флорином связана переменная "номер клиента", значение которой указывает клиента, которому выдан этот флорин.
Каждый клиент имеет переменную состояния "клиентпер" - переменная клиента; при этом "клиентпер = 1" означает "Я хочу получить заем" (иначе, "клиентпер = 0"). Каждый флорин имеет переменную состояния "флоринпер"; при этом "флоринпер = 1" означает "Я нахожусь среди наличного капитала". С каждым клиентом и каждым флорином связаны двоичные семафоры "клиентсем" и "флоринсем" соответственно, которые будут использоваться обычным образом.
Предполагаем, что каждый флорин выдается и возвращается на основании указаний клиента, но клиент не имеет возможности возвратить занятый флорин мгновенно. После того как клиент заявил, что флорин ему больше не нужен, последний не становится немедленно доступным для последующего использования. То есть клиент как будто говорит взятому им флорину: "Ступай обратно к банкиру". Фактический возврат флорина заканчивается после того, как тот действительно присоединится к наличному капиталу банкира: об этом флорин будет сообщать клиенту с помощью общего семафора клиента "возвращенные флорины". P-операция над этим семафором должна предостеречь клиента от неумышленного превышения своего кредита в банке. Перед каждым запросом флорина клиент выполнит P-операцию над семафором "возвращенные флорины"; начальное значение переменной "возвращенные флорины" полагается равным "потребность".
Предполагаем, что целочисленные константы "N" и "M" (равная капиталу) и массив целочисленных констант "потребность" описаны и определены во внешних по отношению к данной программе блоках.
Значение булевой процедуры "попытка выдать флорин клиенту" говорит о том, удовлетворен ли задержанный запрос на флорин. В программе для флорина используется тот факт, что возврат флорина может теперь привести к удовлетворению единственного задержанного запроса на флорин. (Если банкир распоряжается услугами более чем одного вида, то последнее свойство уже не будет выполняться. Тогда выход из цикла на оператор с меткой "выход" в конце программы для флорина недопустим.)
begin integer array заем, требование, клинтсем, клиентпер, номер флорина, возвращенные флорины[1 : N], флоринсем, флоринпер, номер клиента[1 : М]; integer взаимискл, наличные, k; Boolean procedure попытка выдать флорин клиенту(j); value j; integer j; begin if клиентпер[j] = 1 then
begin integer i, свободные деньги; Boolean array завершение под сомнением[1 : N]; свободные деньги := наличные - 1; требование[j] := требование[j] - 1; заем[j] := заем[j] + 1; for i := 1 step 1 until N do завершение под сомнением[i] := true; L0: for i := 1 step 1 until N do
begin if завершение под сомнением[i] and
требование[i] свободные деньги then
begin if i j then
begin завершение под сомнением[i] := false; свободные деньги := свободные деньги + заем[i]; goto L0 end
else
begin comment Можно реализовать и более сложный способ выбора свободного флорина, чем предлагаемый здесь; i := 0; L1: i := i + 1; if флоринпер[i] = 0 then goto L1; номер флорина[j] := i; номер клиента[i] := j; клиентпер[j] = 0; флоринпер[i] := 0; наличные := наличные - 1; попытка выдать флорин клиенту := true; V(клиентсем[i]); V(флоринсем[i]); goto L2 end
end
end; требование[j] := требование[j] + 1; зaeм[j] := зaeм[j] - 1 end; попытка выдать флорин клиенту := false; L2: end процедуры; взаимискл := 1; наличные := M; for k := 1 step 1 until N do
begin заем[k] := 0; клиентсем[k] := 0; клиентпер[k] := 0; требование[k] := потребность[k]; возвращенные флорины[k] := потребность[k] end; for k := 1 step 1 until M do
begin флоринсем[k] := 0; флоринпер[k] := 1 end; parbegin
клиент 1: begin. ........... end; . . . клиент N: begin. ........... end; флорин 1: begin. ........... end; . . . флорин M: begin. ........... end; parend
end
У клиента "n" запрос нового флорина описывается следующей последовательностью операторов:
P(возвращенные флорины[n]); P(взаимискл); клиентпер[n] := 1; попытка выдать флорин клиенту(n) V(взаимискл); P(клиентсем[n]);
после завершения последнего оператора значение переменной "номер флорина [n]" определяет только что выданный флорин; клиент может использовать его, но обязан возвратить его в надлежащее время банкиру.
Структура программы для флорина следующая:
флорин m: begin integer h;
начало: P(флоринсем[m]); comment Теперь "номер клиента [m]" указывает клиента, которому выдан данный флорин. Флорин может обслуживать клиента до тех пор, пока не закончит задачу, поставленную перед ним в течение этого заема. Чтобы возвратиться к наличному капиталу, флорин поступает следующим образом: P(взаимискл); требование[номер клиента[m]] := требование[номер клиента [m]] + 1; заем[номер клиента[m]] := заем[номер клиента[m]] - 1; флоринпер[m] := 1; наличные := наличные + 1; V(возвращенные флорины[номер клиента[m]]); for h := 1 step 1 until N do
begin if попытка выдать флорин клиенту(h) then
goto выход end; выход: V(взаимискл); goto начало end
Применение синхронизирующих примитивов к задаче взаимного исключения
3.3. Применение синхронизирующих примитивов к задаче взаимного исключения
Построение N процессов, содержащих критические интервалы, которые не должны выполняться одновременно (см. ¬2.2), теперь становится тривиальной задачей. Ее можно решить с помощью единственного двоичного семафора, который назовем, скажем, "свободно". Значение семафора "свободно" равняется числу процессов, которым разрешено в данный момент войти в свои критические интервалы: "свободно = 1" означает, что ни один из процессов не находится в своем критическом интервале; "свободно = 0" означает, что один из процессов находится в своем критическом интервале.
Общая схема программы такова:
begin integer свободно; свободно := 1; parbegin
процесс 1: begin ....... end; процесс 2: begin ....... end; процесс N: begin ....... end; parend
end
где i-ый процесс имеет вид:
процесс i: begin
Li: P(свободно); критический интервал i; V(свободно); остаток цикла i; goto Li end
В приведенной программе использована последовательность
2.3. Пример
В ¬2.2 мы описали взаимодействие N процессов. В приведенной программе использована последовательность вертикальных точек между скобками "parbegin" и "parend", что является лишь нестрогим формализмом для изображения совокупности N взаимодействующих последовательных процессов, при условии что N задано заранее. Эта общая форма может быть развернута для 3, 4 или 5071 взаимодействующих процессов, но она не дает формального описания N взаимодействующих процессов в случае, когда N является параметром, т. е. она не справедлива для любого значения N.
Цель данного параграфа - кратко показать, как может помочь в данном случае понятие так называемой "рекурсивной процедуры" в АЛГОЛе.
Мы видели, как с помощью описаний, следующих за "begin", вводились и именовались простые переменные (перечислением их имен) и упорядоченные множества переменных (описание массива). С помощью так называемого "описания процедуры" мы можем определить и поименовать отдельное действие. Такое действие вызывается затем использованием его имени в качестве оператора; при этом задаются параметры, к которым требуется применить это действие.
Рассмотрим в качестве иллюстрации следующую программу:
begin integer a, b; procedure квадрат(u, v); integer u, v; begin u := v v end; L: квадрат(а, 3); квадрат(b, а); квадрат(а, b); end
В первой строке программы описываются целые переменные "а" и "b". В следующей строке начинается описание процедуры, названной "квадрат", которая использует два параметра, являющихся простыми целочисленными переменными (а не, скажем, массивами). Эта строка называется "заголовком процедуры". Следующий далее оператор - так называемое "тело процедуры" - описывает само действие с именем "квадрат": присвоить первому параметру квадрат значения второго параметра (отметим, что скобки "begin . . . end" в третьей строке, вообще говоря, избыточны). Затем следует, снабженный меткой "L", первый выполняемый оператор программы.
До его выполнения значения переменных "а" и "b" не определены, после выполнения имеем "а = 9". После выполнения следующего оператора значение "b" становится равным "81", после выполнения последнего оператора получаем "а = 6561", а значение "b" по-прежнему равно "81".
В этом примере процедура послужила по существу средством сокращения записи, позволив избежать трехкратного включения "тела" в программу, хотя мы вполне могли бы написать:
begin integer a, b; L: а := 3 3; b := а а; а := b b end
В случае более сложного, чем в этом примере, тела длина программы значительно увеличилась бы.
Метод "подстановки вместо обращения к процедуре соответствующим образом преобразованного тела процедуры", однако, невозможен, если процедура является рекурсивной, т. е. сама может вызывать себя. Такая процедура действительно расширяет выразительную силу языка программирования.
Проиллюстрируем использование рекурсивной процедуры на простом примере. Общий наибольший делитель (ОНД) двух натуральных чисел определяется так:
если числа равны, то ОНД равен этому общему значению; если числа не равны, то ОНД равен общему наибольшему делителю меньшего из исходных чисел и их разности.
Иначе говоря, если ОНД не определяется тривиально (первый случай), то задача его нахождения заменяется отысканием ОНД для двух чисел с меньшими значениями.
(В следующей ниже программе спецификация "value v, w;" может быть пропущена читателем как не относящаяся по существу к обсуждаемому вопросу; она указывает, что для тела процедуры представляют интерес лишь числовые значения перечисленных параметров, задаваемые при обращении к процедуре).
begin integer a; procedure ОНД (u, v, w); value v, w; integer u, v, w; if v = w then u := v else begin if v < w then ОНД (u, v, w - v) else ОНД (u, v - w, w) end; ОНД (a, 12, 33) end
(B этом примере использована более сложная форма условного оператора, а именно:
if условие then оператор 1 else оператор 2
что означает: если "условие" удовлетворяется, то выполняется "оператор 1", а "оператор 2" пропускается; если "условие" не удовлетворяется, то пропускается "оператор 1", а выполняется "оператор 2".)
Читателю предоставляется проследить за последовательностью обращений к процедуре ОНД и убедиться, что переменная "а" получает значение "З". Необходимо также осознать, что (динамическая) схема обращений зависит от заданных параметров, и поэтому метод подстановки из предыдущего примера - замещение обращения к процедуре телом процедуры - привел бы здесь к трудностям.
Теперь мы составим программу умножения матрицы на вектор, в которой:
порядок вычисления М произведений скаляра на скаляр точно определен (строки матрицы просматриваются слева направо); N строк матрицы могут обрабатываться параллельно. (Там, где мы не хотим ограничиваться только целочисленными значениями, использован описатель "real" вместо описателя "integer"; кроме того, мы ввели двумерный массив, что, вероятно, у читателя не вызовет затруднений.)
Предполагается, что перед входом в этот блок целые переменные "М" и "N" получают положительные значения.
begin real array матрица[1 : N, 1 : M]; real array вектор[1 : M]; real array произведение[1 : N]; procedure умножстроки(k); value k; integer k; begin if k > 0 then
parbegin
begin real s; integer j; s := 0; for j := 1 step 1 until M do
s := s + матрица[k, 3] вектор[jl; произведение[k] := s end; умножстроки(k - 1) parend
end; . . . . умножстроки(N); . . end
Пример приоритетного правила
5.1. Пример приоритетного правила
В ¬4.3 мы использовали общий семафор для организации взаимодействия производителя и потребителя через ограниченный буфер. Предложенное решение легко обобщается на большее число производителей и (или) потребителей; оно применимо в случае, когда "порция" на буфере является к тому же и удобной единицей информации, т. е. когда можно считать, что все порции одинакового размера.
В настоящей задаче мы рассмотрим производителей, которые выдают порции различного размера, и предположим, что размер каждой из этих порций выражается в некоторых единицах. Потребители опять будут обрабатывать последовательные порции из буфера, а потому должны уметь обрабатывать порции, размер которых заранее не задан. Максимальный размер порции пусть будет, однако, известен.
Итак, размер порции задается в единицах информации; предполагаем также, что в единицах информации определяется и максимальная емкость буфера. Тогда вопрос о том, можно ли разместить на буфере очередную выработанную порцию, зависит от размера этой порции. Требования осуществимости операций "добавление порции к буферу" и "взятие порции из буфера" означают, что размер буфера не меньше размера максимальной порции.
Наш буфер ограничен, и поэтому может оказаться, что производитель должен ждать, пока он сможет поместить в буфер созданную порцию. При порциях фиксированного размера это случалось только тогда, когда буфер был полон; теперь это может происходить из-за того, что имеющегося на буфере свободного места недостаточно для размещения данной порции.
Кроме того, если имеется более одного производителя и какой-то из них ждет из-за отсутствия достаточного места на буфере, то другие производители вполне могут продолжать работу и достигнуть точки, когда они желают выдать выработанную порцию. Предлагаемая порция от нового производителя также может быть слишком велика, но она может быть и достаточно мала, чтобы поместиться на свободном месте буфера. Мы наложим на искомое решение требование, до некоторой степени произвольное, о том, что производитель, предлагающий большую порцию, получает приоритет над производителем, предлагающим меньшую порцию. (Когда два или больше производителей предлагают порции одинакового размера, нам безразлично, кто добавит порцию к буферу.)
Если какой-то производитель находится в состоянии ожидания, потому что его порцию нельзя разместить на буфере, то никакой другой производитель не сможет добавить свою порцию к буферу впредь до момента появления дополнительного свободного места: во-первых, другой производитель не сможет сделать это у если его порция больше (так как ее негде поместить); во-вторых, - ему не разрешено это делать, если его порция меньше, так как тогда он имеет более низкий приоритет и должен уступить буфер предыдущему запросу.
Рассмотрим момент, когда буфер полностью заполнен, и три производителя ожидают возможности добавить порции размером 1, 2 и 3 соответственно. Если теперь потребитель обработает порцию в пять единиц, то правило приоритетов будет означать, что получат возможность продолжать работу производители с порциями в 3 и 2 единицы, а не производитель с порцией в 1 единицу. Но это не означает, что в данном случае порция в 3 единицы будет действительно выдана раньше порции в 2 единицы.
Сейчас мы попытаемся ввести так называемые "переменные состояния" для различных элементов системы, с помощью которых мы сможем описывать состояния системы в любой момент времени.
Для каждого производителя вводим переменную с именем "желание"; эта переменная будет обозначать число единиц буфера, необходимых для размещения порции, которая не могла быть добавлена к буферу. Так как значение этой переменной всегда есть положительное число, мы можем придать соотношению "желание = 0" тот смысл, что у данного производителя нет неудовлетворенного требования на добавление порции. Кроме того, для каждого производителя введем двоичный "семафор производителя".
Для буфера мы вводим двоичный семафор "работбуф" - работа с буфером, который предназначается для взаимного исключения действий с буфером в широком смысле (т. е. не только добавление и взятие порций из буфера, но также проверка и модификация связанных с буфером переменных состояния).
Далее, мы нуждаемся в механизме сигнализации потребителям о появлении следующей порции.Как только в буфер добавлена новая порция, она может быть обработана; и поскольку нам безразлично, какой из потребителей возьмет ее, то для этого можно воспользоваться общим семафором "число порций в буфере". (Отметим, что он указывает число порций, а не число заполненных единиц информации в буфере.)
Об освобождении областей буфера необходимо сообщать производителям, но возможные последствия освобождения областей буфера вызывают более сложные решения, и нельзя ожидать, что общий семафор будет здесь подходящим средством. Попробуем ввести для этих целей целочисленную переменную состояния "число свободных единиц буфера". Отметим, что эта переменная отсчитывает единицы информации, а не порции.
Пример с диалогами
5.2. Пример с диалогами
В этом параграфе мы обсудим более сложный пример, в котором один из взаимодействующих процессов является не машиной, а человеком - "оператором".
Оператор системы связан с процессами посредством так называемого "полудуплексного канала" (применяется также термин "телесвязь"). Канал называется дуплексным, если информация но нему передается в обоих направлениях: оператор может с помощью клавиатуры передавать сообщения процессам, а процессы, в свою очередь, могут выдавать сообщения оператору на телепринтер. Канал называется полудуплексным, если передача информации возможна за один раз только в одном направлении.
Теперь давайте рассмотрим требования к системе в целом, отчасти упрощенные, чтобы не загромождать основную схему решения множеством несущественных деталей, но все же, я надеюсь, достаточно сложные, чтобы дать нам представление о реальной проблеме.
Имеется N идентичных процессов (пронумерованных от 1 до N). Каждый из них может задавать единственный вопрос, назовем его "Q1", который означает: "Каким образом мне продолжать выполнение?" Оператор системы может дать один из двух возможных ответов на этот вопрос, обозначаемых "А1" и "А2". Предполагается, что оператор должен знать, какой из процессов задает вопрос (так как его ответ может зависеть от этого), поэтому i-й процесс идентифицирует себя при передаче вопроса. Мы будем дальше говорить, что передается вопрос "Q1(i)". В некотором смысле это требование является следствием того, что все N процессов используют один и тот же канал связи.
Другое следствие этого деления средства связи между различными процессами состоит в том, что никакие два процесса не могут задать вопрос одновременно; таким образом, за всем этим должен наблюдать со стороны некоторый механизм взаимного исключения. Если взаимно исключаются только Ql-вопросы, то оператор может столкнуться с такой ситуацией: поставлен вопрос, скажем "Q1(3)", но прежде чем оператор решил, как на него ответить, приходит следующий вопрос, скажем "Q1(7)".
Тогда единственного ответа "А1" уже недостаточно, поскольку теперь не ясно, предназначается ли он "процессу 7" или "процессу З". Это можно было бы преодолеть добавлением к ответу указания о том, какому процессу он адресован, скажем "Al(i)" и "A2(i)" с соответствующим значением i.
Но это только один способ. Другое решение заключается в том, чтобы сделать вопрос и следующий на него ответ непрерываемым событием; это освобождает оператора от обязанности идентифицировать процесс, и поэтому мы выбираем это последнее соглашение. Итак, мы придерживаемся допустимой формы ответов "А1" и "А2" и имеем, следовательно, два вида диалогов: "Ql(i), А1" и "Ql(i), A2"; при этом следующий диалог может начаться только тогда, когда предыдущий завершен.
Теперь усложним задачу в трех отношениях.
Во-первых, процессам разрешается использовать канал связи для передачи специальных сообщений "M(i)", которые не требуют ответа от оператора.
Во-вторых, нам хочется предоставить оператору возможность отложить ответ. Конечно, он может сделать это, просто не отвечая в течение нужного ему времени, но тогда канал связи останется заблокированным для оставшихся N - 1 процессов, что нежелательно. Введем новый тип ответа "A3", означающий: "Канал освобождается, но диалог с соответствующим процессом остается неоконченным". Очевидно, что оператору нужно предоставить средство возобновить диалог. Он может это сделать с помощью "A4(i)" или "A5(i)", где i изменяется от 1 до N и указывает нужный процесс, причем "A4(i)" вызывает такое же продолжение процесса, как и при немедленном ответе "A1", a "A5(i)" предписывает процессу ту же реакцию, что и на ответ "А2". Приведем теперь возможные виды диалогов:
а) "Ql(i), A1" б) "Ql(i), A2" в) "Ql(i), A3" - - - "A4(i)" г) "Ql(i), A3" - - - "A5(i)".
Что касается выполнения процесса i, то для него диалог (а) эквивалентен (в), а (б) эквивалентен (г).
Рассмотренное выше второе требование имеет следующее следствие: без него, т.е. при единственно допустимых формах ответов "A1" и "A2", интерпретация входного сообщения (от оператора) могла бы быть всегда передана одному из N процессов, а именно тому, который задал вопрос; он мог дождаться ответа и затем соответственно действовать. Сейчас же мы не знаем заранее, когда появятся сообщения "A4(i)" или "A5(i)", и мы не можем поручить интерпретацию этих сообщений от оператора целиком самому i-му процессу, так как выявление принадлежности входящего сообщения (от оператора) i-му процессу является частью самой интерпретации сообщения!
В-третьих, А4- и А6-сообщения должны иметь приоритет над Q1- и М-сообщениями. Это означает следующее. В то время как канал связи занят (передачей Q1- или М-сообщения), процессы могут достигнуть точки, когда им необходимо использовать канал. Но такая же потребность может появиться в это же время у оператора. Мы хотим, чтобы оператор мог использовать канал как только он освободится, и, если оператор пожелал использовать канал, то последний не может быть снова захвачен каким-либо процессом. Это означает, что оператор имеет средства выразить свое желание с помощью какой-либо элементарной формы ввода, даже если сам канал занят выводом для оператора.
Предположим, что оператор
а) может выполнить какими-то внешними средствами операцию "V(входящее сообщение)", которую он может использовать для объявления сообщения (A1, A2, A3, А4 или А5);
б) может обнаружить по реакции машины, принято его вмешательство или отвергнуто.
Проблема тупиков
6. ПРОБЛЕМА ТУПИКОВ
Во вводной части этого раздела мы остановимся на логической задаче, которая возникает при взаимодействии различных процессов, когда они должны делить одни и те же ресурсы. Эта проблема выбрана по разным причинам. Во-первых, она является непосредственным обобщением известной ситуации, согласно которой два человека не могут воспользоваться одновременно одной секцией вращающейся двери. Во-вторых, решение этой проблемы, которое я считаю нетривиальным и которое будет приведено в ¬6.1, дает нам хороший пример более тонких правил взаимодействия, чем те, с которыми мы до сих пор встречались. В-третьих, она предоставляет нам возможность проиллюстрировать (в ¬6.2) методы программирования, с помощью которых может быть достигнут дальнейший прогресс в наглядности представления. Для начала я приведу один пример разделения ресурсов. В качестве "процессов" мы можем принять "программы", описывающие некоторый вычислительный процесс, выполняемый вычислительной машиной. Выполнение такого вычислительного процесса требует определенного времени, в течение которого в памяти вычислительной машины хранится информация. Ограничимся процессами, о которых заранее известно следующее:
Их требования к объему памяти не будут превышать определенного предела. Каждый вычислительный процесс завершится при условии, что требуемый процессу объем памяти будет предоставлен в его распоряжение. Завершение вычислительного процесса будет означать, что его требования к памяти уменьшились до нуля.
Предполагаем, что имеющаяся память поделена на "страницы" фиксированного размера, которые с точки зрения программы считаются эквивалентными.
Фактическое требование нужного процессу объема памяти может быть функцией, изменяющейся по мере протекания процесса, но, конечно, в соответствии с заранее заданной верхней границей. Предположим, что отдельные процессы запрашивают и возвращают память единицами в одну страницу. "Эквивалентность" (см. последнее слово предыдущего абзаца) означает, что процесс, запрашивающий новую страницу, просит просто "новую страницу", но никогда не специальную страницу или страницу из специальной группы.
Теперь мы потребуем, чтобы процесс, однажды начатый, получил рано или поздно возможность завершить свои действия, и будем отбрасывать любую схему, при которой может случиться, что процесс уничтожается на полдороге из-за своих действий, тем самым напрасно растратив уже выделенное ему на вычисления время.
Если вычислительная машина выполняет процессы один за другим, то они должны удовлетворять единственному условию, чтобы максимально требуемый ими объем памяти не превышал общую емкость памяти машины.
Если, однако, вычислительная машина обслуживает одновременно более одного процесса, то можно придерживаться правила, что допускаются только такие программы, у которых сумма их максимальных требований не превышает общей емкости памяти. Это правило, хотя и обеспечивает безопасность, является излишне ограничивающим, так как предполагает, что каждый процесс действительно занимает максимальную память во все время выполнения. Если мы посмотрим на следующую таблицу (где процессы "заимствуют" страницы из имеющейся памяти)
Процесс | Максимальное требование |
Настоящий объем |
Дальнейшее требование |
П1 П2 |
80 60 |
40 + 20 |
40 40 |
Свободная память = 100 - 60 = 40 |
Если бы, однако, оба процесса затребовали теперь по следующей странице, и получили бы ее, то сложилась бы такая ситуация:
Процесс | Максимальное требование |
Настоящий объем |
Дальнейшее требование |
П1 П2 |
80 60 |
41 + 21 |
39 39 |
Свободная память = 100 - 62 = 38 |
Эта ситуация, когда один из процессов может быть продолжен только при условии, что другой будет сперва уничтожен, называется "Смертельное Объятие" ("The Deadly Embrace").Проблема, которую нам необходимо решить, заключается в следующем: как избежать опасности тупика, не накладывая слишком больших ограничений.
Простой пример
2.1. Простой пример
Рассмотрим два последовательных процесса: "процесс 1" и "процесс 2", которые для наших целей удобно считать циклическими. В каждом цикле выполнения процесса существует "критический интервал", критический в том смысле, что в любой момент времени только один из процессов может находиться внутри своего критического интервала. Чтобы осуществить такое "взаимное исключение", оба процесса имеют доступ к некоторому числу общих переменных. Мы постулируем, что проверка текущего значения такой общей переменной и присваивание нового значения общей переменной рассматриваются как неделимые, не допускающие вмешательства действия; то есть, если два процесса осуществляют присваивание нового значения одной и той же общей переменной "одновременно", то присваивания происходят друг за другом и окончательное значение переменной соответствует одному из присвоенных значений, но никогда не есть их "смесь".
Подобно этому, если один процесс проверяет значение переменной "одновременно" с присваиванием ей значения другим процессом, то первый обнаруживает либо старое, либо новое значение, но никогда не их смесь.
Для наших целей АЛГОЛ-60 не подходит, так как он создан для описания единственного последовательного процесса. Поэтому /мы используем некоторое его расширение, позволяющее описывать параллельное выполнение. Если последовательность операторов - как обычно разделенных точкой с запятой - заключена в специальные операторные скобки "parbegin" и "parend", то это интерпретируется как параллельное выполнение составляющих конструкцию операторов. Вся конструкция - назовем ее "параллельный блок" - может рассматриваться как оператор. Запуск параллельного блока означает одновременный запуск всех составляющих его операторов; выполнение блока завершается после завершения выполнения всех составляющих его операторов. Например,
begin S1; parbegin S2; S3; S4; parend; S5 end
(где S1, S2, S3, S4 и S5 есть операторы) означает, что после завершения S1, операторы S2, S3 и S4 будут выполняться параллельно, и только после того, как все они завершатся, начнется выполнение оператора S5.
Теперь при определенных выше соглашениях об использовании общих переменных мы можем написать первое решение проблемы взаимного исключения:
begin integer очередь; очередь := 1; parbegin
процесс 1: begin L1: if очередь = 2 then goto L1; критический интервал 1; очередь := 2; остаток цикла 1; goto L1 end; процесс 2: begin L2: if очередь = 1 then goto L2; критический интервал 2; очередь := 1; остаток цикла 2; goto L2 end; parend
end
(Сделаем замечание для читателя, недостаточно знакомого с языком АЛГОЛ-60. После "begin" в первой строке стоит так называемое описание "integer очередь", ибо, согласно правилам языка АЛГОЛ-60 в тексте программы нельзя ссылаться на переменные, не введенные с помощью описания. Так как это описание располагается после "begin", являющегося самой внешней операторной скобкой, то это означает, что на время выполнения всей программы введена переменная, которая будет принимать только целые значения, и к которой можно обратиться с помощью имени "очередь".)
Два процесса связываются друг с другом через общую целочисленную переменную "очередь", значение которой показывает, какой из двух процессов первым выполнит (точнее, закончит) свой критический интервал. Из программы ясно, что после первоначального присваивания единственными возможными значениями переменной "очередь" являются "1" и "2". Условием входа в критический интервал для процесса 2 является "очередь 1", т. е. "очередь = 2". Но единственный способ для переменной "очередь" получить это значение есть присваивание "очередь := 2" в процессе 1. Так как процесс 1 выполняет это присваивание только по завершении своего критического интервала, то процесс 2 может войти в свой критический интервал только после завершения критического интервала 1. А критический интервал 1 действительно мог быть выполнен, потому что начальное условие "очередь = 1" означает одновременно "очередь 2", и значит потенциальный цикл ожидания, помеченный в программе как L1, первоначально бездействует.
После присваивания "очередь := 2" роли процессов меняются. {Замечание. Предполагается, что других ссылок на переменную "очередь", кроме тех, которые явно присутствуют в программе, не существует.)
Наше решение, хотя и правильное, имеет, однако, излишнее ограничение: после завершения критического интервала 1, переменная "очередь" становится равной "2" и должна вновь получить значение "1", чтобы разрешить следующий вход в критический интервал 1. Как результат этого, единственно допустимая последовательность критических интервалов представляет собой строгое их чередование "1, 2, 1, 2, 1, 2, 1, ... ", т. е. процессы синхронизированы. Для того, чтобы четко определить нежелательность для нас подобного решения, мы поставим дополнительное условие: "если один из процессов остановился вне своего критического интервала, то это не должно привести к блокировке другого процесса" . Поэтому предыдущее решение не приемлемо, и мы должны искать новое.
Наша вторая попытка связана с введением двух целочисленных переменных "cl" и "с2", причем cl = 0 (или 1) или c2 = 0 (или 1) соответственно будет означать, что процесс 1 или процесс 2 находятся внутри (или вне) критического интервала. Предлагается следующее решение:
begin integer cl, c2; cl := 1; c2 := 1; parbegin
процесс 1: begin L1: if c2 = 0 then goto L1; cl := 0; критический интервал 1; c1:= i; остаток цикла 1; goto L1 end; процесс 2: begin L2: if cl = 0 then goto L2; c2 := 0; критический интервал 2; c2 := 0; остаток цикла 2; goto L2 end; parend; end
Первоначальные присваивания устанавливают cl и c2 в "1" в соответствии с тем фактом, что процессы начинают выполняться вне своих критических интервалов. Во все время выполнения критического интервала 1 сохраняется соотношение "cl = 0" и потому первая строка в записи процесса 2 представляет по существу ожидание: "ждать до тех пор, пока процесс 1 находится в своем критическом интервале." Такое решение проблемы действительно отчасти предохраняет от одновременного выполнения критических интервалов, но оно, к сожалению, потому слишком просто, что неверно.
Пусть сначала процесс 1 обнаружит, что "c2 = 1".
Пусть процесс 2 немедленно вслед за этим проверяет значение cl; тогда он еще найдет, что "cl = 1". Каждый из процессов, удостоверившись, что другой не находится в критическом интервале, решит, что он может безопасно войти в свой собственный критический интервал!
Мы должны действовать более осторожно. Давайте поменяем местами в самом начале процессов проверку чужого "с" и установку собственного "с". Получаем такую программу:
begin integer cA, c2; cl := 1; c2 := 1; parbegin
процесс 1: begin Al : cl := 0; L1 : if c2 = 0 then goto L1; критический интервал 1; cl := 1; остаток цикла 1; goto Al end; процесс 2: begin A2 : c2 := 0; L2 : if cl = 0 then goto L2; критический интервал 2; c2 := 1; остаток цикла 2; goto A2 end; parend; end
Имеет смысл убедиться в том, что это решение во всяком случае совершенно безопасно. Давайте сосредоточим внимание на моменте, когда процесс 1 обнаруживает, что "c2 = 1", и поэтому решает войти в свой критический интервал. В этот момент мы можем заключить:
соотношение "cl = 0" уже установлено и будет сохраняться, пока процесс 1 не завершит выполнение своего критического интервала; так как "c2 = 1", то процесс 2 находится вне критического интервала, в который он не может войти, пока сохраняется "cl = 0", т. е. пока процесс 1 еще пребывает в своем критическом интервале.
Итак, взаимное исключение действительно гарантировано.
Но, увы, это решение также должно быть отвергнуто: предпринятые в нем меры безопасности слишком сильны, так что оно содержит опасность взаимной блокировки. Если после присваивания "cl := 0", но еще до проверки c2 (и то, и другое в процессе 1), процесс 2 выполнит присваивание "c2 := 0", то это значит, что оба процесса достигли соответственно меток L1 и L2 и одновременно справедливы соотношения "cl = 0" и "c2 = 0". В итоге процессы будут безрезультатно ждать друг от друга разрешения войти в критический интервал.
Мы правильно поступили, установив собственное "с" до проверки чужого "с", но неправильно было сохранять только состояние ожидания с неизменным установленным собственным "с". Это до некоторой степени исправлено в следующей конструкции:
begin integer cl, c2; cl := 1; c2 := 1; parbegin
процесс 1: begin L1: cl := 0; if c2 = 0 then
begin cl := 1; goto L1 end; критический интервал 1; cl := 1; остаток цикла 1; goto L1 end; процесс 2: begin L2: c2 := 0; if cl = 0 then
begin c2 := 1; goto L2 end; критический интервал 2; c2 := 1; остаток цикла 2; goto L2 end; parend; end
Эта конструкция столь же безопасна, как и предыдущая, а если присваивания "cl := 0" и "с2 := 0" выполняются "одновременно", то это не приводит с неизбежностью к взаимной блокировке до бесконечности; дело в том, что оба процесса установят свои собственные "с" обратно в "1", прежде чем возобновить попытку входа в критический интервал, тем самым предоставляя другому процессу возможность поймать удобный момент. Но наши принципы заставляют отбросить также и это решение, так как отказ от каких-либо предположений относительно соотношения скоростей означает, что решение должно быть справедливым при любых скоростях, а последняя конструкция позволяет так подобрать скорости, что процессы будут проверять чужие "с" только в те моменты времени, когда значения их собственных "с" нулевые. Чтобы четко определить неприемлемость таких решений, которые работают только при некоторых удачных обстоятельствах, мы установим следующее требование: "если два процесса находятся перед входом в свои критические интервалы, то должно быть выполнено требование о невозможности подобрать для них такие конечные скорости, при которых решение о том, какому из них первому войти в свой критический интервал, откладывается до бесконечности".
Между прочим, заметим, что отброшенное решение вполне приемлемо в повседневной жизни. Например, когда два человека разговаривают по телефону и связь неожиданно разъединяется, оба, как правило, пытаются восстановить связь.
Каждый из собеседников набирает номер и, если слышит сигнал "занято", то кладет телефонную трубку. Если тут же не происходит вызов, то он делает вторую попытку, спустя несколько секунд. Конечно, эта попытка может совпасть со следующей попыткой партнера, но обычно связь восстанавливается после небольшого числа проб. В наших условиях мы не можем принять такую схему поведения: у нас партнеры могут быть совершенно идентичны.
Предлагалось довольно много решений этой задачи, и все они оказались некорректными, так что у тех, кто занимался ею, возникло в какой-то момент сомнение, имеет ли она решение вообще. Первое правильное решение принадлежит голландскому математику Деккеру. Это решение представляет в действительности некоторое объединение наших предыдущих попыток: в нем используются "переменные безопасности", подобные тем, что обеспечивали взаимное исключение в последних конструкциях, вместе с целочисленной переменной "очередь" первого решения, но только для разрешения неопределенности, когда ни один из двух процессов не продвигается немедленно в критический интервал. Отметим, что в предлагаемой ниже программе начальное значение переменной "очередь" может быть положено также и равным "2".
begin integer cl, c2, очередь; cl := 1; c2 := 1; очередь := 1; parbegin
процесс 1: begin Al: cl := 0; L1: if c2 = 0 then
begin if очередь = 1 then goto L1; cl := 1; Bl: if очередь = 2 then goto Bl; goto A1 end; критический интервал 1; очередь := 2; cl := 1; остаток цикла 1; goto Al end; процесс 2: begin A2: c2 := 0; L2: if cl = 0 then
begin if очередь = 2 then goto L2; c2 = 1; B2: if очередь = 1 then goto B2; goto A2 end; критический интервал 2; очередь := 1; c2 := 1; остаток цикла 2; goto A2 end; parend; end
Докажем теперь корректность этого решения. Во-первых, отметим, что каждый процесс оперирует только с собственным "с".
Вследствие этого процесс 1 проверяет "c2" только при "cl = 0"; он войдет в свой критический интервал только тогда, когда обнаружит, что "c2 = 1".
Для процесса 2 можно сделать аналогичное замечание.
Короче говоря, мы узнаем переменные безопасности наших последних конструкций, и поэтому решение безопасно в том смысле, что два процесса никогда не могут оказаться одновременен) в своих критических интервалах.
Во второй части доказательства необходимо показать, что в случае сомнения, какому из двух процессов первым войти в критический интервал, выяснение этого вопроса не может откладываться до бесконечности. Теперь мы обратим внимание на целочисленную переменную "очередь": замечаем, что присваивание значения этой переменной происходит только при окончании критических интервалов (или по окончании некоторых их частей), поэтому можно считать переменную "очередь" константой во время принятия решения о том, кому войти в критический интервал. Предположим, что "очередь = 1". Тогда процесс 1 может только циклиться через метку L1 (при этом "с1 = 0") и только до тех пор, пока он находит, что "с2 = 0". Но если "очередь = 1", то процесс 2 может циклиться только через В2, а это состояние процесса 2 означает, что "с2 = 1", поэтому процесс 1 не может циклиться и непременно попадает в свой критический интервал. Для случая "очередь = 2" применяется симметричное (относительно процессов и переменных) рассуждение.
В третьей и заключительной части доказательства мы отмечаем, что остановка, скажем процесса 1 в "остатке цикла 1", не препятствует продвижению процесса 2: тогда справедливо соотношение "с1 = 1", и процесс 2 может входить в свой критический интервал совершенно независимо от текущего значения переменной "очередь". Этим завершается доказательство корректности решения Деккера. Тех читателей, которые не оценили изобретательности этого решения, я прошу учесть, что для них уже была подготовлена почва из тщательно подобранных мною и затем отвергнутых, как непригодные, решений.
Синхронизирующие примитивы
3.2. Синхронизирующие примитивы
Источник трудностей, которые приводят к таким сложным решениям, как описанное в ¬2.2, состоит в том, что неделимые обращения к общим переменным всегда подразумевают "одностороннее движение информации": отдельный процесс может либо присвоить новое значение, либо проверить текущее значение. Однако сама такая проверка не оставляет после себя никаких следов для других процессов, и вследствие этого, в то время как процесс желает отреагировать на текущее значение общей переменной, значение этой переменной может быть изменено другими процессами между моментом проверки и последующей реакцией. Иначе говоря, предыдущий набор средств связи между процессами должен считаться неадекватным для рассматриваемой проблемы, и мы должны искать более подходящие возможности.
Такая возможность обеспечивается:
а) введением специальных целочисленных общих переменных, которые мы назовем "семафорами";
б) добавлением к набору элементарных действий, из которых строятся отдельные процессы, двух новых примитивов, которые мы назовем "P-операция" и "V-операция".
Эти две последние операции всегда выполняются над семафорами, и представляют единственный способ обращения к семафорам со стороны одновременно действующих процессов.
Семафоры являются по существу неотрицательными целыми величинами. Если они используются только для решения задачи взаимного исключения, то область их значений составляют лишь "0" и "1". Заслугой голландского физика и конструктора вычислительных машин Шольтена является то, что он показал важную область применения семафоров, которые могут принимать также и большие значения. Там, где необходимо делать это различие, мы будем говорить о "двоичных семафорах" и "общих семафорах" соответственно. Определения P- и V-операций, которые сейчас будут даны, справедливы для обоих типов семафоров.
Слабо связанные процессы
2. СЛАБО СВЯЗАННЫЕ ПРОЦЕССЫ
Предметом главы в целом является изучение слабо связанных последовательных процессов. Данный раздел посвящен тщательному рассмотрению простой, но характерной задачи, на примере которой читатель познакомится с возникающими в этой области проблемами.
В предыдущем разделе мы описали природу изолированного последовательного процесса, в котором последовательность действий выполняется автономно, т.е. независимо от окружающей обстановки.
Если двум или более последовательным процессам необходимо взаимодействовать друг с другом, то они должны быть связаны, т. е. иметь средства для обмена информацией. Как мы увидим ниже, свойства таких средств связи играют важную роль.
Кроме того, мы предполагаем, что процессы связаны слабо. Под этим подразумевается, что кроме (достаточно редких) моментов явной связи, эти отдельные процессы рассматриваются как совершенно независимые друг от друга. В частности, не допускаются какие-либо предположения об относительных скоростях различных процессов. (Скажем, такое предположение, как "процессы синхронизированы относительно некоторого общего времени", может рассматриваться как неявная связь.) Независимость от соотношения скоростей полностью соответствует нашему определению последовательного процесса, единственным существенным свойством которого является то, что элементарные шаги процесса выполняются последовательно. Если нужно, мы можем следить по часам за выполнением процесса, но сам он от этого совершенно не зависит.
Отказ от каких-либо предположений о соотношении скоростей на первый взгляд покажется читателю неоправданной попыткой представить вещи в более сложном виде, чем они есть на самом деле. Однако это полностью обосновано. Во-первых, нам, возможно, придется иметь дело с ситуациями, в которых действительно мало что известно о скоростях. Например, одной частью системы может быть управляемая вручную станция, а другая часть системы характеризуется тем, что она может останавливаться по внешнему воздействию на неопределенное время, тем самым уменьшая скорость "выполнения" процесса до нуля. Во-вторых, - и это значительно более важно, - когда мы думаем, что можем полагаться на некоторое соотношение скоростей, то оказывается в конце концов, что мы погнались за пенни, а упустили фунт. Конечно, отдельные устройства можно сделать проще в предположении ограничений на их скорости. Однако задача создания надежной работоспособной системы из многих связанных элементов значительно усложняется, если необходимо учитывать их взаимное влияние друг на друга и согласовывать скорости. (Прежде всего это создает весьма неустойчивое равновесие в работе, чувствительное к любым изменениям скоростей, которые легко возникают при замене элементов системы, скажем, при установке более быстрой модели построчного печатающего устройства или при перепрограммировании какой-либо части программного обеспечения.)
Совершенствование предыдущей программы
5.2.1. Совершенствование предыдущей программы
В ¬5.2 предложен первый вариант программы; он включен в изложение не потому, что является удовлетворительным, а потому что он завершает общую картину создания решения. Давайте попытаемся сделать его более красивым во имя большей лаконичности, ясности и, возможно, эффективности. Давайте попытаемся обнаружить, в каких отношениях мы совершили просчет.
Сравним потоки информации от процесса к интерпретатору сообщений и обратно. В одном направлении мы с помощью общей переменной "номерпроц" извещали интерпретатор сообщений о том, какой из процессов задал вопрос. Установку и проверку "номерпроп" вполне безопасно можно делать вне критических интервалов, управляемых семафором "взаимискл", так как в каждый момент самое большее один из N + 1 процессов будет обращаться к "номерпроц". В обратном направлении интерпретатор сообщений извещает i-й процесс о характере окончательного ответа оператора, представляя его с помощью значения переменной "процпер". Здесь происходит некоторое смешение понятий, что проявляется:
а) в проверке значения "процпер" (равно ли ее значение "З" или "4"), которую вдруг разрешено проводить вне критического интервала;
б) в избыточности сброса значения "процпер" в "0".
Предлагается ввести массив
integer array ответоператора[1 : N],
элементы которого будут использоваться подобно переменной "номерпроц". (Привлекательным следствием этого является то, что число возможных значений "процпер" - более фундаментальной величины (см. ниже) - не будет расти с увеличением числа возможных ответов на вопрос Q1.)
Мне хотелось бы исследовать такой вопрос: можно ли достигнуть большей ясности в решении, разделив общие переменные на две (или, возможно, больше) различные группы для того, чтобы отразить заметную иерархию в способах их использования. Давайте попробуем упорядочить их с точки зрения их "не важности".
Семафор " входящее сообщение" на первый взгляд кажется достаточно важным, обусловленным окружающей средой. Однако это иллюзия: в параллельном блоке мы запрограммировали бы (в качестве (N + 2)-го процесса) самого оператора, и семафор, "входящее сообщение" был бы тогда частным семафором для интерпретатора сообщений, подобно семафору "процсем[i]" для i-го процесса.
Таким образом, наиболее важной величиной является семафор "взаимискл", обеспечивающий взаимное исключение критических интервалов.
Затем следуют переменные состояния "общпер" и "процпер", которые проверяются и могут изменяться внутри критических интервалов.
Только что упомянутые величины обладают тем общим свойством, что их значения должны быть установлены до входа в параллельный блок. Этим же свойством обладают семафоры "процсем" (и семафор "входящее сообщение", см. выше), если мы придерживаемся того правила, что параллельно выполняющиеся процессы обращаются к семафорам исключительно с помощью P- и V-операций.
(Без этого ограничения запрос на средства связи процессом n мог бы начинаться так:
Р(взаимискл); if общпер = 0 then
begin общпер := 1; V(взаимискл) end
else
begin процпер[n] .= 1; процсем[n] := 0; V(взаимискл); Р(процсем[n]1) end
Мы отбрасываем это решение, так как дальнейшее рассмотрение убеждает нас в том, что присваивание переменной "процсем[n]" имеет смысл только в первый раз; поэтому присваивание начальных значений переменным "процсем" вне параллельного блока кажется более подходящим.)
Для перечисленных до сих пор общих переменных мне хотелось бы сохранить название "переменные состояния", чтобы отличать их от оставшихся общих переменных "номерпроц" и "ответоператора", которые мне хочется назвать "передаточные переменные", потому что всякий раз, когда один из процессов присваивает значение такой переменной, он адресует его известному "партнеру-получателю".
Эти общие переменные используются для передачи информации между известными партнерами.
Давайте теперь переключим наше внимание с общих переменных на программы. В программах мы научились выделять так называемые "критические интервалы", для которых семафор "взаимискл" обеспечивает взаимное исключение. Помимо них, мы можем выделить области (динамические участки программы), в которых выполняются некоторые вполне определенные действия, такие как:
В i-ом процессе:
Область 1: посылка М-сообщения Область 2: посылка Ql(i)-Bonpoca Область 3: реакция на ответ оператора[i] (эта область не столь строго очерчена, как предыдущие).
В интерпретаторе сообщений:
Область 4: игнорирование входящих сообщений Область 5: ожидание Al, A2 или A3 Область 6: ожидание A4(i), A5(i) или А6.
Перед нами теперь возникает следующая картина. Мы имеем в программе критические интервалы, взаимно исключаемые семафором "взаимискл". Назначение критических интервалов - устранить какую-либо неоднозначность при проверке и модификации остальных переменных состояния. Целью этих проверок и модификаций является создание более сложных "последовательных структур" из областей, которые делают возможным однозначное использование передаточных переменных. (Если один процесс должен передать информацию другому, то он может теперь осуществить это через передаточные переменные при условии, что за выполнением области присваивания всегда следует область проверки, прежде чем будет выполнена следующая область присваивания.)
В улучшенном варианте программы мы будем придерживаться того правила, что обращения к подлинным переменным состояния будут происходить только в критических интервалах (если они не являются семафорами) или с помощью P- и V-операций (если они являются семафорами), тогда как обращения к передаточным переменным будут происходить только во введенных выше областях. (В более сложных примерах это правило может оказаться слишком жестким, и размножения общих переменных можно избежать, разрешив по крайней мере проверку передаточных переменных в критическом интервале.
В этом примере, однако, мы будем соблюдать упомянутое выше правило.)
Оставшиеся улучшения в программе менее существенны. Программе можно придать более привлекательный вид, если представлять наличие приоритетных запросов оператора не дополнительными значениями переменной "общпер", а при помощи дополнительной переменной состояния с двумя значениями?
Boolean приоритет оператора
(Переменные типа "Boolean" могут принимать два значения, обозначаемые "true" и "false", совпадающие с областью значений "условий", которые мы встречали в конструкциях if.)
Кроме того, введем две процедуры; они описываются вне параллельного блока и поэтому могут использоваться составными элементами параллельного блока.
Сначала мы кратко опишем новый смысл значений переменных состояния "процпер" и "общпер":
процпер[i] = 0 внутреннее положение процпер[i] = 1 ожидание доступности средств связи для передачи М или Ql(i) процпер[i] = 2 ожидание ответа "A4(i)" или "A5(i)". общпер = 0 средства связи свободны общпер = 1 средства связи используются для М или Q1 общпер = 2 средства связи используются для Al, A2 или A3 общпер = 3 средства связи используются для А4, А5 или А6.
Мы приводим программу без комментариев, и сделаем это в два приема: сначала дадим программу вне параллельного блока, а затем - составные элементы параллельного блока.
begin integer взаимискл, общпер, номерпроц, цикл; Boolean приоритет оператора; integer array процпер, процсем, ответоператора[1 : N]; procedure М или Q(n); value n; integer n; begin Р(взаимискл); if общпер = 0 then
begin общпер := 1; V(взаимискл) end
else
begin процпер[n]:= 1; V(взаимискл); Р(процсем[n1) end
end М или Q; procedure выбрать новое значение для общпер; begin integer i;
if приоритет оператора then
begin приоритет оператора:= false; общпер := 3 end
else
begin for i := 1 step 1 until N do
begin if процпер[i] = 1 then
begin процпер[i] = 0; общпер := 1; V(процсем[i]); goto готов end
end; общпер := 0; готов: end
end; for цикл := 1 step 1 until N do
begin процпер[цикл] := 0; процсем[цикл] ;= 0 end; общпер := 0; взаимискл := 1; приоритет оператора := false; parbegin
процесс 1: begin. ........... end; . . . процесс N: begin. ........... end; интерпретатор сообщений; begin. ........... end
parend
end
Здесь n-й процесс представляется в следующем виде;
процесс n: begin
. . . М сообщение: М или Q(n); Область 1: посылка М-сообщения; Р(взаимискл); выбрать новое значение для общпер; V(взаимискл); . . . Q1 вопрос: М или Q(n); Область 2: номерпроц := n; посылка Q1(n)-вonpoca;
Р(взаимискл); общпер := 2; V(взаимискл); Р(процсем[n]); Область 3: if ответоператора[n] = 1 then Реакция 1 else Реакция 2; end
Если интерпретатор сообщений решает войти в Область 6, то он перед входом получает копию массива "процпер": если принимается сообщение A4(i) или A5(i), то в момент объявления ответа уже должно выполняться "процпер[i] = 2.
Интерпретатор сообщений:
begin integer i; integer array копияпроцпер[1 : N]; ждать: Р(входящее сообщение); Р(взаимискл); if общпер = 1 then
Область 4: begin приоритет оператора := true; выход: V(взаимискл); goto ждать end; if общпер 2 then goto Область 6; Область 5: V(взаимискл); прием сообщения; if сообщение Ai and сообщение А2 and сообщение A3 then goto ждать; i: = номерпроц; if сообщение = Al then
ответоператора[i] := 1 else
if сообщение = A2 then
ответоператора[i] := 2; Р(взаимискл); if сообщение = A3 then процпер[i] := 2 else
извещение процесса i: V(процсем[i]); предварительный выход: выбрать новое значение для общпер; goto выход; Область 6: if общпер = 0 then общпер := 3; for i : = 1 step 1 until N do
копияпроцпер[i] := процпер[i]; V(взаимискл); прием сообщения; if сообщение = А6 then
begin Р(взаимискл); goto предварительный выход end; if сообщение А4(заданный процесс) and сообщение А5(заданный процесс) then goto ждать; i := ; if копияпроцпер[i] 2 then goto ждать; ответоператора[i] := if сообщение = А4 then 1 else 2; Р(взаимискл); процпер[i] := 0; goto извещение процесса i end
В качестве упражнения мы предлагаем читателю составить такой вариант программы, в котором ожидающие запросы на Q1-вопросы, имеют приоритет над запросами на М-сообщения. Следующее расширение примера состоит в составлении программы двухпультовой конфигурации с дополнительным ограничением: А4- или А6-сообщения допускаются только с того пульта, где диалог был начат. (Иначе мы должны исключить одновременные противоречивые сообщения "A4(i)" и "A5(i)" с различных пультов. Решение без этого ограничения адресовано поистине увлеченному читателю.)
5.2.2. Доказательство корректности
В этом заголовке слово "доказательство" использовано в не формальном смысле. Я не определил, какие формальные условия необходимо соблюсти в "истинном доказательстве" и не собираюсь этого делать. Если я смогу найти такой способ обсуждения программы из п.5.2.1, который позволит мне убедиться самому - и, надеюсь, убедить сомневающихся - в корректности общего функционирования этой совокупности процессов, я буду удовлетворен.
В приведенной "схеме состояний" дается диаграмма всех состояний, в которых может оказаться процесс (вне критических интервалов). Стрелки указывают переходы из состояния в состояние, которые происходят внутри критических интервалов; стрелки сопровождаются надписями, отражающими изменения "общпер" или условия, при которых такой переход имел место.
Нейтральную область процесса до входа в Область 1 или Область 2 мы называем "Область 0".
Рис.8. |
Рис.9. |
Рис.10. |
Рис.11. |
Конечно, эти диаграммы ничего нового нам не говорят, но они могут оказаться мощным средством при проверке программ.
Сначала мы убеждаемся, что "общпер = 0" действительно означает доступность средств связи, что обеспечивает вход в Область 1 или Область 2 (одного из процессов), или вход в Область 6 (интерпретатора сообщений после приема входящего сообщения, которое он ждет).
Вход в Области 1, 2 или 6 при условии "общпер = 0" сопровождается или присваиванием "общпер : = 1", или присваиванием "общпер := З"; таким образом, обеспечивается взаимное исключение Областей 1, 2 и 6.
Взаимное исключение означает, что процессам может быть запрещено немедленно войти в Область 1 или 2, или что входящее сообщение не может быть принято, если оно приходит в неподходящий момент. В первом случае процессы устанавливают "процпер := 1", а во втором случае (в Области 4) интерпретатор сообщения устанавливает "приоритет оператора := true".
Эти присваивания выполняются только при условии "общпер = 0"; кроме того, присваивание "общпер := 0", которое происходит исключительно в процедуре "выбрать новое значение для общпер" - выполняется только при условии "нет приоритета оператора и все процпер 1". Исходя из этих двух обстоятельств и принимая во внимание начальные значения переменных, мы можем заключить:
"общпер = 0" исключает "приоритет оператора = true" так же, как и выполнение хотя бы для одного из процессов "процпер = 1".
Так как во всех случаях освобождения средств связи (т. е. в конце Областей 1, 5 и 6) вызывается процедура "выбрать новое значение для общпер", то мы устанавливаем, что
а) вход в Области 1, 2 и 6 только временно задерживается, если это необходимо;
б) такая задержка обеспечивается до первой же ближайшей возможности ее устранения.
Структура интерпретатора сообщений отчетливо показывает, что:
а) он может выполнить Область 5 только при "общпер = 2";
б) он может выполнить только Область 5 при "общпер = 2";
в) выполнение Области 5 есть единственный путь сделать так, чтобы "общпер 2".
Единственное присваивание "общпер := 2" происходит в конце Области 2. В результате этого за каждой Областью 2 может следовать только Область 5 и обратно: каждой Области 5 должна предшествовать Область 2. Такая последовательность выполнения областей позволяет нам использовать передаточную переменную "номерпроц", значение которой устанавливается в Области 2 и используется в Области 5.
Подобный анализ можно провести и для передаточных переменных "ответоператора". За Областью 2 последует Область 5 (см. выше); если оказывается, что ответ оператора был окончательный (А1 или А2), то переменной "ответоператора[i]" присваивается подходящее значение, прежде чем выполнить "V(процсем[i])"; так что передаточная переменная устанавливается до того, как процесс сможет войти (и войдет) в Область 3, где проверяет свою переменную "ответоператора". Если в Области 5 обнаруживается, что ответ оператора был A3, то интерпретатор сообщений выполняет присваивание "процпер[i] := 2" для этого ("номерпроц") процесса, тем самым допуская когда-то в Области 6 лишь ответы А4 или А5 от оператора для этого ("заданный процесс") процесса. Снова "V(процсем[i])" выполняется только после присваивания соответствующего значения переменной "ответоператора". Итак мы убедились, что:
а) "ответоператора" устанавливается только один раз интерпретатором после запроса, выданного процессом в Области 2;
б) этот "ответоператора" будет проверен в следующей далее Области 3 только после того, как посланный запрос будет удовлетворен (в Области 5 или Области 6).
Этим завершается анализ правомочности использования передаточных переменных "ответоператора".
Изучение интерпретатора сообщений (в особенности схемы его состояний) показывает, что
а) не принятое сообщение (Область 4) рано или поздно обязано привести к входу в Область 6;
б) неправильные сообщения игнорируются, а оператору дается возможность исправить ошибку.
Я надеюсь, что приведенный анализ создал достаточную уверенность в корректности нашей конструкции. В процессе анализа мы проследили за теми стадиями, о которых уже упоминалось в п.5.2.1: после создания критических интервалов (с помощью "взаимискл") последние используются для организации надлежащего порядка следования областей, благодаря чему однозначным образом можно использовать передаточные переменные.
Типичное использование общего семафора
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-операций в потребителе существен.
Взаимодействие через переменные состояния
5. ВЗАИМОДЕЙСТВИЕ ЧЕРЕЗ ПЕРЕМЕННЫЕ СОСТОЯНИЯ
В ¬¬4.1 и 4.3 мы проиллюстрировали применение общего семафора. Это проверенное и удобное средство использовалось для реализации довольно примитивной формы взаимодействия. Правила работы потребителя были очень просты: есть что-нибудь на буфере - бери.
Если необходимо построить несколько взаимодействующих последовательных процессов так, чтобы их общее поведение удовлетворяло более сложным требованиям, и вся совокупность в целом работала в определенном смысле правильно, то следует ожидать, что достигнуть этого можно только в случае, когда и сами отдельные процессы и способы их взаимодействия будут более изощренными. Нельзя надеяться, что мы получим решение с помощью уже имеющихся и таких простых средств, как общий семафор. Нам может потребоваться вся гибкость, на которую способна программа универсальной вычислительной машины.
В нашем распоряжении имеется сейчас некоторый исходный материал: мы можем определять отдельные процессы; эти процессы могут связываться друг с другом через общие переменные; наконец, у нас есть средства синхронизации. Однако совершенно не очевидно, как всем этим пользоваться. Сейчас нам необходимо научиться применять этот материал, развить стиль "параллельного программирования". Нужно подчеркнуть два момента.
Во-первых, мы столкнемся с большой свободой выбора. При взаимодействии процессов могут возникать решения, которые касаются более чем одного процесса, и не всегда очевидно, какой из процессов должен принять то или иное решение. Если мы не сможем найти какой-то руководящий принцип (например, соображения эффективности), то нужно иметь смелость наложить ради определенности некоторые ограничения.
Во-вторых, если для нас представляют интерес реально работающие системы, то требуется убедиться (и убедить всех сомневающихся) в корректности наших построений. При не параллельном программировании программист уже сталкивается с задачей проверки программы (трудность этой задачи, кстати, часто недооценивают); но там он еще может надеяться отладить программу с помощью тестов. В нашем случае системе часто придется работать в невоспроизводимых обстоятельствах, и мы едва ли можем ожидать сколько-нибудь серьезной помощи от тестов. Поэтому вопросы проверки программы должны интересовать нас с самого начала.
Теперь мы приступим к более сложному примеру в надежде приобрести некоторый опыт, который можно будет использовать в качестве руководящего принципа.
Заключительные замечания
7. ЗАКЛЮЧИТЕЛЬНЫЕ ЗАМЕЧАНИЯ
В литературе иногда проводят отчетливое различие между "параллельным программированием" - обработка одного задания с помощью нескольких центральных процессоров - и "мультипрограммированием" - разделение времени центрального процессора между различными заданиями. Я всегда считал, что это различие довольно искусственное и поэтому способно подчас вызвать путаницу. С общей точки зрения мы имеем в обоих случаях несколько последовательных процессов, которые должны взаимодействовать друг с другом, и наши обсуждения такого взаимодействия в равной степени относятся как к "параллельному программированию", так и к "мультипрограммированию", а также и к любой их комбинации. Если в параллельном программировании речь идет о распределении оборудования, то в мультипрограммировании - о распределении времени; и то и другое - различные реализации одной логической структуры, и я считаю, что развитие средств для описания и построения таких структур само по себе, т.е. независимо от различий в реализации, является одним из основных результатов работы, на основе которой возникла эта глава. В качестве конкретного примера такой унификации взгляда на вещи мне хотелось бы упомянуть о полной симметрии между обычной последовательной вычислительной машиной, с одной стороны, и ее периферийным устройством - с другой (что отражено, например, в ¬4.3 "Ограниченный буфер").
Наконец, я хочу еще раз выразить свое отношение к вопросу о корректности программ, так как не очень уверен, что все оказанное об этом ранее прозвучало достаточно ясно и убедительно.
Если я предлагаю методы, с помощью которых мы могли бы достигнуть большей уверенности в правильности наших построений, то это, конечно, скорее психология, чем математика. Я чувствую, что человеческий разум чрезвычайно неприспособлен мыслить в категориях развивающегося во времени процесса, и в этом случае нашим сильнейшим средством для оперирования этими понятиями является придание определенного смысла значениям соответствующих величин.
Например, глядя на программу:
i := 10; LO: x := sqrt(x); i := i - 1; if i > 0 then goto L0
мы заключаем, что операция "x := sqrt(x)" повторяется десять раз, и у меня создается впечатление, что мы делаем такое заключение, придавая "i" следующий смысл: число раз, которое еще должна быть повторена операция "x := sqrt(x)". Но нам следует сознавать, что такая, не связанная с временем трактовка, не является постоянно верной при течении процесса: немедленно за выполнением "x := sqrt(x)", но еще до выполнения следующего оператора "i := i - 1" значение "i" на единицу больше того числа раз, какое еще должна быть повторена операция "x := sqrt(x)". Иначе говоря, мы должны указать, на каких стадиях протекания процесса такой смысл применим, и, конечно, он должен иметь силу в каждой ситуации, где мы полагаемся на этот смысл в рассуждениях, убеждающих нас в том, что программа в целом выполняется желаемым образом.
При полностью последовательном программировании, как в приведенном примере, области применения такого смысла обычно тесно связаны с определенными местами в тексте программы (если это не так, то мы просто имеем мудреную и беспорядочно составленную программу). При параллельном программировании мы видели, в частности в п.5.2.1, что сознательное построение таких "областей применимости смысла" является стоящим делом. Признание иерархического различия между наличием сообщения и самим сообщением, что здесь было вынужденным делом, может служить средством более ясного понимания даже при не параллельном программировании.
Например, если я женат на одной из десяти женщин, пронумерованных от 1 до 10, то этот факт можно представить значением связанной со мной переменной "номер женщины". Если же я холост, то обычным программистским приемом было бы представление статуса холостяка одиннадцатым значением той же переменной, скажем "номер женщины = 0". Смысл значения этой переменной теперь таков: "Если номер моей жены равен 0, то я холост; если он отличен от нуля, то указывает номер моей жены".
Вывод таков, что введение отдельной булевой переменной "женат" может быть более правильным.
Мы знаем, что сила и гибкость машин фон Неймана основана на том, что они трактуют все слова в машине одинаковым образом. Часто еще недопонимается, что вследствие этого пользователю приходится строить такую структуру, которая всегда должна быть распознаваемой.
Обычно в качестве обоснования достоинств машин фон Неймана называют то, что они могут изменять собственные команды; однако большинство современных алгоритмических трансляторов строят объектные программы, которые во все время выполнения остаются так же неизменны, как и первоначальный текст. Вместо хаотической модификации своих собственных команд до или после их выполнения создание и выполнение этих команд происходит в различные последовательные стадии: фаза трансляции и фаза выполнения. И это всем нам на пользу.
Я твердо убежден, что в каждом процессе любой сложности встречающиеся переменные допускают аналогичное иерархическое упорядочивание и что если эти уровни иерархии легко распознаются в тексте программы, то выигрыш в наглядности программы и в эффективности реализации будет значительным. Отмечу еще, что если из этой главы читатель получил более ясное представление о том, какой признак упорядоченности является в том или ином случае наиболее подходящим, то я достиг одной из своих целей. И, кроме того, разве мы не можем надеяться, что сопоставление со сложностями Мультипрограммирования даст нам более ясное понимание о не параллельном программировании как таковом?
Программа для отдельного процесса начинается
Замечание
. Программа для отдельного процесса начинается с описания "integer j". В соответствии с правилами АЛГОЛа это означает, что каждый процесс вводит свою индивидуальную целочисленную переменную "j" (так называемую локальную величину).
Доказательство мы предоставляем читателю. Снова необходимо показать:
в любой момент самое большее один процесс находится в своем критическом интервале; решение о том, какому из процессов первым войти в свои критический интервал, не может откладываться до бесконечности; остановка процесса в "остатке цикла" не влияет на другие процессы.
Доказательство второго утверждения наиболее трудно. {Краткое указание. Как только один из процессов выполнил присваивание "очередь := i", никакой другой процесс не может принять решение о присваивании своего номера переменной "очередь", прежде чем завершится критический интервал. Помните, что два процесса могут "одновременно" решить присвоить значение своего номера переменной "очередь"!)
(Замечание, которое может быть пропущено при первом чтении.) Только что приведенная программа проверяет значение "b[очередь]" в условиях, когда массив "b" и переменная "очередь" размещаются в общей памяти. Мы договорились, что проверка значения одной переменной есть неделимое действие, и поэтому проверка переменной с индексами "b[очередь]" может означать единственно следующее: проверяется значение переменной "очередь", и если оно оказывается равным "5", то проверяется "b[5]". Или более точно в алгольной записи:
процесс i: begin integer j, k; . . . k := очередь; if b[k] = 1 then. . .
подразумевая, что за время, пока проверяется "b[k]", "очередь" может уже получить значение, отличное от текущего значения "k". Без сформулированных выше правил обращения к переменной с индексами в общей памяти другой допустимой интерпретацией для "значение b[очередь]" было бы: "значение элемента массива b, определенного текущим значением очереди". При так называемом не параллельном программировании, т. е. когда единственный последовательный процесс оперирует с величинами, локализованными в нем, две интерпретации эквивалентны. При параллельном программировании, когда другие активные процессы могут иметь доступ к общей информации и изменять ее, эти две интерпретации становятся совершенно различными! Для читателя, имеющего опыт главным образом в не параллельном программировании, это замечание включено как пример тонкостей, с которыми приходится здесь иметь дело.
begin integer array желание, семафор производителя[1 : Nl; integer число порций в буфере, число свободных единиц буфера, блокировка буфера, работбуф, цикл; for цикл := 1 step 1 until N do
begin желание[цикл] := 0; семафор производителя[цикл] := 0 end; число порций в буфере := 0; число свободных единиц буфера := Размер буфера; блокировка буфера := 0; работбуф := 1; parbegin
производитель 1: begin ............ end; . . . производитель n; begin integer размер порции; снова n: производство новой порции и установка размера порции; Р(работбуф); if блокировка буфера = 0 and
число свободных единиц буфера размер порции then
число свободных единиц буфера := число свободных единиц буфера - размер порции else
begin блокировка буфера := блокировка буфера + 1; желание[n] := размер порции; V(работбуф); Р(семафор производителяЫ); Р(работбуф) end; добавление порции к буферу; V(работбуф); V(число порций в буфере); goto снова n end; производитель N: begin ........... end; потребитель 1: begin ........... end; . . . потребитель m: begin integer размер порции, n, max, nmax; снова m: Р(число порций в буфере); Р(работбуф); взятие порции из буфера и установка размера порции; число свободных единиц буфера := число свободных единиц буфера + размер порции; проверка: if блокировка буфера > 0 then
begin шах := 0; for n := 1 step until N do
begin if max < желание[n] then
begin шах := желание[n]; пшах:= n end
end; if max число свободных единиц буфера then begin число свободных единиц буфера:= число свободных единиц буфера - max; желание[nmax] := 0; блокировка буфера := блокировка буфера - 1; V(семафор производителя [nmax]); goto проверка end
end; V(работбуф); обработка взятой порции; goto снова m end; . . . потребитель M: begin .............. end
parend
end
В самом внешнем блоке описываются общие переменные и там же им присваиваются начальные значения; надеюсь, что эта часть программы не вызовет трудностей у читателей, которые разобрались во всем предыдущем изложении.
Давайте сначала попытаемся понять поведение производителя. Когда он хочет добавить новую порцию к буферу, возможны два случая: или это можно сделать немедленно, или нет. Немедленное добавление порции возможно при следующем комбинированном условии:
блокировка буфера = 0 and число свободных единиц буфера размер порции
Если условие удовлетворяется, то производитель уменьшает "число свободных единиц буфера" и, - оставаясь динамически в том же критическом интервале, - добавляет порцию к буферу. Две следующие V-операции (порядок которых безразличен) завершают Критический интервал и извещают потребителей о существовании следующей порции. Если добавление порции нельзя осуществить немедленно, т.е. если
блокировка буфера > 0 or число свободных единиц буфера < размер порции
(или оба эти условия удовлетворяются одновременно), то производитель переходит в состояние ожидания, "приостанавливается", поручая потребителям запустить его снова в подходящее время. Факт ожидания для данного производителя выражается соотношением "желание[n] > 0", и соответственно "блокировка буфера" увеличивается на единицу. После того как выполнены все необходимые операции над общими переменными, критический интервал заканчивается (с помощью "V(работбуф)") и производитель инициирует P-операцию над своим частным семафором. Как только эта P-операция завершается, производитель снова входит в критический интервал, динамически сливающийся с критическим интервалом первого случая (немедленное добавление порции), и добавляет порцию к буферу. (Вспомните также потребителя во второй программе из ¬4.2, в которой мы уже встречались с прерывающимся открыванием критического интервала.) Отметим, что в рассматриваемом случае ожидания производитель пропускает уменьшение "числа свободных единиц буфера". Заметим также, что производитель начинает P-операцию над своим частным семафором в момент, когда тот уже мог быть установлен в "1", т.е.
опять P- операция является лишь потенциальной задержкой. Теперь рассмотрим, выполняют ли потребители возложенные на них задачи. Присутствие следующей порции становится им известно через общий семафор "число порций в буфере", а так как P-операция над ним происходит вне критического интервала, то нет опасений, что потребители не начнут ее выполнение. После этой P-операции потребитель входит в критический интервал, берет порцию и увеличивает "число свободных единиц буфера".
Если "блокировка буфера = 0", то следующий составной оператор целиком пропускается, и критический интервал немедленно заканчивается. Так и должно быть, так как соотношение "блокировка буфера = 0" означает, что ни одна из величин "желание" не положительна, т. е. ни один из производителей не ждет только что освободившегося места в буфере. Если, однако, потребитель обнаруживает, что "блокировка буфера > 0", то ему ясно, что по меньшей мере один из производителей приостановил выполнение, и тогда он определяет, можно ли запустить каких-либо производителей. Потребитель отыскивает максимальное значение переменной "желание". Если оно не слишком велико (свободного места в буфере достаточно), то он решает, что соответствующий производитель должен продолжить работу. Это решение приводит к следующим трем действиям:
а) "Число свободных единиц буфера" уменьшается на число единиц, требуемых данному производителю. Поэтому мы гарантированы от того, что одно и то же свободное место буфера будет предоставлено более чем одному производителю. Кроме того, это уменьшение соответствует требованию производителя.
б) "желание" производителя, о котором идет речь, устанавливается в нуль; это справедливо, поскольку его требование удовлетворено; соответственно и "блокировка буфера" уменьшается на единицу.
в) V-операция над семафором рассматриваемого производителя позволяет последнему продолжить работу.
После этого управление возвращается по метке "проверка" для того, чтобы выяснить, нельзя ли запустить и других приостановленных производителей. Этот процесс выяснения заканчивается одним из двух способов: или не остается больше приостановленных производителей ("блокировка буфера = 0"), или такие производители есть, но свободного места на буфере недостаточно для размещения максимальной предложенной порции информации. Окончательное значение переменной "блокировка буфера" в обоих случаях правильное. После запуска соответствующих производителей, критический интервал потребителя завершается.
доступность средств связи для M-сообщений, Ql-вопросов и спонтанных сообщений оператора; приемлемость ( более общо: интерпретируемость) поступающих от оператора сообщений; приоритет оператора при передаче сообщений.
Для того чтобы сразу не усложнять вопрос, мы начнем рассмотрение, игнорируя третий пункт. Без него можно определить следующие состояния.
общпер = 0
"Средства связи свободны", т.е. в равной мере доступны и для процессов, и для оператора. Для процессов соотношение "общпер = 0" означает доступность средств связи, для интерпретатора . сообщений это означает, что входящие сообщения нельзя игнорировать, но они обязательно должны быть одного из типов: "А4", "А5" или "А6".
общпер = 1
"Средства связи используются для передачи М-сообщения или Q1-вопроса". В этот промежуток времени значение переменной "общпер" должно быть " 0", так как средства связи недоступны процессам; для интерпретатора сообщений это означает, что входящие сообщения должны игнорироваться.
общпер = 2
"Средства связи зарезервированы для Al-, A2- или АЗ-ответа". После завершения передачи М-сообщения средства связи снова становятся общедоступными; однако после Ql-вопроса они должны остаться зарезервированными. В течение этого промежутка времени, характеризуемого соотношением "общпер = 2", интерпретатор сообщений обязан знать, какому процессу предназначается ответ оператора. По окончании ответа средства связи снова становятся общедоступными.
Теперь примем во внимание третье требование. Это приведет к размножению некоторых состояний. Если "общпер = 0", то входящее сообщение принимается; если "общпер = 1", то входящее сообщение должно игнорироваться. Этот случай должен быть специально выделен, поскольку после освобождения средств связи оператор, имея высший приоритет, должен получить возможность выдать сообщение.
Мы можем ввести новое состояние.
общпер = 3
"Как и в случае "общпер = 1", но с запросом оператора".
Если переход в состояние "общпер = З" происходит при передаче М-сообщения, оператор получает возможность выдать сообщение немедленно по окончании передачи. Если, однако, переход в состояние "общпер = З" произошел при передаче Ql-вопроса, то средства связи могут быть предоставлены оператору только после его ответа на Ql-вопрос.
Поэтому размножается также и состояние 2.
общпер = 4
"Как и в случае "общпер = 2", но с запросом оператора".
Наконец, имеем еще одно состояние.
общпер = 5
"Средства связи зарезервированы или используются для передачи отложенных ответов оператора". Для процессов это означает недоступность средств связи, для интерпретатора сообщений - приемлемость входящих сообщений типа "А4", "А5" и "А6".
Обычно требование оператора на передачу этих сообщений объявляется интерпретатору сообщений при "общпер = 0". Если мы не хотим, чтобы ожидание передачи и интерпретация этих сообщений происходили внутри того же самого критического интервала, то интерпретатор сообщений может прервать его. Во всех случаях необходимо, чтобы значение "общпер" было отлично от "0". Мы можем попытаться использовать для этих целей то же значение "5": для процессов это просто означает недоступность средств связи, в то время как управление интерпретатором сообщений точно знает, ожидает ли он отложенное сообщение оператора или интерпретирует такое сообщение.
Прежде чем начать составление программы, мы должны вспомнить пункт в): средства связи нужны всем процессам и являются узким местом системы, поэтому мы должны заботиться о том, чтобы каждый процесс, освободивший средства связи, принял решение об их будущем использовании. Это происходит в процессах по окончании передачи М-сообщения (в меньшей степени по окончании Ql-вопроса, так как средства связи остаются зарезервированными для ответа), а в интерпретаторе сообщений - по окончании интерпретации сообщения оператора.
Доказательство существования пудинга мы получаем, когда едим его: так давайте попытаемся написать программу, чтобы удостовериться, что все необходимые средства введены. (В программе последовательность символов, начинающаяся со слова "comment", и кончающаяся первой же точкой с запятой (включая ее) служит исключительно для пояснений. В АЛГОЛе такие пояснения допускаются только сразу же за "begin", но я не обещаю следовать этому (излишнему) ограничению. Предполагается, что следующая ниже программа содержится в большей программе, в которой описаны оператор, средства связи и семафор "входящее сообщение", первоначально равный "0".)
begin integer взаимискл, общпер, номерпроц, цикл; comment Целая переменная "номерпроц" является переменной состояния для интерпретатора сообщений и используется, главным образом, при интерпретации ответов Al, A2 и A3. Это - общая переменная, так как ее значение устанавливается процессом, задающим вопрос; integer array процпер, процсем[1 : N]; for цикл := 1 step 1 until N do
begin процпер[цикл] := 0; процсем[цикл] := 0 end; общпер := 0; взаимискл := 1; parbegin
процесс 1: begin. ........... end; . . . процесс n: begin integer i; comment Целочисленная переменная "i" является локальной переменной, очень похожей по использованию на переменную "цикл"; . . . М сообщение: Р (взаимискл); if общпер = 0 then
begin comment Если средства связи свободны, они используются; общпер := 1; V(взаимскл) end; else
begin comment В противном случае процесс объявляет себя задержанным и приостанавливается; процпер[n] := 1; V(взаимискл); Р(процсем[n]); comment После завершения этой Р-операции "процпер[n]" окажется опять установленной в "0", но "общпер" будет равна "1" или "З"; end; посылка М-сообщения; comment Теперь процесс должен проанализировать, должен ли оператор (первым) или один из других процессов получить средства связи; Р(взаимискл); if общпер = 3 then общпер := 5 else
begin comment В противном случае выполняется "общпер = 1", и процесс "n" должен посмотреть, ожидает ли один из других процессов. Заметим, что"процпер[n] = 0"; for i := 1 step 1 until N do
begin if процпер[i] = 1 then
begin процпер[i] := 0; V(процсем[i]); goto готов end
end; общпер := 0 end; готов: V(взаимискл); . . . Q1 вопрос: Р(взаимискл); if общпер = 0 then
begin общпер := 1; V(взаимискл) end
else
begin процпер[n] := 1; V(взаимискл); Р(процсем[n]) end; comment Это все идентично М-сообщению. Заметим, что мы находимся вне критического интервала, тем не менее, этот процесс установит "номерпроц". Это можно делать свободно, так как никакой другой процесс, ни интерпретатор сообщений не получит доступ к "номерпроп", пока выполняется "общпер = 1"; номерпроц := n; посылка Ql(n)-вonpoca; Р(взаимискл);
comment "общпер" в этот момент равна "1" или "З"; if общпер = 1 then общпер := 2 else общпер := 4; М(взаимискл); Р(процсем[тъ); comment После завершения этой Р-операции,. "процпер[т]" будет равна "З" или "4". Этот процесс может теперь исследовать и сбросить в "0" свою "процпер", хотя мы находимся вне критического интервала; if процпер[n] = 3 then Реакция 1 else Реакция 2; процпер[n] := 0; comment Это последнее присваивание избыточно; . . . end процесса n; . . . процесс N: begin ............ end; интерпретатор сообщений: begin integer i; ждать: Р(входящее сообщение); Р(взаимискл); if общпер = 1 then общпер := 3; if общпер = 3 then
begin comment Интерпретатор сообщений игнорирует входящее сообщение, но в надлежащий момент оператор получит возможность передать сообщение; V(взаимискл); goto ждать end; if общпер = 2 or общпер = 4 then
begin comment Допустимы только сообщения Al, A2 или A3. Интерпретацию сообщения не обязательно производить внутри критического интервала; V(взаимискл); интерпретация входящего сообщения; if сообщение = Al then
begin процпер[номерпроц] := 3; V(процсем[номерпроц]); goto после правильного ответа end; if сообщение = A2 then
begin процпер[номерпроц] :=4; V(процсем[номерпроц]); goto после правильного ответа end; if сообщение = A3 then
begin процпер [номерпроц] := 2; goto после правильного ответа end; comment Оператор дал неправильный ответ и должен повторить сообщение; goto ждать; после правильного ответа: Р(взаимискл); if общпер = 4 then
begin comment Теперь оператор должен получить возможность передачи своего сообщения; общпер := 5; V(взаимискл); goto ждать end; возможная установка в 0 общпер: for i := 1 step 1 until N do
begin if процпер[i] = 1 then
begin проппер[i] := 0; общпер := 1; V(процсем[i]); goto готов end; end; общпер := 0; готов: V(взаимискл); goto ждать end; comment Остаются случаи "общпер = o" и "общпер = 5". Допустимы сообщения А4, А5 и А6; if общпер = 0 then общпер := 5; comment Смотри Замечание 1 после программы;
V(взаимискл); интерпретация входящего сообщения; Р(взаимискл); if сообщение = А4 (заданный процесс) then
begin i := "номер процесса, заданный в сообщении"; if процпер[i] = 2 then
begin процпер[i] := 3; V(процсем[i]); goto возможная установка в 0 общпер; end; comment В противном случае процесс не ожидает отложенного ответа; goto неправильное сообщение end; if сообщение = А5 (заданный процесс) then
begin i := "номер процесса, заданный в сообщении"; if процпер[i] = 2 then
begin процпер[i] := 4; V(процсем[i]); goto возможная установка в 0 общпер; end; comment В противном случае процесс не ожидает отложенного ответа; goto неправильное сообщение end; if сообщение = А6 then
goto возможная установка в 0 общпер;
неправильное сообщение: comment Сохраняется "общпер = 5", давая оператору приоритетную возможность повторить сообщение; V(взаимискл); goto ждать end интерпретатора сообщений; parend
end
Если оператор при "общпер = 0"
Замечание 1. Если оператор при "общпер = 0" или "общпер = 5" выдает не интерпретируемое (или неподходящее) сообщение, то средства связи остаются зарезервированными для его следующей попытки.
в программе сканируют процессы по
Замечание 3
. Циклы for в программе сканируют процессы по порядку, начиная с процесса 1; при циклическом просматривании процессов, начиная с произвольно выбранного процесса (например, с помощью генератора псевдослучайных чисел), мы могли бы получить более симметричное решение для N процессов.