Параллельные процессы
Процесс определяется полным описанием его потенциального поведения. При этом часто имеется выбор между несколькими различными действиями. В каждом таком случае выбор того, какое из событий произойдет в действительности, может зависеть от окружения, в котором работает процесс. Само окружение процесса может быть описано как процесс, поведение которого определяется в уже знакомых терминах. Это позволяет исследовать поведение целой системы, состоящей из процесса и его окружения, взаимодействующих по мере их параллельного исполнения. Всю систему также следует рассматривать как процесс, поведение которого определяется в терминах поведения составляющих его процессов. Эта система в свою очередь может быть помещена в еще более широкое окружение, и т.д.
Взаимодействие
Объединяя два процесса для совместного исполнения, как правило, хотят, чтобы они взаимодействовали друг с другом. Эти взаимодействия можно рассматривать, как события, требующие одновременного участия обоих процессов.
Законы
Законы, управляющие поведением (P || Q), параллельно развивающихся процессов P и Q, достаточно просты. Первый закон выражает логическую симметрию между процессом и его окружением:
L 1. P || Q = Q || P.
Следующий закон показывает, что при совместной работе трех процессов неважно, в каком порядке они объединены оператором параллельной композиции ||:
L 2. P || (Q || R) = (P || Q) || R.
|
|
|
Процесс, находящийся в тупиковой ситуации, приводит к тупику всей системы.
L 3. P || СТОП a P = СТОП a P.
Следующий закон гласит, что пара процессов с одинаковыми алфавитами либо одновременно выполняет одно и то же действие, либо попадает в состояние тупика, если начальные события процессов не совпадают:
L 4 А. (с 
Р) || (с Q) = с (Р || Q).
L 4 B. (с Р) || (d Q) = СТОП.
Параллелизм
Рассмотрим случай, когда операнды Р и Q оператора || имеют неодинаковые алфавиты a Р 
a Q.
Когда такие процессы объединяются для совместного исполнения, события, содержащиеся в обоих алфавитах, требуют одновременного участия Р и Q. События же из алфавита Р, не содержащиеся в алфавите Q, не имеют никакого отношения к Q, который физически неспособен ни контролировать, ни замечать такие события. Такие события процесса P могут происходить независимо от Q. Аналогично Q может самостоятельно участвовать в событиях, содержащихся в его алфавите, но отсутствующих в алфавите Р.
Таким образом, множество всех событий, логически возможных для данной системы, есть просто объединение алфавитов составляющих ее процессов a(Р || Q) = a Р 
a Q.
Законы
Формальное описание вышесказанного осуществляется с помощью следующих законов:
|
|
|
Пусть а 
(a Р - a Q), b (a Q - a Р) и { c, d } (a Р 
a Q). Следующие законы показывают, каким образом процесс Р один участвует в событии a, Q один участвует в b, а c и d требуют одновременного участия P и Q.
L 1 А. (с Р) || (с Q)= с (Р || Q).
L 1 B. (с Р) || (d Q)= СТОП.
L 2 А. (a Р) || (с Q)= a (Р || (с Q)).
L 2 B. (с Р) || (b Q)= b ((с Р) || Q)..
L 3. (a Р) || (b Q)=.(a (Р || (b Q)) | b ((a Р) || Q)).
Эти законы можно обобщить для общего случая оператора выбора:
L 3. Пусть Р = (х: А Р (х)), Q = (y: B Q (y)). Тогда
Р || Q = (z: C (Р ' || Q ')),
где С = (A B) (А - a Q) (B - a P), P ' = P (z), если z A, иначе P ' = Р, а Q ' = Q (z), если z B, иначе Q ' = Q.
С помощью этих законов можно переопределить процесс, удалив из его описания, параллельный оператор, как это показано в следующем примере.
Пример 3.17.
Пусть a Р = { a, c }, a Q = { b, c }, P = (a c P), Q = (c b Q). Тогда
Р || Q = (a c P) || (c b Q) = a ((c P) || (c b Q)) по L 2 A
= a c (P || (b Q)), по L 1 A (1)
(P || (b Q)) = a ((c P) || (b Q)) | b (P || Q) по L 3
= a b ((c P) || Q) | b (P || Q)по L 2 B
= a b c (P || (b Q)) | b a c (P ||(b Q)) по L 1 A и (1)
= m X. (a b c X | b a c X).
Отсюда следует, что
Р || Q = a c m X. (a b c X | b a c X).по (1)
Реализация
Реализация операции || выводится непосредственно из закона L 3. Алфавиты операндов представляются конечными списками символов A и B.
Протоколы
Пусть t — протокол (Р || Q). Тогда все события из t, принадлежащие алфавиту a Р, являлись событиями в жизни P, а все события из t, не принадлежащие a Р, происходили без участия P. Таким образом, (t a Р) — это протокол всех событий, в которых участвовал процесс P, и поэтому он является протоколом P. По тем же соображениям (t a Q) является протоколом Q. Более того, каждое событие из t должно содержаться либо вa Р, либо в a Q. Эти рассуждения позволяют сформулировать закон
|
|
|
L 1. протоколы (Р || Q) = { t | (t a Р) протоколы (Р)
AND (t a Q) протоколы (Q) AND t (a Р a Q)*}.
Дата добавления: 2015-12-20; просмотров: 20; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!