18c0693f

Заметки о программировании

Алгоритм банкира

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" критический интервал потребителя динамически распадается на две части: это исключительно важно, так как иначе производитель никогда не получит возможность добавить новую порцию, которую уже ждет потребитель.



    (Только что приведенная программа известна под названием "Спящий парикмахер". Имеется парикмахерская с отдельной комнатой ожидания. Входная дверь в комнату ожидания расположена рядом с дверью в комнату, где находится кресло парикмахера. Вход и выход прикрываются одной и той же скользящей дверью, так что или вход, или выход закрыт. Кроме того, вход настолько узок, что посетители могут входить только по одному, тем самым фиксируется очередность входа. Взаимные исключения поэтому обеспечиваются.





    Когда парикмахер заканчивает обслуживание, он открывает дверь в комнату ожидания и осматривает ее. Если комната не пуста, то он приглашает следующего посетителя, в противном случае он устраивается спать в одном из кресел комнаты ожидания. Поведение посетителей определяется следующим образом: если они видят "нуль или более" посетителей в комнате ожидания, то ждут своей очереди; если они видят спящего парикмахера, - "числопорцбуф = -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

    Пример приоритетного правила

    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);

    б) может обнаружить по реакции машины, принято его вмешательство или отвергнуто.

    В приведенной программе использована последовательность

    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

    Проблема тупиков

    6. ПРОБЛЕМА ТУПИКОВ

    Во вводной части этого раздела мы остановимся на логической задаче, которая возникает при взаимодействии различных процессов, когда они должны делить одни и те же ресурсы. Эта проблема выбрана по разным причинам. Во-первых, она является непосредственным обобщением известной ситуации, согласно которой два человека не могут воспользоваться одновременно одной секцией вращающейся двери. Во-вторых, решение этой проблемы, которое я считаю нетривиальным и которое будет приведено в ¬6.1, дает нам хороший пример более тонких правил взаимодействия, чем те, с которыми мы до сих пор встречались. В-третьих, она предоставляет нам возможность проиллюстрировать (в ¬6.2) методы программирования, с помощью которых может быть достигнут дальнейший прогресс в наглядности представления. Для начала я приведу один пример разделения ресурсов. В качестве "процессов" мы можем принять "программы", описывающие некоторый вычислительный процесс, выполняемый вычислительной машиной. Выполнение такого вычислительного процесса требует определенного времени, в течение которого в памяти вычислительной машины хранится информация. Ограничимся процессами, о которых заранее известно следующее:
  • Их требования к объему памяти не будут превышать определенного предела.
  • Каждый вычислительный процесс завершится при условии, что требуемый процессу объем памяти будет предоставлен в его распоряжение. Завершение вычислительного процесса будет означать, что его требования к памяти уменьшились до нуля.
    Предполагаем, что имеющаяся память поделена на "страницы" фиксированного размера, которые с точки зрения программы считаются эквивалентными.
    Фактическое требование нужного процессу объема памяти может быть функцией, изменяющейся по мере протекания процесса, но, конечно, в соответствии с заранее заданной верхней границей. Предположим, что отдельные процессы запрашивают и возвращают память единицами в одну страницу. "Эквивалентность" (см. последнее слово предыдущего абзаца) означает, что процесс, запрашивающий новую страницу, просит просто "новую страницу", но никогда не специальную страницу или страницу из специальной группы.

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

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

    Если, однако, вычислительная машина обслуживает одновременно более одного процесса, то можно придерживаться правила, что допускаются только такие программы, у которых сумма их максимальных требований не превышает общей емкости памяти. Это правило, хотя и обеспечивает безопасность, является излишне ограничивающим, так как предполагает, что каждый процесс действительно занимает максимальную память во все время выполнения. Если мы посмотрим на следующую таблицу (где процессы "заимствуют" страницы из имеющейся памяти)

    Процесс Максимальное
    требование    		 Настоящий
    объем    		 Дальнейшее
    требование
    П1

    П2    		 80

    60    		 40
    +
    20    		 40

    40
    Свободная память = 100 - 60 = 40
    (предполагается, что вся память составляет 100 страниц), то увидим, что в этой ситуации еще нет ничего страшного.

    Если бы, однако, оба процесса затребовали теперь по следующей странице, и получили бы ее, то сложилась бы такая ситуация:

    Процесс Максимальное
    требование    		 Настоящий
    объем    		 Дальнейшее
    требование
    П1

    П2    		 80

    60    		 41
    +
    21    		 39

    39
    Свободная память = 100 - 62 = 38
    Эта ситуация опасная, так как оба процесса могут пожелать полностью затребовать свой допустимый объем памяти, не возвращая ни одной страницы. Так, каждый из них может нуждаться в следующих 39 страницах, в то время как их осталось только 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.
    Выход из Области 1 можно изобразить так:





    Рис.9.
    Выход из Области 2, с возможностью задержки ответа, можно изобразить так:





    Рис.10.




    Рис.11.
    Можно попытаться сделать то же самое для интерпретатора сообщений. В диаграмме на рис.11 вдоль стрелок показаны соответствующие обстоятельства, сопровождающие переход в другое состояние, такие, как изменения "процпер" и вид сообщения. Сокращение ОВС означает "Ожидание Входящего Сообщения".


    Конечно, эти диаграммы ничего нового нам не говорят, но они могут оказаться мощным средством при проверке программ.

    Сначала мы убеждаемся, что "общпер = 0" действительно означает доступность средств связи, что обеспечивает вход в Область 1 или Область 2 (одного из процессов), или вход в Область 6 (интерпретатора сообщений после приема входящего сообщения, которое он ждет).

    Вход в Области 1, 2 или 6 при условии "общпер = 0" сопровождается или присваиванием "общпер : = 1", или присваиванием "общпер := З"; таким образом, обеспечивается взаимное исключение Областей 1, 2 и 6.

    Взаимное исключение означает, что процессам может быть запрещено немедленно войти в Область 1 или 2, или что входящее сообщение не может быть принято, если оно приходит в неподходящий момент. В первом случае процессы устанавливают "процпер := 1", а во втором случае (в Области 4) интерпретатор сообщения устанавливает "приоритет оператора := true".