Программа для отдельного процесса начинается

Замечание

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

Замечание

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

Замечание

. Значение переменной " число свободных единиц буфера" почти всегда будет равно размеру буфера, уменьшенному на суммарный размер порций, подсчитанных в "числе порций в буфере", но оно может быть и меньше! Я отсылаю читателя к программе из ¬4.3; там сумма
"число порций в буфере + число пустых позиций"
первоначально (и обычно) равняется N, но она может быть равна и N - 1, потому что P-операция над одним из семафоров всегда предшествует V-операции над другим семафором. (Проверьте, что эта сумма может быть равна даже N - 2, и что она могла быть еще меньше, если бы мы имели больше производителей и (или) потребителей.) Здесь можно ожидать похожее явление: семафор "число порций в буфере" будет подсчитывать порции буфера, действительно заполненные и еще не замеченные потребителями; переменная "число свободных единиц буфера" будет подсчитывать полностью свободные, не распределенные производителям единицы в буфере. Но те единицы, которые зарезервированы для заполнения, предоставлены (ожидающему) производителю, но еще не заполнены, не будут учитываться ни одной из переменных.
Наконец, мы введем целочисленную переменную "блокировка буфера", значение которой равно числу положительных (строго больших нуля) величин "желание". Очевидно, что эта переменная является избыточной; она введена для более удобного распознавания рассмотренной несколько ранее ситуации: как только одна из переменных "желание" станет положительной, никакие добавления к буферу производиться не могут до "специального уведомления" (появление дополнительного свободного места в буфере). Одновременно эта переменная играет роль предупреждения потребителям, что такое "специальное уведомление" необходимо.
Предлагается следующая программа, составленная для N производителей и М потребителей ("N", "М", "Размер буфера" и все остальное, что касается буфера, предполагается описанным и определенным во внешних по отношению к данной программе блоках).

Замечание

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

Правило приоритетов позволяет вызвать резервирование канала связи для А4- или А6-сообщения. За время, пока оператор получит возможность выдать сообщение, он может передумать, и поэтому мы расширяем список ответов оператора формой "А6" - фиктивное сообщение, которое позволяет оператору после размышления отказаться от посылки "А4" или "А5".
Важной характеристикой интерпретатора сообщений является надлежащая проверка поступающих от оператора сообщений. Оператор - человек, и мы можем быть уверены, что он допускает ошибки. Возможные состояния интерпретатора сообщений таковы, что в каждый момент допустимы не все сообщения; если сообщение отвергается как неприемлемое, то интерпретатор должен возвратиться в такое состояние, чтобы оператор мог выдать затем правильное сообщение.
Наши усилия будут сосредоточены на следующих направлениях:

Кроме N процессов мы введем еще один процесс, называемый "интерпретатор сообщений"; это сделано из-за того, что интерпретацию сообщений "А4", "А5" и "А6" трудно выполнять одним из N процессов.

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

Для N процессов мы введем массив частных семафоров "процсем" - семафор процесса - и массив переменных состояния "процпер" - переменная процесса, которые будут использоваться Для связи процессов друг с другом и с интерпретатором сообщений.

Наконец, мы вводим единственный двоичный семафор "взаимискл"- взаимное исключение, который обеспечивает взаимное исключение при проверке и (или) модификации общих переменных.

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

Замечание

. Грубо говоря, успешный заем флорина может иметь место только при удовлетворении двух условий: флорин должен быть затребован и флорин должен быть доступен. В этой программе механизм общих переменных "клиентпер" и "клиентсем" используется также (клиентом) в случае, когда затребованный флорин немедленно предоставлен; подобно этому, механизм общих переменных "флоринпер" и "флоринсем" используется также (флорином) в случае, если после возвращения его в наличный капитал он может немедленно быть выдан снова ожидающему клиенту. Этот метод программирования был предложен Лайтмансом и Вуурхоеве, и я упоминаю о нем потому, что в случае более сложных правил взаимодействия он приводит к упрощениям, которые оказываются крайне полезными. Основной причиной достижения большей простоты является то, что динамическое движение через топологическую структуру программы больше не проводит различие между фактической задержкой и потенциальной, точно так же как в случае самой P-операции.

