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