Программа для отдельного процесса начинается
Замечание
. Программа для отдельного процесса начинается с описания "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 проверка endend; 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"), или такие производители есть, но свободного места на буфере недостаточно для размещения максимальной предложенной порции информации. Окончательное значение переменной "блокировка буфера" в обоих случаях правильное. После запуска соответствующих производителей, критический интервал потребителя завершается.
Для того чтобы сразу не усложнять вопрос, мы начнем рассмотрение, игнорируя третий пункт. Без него можно определить следующие состояния.
общпер = 0
"Средства связи свободны", т.е. в равной мере доступны и для процессов, и для оператора. Для процессов соотношение "общпер = 0" означает доступность средств связи, для интерпретатора . сообщений это означает, что входящие сообщения нельзя игнорировать, но они обязательно должны быть одного из типов: "А4", "А5" или "А6".
общпер = 1
"Средства связи используются для передачи М-сообщения или Q1-вопроса". В этот промежуток времени значение переменной "общпер" должно быть "
0", так как средства связи недоступны процессам; для интерпретатора сообщений это означает, что входящие сообщения должны игнорироваться.общпер = 2
"Средства связи зарезервированы для Al-, A2- или АЗ-ответа". После завершения передачи М-сообщения средства связи снова становятся общедоступными; однако после Ql-вопроса они должны остаться зарезервированными. В течение этого промежутка времени, характеризуемого соотношением "общпер = 2", интерпретатор сообщений обязан знать, какому процессу предназначается ответ оператора. По окончании ответа средства связи снова становятся общедоступными.
Теперь примем во внимание третье требование. Это приведет к размножению некоторых состояний. Если "общпер = 0", то входящее сообщение принимается; если "общпер = 1", то входящее сообщение должно игнорироваться. Этот случай должен быть специально выделен, поскольку после освобождения средств связи оператор, имея высший приоритет, должен получить возможность выдать сообщение.
Мы можем ввести новое состояние.
общпер = 3
"Как и в случае "общпер = 1", но с запросом оператора".
Если переход в состояние "общпер = З" происходит при передаче М-сообщения, оператор получает возможность выдать сообщение немедленно по окончании передачи. Если, однако, переход в состояние "общпер = З" произошел при передаче Ql-вопроса, то средства связи могут быть предоставлены оператору только после его ответа на Ql-вопрос.
Поэтому размножается также и состояние 2.
общпер = 4
"Как и в случае "общпер = 2", но с запросом оператора".
Наконец, имеем еще одно состояние.
общпер = 5
"Средства связи зарезервированы или используются для передачи отложенных ответов оператора". Для процессов это означает недоступность средств связи, для интерпретатора сообщений - приемлемость входящих сообщений типа "А4", "А5" и "А6".
Обычно требование оператора на передачу этих сообщений объявляется интерпретатору сообщений при "общпер = 0". Если мы не хотим, чтобы ожидание передачи и интерпретация этих сообщений происходили внутри того же самого критического интервала, то интерпретатор сообщений может прервать его. Во всех случаях необходимо, чтобы значение "общпер" было отлично от "0". Мы можем попытаться использовать для этих целей то же значение "5": для процессов это просто означает недоступность средств связи, в то время как управление интерпретатором сообщений точно знает, ожидает ли он отложенное сообщение оператора или интерпретирует такое сообщение.
Прежде чем начать составление программы, мы должны вспомнить пункт в): средства связи нужны всем процессам и являются узким местом системы, поэтому мы должны заботиться о том, чтобы каждый процесс, освободивший средства связи, принял решение об их будущем использовании. Это происходит в процессах по окончании передачи М-сообщения (в меньшей степени по окончании Ql-вопроса, так как средства связи остаются зарезервированными для ответа), а в интерпретаторе сообщений - по окончании интерпретации сообщения оператора.
Доказательство существования пудинга мы получаем, когда едим его: так давайте попытаемся написать программу, чтобы удостовериться, что все необходимые средства введены. (В программе последовательность символов, начинающаяся со слова "comment", и кончающаяся первой же точкой с запятой (включая ее) служит исключительно для пояснений. В АЛГОЛе такие пояснения допускаются только сразу же за "begin", но я не обещаю следовать этому (излишнему) ограничению. Предполагается, что следующая ниже программа содержится в большей программе, в которой описаны оператор, средства связи и семафор "входящее сообщение", первоначально равный "0".)
begin integer взаимискл, общпер, номерпроц, цикл; comment Целая переменная "номерпроц" является переменной состояния для интерпретатора сообщений и используется, главным образом, при интерпретации ответов Al, A2 и A3. Это - общая переменная, так как ее значение устанавливается процессом, задающим вопрос; integer array процпер, процсем[1 : N]; for цикл := 1 step 1 until N do
begin процпер[цикл] := 0; процсем[цикл] := 0 end; общпер := 0; взаимискл := 1; parbegin
процесс 1: begin. ........... end; . . . процесс n: begin integer i; comment Целочисленная переменная "i" является локальной переменной, очень похожей по использованию на переменную "цикл"; . . . М сообщение: Р (взаимискл); if общпер = 0 then
begin comment Если средства связи свободны, они используются; общпер := 1; V(взаимскл) end; else
begin comment В противном случае процесс объявляет себя задержанным и приостанавливается; процпер[n] := 1; V(взаимискл); Р(процсем[n]); comment После завершения этой Р-операции "процпер[n]" окажется опять установленной в "0", но "общпер" будет равна "1" или "З"; end; посылка М-сообщения; comment Теперь процесс должен проанализировать, должен ли оператор (первым) или один из других процессов получить средства связи; Р(взаимискл); if общпер = 3 then общпер := 5 else
begin comment В противном случае выполняется "общпер = 1", и процесс "n" должен посмотреть, ожидает ли один из других процессов. Заметим, что"процпер[n] = 0"; for i := 1 step 1 until N do
begin if процпер[i] = 1 then
begin процпер[i] := 0; V(процсем[i]); goto готов end
end; общпер := 0 end; готов: V(взаимискл); . . . Q1 вопрос: Р(взаимискл); if общпер = 0 then
begin общпер := 1; V(взаимискл) end
else
begin процпер[n] := 1; V(взаимискл); Р(процсем[n]) end; comment Это все идентично М-сообщению. Заметим, что мы находимся вне критического интервала, тем не менее, этот процесс установит "номерпроц". Это можно делать свободно, так как никакой другой процесс, ни интерпретатор сообщений не получит доступ к "номерпроп", пока выполняется "общпер = 1"; номерпроц := n; посылка Ql(n)-вonpoca; Р(взаимискл);
comment "общпер" в этот момент равна "1" или "З"; if общпер = 1 then общпер := 2 else общпер := 4; М(взаимискл); Р(процсем[тъ); comment После завершения этой Р-операции,. "процпер[т]" будет равна "З" или "4". Этот процесс может теперь исследовать и сбросить в "0" свою "процпер", хотя мы находимся вне критического интервала; if процпер[n] = 3 then Реакция 1 else Реакция 2; процпер[n] := 0; comment Это последнее присваивание избыточно; . . . end процесса n; . . . процесс N: begin ............ end; интерпретатор сообщений: begin integer i; ждать: Р(входящее сообщение); Р(взаимискл); if общпер = 1 then общпер := 3; if общпер = 3 then
begin comment Интерпретатор сообщений игнорирует входящее сообщение, но в надлежащий момент оператор получит возможность передать сообщение; V(взаимискл); goto ждать end; if общпер = 2 or общпер = 4 then
begin comment Допустимы только сообщения Al, A2 или A3. Интерпретацию сообщения не обязательно производить внутри критического интервала; V(взаимискл); интерпретация входящего сообщения; if сообщение = Al then
begin процпер[номерпроц] := 3; V(процсем[номерпроц]); goto после правильного ответа end; if сообщение = A2 then
begin процпер[номерпроц] :=4; V(процсем[номерпроц]); goto после правильного ответа end; if сообщение = A3 then
begin процпер [номерпроц] := 2; goto после правильного ответа end; comment Оператор дал неправильный ответ и должен повторить сообщение; goto ждать; после правильного ответа: Р(взаимискл); if общпер = 4 then
begin comment Теперь оператор должен получить возможность передачи своего сообщения; общпер := 5; V(взаимискл); goto ждать end; возможная установка в 0 общпер: for i := 1 step 1 until N do
begin if процпер[i] = 1 then
begin проппер[i] := 0; общпер := 1; V(процсем[i]); goto готов end; end; общпер := 0; готов: V(взаимискл); goto ждать end; comment Остаются случаи "общпер = o" и "общпер = 5". Допустимы сообщения А4, А5 и А6; if общпер = 0 then общпер := 5; comment Смотри Замечание 1 после программы;
V(взаимискл); интерпретация входящего сообщения; Р(взаимискл); if сообщение = А4 (заданный процесс) then
begin i := "номер процесса, заданный в сообщении"; if процпер[i] = 2 then
begin процпер[i] := 3; V(процсем[i]); goto возможная установка в 0 общпер; end; comment В противном случае процесс не ожидает отложенного ответа; goto неправильное сообщение end; if сообщение = А5 (заданный процесс) then
begin i := "номер процесса, заданный в сообщении"; if процпер[i] = 2 then
begin процпер[i] := 4; V(процсем[i]); goto возможная установка в 0 общпер; end; comment В противном случае процесс не ожидает отложенного ответа; goto неправильное сообщение end; if сообщение = А6 then
goto возможная установка в 0 общпер;
неправильное сообщение: comment Сохраняется "общпер = 5", давая оператору приоритетную возможность повторить сообщение; V(взаимискл); goto ждать end интерпретатора сообщений; parend
end