begin integer array желание, семафор производителя[1 : Nl; integer число порций в буфере, число свободных единиц буфера, блокировка буфера, работбуф, цикл; for цикл := 1 step 1 until N do
begin желание[цикл] := 0; семафор производителя[цикл] := 0 end; число порций в буфере := 0; число свободных единиц буфера := Размер буфера; блокировка буфера := 0; работбуф := 1; parbegin
производитель 1: begin ............ end; . . . производитель n; begin integer размер порции; снова n: производство новой порции и установка размера порции; Р(работбуф); if блокировка буфера = 0 and
число свободных единиц буфера размер порции then
число свободных единиц буфера := число свободных единиц буфера - размер порции else
begin блокировка буфера := блокировка буфера + 1; желание[n] := размер порции; V(работбуф); Р(семафор производителяЫ); Р(работбуф) end; добавление порции к буферу; V(работбуф); V(число порций в буфере); goto снова n end; производитель N: begin ........... end; потребитель 1: begin ........... end; . . . потребитель m: begin integer размер порции, n, max, nmax; снова m: Р(число порций в буфере); Р(работбуф); взятие порции из буфера и установка размера порции; число свободных единиц буфера := число свободных единиц буфера + размер порции; проверка: if блокировка буфера > 0 then
begin шах := 0; for n := 1 step until N do
begin if max < желание[n] then
begin шах := желание[n]; пшах:= n end
end; if max число свободных единиц буфера then begin число свободных единиц буфера:= число свободных единиц буфера - max; желание[nmax] := 0; блокировка буфера := блокировка буфера - 1; V(семафор производителя [nmax]); goto проверка end
end; V(работбуф); обработка взятой порции; goto снова m end; . . . потребитель M: begin .............. end
parend
end
В самом внешнем блоке описываются общие переменные и там же им присваиваются начальные значения; надеюсь, что эта часть программы не вызовет трудностей у читателей, которые разобрались во всем предыдущем изложении.

Давайте сначала попытаемся понять поведение производителя. Когда он хочет добавить новую порцию к буферу, возможны два случая: или это можно сделать немедленно, или нет. Немедленное добавление порции возможно при следующем комбинированном условии:
блокировка буфера = 0 and число свободных единиц буфера размер порции
Если условие удовлетворяется, то производитель уменьшает "число свободных единиц буфера" и, - оставаясь динамически в том же критическом интервале, - добавляет порцию к буферу. Две следующие V-операции (порядок которых безразличен) завершают Критический интервал и извещают потребителей о существовании следующей порции. Если добавление порции нельзя осуществить немедленно, т.е. если
блокировка буфера > 0 or число свободных единиц буфера < размер порции

(или оба эти условия удовлетворяются одновременно), то производитель переходит в состояние ожидания, "приостанавливается", поручая потребителям запустить его снова в подходящее время. Факт ожидания для данного производителя выражается соотношением "желание[n] > 0", и соответственно "блокировка буфера" увеличивается на единицу. После того как выполнены все необходимые операции над общими переменными, критический интервал заканчивается (с помощью "V(работбуф)") и производитель инициирует P-операцию над своим частным семафором. Как только эта P-операция завершается, производитель снова входит в критический интервал, динамически сливающийся с критическим интервалом первого случая (немедленное добавление порции), и добавляет порцию к буферу. (Вспомните также потребителя во второй программе из ¬4.2, в которой мы уже встречались с прерывающимся открыванием критического интервала.) Отметим, что в рассматриваемом случае ожидания производитель пропускает уменьшение "числа свободных единиц буфера". Заметим также, что производитель начинает P-операцию над своим частным семафором в момент, когда тот уже мог быть установлен в "1", т.е.

опять P- операция является лишь потенциальной задержкой. Теперь рассмотрим, выполняют ли потребители возложенные на них задачи. Присутствие следующей порции становится им известно через общий семафор "число порций в буфере", а так как P-операция над ним происходит вне критического интервала, то нет опасений, что потребители не начнут ее выполнение. После этой P-операции потребитель входит в критический интервал, берет порцию и увеличивает "число свободных единиц буфера".
Если "блокировка буфера = 0", то следующий составной оператор целиком пропускается, и критический интервал немедленно заканчивается. Так и должно быть, так как соотношение "блокировка буфера = 0" означает, что ни одна из величин "желание" не положительна, т. е. ни один из производителей не ждет только что освободившегося места в буфере. Если, однако, потребитель обнаруживает, что "блокировка буфера > 0", то ему ясно, что по меньшей мере один из производителей приостановил выполнение, и тогда он определяет, можно ли запустить каких-либо производителей. Потребитель отыскивает максимальное значение переменной "желание". Если оно не слишком велико (свободного места в буфере достаточно), то он решает, что соответствующий производитель должен продолжить работу. Это решение приводит к следующим трем действиям:

а) "Число свободных единиц буфера" уменьшается на число единиц, требуемых данному производителю. Поэтому мы гарантированы от того, что одно и то же свободное место буфера будет предоставлено более чем одному производителю. Кроме того, это уменьшение соответствует требованию производителя.

б) "желание" производителя, о котором идет речь, устанавливается в нуль; это справедливо, поскольку его требование удовлетворено; соответственно и "блокировка буфера" уменьшается на единицу.

в) V-операция над семафором рассматриваемого производителя позволяет последнему продолжить работу.
После этого управление возвращается по метке "проверка" для того, чтобы выяснить, нельзя ли запустить и других приостановленных производителей. Этот процесс выяснения заканчивается одним из двух способов: или не остается больше приостановленных производителей ("блокировка буфера = 0"), или такие производители есть, но свободного места на буфере недостаточно для размещения максимальной предложенной порции информации. Окончательное значение переменной "блокировка буфера" в обоих случаях правильное. После запуска соответствующих производителей, критический интервал потребителя завершается.
доступность средств связи для M-сообщений, Ql-вопросов и спонтанных сообщений оператора;
приемлемость ( более общо: интерпретируемость) поступающих от оператора сообщений;
приоритет оператора при передаче сообщений.

Для того чтобы сразу не усложнять вопрос, мы начнем рассмотрение, игнорируя третий пункт. Без него можно определить следующие состояния.
общпер = 0
"Средства связи свободны", т.е. в равной мере доступны и для процессов, и для оператора. Для процессов соотношение "общпер = 0" означает доступность средств связи, для интерпретатора . сообщений это означает, что входящие сообщения нельзя игнорировать, но они обязательно должны быть одного из типов: "А4", "А5" или "А6".
общпер = 1
"Средства связи используются для передачи М-сообщения или Q1-вопроса". В этот промежуток времени значение переменной "общпер" должно быть "