5.1. Пример приоритетного правила
В ╖4.3 мы использовали общий семафор для организации взаимодействия производителя и потребителя через ограниченный буфер. Предложенное решение легко обобщается на большее число производителей и (или) потребителей; оно применимо в случае, когда "порция" на буфере является к тому же и удобной единицей информации, т. е. когда можно считать, что все порции одинакового размера.
В настоящей задаче мы рассмотрим производителей, которые выдают порции различного размера, и предположим, что размер каждой из этих порций выражается в некоторых единицах. Потребители опять будут обрабатывать последовательные порции из буфера, а потому должны уметь обрабатывать порции, размер которых заранее не задан. Максимальный размер порции пусть будет, однако, известен.
Итак, размер порции задается в единицах информации; предполагаем также, что в единицах информации определяется и максимальная емкость буфера. Тогда вопрос о том, можно ли разместить на буфере очередную выработанную порцию, зависит от размера этой порции. Требования осуществимости операций "добавление порции к буферу" и "взятие порции из буфера" означают, что размер буфера не меньше размера максимальной порции.
Наш буфер ограничен, и поэтому может оказаться, что производитель должен ждать, пока он сможет поместить в буфер созданную порцию. При порциях фиксированного размера это случалось только тогда, когда буфер был полон; теперь это может происходить из-за того, что имеющегося на буфере свободного места недостаточно для размещения данной порции.
Кроме того, если имеется более одного производителя и какой-то из них ждет из-за отсутствия достаточного места на буфере, то другие производители вполне могут продолжать работу и достигнуть точки, когда они желают выдать выработанную порцию. Предлагаемая порция от нового производителя также может быть слишком велика, но она может быть и достаточно мала, чтобы поместиться на свободном месте буфера. Мы наложим на искомое решение требование, до некоторой степени произвольное, о том, что производитель, предлагающий большую порцию, получает приоритет над производителем, предлагающим меньшую порцию. (Когда два или больше производителей предлагают порции одинакового размера, нам безразлично, кто добавит порцию к буферу.)
Если какой-то производитель находится в состоянии ожидания, потому что его порцию нельзя разместить на буфере, то никакой другой производитель не сможет добавить свою порцию к буферу впредь до момента появления дополнительного свободного места: во-первых, другой производитель не сможет сделать это у если его порция больше (так как ее негде поместить); во-вторых, - ему не разрешено это делать, если его порция меньше, так как тогда он имеет более низкий приоритет и должен уступить буфер предыдущему запросу.
Рассмотрим момент, когда буфер полностью заполнен, и три производителя ожидают возможности добавить порции размером 1, 2 и 3 соответственно. Если теперь потребитель обработает порцию в пять единиц, то правило приоритетов будет означать, что получат возможность продолжать работу производители с порциями в 3 и 2 единицы, а не производитель с порцией в 1 единицу. Но это не означает, что в данном случае порция в 3 единицы будет действительно выдана раньше порции в 2 единицы.
Сейчас мы попытаемся ввести так называемые "переменные состояния" для различных элементов системы, с помощью которых мы сможем описывать состояния системы в любой момент времени.
Для каждого производителя вводим переменную с именем "желание"; эта переменная будет обозначать число единиц буфера, необходимых для размещения порции, которая не могла быть добавлена к буферу. Так как значение этой переменной всегда есть положительное число, мы можем придать соотношению "желание = 0" тот смысл, что у данного производителя нет неудовлетворенного требования на добавление порции. Кроме того, для каждого производителя введем двоичный "семафор производителя".
Для буфера мы вводим двоичный семафор "работбуф" - работа с буфером, который предназначается для взаимного исключения действий с буфером в широком смысле (т. е. не только добавление и взятие порций из буфера, но также проверка и модификация связанных с буфером переменных состояния).
Далее, мы нуждаемся в механизме сигнализации потребителям о появлении следующей порции. Как только в буфер добавлена новая порция, она может быть обработана; и поскольку нам безразлично, какой из потребителей возьмет ее, то для этого можно воспользоваться общим семафором "число порций в буфере". (Отметим, что он указывает число порций, а не число заполненных единиц информации в буфере.)
Об освобождении областей буфера необходимо сообщать производителям, но возможные последствия освобождения областей буфера вызывают более сложные решения, и нельзя ожидать, что общий семафор будет здесь подходящим средством. Попробуем ввести для этих целей целочисленную переменную состояния "число свободных единиц буфера". Отметим, что эта переменная отсчитывает единицы информации, а не порции.
Замечание. Значение переменной "число свободных единиц буфера" почти всегда будет равно размеру буфера, уменьшенному на суммарный размер порций, подсчитанных в "числе порций в буфере", но оно может быть и меньше! Я отсылаю читателя к программе из ╖4.3; там сумма
"число порций в буфере + число пустых позиций"первоначально (и обычно) равняется N, но она может быть равна и N - 1, потому что P-операция над одним из семафоров всегда предшествует V-операции над другим семафором. (Проверьте, что эта сумма может быть равна даже N - 2, и что она могла быть еще меньше, если бы мы имели больше производителей и (или) потребителей.) Здесь можно ожидать похожее явление: семафор "число порций в буфере" будет подсчитывать порции буфера, действительно заполненные и еще не замеченные потребителями; переменная "число свободных единиц буфера" будет подсчитывать полностью свободные, не распределенные производителям единицы в буфере. Но те единицы, которые зарезервированы для заполнения, предоставлены (ожидающему) производителю, но еще не заполнены, не будут учитываться ни одной из переменных.
Наконец, мы введем целочисленную переменную "блокировка буфера", значение которой равно числу положительных (строго больших нуля) величин "желание". Очевидно, что эта переменная является избыточной; она введена для более удобного распознавания рассмотренной несколько ранее ситуации: как только одна из переменных "желание" станет положительной, никакие добавления к буферу производиться не могут до "специального уведомления" (появление дополнительного свободного места в буфере). Одновременно эта переменная играет роль предупреждения потребителям, что такое "специальное уведомление" необходимо.
Предлагается следующая программа, составленная для N производителей и М потребителей ("N", "М", "Размер буфера" и все остальное, что касается буфера, предполагается описанным и определенным во внешних по отношению к данной программе блоках).
begin integer array желание, семафор производителя[1 : Nl;
integer число порций в буфере, число свободных единиц буфера,
блокировка буфера, работбуф, цикл;
for цикл := 1 step 1 until N do
begin желание[цикл] := 0;
семафор производителя[цикл] := 0
end;
число порций в буфере := 0;
число свободных единиц буфера := Размер буфера;
блокировка буфера := 0; работбуф := 1;
parbegin
производитель 1: begin ............ end;
.
.
.
производитель n; begin integer размер порции;
снова n: производство новой порции и
установка размера порции;
Р(работбуф);
if блокировка буфера = 0 and
число свободных единиц буфера 
размер порции
then
число свободных единиц буфера :=
число свободных единиц буфера - размер порции
else
begin блокировка буфера := блокировка буфера + 1;
желание[n] := размер порции;
V(работбуф);
Р(семафор производителяЫ);
Р(работбуф)
end;
добавление порции к буферу;
V(работбуф); V(число порций в буфере);
goto снова n
end;
производитель N: begin ........... end;
потребитель 1: begin ........... end;
.
.
.
потребитель m: begin integer размер порции, n, max, nmax;
снова m: Р(число порций в буфере);
Р(работбуф);
взятие порции из буфера и установка размера порции;
число свободных единиц буфера :=
число свободных единиц буфера + размер порции;
проверка: if блокировка буфера > 0 then
begin шах := 0;
for n := 1 step until N do
begin if max < желание[n] then
begin шах := желание[n]; пшах:= n end
end;
if max 
число свободных единиц буфера then
begin
число свободных единиц буфера:=
число свободных единиц буфера - max;
желание[nmax] := 0;
блокировка буфера := блокировка буфера - 1;
V(семафор производителя [nmax]);
goto проверка
end
end;
V(работбуф);
обработка взятой порции;
goto снова m
end;
.
.
.
потребитель M: begin .............. end
parend
end
В самом внешнем блоке описываются общие переменные и там же им присваиваются начальные значения; надеюсь, что эта часть программы не вызовет трудностей у читателей, которые разобрались во всем предыдущем изложении.
Давайте сначала попытаемся понять поведение производителя. Когда он хочет добавить новую порцию к буферу, возможны два случая: или это можно сделать немедленно, или нет. Немедленное добавление порции возможно при следующем комбинированном условии:
блокировка буфера = 0 and
число свободных единиц буфера размер порции
Если условие удовлетворяется, то производитель уменьшает "число свободных единиц буфера" и, - оставаясь динамически в том же критическом интервале, - добавляет порцию к буферу. Две следующие V-операции (порядок которых безразличен) завершают Критический интервал и извещают потребителей о существовании следующей порции. Если добавление порции нельзя осуществить немедленно, т.е. если
блокировка буфера > 0 or
число свободных единиц буфера < размер порции
(или оба эти условия удовлетворяются одновременно), то
производитель переходит в состояние ожидания, "приостанавливается", поручая
потребителям запустить его снова в подходящее время. Факт ожидания для данного
производителя выражается соотношением "желание[n] > 0", и
соответственно "блокировка буфера" увеличивается на единицу. После
того как выполнены все необходимые операции над общими переменными, критический
интервал заканчивается (с помощью "V(работбуф)") и производитель
инициирует P-операцию над своим частным семафором. Как только эта
P-операция завершается, производитель снова входит в критический
интервал, динамически сливающийся с критическим интервалом первого случая
(немедленное добавление порции), и добавляет порцию к буферу. (Вспомните также
потребителя во второй программе из ╖4.2, в которой мы уже встречались с
прерывающимся открыванием критического интервала.)5)
Отметим, что в рассматриваемом случае ожидания производитель пропускает
уменьшение "числа свободных единиц буфера". Заметим также, что
производитель начинает P-операцию над своим частным семафором в
момент, когда тот уже мог быть установлен в "1", т.е. опять
P-операция является лишь потенциальной задержкой. Теперь
рассмотрим, выполняют ли потребители возложенные на них задачи. Присутствие
следующей порции становится им известно через общий семафор "число порций
в буфере", а так как P-операция над ним происходит вне
критического интервала, то нет опасений, что потребители не начнут ее
выполнение. После этой P-операции потребитель входит в критический
интервал, берет порцию и увеличивает "число свободных единиц
буфера".
Если "блокировка буфера = 0", то следующий составной оператор
целиком пропускается, и критический интервал немедленно заканчивается. Так и
должно быть, так как соотношение "блокировка буфера = 0" означает,
что ни одна из величин "желание" не положительна, т. е. ни один из
производителей не ждет только что освободившегося места в буфере. Если, однако,
потребитель обнаруживает, что "блокировка буфера > 0", то ему
ясно, что по меньшей мере один из производителей приостановил выполнение, и
тогда он определяет, можно ли запустить каких-либо производителей. Потребитель
отыскивает максимальное значение переменной "желание". Если оно не
слишком велико (свободного места в буфере достаточно), то он решает, что
соответствующий производитель должен продолжить работу. Это решение приводит к
следующим трем действиям:
а) "Число свободных
единиц буфера" уменьшается на число единиц, требуемых данному
производителю. Поэтому мы гарантированы от того, что одно и то же свободное
место буфера будет предоставлено более чем одному производителю. Кроме того, это
уменьшение соответствует требованию
производителя.
б) "желание"
производителя, о котором идет речь, устанавливается в нуль; это справедливо,
поскольку его требование удовлетворено; соответственно и "блокировка
буфера" уменьшается на единицу.
в)
V-операция над семафором рассматриваемого производителя позволяет
последнему продолжить работу.
После этого управление возвращается по метке "проверка" для
того, чтобы выяснить, нельзя ли запустить и других приостановленных
производителей. Этот процесс выяснения заканчивается одним из двух способов: или
не остается больше приостановленных производителей ("блокировка буфера =
0"), или такие производители есть, но свободного места на буфере
недостаточно для размещения максимальной предложенной порции информации.
Окончательное значение переменной "блокировка буфера" в обоих
случаях правильное. После запуска соответствующих производителей, критический
интервал потребителя завершается.
В этом параграфе мы обсудим более сложный пример, в котором один из
взаимодействующих процессов является не машиной, а человеком - "оператором".
Оператор системы связан с процессами посредством так называемого
"полудуплексного канала" (применяется также термин "телесвязь"). Канал
называется дуплексным, если информация но нему передается в обоих направлениях:
оператор может с помощью клавиатуры передавать сообщения процессам, а процессы,
в свою очередь, могут выдавать сообщения оператору на телепринтер. Канал
называется полудуплексным, если передача информации возможна за один раз только
в одном направлении.
Теперь давайте рассмотрим требования к системе в целом, отчасти упрощенные,
чтобы не загромождать основную схему решения множеством несущественных деталей,
но все же, я надеюсь, достаточно сложные, чтобы дать нам представление о
реальной проблеме.
Имеется 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". Приведем теперь возможные виды диалогов: Что касается выполнения процесса i, то для него диалог (а)
эквивалентен (в), а (б) эквивалентен (г).
Рассмотренное выше второе требование имеет следующее следствие: без него,
т.е. при единственно допустимых формах ответов "A1" и
"A2", интерпретация входного сообщения (от оператора) могла бы быть
всегда передана одному из N процессов, а именно тому, который задал
вопрос; он мог дождаться ответа и затем соответственно действовать. Сейчас же мы
не знаем заранее, когда появятся сообщения "A4(i)" или
"A5(i)", и мы не можем поручить интерпретацию этих сообщений от
оператора целиком самому i-му процессу, так как выявление
принадлежности входящего сообщения (от оператора) i-му процессу
является частью самой интерпретации сообщения!
В-третьих, А4- и А6-сообщения должны иметь
приоритет над Q1- и М-сообщениями. Это означает
следующее. В то время как канал связи занят (передачей Q1- или
М-сообщения), процессы могут достигнуть точки, когда им необходимо
использовать канал. Но такая же потребность может появиться в это же время у
оператора. Мы хотим, чтобы оператор мог использовать канал как только он
освободится, и, если оператор пожелал использовать канал, то последний не может
быть снова захвачен каким-либо процессом. Это означает, что оператор имеет
средства выразить свое желание с помощью какой-либо элементарной формы ввода,
даже если сам канал занят выводом для оператора.
Предположим, что оператор Замечание. Это аналогично восклицанию школьного учителя: "А теперь,
дети, слушайте!" Если это восклицание рассматривать как обычное сообщение, то
оно бессмысленно: или дети слушают, и оно поэтому избыточно; или они не слушают,
и поэтому не услышат его. В действительности оно является "метасообщением",
которое только извещает, что последует обычное сообщение, и воспринимается
детьми, если даже они не слушают (разговаривают, например).
Правило приоритетов позволяет вызвать резервирование канала связи для
А4- или А6-сообщения. За время, пока оператор получит
возможность выдать сообщение, он может передумать, и поэтому мы расширяем список
ответов оператора формой "А6" - фиктивное сообщение, которое
позволяет оператору после размышления отказаться от посылки "А4"
или "А5".
Важной характеристикой интерпретатора сообщений является надлежащая проверка
поступающих от оператора сообщений. Оператор - человек, и мы можем быть уверены,
что он допускает ошибки. Возможные состояния интерпретатора сообщений таковы,
что в каждый момент допустимы не все сообщения; если сообщение отвергается как
неприемлемое, то интерпретатор должен возвратиться в такое состояние, чтобы
оператор мог выдать затем правильное сообщение.
Наши усилия будут сосредоточены на следующих направлениях:
Перечисленные выше пять пунктов, очевидно, полезны, и на основании нашего
предыдущего опыта, они, кажется, составляют систему разумных правил. Я могу
теперь предложить решение, являющееся развитием этих правил и показать его
корректность. Но было бы еще лучше, если бы мне также удалось показать, каким
путем это решение было получено. По общему признанию, такого рода решение ищется
методом проб и ошибок, но даже если это так, то мы могли бы попытаться более
отчетливо выделить основной руководящий принцип (в математике обычно называемый
"гениальная догадка"). Нам все еще предстоит
решить: Трудность в том, что два упомянутых вопроса взаимозависимы. Ибо значения
переменных состояния имеют недвусмысленное, интерпретируемое значение, только
тогда, когда выполняется "взаимискл = 1", т. е. когда ни один из
процессов не находится внутри критического интервала, где эти значения
изменяются. Другими словами, условия, в которых должны быть применимы значения
переменных состояния, известны только тогда, когда построены программы; но
строить программы мы можем только после выяснения того, какие проверки и
операции выполняются над переменными состояния. Мой опыт подсказывает, что
удобно начинать с грубого представления и о программах и о переменных состояния,
затем перечислить все различные состояния и окончательно попытаться построить
программы. Могут встретиться два случая: или автор обнаруживает, что введено
слишком много состояний, или он убеждается, что, наоборот, не ввел их в
достаточном количестве, проглядев необходимость деления критического интервала
на части. Тогда он изменяет состояния, а затем и программу, и при удаче и
должном внимании процесс построения сходится. Я обычно довольствовался
корректным решением и не беспокоился о минимизации числа введенных состояний.
На своем опыте я убедился, что проще представить сначала состояния (они
интерпретируются статически), а затем программы. При введении состояний следует
помнить три обстоятельства: Первые два обстоятельства полезны главным образом для понимания различных
состояний системы; последнее помогает строить правильные программы.
Давайте попытаемся отыскать набор подходящих состояний. Мы начнем с элемента
"процпер[i]", описывающего состояние процесса i. Назовем это состояние "внутренним положением". Оно будет означать, что
процесс i не требует какого-либо специального обслуживания от
интерпретатора сообщений или от других процессов. "Из-за недоступности канала связи процесс i решил ждать открытия
частного семафора". Это решение может быть принято независимо в каждом процессе
и поэтому разумно отражать его в состоянии процесса. Пока нет очевидных причин
делать различие между ожиданием доступности канала связи для передачи
М-сообщения или Q1-вопроса, поэтому попытаемся
обойтись без него. "На вопрос "Ql(i)" поступил ответ "A3", т.е. по
отношению к процессу i оператор отложил окончательное решение".
Этот факт должен быть зафиксирован, так как решение может быть отложено на
неопределенно долгое время (см. (а)); это состояние должно отражаться переменной
состояния данного процесса, поскольку в такое состояние может быть переведено
любое число (даже все N) процессов (см. (б)). Кроме того,
"процпер[i] = 2" будет выступать как критерий допустимости
сообщений "A4(i)" и "А5(1)". "На вопрос "Ql(i)" поступил ответ "А1" или
"A3" - - - "A4(i)"." "На вопрос "Ql(i)" поступил ответ "А2" или
"A3" - - - "A5(i)"."
Прежде всего заметим, что для отдельного процесса не представляет интереса,
отложил оператор окончательный ответ или нет. Читатель может, однако, быть
удивлен тем, что факт выдачи и форма ответа ("А4" или
"А5") отражается в значении "процпер", хотя за один
раз выдается только один ответ6).
Причина заключается в том, что мы не знаем, сколько времени потребуется
процессу, которому адресован ответ, для того чтобы определить свою реакцию на
ответ: прежде, чем он это сделает, следующий процесс может получить от оператора
окончательный ответ на Ql-вопрос.
Теперь давайте попробуем перечислить возможные состояния системы связи.
Введем единственную переменную "общпер" - общая переменная, - чтобы
по ее значению различать эти состояния. Мы должны учитывать три различных
аспекта:
Для того чтобы сразу не усложнять вопрос, мы начнем рассмотрение, игнорируя
третий пункт. Без него можно определить следующие состояния. "Средства связи свободны", т.е. в равной мере доступны и для процессов, и для
оператора. Для процессов соотношение "общпер = 0" означает
доступность средств связи, для интерпретатора . сообщений это означает, что
входящие сообщения нельзя игнорировать, но они обязательно должны быть одного из
типов: "А4", "А5" или "А6". "Средства связи используются для передачи М-сообщения или
Q1-вопроса". В этот промежуток времени значение переменной
"общпер" должно быть " "Средства связи зарезервированы для Al-, A2- или
АЗ-ответа". После завершения передачи М-сообщения
средства связи снова становятся общедоступными; однако после
Ql-вопроса они должны остаться зарезервированными. В течение этого
промежутка времени, характеризуемого соотношением "общпер = 2",
интерпретатор сообщений обязан знать, какому процессу предназначается ответ
оператора. По окончании ответа средства связи снова становятся общедоступными.
Теперь примем во внимание третье требование. Это приведет к размножению
некоторых состояний. Если "общпер = 0", то входящее сообщение
принимается; если "общпер = 1", то входящее сообщение должно
игнорироваться. Этот случай7)
должен быть специально выделен, поскольку после освобождения средств связи
оператор, имея высший приоритет, должен получить возможность выдать сообщение.
Мы можем ввести новое состояние. "Как и в случае "общпер = 1", но с запросом оператора".
Если переход в состояние "общпер = З" происходит при передаче
М-сообщения, оператор получает возможность выдать сообщение
немедленно по окончании передачи. Если, однако, переход в состояние
"общпер = З" произошел при передаче Ql-вопроса, то
средства связи могут быть предоставлены оператору только после его ответа на
Ql-вопрос.
Поэтому размножается также и состояние 2. "Как и в случае "общпер = 2", но с запросом оператора".
Наконец, имеем еще одно состояние. "Средства связи зарезервированы или используются для передачи отложенных
ответов оператора". Для процессов это означает недоступность средств связи, для
интерпретатора сообщений - приемлемость входящих сообщений типа
"А4", "А5" и "А6".
Обычно требование оператора на передачу этих сообщений объявляется
интерпретатору сообщений при "общпер = 0". Если мы не хотим, чтобы
ожидание передачи и интерпретация этих сообщений происходили внутри того же
самого критического интервала, то интерпретатор сообщений может прервать его. Во
всех случаях необходимо, чтобы значение "общпер" было отлично от
"0". Мы можем попытаться использовать для этих целей то же значение
"5": для процессов это просто означает недоступность средств связи,
в то время как управление интерпретатором сообщений точно знает, ожидает ли он
отложенное сообщение оператора или интерпретирует такое сообщение.
Прежде чем начать составление программы, мы должны вспомнить пункт в):
средства связи нужны всем процессам и являются узким местом системы, поэтому мы
должны заботиться о том, чтобы каждый процесс, освободивший средства связи,
принял решение об их будущем использовании. Это происходит в процессах по
окончании передачи М-сообщения (в меньшей степени по окончании
Ql-вопроса, так как средства связи остаются зарезервированными для ответа), а в
интерпретаторе сообщений - по окончании интерпретации сообщения оператора.
Доказательство существования пудинга мы получаем, когда едим его: так давайте
попытаемся написать программу, чтобы удостовериться, что все необходимые
средства введены. (В программе последовательность символов, начинающаяся со
слова "comment", и кончающаяся первой же точкой с запятой
(включая ее) служит исключительно для пояснений. В АЛГОЛе такие пояснения
допускаются только сразу же за "begin", но я не обещаю
следовать этому (излишнему) ограничению8).
Предполагается, что следующая ниже программа содержится в большей программе, в
которой описаны оператор, средства связи и семафор "входящее
сообщение", первоначально равный "0".) Замечание 1. Если оператор при "общпер = 0" или
"общпер = 5" выдает не интерпретируемое (или неподходящее)
сообщение, то средства связи остаются зарезервированными для его следующей
попытки.
Замечание 2. Окончательная интерпретация сообщений "А4" и
"А5" интерпретатором сообщений происходит внутри критического
интервала, так как их допустимость зависит от состояния рассматриваемого
процесса. Если мы имеем только один канал связи и одного оператора, то это
излишняя предосторожность.
Замечание 3. Циклы for в программе сканируют
процессы по порядку, начиная с процесса 1; при циклическом просматривании
процессов, начиная с произвольно выбранного процесса (например, с помощью
генератора псевдослучайных чисел), мы могли бы получить более симметричное
решение для N процессов.
Замечание 4. В этом параграфе мы сделали сначала довольно полное
исследование возможных состояний системы, а затем составили программу. Читателю
может быть интересно узнать, насколько правдива картина происхождения этого
решения и насколько жизнеспособна она. Когда я начал писать этот параграф,
поставленная проблема была так же нова для меня, как и для читателя:
предложенная программа является моим первым вариантом, построенным с учетом
приведенных соображений и исследований. Я надеюсь поэтому, что настоящее
изложение может служить ориентиром при поиске подобных решений.
5.2.1. Совершенствование предыдущей программы
В ╖5.2 предложен первый вариант программы; он включен в изложение не потому,
что является удовлетворительным, а потому что он завершает общую картину
создания решения. Давайте попытаемся сделать его более красивым во имя большей
лаконичности, ясности и, возможно, эффективности. Давайте попытаемся обнаружить,
в каких отношениях мы совершили просчет.
Сравним потоки информации от процесса к интерпретатору сообщений и обратно. В
одном направлении мы с помощью общей переменной "номерпроц"
извещали интерпретатор сообщений о том, какой из процессов задал вопрос.
Установку и проверку "номерпроп" вполне безопасно можно делать вне
критических интервалов, управляемых семафором "взаимискл", так как
в каждый момент самое большее один из N + 1 процессов будет
обращаться к "номерпроц". В обратном направлении интерпретатор
сообщений извещает i-й процесс о характере окончательного ответа
оператора, представляя его с помощью значения переменной "процпер".
Здесь происходит некоторое смешение понятий, что
проявляется: Предлагается ввести массив Мне хотелось бы исследовать такой вопрос: можно ли достигнуть большей ясности
в решении, разделив общие переменные на две (или, возможно, больше) различные
группы для того, чтобы отразить заметную иерархию в способах их использования.
Давайте попробуем упорядочить их с точки зрения их "не важности".
Семафор "входящее сообщение" на первый взгляд кажется достаточно
важным, обусловленным окружающей средой. Однако это иллюзия: в параллельном
блоке мы запрограммировали бы (в качестве (N + 2)-го процесса)
самого оператора, и семафор, "входящее сообщение" был бы тогда
частным семафором для интерпретатора сообщений, подобно семафору
"процсем[i]" для i-го процесса.
Таким образом, наиболее важной величиной является семафор
"взаимискл", обеспечивающий взаимное исключение критических
интервалов.
Затем следуют переменные состояния "общпер" и
"процпер", которые проверяются и могут изменяться внутри
критических интервалов.
Только что упомянутые величины обладают тем общим свойством, что их значения
должны быть установлены до входа в параллельный блок. Этим же свойством обладают
семафоры "процсем" (и семафор "входящее сообщение",
см. выше), если мы придерживаемся того правила, что параллельно выполняющиеся
процессы обращаются к семафорам исключительно с помощью P- и
V-операций.
(Без этого ограничения запрос на средства связи процессом n мог
бы начинаться так: Мы отбрасываем это решение, так как дальнейшее рассмотрение убеждает нас в
том, что присваивание переменной "процсем[n]" имеет смысл только в
первый раз; поэтому присваивание начальных значений переменным
"процсем" вне параллельного блока кажется более подходящим.)
Для перечисленных до сих пор общих переменных мне хотелось бы сохранить
название "переменные состояния", чтобы отличать их от оставшихся общих
переменных "номерпроц" и "ответоператора", которые мне
хочется назвать "передаточные переменные", потому что всякий раз, когда один из
процессов присваивает значение такой переменной, он адресует его известному
"партнеру-получателю". Эти общие переменные используются для передачи информации
между известными партнерами.
Давайте теперь переключим наше внимание с общих переменных на программы. В
программах мы научились выделять так называемые "критические интервалы", для
которых семафор "взаимискл" обеспечивает взаимное исключение.
Помимо них, мы можем выделить области (динамические участки программы), в
которых выполняются некоторые вполне определенные действия, такие как:
В i-ом процессе: В интерпретаторе сообщений: Перед нами теперь возникает следующая картина. Мы имеем в программе
критические интервалы, взаимно исключаемые семафором "взаимискл".
Назначение критических интервалов - устранить какую-либо неоднозначность при
проверке и модификации остальных переменных состояния. Целью этих проверок и
модификаций является создание более сложных "последовательных структур" из
областей, которые делают возможным однозначное использование передаточных
переменных. (Если один процесс должен передать информацию другому, то он может
теперь осуществить это через передаточные переменные при условии, что за
выполнением области присваивания всегда следует область проверки, прежде чем
будет выполнена следующая область присваивания.)
В улучшенном варианте программы мы будем придерживаться того правила, что
обращения к подлинным переменным состояния будут происходить только в
критических интервалах (если они не являются семафорами) или с помощью
P- и V-операций (если они являются семафорами), тогда
как обращения к передаточным переменным будут происходить только во введенных
выше областях. (В более сложных примерах это правило может оказаться слишком
жестким, и размножения общих переменных можно избежать, разрешив по крайней мере
проверку передаточных переменных в критическом интервале. В этом примере,
однако, мы будем соблюдать упомянутое выше правило.)
Оставшиеся улучшения в программе менее существенны. Программе можно придать
более привлекательный вид, если представлять наличие приоритетных запросов
оператора не дополнительными значениями переменной "общпер", а при
помощи дополнительной переменной состояния с двумя значениями? (Переменные типа "Boolean" могут принимать два значения,
обозначаемые "true" и "false", совпадающие с областью
значений "условий", которые мы встречали в конструкциях
if.)
Кроме того, введем две процедуры; они описываются вне параллельного блока и
поэтому могут использоваться составными элементами параллельного блока.
Сначала мы кратко опишем новый смысл значений переменных состояния
"процпер" и "общпер": Мы приводим программу без комментариев, и сделаем это в два приема: сначала
дадим программу вне параллельного блока, а затем - составные элементы
параллельного блока. Здесь n-й процесс представляется в следующем виде; Если интерпретатор сообщений решает войти в Область 6, то он
перед входом получает копию массива "процпер": если принимается
сообщение A4(i) или A5(i), то в момент объявления
ответа уже должно выполняться "процпер[i] = 2.
Интерпретатор сообщений: В качестве упражнения мы предлагаем читателю составить такой вариант
программы, в котором ожидающие запросы на Q1-вопросы, имеют
приоритет над запросами на М-сообщения. Следующее расширение примера состоит в
составлении программы двухпультовой конфигурации с дополнительным ограничением:
А4- или А6-сообщения допускаются только с того пульта,
где диалог был начат. (Иначе мы должны исключить одновременные противоречивые
сообщения "A4(i)" и "A5(i)" с различных пультов.
Решение без этого ограничения адресовано поистине увлеченному читателю.)
5.2.2. Доказательство корректности
В этом заголовке слово "доказательство" использовано в не формальном смысле.
Я не определил, какие формальные условия необходимо соблюсти в "истинном
доказательстве" и не собираюсь этого делать. Если я смогу найти такой способ
обсуждения программы из п.5.2.1, который позволит мне убедиться самому - и,
надеюсь, убедить сомневающихся - в корректности общего функционирования этой
совокупности процессов, я буду удовлетворен.
В приведенной "схеме состояний" дается диаграмма всех состояний, в которых
может оказаться процесс (вне критических интервалов). Стрелки указывают переходы
из состояния в состояние, которые происходят внутри критических интервалов;
стрелки сопровождаются надписями, отражающими изменения "общпер"
или условия, при которых такой переход имел место.
Нейтральную область процесса до входа в Область 1 или
Область 2 мы называем "Область 0".
5.2. Пример с диалогами
а) "Ql(i), A1"
б) "Ql(i), A2"
в) "Ql(i), A3" - - - "A4(i)"
г) "Ql(i), A3" - - - "A5(i)".
а) может выполнить
какими-то внешними средствами операцию "V(входящее сообщение)",
которую он может использовать для объявления сообщения (A1,
A2, A3, А4 или
А5);
б) может обнаружить по реакции
машины, принято его вмешательство или отвергнуто.
а) Какую структуру нужно придать N +
1 процессам?
6) Какие состояния мы должны
ввести (т. е. как много значений должны иметь переменные состояния и что эти
значения должны означать)?
а) Переменные состояния
должны иметь четкий смысл при "взаимискл = 1"; кроме того, процесс
должен покинуть критический интервал прежде, чем он начнет ждать открытия
частного семафора. Необходимо проявлять большую проницательность во всех тех
местах, где процесс пожелает ждать чего-то более сложного, чем разрешения
завершить "Р(взаимискл)".
б)
Совокупность переменных состояния описывает общее состояние системы. Тем не
менее, наша задача сильно облегчается, если мы можем рассматривать переменные
состояния "принадлежащими такому-то и такому-то процессу". Если некоторая
характеристика общего состояния увеличивается линейно с N, то проще
представлять эту часть состояния системы поделенной поровну между N
процессами.
в) Если какой-то процесс должен ждать
из-за некоторого (частного) состояния системы, то каждый процесс, который
выводит систему из этого частного состояния, обязан проверить, не должен ли быть
продолжен из-за этого изменения состояния некоторый ожидающий процесс. (Это
всего лишь обобщение принципа, уже проиллюстрированного в программе "Спящий
парикмахер".)
процпер[i] = 0
процпер[i] = 1
процпер[i] =2
процпер[i] = 3
процпер[i] =4
общпер = 0
общпер = 1
0", так как средства связи недоступны процессам; для интерпретатора
сообщений это означает, что входящие сообщения должны игнорироваться. общпер = 2
общпер = 3
общпер = 4
общпер = 5
begin integer взаимискл, общпер, номерпроц, цикл;
comment Целая переменная "номерпроц" является переменной состояния
для интерпретатора сообщений и используется, главным образом, при
интерпретации ответов Al, A2 и A3. Это - общая переменная, так как
ее значение устанавливается процессом, задающим вопрос;
integer array процпер, процсем[1 : N];
for цикл := 1 step 1 until N do
begin процпер[цикл] := 0; процсем[цикл] := 0
end;
общпер := 0; взаимискл := 1;
parbegin
процесс 1: begin. ........... end;
.
.
.
процесс n: begin integer i;
comment Целочисленная переменная "i" является локальной
переменной, очень похожей по использованию на переменную
"цикл";
.
.
.
М сообщение: Р (взаимискл);
if общпер = 0 then
begin comment Если средства связи свободны,
они используются;
общпер := 1; V(взаимскл) end;
else
begin comment В противном случае процесс объявляет себя
задержанным и приостанавливается;
процпер[n] := 1; V(взаимискл);
Р(процсем[n]);
comment После завершения этой Р-операции "процпер[n]"
окажется опять установленной в "0", но "общпер" будет
равна "1" или "З"; end;
посылка М-сообщения;
comment Теперь процесс должен проанализировать, должен ли
оператор (первым) или один из других процессов получить
средства связи;
Р(взаимискл);
if общпер = 3 then общпер := 5 else
begin comment В противном случае выполняется "общпер = 1",
и процесс "n" должен посмотреть, ожидает ли один из
других процессов. Заметим, что"процпер[n] = 0";
for i := 1 step 1 until N do
begin if процпер[i] = 1 then
begin процпер[i] := 0;
V(процсем[i]); goto готов
end
end;
общпер := 0
end;
готов: V(взаимискл);
.
.
.
Q1 вопрос: Р(взаимискл);
if общпер = 0 then
begin общпер := 1; V(взаимискл) end
else
begin процпер[n] := 1; V(взаимискл);
Р(процсем[n])
end;
comment Это все идентично М-сообщению. Заметим, что мы
находимся вне критического интервала, тем не менее,
этот процесс установит "номерпроц". Это можно делать
свободно, так как никакой другой процесс, ни интерпретатор
сообщений не получит доступ к "номерпроп", пока выполняется
"общпер = 1";
номерпроц := n; посылка Ql(n)-вonpoca;
Р(взаимискл);
comment "общпер" в этот момент равна "1" или "З";
if общпер = 1 then общпер := 2 else общпер := 4;
М(взаимискл); Р(процсем[тъ);
comment После завершения этой Р-операции,. "процпер[т]" будет
равна "З" или "4". Этот процесс может теперь исследовать и
сбросить в "0" свою "процпер", хотя мы находимся вне
критического интервала;
if процпер[n] = 3 then Реакция 1 else Реакция 2;
процпер[n] := 0;
comment Это последнее присваивание избыточно;
.
.
.
end процесса n;
.
.
.
процесс N: begin ............ end;
интерпретатор сообщений:
begin integer i;
ждать: Р(входящее сообщение);
Р(взаимискл);
if общпер = 1 then общпер := 3;
if общпер = 3 then
begin comment Интерпретатор сообщений игнорирует входящее сообщение,
но в надлежащий момент оператор получит возможность передать
сообщение;
V(взаимискл); goto ждать end;
if общпер = 2 or общпер = 4 then
begin comment Допустимы только сообщения Al, A2 или A3.
Интерпретацию сообщения не обязательно производить
внутри критического интервала;
V(взаимискл);
интерпретация входящего сообщения;
if сообщение = Al then
begin процпер[номерпроц] := 3;
V(процсем[номерпроц]);
goto после правильного ответа
end;
if сообщение = A2 then
begin процпер[номерпроц] :=4;
V(процсем[номерпроц]);
goto после правильного ответа
end;
if сообщение = A3 then
begin процпер [номерпроц] := 2;
goto после правильного ответа
end;
comment Оператор дал неправильный ответ
и должен повторить сообщение;
goto ждать;
после правильного
ответа: Р(взаимискл);
if общпер = 4 then
begin comment Теперь оператор должен получить возможность
передачи своего сообщения;
общпер := 5; V(взаимискл);
goto ждать
end;
возможная установка в 0 общпер:
for i := 1 step 1 until N do
begin if процпер[i] = 1 then
begin проппер[i] := 0; общпер := 1;
V(процсем[i]); goto готов
end;
end;
общпер := 0;
готов: V(взаимискл); goto ждать
end;
comment Остаются случаи "общпер = o" и "общпер = 5".
Допустимы сообщения А4, А5 и А6;
if общпер = 0 then общпер := 5;
comment Смотри Замечание 1 после программы;
V(взаимискл);
интерпретация входящего сообщения;
Р(взаимискл);
if сообщение = А4 (заданный процесс) then
begin i := "номер процесса, заданный в сообщении";
if процпер[i] = 2 then
begin процпер[i] := 3; V(процсем[i]);
goto возможная установка в 0 общпер;
end;
comment В противном случае процесс не ожидает отложенного ответа;
goto неправильное сообщение
end;
if сообщение = А5 (заданный процесс) then
begin i := "номер процесса, заданный в сообщении";
if процпер[i] = 2 then
begin процпер[i] := 4; V(процсем[i]);
goto возможная установка в 0 общпер;
end;
comment В противном случае процесс не ожидает отложенного ответа;
goto неправильное сообщение
end;
if сообщение = А6 then
goto возможная установка в 0 общпер;
неправильное сообщение: comment Сохраняется "общпер = 5",
давая оператору приоритетную возможность повторить сообщение;
V(взаимискл); goto ждать
end интерпретатора сообщений;
parend
end
а) в проверке значения
"процпер" (равно ли ее значение "З" или
"4"), которую вдруг разрешено проводить вне критического интервала;
б) в избыточности сброса значения
"процпер" в "0".
integer array ответоператора[1 : N],
элементы которого будут использоваться подобно переменной
"номерпроц". (Привлекательным следствием этого является то, что
число возможных значений "процпер" - более фундаментальной величины
(см. ниже) - не будет расти с увеличением числа возможных ответов на вопрос
Q1.)
Р(взаимискл);
if общпер = 0 then
begin общпер := 1; V(взаимискл) end
else
begin процпер[n] .= 1; процсем[n] := 0;
V(взаимискл); Р(процсем[n]1) end
Область 1: посылка М-сообщения
Область 2: посылка Ql(i)-Bonpoca
Область 3: реакция на ответ оператора[i] (эта область
не столь строго очерчена, как предыдущие).
Область 4: игнорирование входящих сообщений
Область 5: ожидание Al, A2 или A3
Область 6: ожидание A4(i), A5(i) или А6.
Boolean приоритет оператора
процпер[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: 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
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
