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

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-операциями над новым двоичным семафором "задержка потребителя".

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

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

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

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

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

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

Пример с диалогами

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

(предполагается, что вся память составляет 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" означает одновременно "очередь

Синхронизирующие примитивы

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

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

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".

Эти присваивания выполняются только при условии "общпер =

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 число свободных единиц буфера

Если оператор при "общпер = 0"

Замечание 1. Если оператор при "общпер = 0" или "общпер = 5" выдает не интерпретируемое (или неподходящее) сообщение, то средства связи остаются зарезервированными для его следующей попытки.

в программе сканируют процессы по

Замечание 3

. Циклы for в программе сканируют процессы по порядку, начиная с процесса 1; при циклическом просматривании процессов, начиная с произвольно выбранного процесса (например, с помощью генератора псевдослучайных чисел), мы могли бы получить более симметричное решение для N процессов.