Теория вычислительных процессов

Таким образом, каждый процесс можно рассматривать как функцию F с областью определения В (множество начальных событий), и областью значения {F(х) | x О B}.

Такой подход позволяет представить любой процесс как функцию в некотором подходящем функциональном языке программирования, например в ЛИСПе. Каждое событие из алфавита процесса представлено атомом ("МОН"). При этом если символ не может быть начальным событием процесса, то результатом функции будет специальный символ "BLEEP". Например, для процесса (х: {} ® СТОП(х)) значением функции будет "BLEEP", что обозначим

СТОП = lx. "BLEEP".

Если же аргумент является событием, возможным для процесса, результатом функции будет другая функция, определяющая последующее поведение процесса.

Пример 3.7. Функция, реализующая процесс (c ® Р) может иметь вид:

префикс(c, Р) = lх. if x = с then Р else "BLEEP".

Пример 3.8. Функция, реализующая двуместный выбор (c ® Р | d ® Q) может иметь вид:

выбор(c, d, Р, Q) = lх. if x = с then Р else if x = d then Q else "BLEEP".

Оказывается возможным прямое кодирование рекурсивных уравнений:

Пример 3.9. ТАП = префикс("МОН", префикс("ШОК", ТАП)).

3.1.4 Протоколы

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

Будем обозначать протокол последовательностью символов, разделенной запятыми и заключенной в угловые скобки, например, протокол <х, у> состоит из двух событий -- х и следующего за ним у, <x> - cостоит из одного события х, а протокол <> - пустой протокол.

Пример 3.10. Протокол простого торгового автомата ТАП в момент завершения обслуживания первых двух покупателей:

<мон, шок, мон, шок>.

Протокол того же автомата перед тем, как второй покупатель вынул свою шоколадку:

<мон, шок, мон>.

3.1.5 Операции над протоколами

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

s, t, u - протоколы,

S, Т, U - множества протоколов,

f, g, h - функции.

3.1.5.1. Конкатенация

Наиболее важной операцией над протоколами является конкатенация s^t, которая строит новый протокол из пары протоколов s и t, просто соединяя их в указанном порядке. Например,

<мон, шок>^<мон> = <мон, шок, мон>.

Самые важные свойства конкатенации -- это ее ассоциативность и то, что пустой протокол <> служит для нее единицей:

L1. s^<> = <>^s.

L2. s^(t^u) = (s^t)^u.

Пусть f -- функция, отображающая протоколы в протоколы. Будем говорить, что функция строгая, если она отображает пустой протокол в пустой протокол: f(<>)=<>.

Будем говорить, что функция f дистрибутивна, если f(s^t) = f(s)^f(t).

Все дистрибутивные функции являются строгими.

Если n -- натуральное число, то tn будет обозначать конкатенацию n копий протокола t. Отсюда следует:

L3. tn+1= t^tn.

L4. (s^t)n+1 = s^(t^s)n^t.

3.1.5.2 Сужение

Выражение (t ? А) обозначает протокол t, суженный на множество символов А; он строится из t отбрасыванием всех символов, не принадлежащих А.

Сужение дистрибутивно и поэтому строго.

L1. s^<> = <>^s.

L2. s^(t^u) = (s^t)^u.

Эффект сужения на одноэлементных последовательностях очевиден:

L3. tⁿ⁺¹= t^tⁿ.

L4. (s^t)ⁿ⁺¹ = s^(t^s)ⁿ^t.

Приведенные ниже законы раскрывают взаимосвязь сужения ? и операций над множествами.

L5. s ­ {} = <>.

L6. (s ­ A) ­ B = s ­ (A З B).

3.1.5.3 Голова и хвост

Если s -- непустая последовательность, обозначим ее первый элемент s0, а результат, полученный после его удаления -- s'. Например, <x, y, х>0 = x, <х, у, х>' = y. Обе эти операции не определены для пустой последовательности.

L1. (<x>^s)₀ = х.

L2. (<x>^s)' = s.

L3. s = (<s₀>^s' ), если s № <>.

Следующий закон предоставляет удобный метод доказательства равенства или неравенства двух протоколов:

L4. s = t є (s = t = <> OR (s₀ = t₀ AND s' = t')).

3.1.5.4 Звёздочка

Множество А* -- это набор всех конечных протоколов (включая <>), составленных из элементов множества А. После сужения на А такие протоколы остаются неизменными, Отсюда следует простое определение:

А* = {s | (s ­ A) = s}.

Приведенные ниже законы являются следствиями этого определения:

L1. <> О А*.

L2. <x> О А* є x О А.

L3. (s^t) О А* є s О А* AND t О А*.

Они обладают достаточной мощностью, чтобы определить, принадлежит ли протокол множеству А*. Например, если х О А, а y--О А, то

<x, y> О А* є (<x>^<y>) О А*

є (<x> О А*) AND (<y> О А*) по L3

є T AND F = F по L2.

3.1.5.5 Порядок

Если s -- копия некоторого начального отрезка t, то можно найти такое продолжение и последовательности s, что s^и = t. Поэтому мы определим отношение порядка

s Ј t = ($u.s^и = t).

и будем говорить, что s является префиксом t. Например:<х, у> Ј <х, у, z>. Отношение Ј является частичным упорядочением и имеет своим наименьшим элементом <>. Об этом говорят законы

L1. <> Ј s наименьший элемент.

L2. s Ј s рефлексивность.

L3. s Ј t AND t Ј s Ю t = s антисимметричность.

L4. s Ј t AND t Ј u Ю s Ј u транзитивность.

Следующий закон вместе с L1 позволяет определить, является ли справедливым отношение s Ј t:

L5. (<x>^s) Ј t є t № <> AND x = t₀ AND s Ј t'.

Будем говорить, что функция f из множества протоколов во множество протоколов монотонна, если она сохраняет отношение порядка ?, т. е. f(s) ? f(t) всякий раз, когда s ? t.

3.1.5.6 Длина

Длину протокола t будем обозначать #t. Например, #<х, у, z> = 3.

Следующие законы определяют операцию #:

L1. #<> = 0.

L2. #<x> = 1.

L3. #(s ^t) = #s + #t.

Число вхождений символа х в протокол s определяется как s ? х = #(s ? {х}).

3.1.6 Протоколы процесса

Понятие протокола введено, как последовательная запись поведения процесса вплоть до некоторого момента времени. До начала процесса неизвестно, какой именно из возможных протоколов будет реализован: его выбор зависит от внешних по отношению к процессу факторов. Однако полный набор всех возможных протоколов процесса Р может быть известен заранее. Введем функцию протоколы(Р) для обозначения этого множества.

Пример 3.11. Единственным протоколом процесса СТОП является <>: протоколы(СТОП) = {<>}.

Пример 3.12. протоколы(ЧАСЫ) = {<>, <тик>, <тик, тик>,…} = {тик}*.

Здесь множество протоколов бесконечно.

3.1.6.1 Законы

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

L1. протоколы(СТОП) = {t | t = <>} = {<>}.

Протокол процесса (с ? Р) может быть пустым, поскольку <> является протоколом поведения любого процесса до момента наступления его первого события.

L2. протоколы(с ® Р) = {t | t = <> OR (t₀ = c AND t' О протоколы(Р))}

= {<> И {<c>^t | t О протоколы(Р)}..

Эти два закона можно объединить в один общий закон, которому подчиняется конструкция выбора:

LЗ. протоколы(x: B ® Р(x)) = {t | t = <> OR (t₀ О В AND t' О протоколы(Р(t₀)))}.

Несколько сложнее найти множество протоколов рекурсивно определенного процесса. Рекурсивно определенный процесс является решением уравнения Х = F(Х).

L4. протоколы(mХ: А.F(Х)) = И_nі0протоколы(Fⁿ(СТОП_A)).

Пример 3.13. протоколы(ТАП) = И_nі0{s | s Ј <мон, шок>ⁿ}.

Доказательство:

1) Согласно предположению индукции протоколы(Fn(ТAП)) = {t ? t ? <мон, шок>n},

где F(X) = (мон ® шок ® X).

2) протоколы((F⁰(СТОП)) = {<>} = {s | s Ј <мон, шок>⁰}, для n = 0 предположение выполняется.

3) Покажем, что предположение также справедливо для n+1:

протоколы(Fⁿ⁺¹(СТОП)) = протоколы(мон ® шок ® Fⁿ(СТОП)) =

= {<>, <мон>} И {<мон, шок>^t | t О протоколы(Fⁿ(СТОП))} =

= {<>, {<мон>} И {<мон, шок>^t | t Ј <мон, шок>ⁿ} =

= {s | s = <> OR s = <мон> OR $t.s = <мон, шок>^t AND t Ј <мон, шок>ⁿ} =

= {s | s Ј <мон, шок>ⁿ⁺¹}.

Справедливо, что <> является протоколом любого процесса до момента наступления его первого события. Кроме того, если (s^t) - протокол процесса до некоторого момента, то s должен быть протоколом того же процесса до некоторого более раннего момента времени. Наконец, каждое происходящее событие должно содержаться в алфавите процесса.

3.1.6.2. После

Если s О протоколы(P), то P/s (P после s) - это процесс, ведущий себя так, как ведет себя Р с момента завершения всех действий, записанных в протоколе s. Если s не является протоколом P, то P/s не определено.

Пример 3.14. (ТАП / <мон>) = (шок > ТАП).

3.1.7 Спецификации

Спецификация изделия - это описание его предполагаемого поведения. Это описание представляет собой предикат, содержащий свободные переменные, каждая из которых соответствует некоторому обозримому аспекту поведения изделия.

Например, спецификация электронного усилителя с входным диапазоном в один вольт и с усилением входного напряжения приблизительно в 10 раз задается предикатом

УСИЛ10 = (0 Ј v Ј 1 Ю |v' - 10ґv | Ј 1).

В этой спецификации v обозначает входное, а v'- выходное напряжения.

В случае процесса наиболее естественно в качестве результата наблюдения за его поведением рассматривать протокол событий, произошедших вплоть до данного момента времени. Для обозначения произвольного протокола процесса будем использовать специальную переменную пр.

Пример 3.15. Владелец торгового автомата не желает терпеть убытков. Поэтому он оговаривает, что число выданных шоколадок не должно превышать числа опущенных монет:

НЕУБЫТ = (#(пр ­ {шок}) Ј #(пр ­ {мон})) = пр Ї шок Ј пр Ї мон. (см. 3.1.5.6.)

Пользователь автомата хочет быть уверенным в том, что машина не будет поглощать монеты, пока не выдаст уже оплаченный шоколад:

ЧЕСТН = (пр Ї мон Ј (пр Ї шок + 1))

Изготовитель торгового автомата должен учесть требования, как владельца, так и клиента:

ТАПВЗАИМ = ТАПНЕУБЫТ AND ЧЕСТН = (0 Ј (пр Ї мон - пр Ї шок) Ј 1)..

3.1.7.1 Соответствие спецификации

Если Р - объект, отвечающий спецификации S, то говорят, что Р удовлетворяет S, сокращенно

Р уд S.

Это означает, что S описывает все возможные результаты наблюдения за поведением Р, или, другими словами, S истинно всякий раз, когда его переменные принимают значения, полученные в результате наблюдения за объектом Р, или, более формально:

?пр.пр препротоколы(Р) О S.

В следующих законах приводятся наиболее общие свойства отношения удовлетворяет. Спецификации истина, не накладывающей никаких ограничений на поведение, будут удовлетворять все объекты.

L1. P уд истина.

Если объект удовлетворяет двум различным спецификациям, он удовлетворяет также и их конъюнкции:

L2А. Если Р уд S и Р уд Т, то Р уд (S AND T).

Пусть S(n) -- предикат, содержащий переменную n и Р не зависит от n.

L2B. Если ?n.(Р уд S(n)), то Р уд ?n.S(n).

Если из спецификации S логически следует другая спецификация T, то всякое наблюдение, описываемое S, описывается также и Т.

LЗ. Если Р уд S и S Ю T, то Р уд Т.

3.1.7.2. Доказательства

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

Результатом наблюдения за процессом СТОП всегда будет пустой протокол:

L4А. СТОП уд (пр = <>).

Протокол процесса (с ® Р) вначале пуст. Каждый последующий протокол начинается с c, а его хвост является протоколом Р.

L4В. Если Р уд S(пр), то (с ® Р) уд (пр = <> OR (пр0 = c AND S(пр'))).

Все приведенные выше законы являются частными случаями закона для обобщенного оператора выбора:

L5. Если ?"x О B.(Р(x) уд S(пр, х)), то (х: В ® Р(x)) уд (пр = <> OR (пр₀ О B AND S(пр', пр₀))).

Закон, устанавливающий корректность рекурсивно определенного процесса.

L6. Если F(X) -- предваренная, СТОП уд S, а ((X уд S) Ю (F(Х) уд S)), то (mХ.F(Х)) уд S.

Пример 1.16. Докажем, что ТАП уд ТАПВЗАИМ.

Доказательство:

1) СТОП уд (пр = <>) Ю 0 Ј (пр Ї мон - пр Ї шок) Ј 1), т.к. (<> Ї мон = (<> Ї шок) = 0.

Это заключение сделано на основании применения законов L4A и LЗ.

2) Предположим, что Х уд (0 Ј ((пр Ї мон) - (пр Ї шок)) Ј 1). Тогда

(мон®шок ®Х) уд (пр Ј <мон, шок> OR (пр і <мон, шок> AND (0 Ј ((пр"Ї мон) - (пр"Ї шок)) Ј 1))) Ю

Ю (0 Ј ((пр Ї мон) - (пр Ї шок))Ј1),

так как <> Ї мон = <> Ї шок = <мон> Ї шок = 0, <мон> Ї мон = <мон, шок> Ї мон = <мон, шок> Ї шок = 1 и пр і <мон ,шок> Ю (пр Ї мон = пр" Ї мон + 1 AND пр Ї шок = пр" Ї шок+1)

Применяя теперь закон L3, а затем -- L6, получим требуемый результат.

Тот факт, что процесс Р удовлетворяет спецификации, еще не означает, что он будет нормально функционировать. Например, так как

пр = <> Ю 0 Ј ((пр Ї мон) - (пр Ї шок)) Ј 1

то с помощью законов L3, L4 можно доказать, что

СТОП уд 0 Ј ((пр Ї мон) - (пр Ї шок)) Ј 1.

Однако СТОП не соответствует ни требованиям владельца торгового автомата, ни покупателя. Он не сделает ничего плохого, но только потому, что он не делает ничего вообще. По той же причине СТОП удовлетворяет любой спецификации, которой может удовлетворять процесс.

3.2 Параллельные процессы

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

3.2.1 Взаимодействие

Объединяя два процесса для совместного исполнения, как правило, хотят, чтобы они взаимодействовали друг с другом. Эти взаимодействия можно рассматривать, как события, требующие одновременного участия обоих процессов.

3.2.1.1 Законы

Законы, управляющие поведением (P || Q), параллельно развивающихся процессов P и Q, достаточно просты. Первый закон выражает логическую симметрию между процессом и его окружением:

L1. P || Q = Q || P.

Следующий закон показывает, что при совместной работе трех процессов неважно, в каком порядке они объединены оператором параллельной композиции ||:

L2. P || (Q || R) = (P || Q) || R.

Процесс, находящийся в тупиковой ситуации, приводит к тупику всей системы.

L3. P || СТОП?P = СТОП?P.

Следующий закон гласит, что пара процессов с одинаковыми алфавитами либо одновременно выполняет одно и то же действие, либо попадает в состояние тупика, если начальные события процессов не совпадают:

L4А. (с ® Р) || (с ® Q) = с ® (Р || Q).

L4B. (с ® Р) || (d ® Q) = СТОП.

3.2.2 Параллелизм

Рассмотрим случай, когда операнды Р и Q оператора || имеют неодинаковые алфавиты aР № aQ.

Когда такие процессы объединяются для совместного исполнения, события, содержащиеся в обоих алфавитах, требуют одновременного участия Р и Q. События же из алфавита Р, не содержащиеся в алфавите Q, не имеют никакого отношения к Q, который физически неспособен ни контролировать, ни замечать такие события. Такие события процесса P могут происходить независимо от Q. Аналогично Q может самостоятельно участвовать в событиях, содержащихся в его алфавите, но отсутствующих в алфавите Р.

Таким образом, множество всех событий, логически возможных для данной системы, есть просто объединение алфавитов составляющих ее процессов a(Р || Q) = aР И aQ.

3.2.2.1 Законы

Формальное описание вышесказанного осуществляется с помощью следующих законов:

Пусть а О (aР - aQ), b О (aQ - aР) и {c, d} О (aР З aQ). Следующие законы показывают, каким образом процесс Р один участвует в событии a, Q один участвует в b, а c и d требуют одновременного участия P и Q.

L1А. (с®Р) || (с®Q)=с®(Р || Q).

L1B. (с®Р) || (d®Q)=СТОП.

L2А. (a®Р) || (с®Q)=a®(Р || (с®Q)).

L2B. (с®Р) || (b®Q)=b®((с®Р) || Q)..

L3. (a®Р) || (b®Q)=.(a®(Р || (b®Q)) | b®((a®Р) || Q)).

Эти законы можно обобщить для общего случая оператора выбора:

L3. Пусть Р = (х: А ® Р(х)), Q = (y: B ® Q(y)).

Тогда Р || Q = (z: C ® (Р' || Q')), где С = (A З B) И (А - aQ) И (B - aP),,

P' = P(z), если z О A, иначе P' = Р, а Q' = Q(z), если z О B, иначе Q' = Q.

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

aР = {a, c}, aQ = {b, c}, P = (a ® c ® P), Q = (c ® b ® Q).

Тогда Р || Q = (a ® c® P) || (c ® b ® Q) = a ® ((c®P) || (c®b®Q))

по L2A

= a ® c ® (P || (b®Q)) по L1A (1)

а (P || (b®Q)) = a ® ((c®P) || (b®Q)) | b ® (P || Q)

по L3

= a ® b ® ((c® P) || Q) | b® (P || Q)

по L2B

= a ® b ® c ® (P || (b®Q)) | b®a®c®(P||(b®Q))

по L1A и (1)

= mX.(a® b®c®X | b®a®c®X).

Отсюда следует, что

Р || Q = a ® c ® mX.(a ® b ® c ® X | b ® a ® c ® X). по (1)

3.2.2.2 Реализация

Реализация операции || выводится непосредственно из закона L3. Алфавиты операндов представляются конечными списками символов A и B.

3.2.3 Протоколы

Пусть t -- протокол (Р || Q). Тогда все события из t, принадлежащие алфавиту aР, являлись событиями в жизни P. а все события из t, не принадлежащие aР, происходили без участия P. Таким образом, (t ­ aР) -- это протокол всех событий, в которых участвовал процесс P, и поэтому он является протоколом P. По тем же соображениям (t ­ aQ) является протоколом Q. Более того, каждое событие из t должно содержаться либо в aР, либо в aQ. Эти рассуждения позволяют сформулировать закон

L1. Протоколы (Р || Q) = {t | (t­aР)О протоколы(Р) AND (t­aQ)О протоколы(Q) AND t О (aР И aQ)^*}.

3.2.3 Задача об обедающих философах

Рассмотрим ещё одну трактовку задачи предложенной Дейкстрой об обедающих философах. В некоем пансионе нашли пристанище пять философов. У каждого философа была своя комната. Была у них и общая столовая с круглым столом, вокруг которого стояли пять стульев. В центре стола стояла большая миска спагетти, содержимое которой постоянно пополнялось. На столе также лежало пять вилок, по одной между соседними посадочными местами.

Звали философов ФИЛ0, ФИЛ1, ФИЛ2, ФИЛ3, ФИЛ4 и за столом они располагались в этом же порядке, против часовой стрелки. Почувствовав голод, философ шёл в столовую, садился на свой стул, брал сначала слева от себя вилку, затем справа и приступал к еде. Закончив трапезу, он клал на место обе вилки, выходил из-за стола, и уходили размышлять.

3.2.3.1 Алфавиты

Теперь построим математическую модель этой системы. Сначала надо выбрать множества событий. Для ФИЛi определим это множество как

программа схема данное стандартный

aФИЛi = {i.садится, i.встаёт, i.берет вил.i, i.берет вил.(i +5 1), i.кладёт вил.i, i.кладёт вил.(i +5 1)},

где +5 -- сложение по модулю 5.

Заметим, что алфавиты философов друг с другом не пересекаются, а возможность взаимодействия между ними исключена.

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

aВИЛКАi = {i.берет вил.i, (i -5 1).берет вил.i, i.кладёт вил.i, (i -5 1).кладёт вил.i},

где -5 обозначает вычитание по модулю 5.

Таким образом, каждое событие, кроме садится и встает, требует участия двух соседних действующих лиц -- философа и вилки.

3.2.3.2 Поведение

Жизнь каждого философа представляет собой повторение цикла из шести событий:

ФИЛ_i = (i.садится ® i.берет вил.i ® i.берет вил.(i +₅ 1) ® i.кладет вил.i ®

® i.кладет вил.(i +₅ 1) > i.встаёт ®ФИЛ_i).

Вилку циклически берёт и кладёт на место кто-нибудь из соседних с ней философов:

ВИЛКА_i = (i.берет вил.i, ® i.кладёт вил.i ® ВИЛКА_i | (i -₅ 1).берет вил.i ® (i -₅ 1).кладёт вил.i ® ВИЛКА_i).

Поведение всего пансиона можно описать как параллельную комбинацию поведения компонент:

ФИЛОСОФЫ = (ФИЛ0 || ФИЛ1 || ФИЛ2 || ФИЛ3 || ФИЛ4 )

ВИЛКИ = (ВИЛКА0 || ВИЛКА1 || ВИЛКА2 || ВИЛКА3 || ВИЛКА4 )

ПАНСИОН = (ФИЛОСОФЫ || ВИЛКИ).

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

aЛЕВАЯ_i = {i.садится, i.встаёт, i.берет вил.i, i.кладёт вил.i}.

aФИЛ_i = {i.садится, i.встаёт, i.берет вил.(i +₅ 1), i.кладёт вил.(i +₅ 1)}.

ЛЕВАЯ_i = (i.садится ® i.берет вил.i ® i.кладет вил.i ® i.встаёт ® ЛЕВАЯ_i).

ПРАВАЯ_i = (i.садится ® i.берет вил.(i +₅ 1) ® i.кладет вил.(i +₅ 1) ® i.встаёт ® ПРАВАЯ_i).

ФИЛ_i = (ЛЕВАЯ_i || ПРАВАЯ_i ).

Синхронизацией процессов ЛЕВАЯi и ПРАВАЯi в момент, когда i-тый философ садится или встаёт (посредством общих событий), достигается то, что он не может поднимать вилки, если не сидит за столом, и не может встать из-за стола, пока не положит вилки.

3.2.3.3 Тупик

Построенная математическая модель первого варианта системы позволяет обнаружить опасность возникновения тупиковой ситуации, когда каждый из философов возьмёт вилку в левую руку. Одним из решений этой проблемы явилось введение в систему слуги. Слуге даётся указание следить за тем, чтобы за столом никогда не оказывалось больше четырех философов одновременно. Алфавит его определяется как C ? B, где

C = {0.садится, … , 4.садится }, B = {0.встаёт, … , 4.встаёт}.

Поведение слуги проще всего описать с помощью взаимной рекурсии. Пусть СЛУГАj определяет поведение слуги, когда за столом сидят j философов:

СЛУГА₀ =(x: C ® СЛУГА₁),

СЛУГА_j =(x: C ® СЛУГА_j+1) | y: B ® СЛУГА_j-1),

jО{1,2.3}.

СЛУГА₄ =(y: B ® СЛУГА₃).

Пансион, свободный от тупика, определяется как НОВПАНСИОН = ((ПАНСИОН || СЛУГА₀).

3.2.3.4 Доказательство беступиковости

Докажем утверждение, что НОВПАНСИОН свободен от тупиков. Для этого достаточно доказать, что любой протокол s этой системы можно продолжить некоторым событием так, что бы снова получить протокол этой же системы. Строго, это можно сформулировать как

?"s, $z (sОпротоколы(НОВПАНСИОН) AND zОaНОВПАНСИОН Ю s^z О протоколы(НОВПАНСИОН)).

Доказательство можно осуществлять двумя способами:

Первый из них предполагает применение (насколько это возможно) приведённых выше законов.

Второй способ доказательства состоит в составлении компьютерной программы для исследования протоколов системы в поисках тупика. Такая программ сможет дать интересующий нас ответ за конечное время, если система имеет конечное число состояний, как в нашем случае НОВПАНСИОН. Достаточно рассмотреть только те протоколы, длина которых не превышает известной верхней границы числа состояний. (Каждому протоколу соответствует некоторое состояние системы, в которое систему приводит из начального состояния последовательность событий, описываемая этим протоколом.)

Число состояний в системе НОВПАНСИОН не превышает 1,8 млн. Но, т. к. в каждом состоянии возможны не меньше двух событий, то количество протоколов, которые надо проверить, будет превышать два в степени 1,8 млн. Трудно представить, что компьютер, когда-нибудь сумеет исследовать все возможные случаи. Таким образом, доказательство отсутствия тупиковых ситуаций, как правило, входит в обязанности разработчика параллельных систем.

3.2.3.5 Бесконечный перехват

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

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

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

3.2.4 Помеченные процессы

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

Процесс P с меткой l обозначают где l: P. Он участвует в событии l.x, когда по определению P участвует в х.

Пример 3.18. Два работающих рядом торговых автомата

(лев: ТАП) || (прав: ТАП)

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

3.2.5 Множественная пометка

Определение пометки можно расширить, позволив помечать каждое событие любой меткой l из некоторого множества L. Если P - процесс, определим (L. : P) как процесс, ведущий себя в точности как P с той разницей, что он участвует в событии l.x (где l О L, xОa P ), если по определению P участвует в х.

Пример 3.19. Лакей - это младший слуга, который имеет одного хозяина, провожает его к столу и из-за стола и прислуживает ему, пока тот ест:

aЛАКЕЙ = {садится, встает}

ЛАКЕЙ = (садится > встает > ЛАКЕЙ)

Лакей обслуживающего всех пятерых философов по очереди определим:

L = {0, 1, 2, 3, 4}

ОБЩИЙ ЛАКЕЙ = (L: ЛАКЕЙ )

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

3.3 Взаимодействие - обмен сообщениями

В предыдущих разделах было введено и проиллюстрировано общее понятие события как действия, не имеющего протяженности во времени, наступление которого может требовать одновременного участия более чем одного независимо описанного процесса. В этом разделе внимание будет сосредоточено на одном специальном классе событий, называемых взаимодействиями. Взаимодействие состоит в передаче сообщений и является событием, описываемым парой c.v, где c - имя канала по которому происходит взаимодействие, а v - значение передаваемого сообщения. Такое обозначение мы уже использовали - это описание процесса КОПИБИТ (см. пример 3.3).

Различают следующие виды каналов:

· Синхронные. Отправив сообщение, передающий процесс ожидает от принимающего подтверждение о приеме сообщения прежде, чем послать следующее сообщение, т.е. принимающий процесс не выполняется, пока не получит данные, а передающий - пока не получит подтверждение о приеме данных.

· Асинхронно/синхронные. Операция передачи сообщения асинхронная - она завершается сразу (сообщение копируется в некоторый буфер, а затем пересылается одновременно с работой процесса-отправителя), не ожидая того, когда данные будут получены приемником. Операция приема сообщения синхронная: она блокирует процесс до момента поступления сообщения.

· Асинхронные. Обе операция асинхронные, то есть они завершаются сразу. Операция передачи сообщения работает, как и в предыдущем случае. Операция приема сообщения, обычно, возвращает некоторые значения, указывающие на то, как завершилась операция - было или нет принято сообщение. В некоторых реализациях операции обмена сообщениями активируют сопроцессы, которые принимают/отправляют сообщения, используя временные буфера и соответствующие синхронные операции. В этом случае имеется еще синхронизирующая операции, которая блокирует процесс до тех пор, пока не завершатся все инициированные операции канала.

Множество всех сообщений, с помощью которых Р может осуществлять взаимодействие по каналу с, определяется как

aс(Р) = {v | c.v О aP}.

Кроме того, определены функции, выбирающие имя канала канал(c.v) = c и значение сообщения сообщ(c.v) = v.

Каналы используются для передачи сообщений только в одном направлении и только между двумя процессами.

3.3.1 Ввод и вывод

Пусть v - элемент с(Р). Процесс, который сначала выводит v по каналу с, а затем ведет себя как Р, обозначим

(с ! v > P) = (c.v > P).

Единственное событие, к которому этот процесс готов в начальном состоянии. - это взаимодействие c.v.

Процесс, который сначала готов ввести любое значение х, предаваемое по каналу с, а затем ведет себя как Р(х), обозначим

(с ? v > P(х)) = (у: {y | канал(у) = c} > P(сообщ(у))).

Пусть P, Q - процессы, с - выходной канал P и входной канал Q. Если P, Q объединены в параллельную систему (P || Q), то взаимодействие по каналу с будет происходить всякий раз, когда P выводит сообщение, а Q в тот же самый момент вводит его. Выводящий процесс однозначно определяет значение передаваемого сообщения, тогда как вводящий процесс готов принять любое поступающее значение. Поэтому в действительности происходящим событием будет взаимодействие c.v, где v - значение. Определяемое выводящим процессом. Отсюда вытекает очевидное ограничение, что алфавиты на обоих концах канала должны совпадать, т.е. aс(Р) = aс(Q).

Пример 3.20. Процесс, копирующий каждое сообщение, поступающее слева, выводя его направо:

aлев(КОПИР) = aправ(КОПИР)

КОПИР = µХ.(лев ? х > прав ! х >Х).

Если aлев = {0, 1}, то КОПИР почти полностью совпадает с КОПИБИТ.

Пример 3.21. Процесс, похожий на КОПИР, с той разницей, что каждое вводимое число перед выводом удваивается:

aлев = aправ = Nat

УДВ = µХ.(лев ? х > прав ! (х + х) >Х).

Пример 3.22. Процесс, принимающий сообщение по одному из двух каналов лев1 и лев2 и немедленно передающий его направо:

aлев1 = aлев2 = aправ

СЛИЯНИЕ = (лев1 ? х > прав ! х > СЛИЯНИЕ | лев2 ? х > прав ! х > СЛИЯНИЕ).

3.3.2 Взаимодействия

Пусть P, Q - процессы, с - выходной канал P и входной канал Q. Тогда множество, состоящее из событий-взаимодействий c.v, содержится в пересечении алфавита P с алфавитом Q. Если процессы объединены в параллельную систему (P || Q), то взаимодействие c.v может происходить только когда в этом событии одновременно участвуют оба процесса, т.е. в тот момент, когда P выводит значение v по каналу c, а Q одновременно вводит это значение. Вводящий процесс готов принять любое возможное поступающее сообщение, и поэтому то, какое именно значение передается, определяет выводящий процесс.

Таким образом, вывод можно рассматривать как специальный случай операции префиксации, а ввод - как специальный случай выбора.

L1. (с ! v > P) || (с ? x > Q(x)) = с ! v > (P || Q(v)).

3.3.3 Подчинение

Пусть P, Q - процессы, такие, что aР Н aQ. В комбинации (P || Q) каждое действие Р может произойти, только если это позволяет Q, тогда как Q может независимо осуществлять действия из (aР - aQ) без разрешения и даже без ведома партнера Р. Таким образом, Р служит по отношению к Q подчиненным процессом, тогда как Q выступает как главный процесс. Это записывается так:

Р // Q. Отсюда: a(Р // Q) = (aР - aQ).

Обычно бывает удобно давать подчиненному процессу имя, скажем m, которое используется главным процессом для всех взаимодействий с подчиненным. Каждое взаимодействие по каналу с обозначается тройкой m.c.v, где

am.c(m : P) = aс(Р), а v О aс(Р).

В конструкции (m : P // Q) процесс Q взаимодействует с P по каналам с составными именами вида m.c, тогда как P для этих же взаимодействий использует соответствующий простой канал с. Так как все эти взаимодействия скрыты от обстановки, имя m недоступно снаружи; следовательно, оно служит локальным именем подчиненного процесса.

Подчинение может быть вложенным, например (n : (m : P//Q)//R). Процесс R не имеет возможности ни непосредственно взаимодействовать с P, ни знать о существовании P и его имени m.

Пример 3.23. удв: УДВ // Q.

Подчиненный процесс ведет себя как обыкновенная подпрограмма, вызываемая внутри главного процесса Q. Внутри Q значение 2?е может быть получено поочередным выводом аргумента е по левому каналу процесса удв и вводом результата по правому каналу:

удв.лев ! е > (удв.прав ? х > …).

Пример 3.22. ст : СТЕК // Q.

Внутри главного процесса Q ст.лев!v используется для проталкивания в верхушку стека, а ст.прав?x выталкивает верхнее значение. Использование конструкции выбора позволяет рассматривать ситуацию, когда стек пуст:

(ст.прав ? x > Q1(х) | ст.пуст > Q2)

Если стек не пуст, то выбирается первая альтернатива; если пуст, то выбор второй альтернативы позволяет избежать тупика.

Оператор подчинения может использоваться для рекурсивного определения подпрограмм. Каждый уровень рекурсии (кроме последнего) задает новую локальную подпрограмму, работающую с рекурсивным вызовом.

Пример 3.24.

ФАКТ = µХ.лев?n > (if n = 0 then (прав!1 > X) else (f: X // (f.лев!(n - 1) > f.прав?y > прав!(nґy) > X))

Программа ФАКТ использует каналы лев и прав для обмена результатами и параметрами с вызывающим ее процессом, а каналы f.лев и f.прав - для взаимодействия со своим подчиненным процессом f.

3.4 Разделяемые ресурсы

Обозначение (m://S) мы использовали для именованного подчиненного процесса (m:R), единственной обязанностью которого является удовлетворение потребностей главного процесса S. Предположим теперь, что S состоит из двух параллельных процессов (P || Q) и они оба нуждаются в услугах одного и того же подчиненного процесса (m :R). К сожалению, P и Q не могут взаимодействовать с R по одним и тем же каналам, потому что тогда эти каналы должны содержаться в алфавитах обоих процессов, и, значит, согласно определению оператора ||, взаимодействия с (m : R) могут происходить, только когда P и Q одновременно посылают одно и то же сообщение, что далеко не соответствует желаемому результату. Нам же требуется своего рода чередование взаимодействий между P и (m:R) с взаимодействиями между Q и (m:R). В этом случае (m:R) служит как ресурс, разделяемый P и Q; каждый из них использует его независимо, и их взаимодействия с ним чередуются.

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

3.4.1 Поочередное использование

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

Пример 3.25. Совместно используемая подпрограмма: удв : УДВ // (P ||| Q).

Здесь и P, и Q могут содержать вызов подчиненного процесса

(удв.лев!v > удв.прав?х > ПРОПУСК),

где ПРОПУСК - процесс, который ничего не делает, но благополучно завершается.

Пример 3.26. Совместно используемое алфавитно-цифровое печатающее устройство:

АЦПУ = занят > µХ.(лев?s > h!s > X | свободен > АЦПУ)

Здесь h - канал, соединяющий АЦПУ с аппаратной частью устройства. После наступления события занят АЦПУ копирует в аппаратную часть последовательно поступающие по левому каналу строки, пока сигнал свободен не приведет его в исходное состояние, в котором он доступен для использования другими процессами. Этот процесс используется как разделяемый ресурс:

ацпу: АЦПУ // … (P ||| Q)…

Внутри P или Q вывод последовательности строк, образующей файл, заключен между событиями ацпу.занят и ацпу.свободен:

ацпу.занят > … ацпу.лев!”Вася” >… ацпу.лев!следстр > … ацпу.свободен

3.4.2 Общая память

Цель этого раздела - привести ряд аргументов против использования общей памяти.

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

Ячейка общей памяти - это разделяемая переменная:

(счет : ПЕРЕМ // (счет.лев!0 > (P ||| Q))).

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

Пример 3.27. Взаимное влияние.

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

счет.прав?х; счет. лев! (х + 1)

К сожалению, эти два взаимодействия могут перемежаться аналогичной парой взаимодействий от другого процесса, в результате чего мы получим последовательность

счет.прав?х > счет.прав?у > счет.лев!(у + 1) > счет.лев!(х+ 1) >...

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

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

Более приемлемое решение было предложено Э. Дейкстрой, которому принадлежит идея использования двоичных семафоров. Семафор можно описать как процесс, поочередно выполняющий действия с именами Р и V;

СЕМ = (Р > V > СЕМ)

Он описывается как совместно используемый ресурс (взаискл: СЕМ // ...).

При условии, что все процессы подчиняются этой дисциплине, каждый из двух процессов не сможет влиять на изменение счетчика -- произвести действие взаискл.V. Таким образом, критический участок, на котором происходит увеличение счетчика, должен иметь вид

взаискл. Р > счет.прав?х > счет.лев!(х + 1) > взаискл.V > ...

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

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

счет:СТ0 //(...Р |||.Q..)

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

3.4.3 Кратные ресурсы

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

Мы будем использовать индексы и операторы с индексами, смысл которых очевиден. Например:

В последнем примере мы требуем, чтобы f была взаимно однозначной для того, чтобы выбор между альтернативами осуществлялся обстановкой.

Пример 3.28. Повторно входимая подпрограмма

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

yдв: (УДВ)) //…

Типичным вызовом этой подпрограммы будет

(удв.3.лев!30 > удв.3.прав?у > ПРОПУСК)

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

удв.3.лев.30,...удв.2.лев.20,... удв.3.прав.60,... удв.2.прав.40,...

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

(удв.i.лев!30 > удв.i.прав?у > ПРОПУСК)