Теория вычислительных процессов |
Лекция 10 |
Лекция 10
3.2. Параллельные процессы
Процесс определяется полным описанием его потенциального поведения. При этом часто имеется выбор между несколькими различными действиями. В каждом таком случае выбор того, какое из событий произойдет в действительности, может зависеть от окружения, в котором работает процесс. Само окружение процесса может быть описано как процесс, поведение которого определяется в уже знакомых терминах. Это позволяет исследовать поведение целой системы, состоящей из процесса и его окружения, взаимодействующих по мере их параллельного исполнения. Всю систему также следует рассматривать как процесс, поведение которого определяется в терминах поведения составляющих его процессов. Эта система в свою очередь может быть помещена в еще более широкое окружение, и т.д.
Объединяя два процесса для совместного исполнения, как правило, хотят, чтобы они взаимодействовали друг с другом. Эти взаимодействия можно рассматривать как события, требующие одновременного участия обоих процессов.
3.2.1.1. Законы
Законы, управляющие поведением (P || Q), параллельно развивающихся процессов P и Q, достаточно просты. Первый закон выражает логическую симметрию между процессом и его окружением:
Ll. P||Q=Q||P.
Следующий закон показывает, что при совместной работе трех процессов неважно, в каком порядке они объединены оператором параллельной композиции:
L2. P || (Q || R) = (P || Q) || R.
Процесс, находящийся в тупиковой ситуации, приводит к тупику всей системы.
L3. P || СТОП
άР = СТОПάР.Следующий закон гласит, что пара процессов с одинаковыми алфавитами либо одновременно выполняет одно и то же действие, либо попадает в состояние тупика, если начальные события процессов не совпадают:
L4A. (с -> Р) || (c -> Q) = c -> (P || Q).
L4B. (c -> Р) || (d -> Q) = стоп.
Рассмотрим случай, когда операнды P и Q оператора || имеют неодинаковые алфавиты Р <>
Q.
Когда такие процессы объединяются для совместного исполнения, события, содержащиеся в обоих алфавитах, требуют одновременного участия P и Q. События же из алфавита P, не содержащиеся в алфавите Q, не имеют никакого отношения к Q, который физически неспособен ни контролировать, ни замечать такие события. Такие события процесса P могут происходить независимо от Q. Аналогично Q может самостоятельно участвовать в событиях, содержащихся в его алфавите, но отсутствующих в алфавите Р.
Таким образом, множество всех событий, логически возможных для данной системы, есть просто объединение алфавитов составляющих ее процессов
(Р || Q)=
P U
Q.
Формальное описание вышесказанного осуществляется с помощью следующих законов:
Пусть а (
P -
Q), b
(
Q -
Р) и {с, d}
(
P ∩
Q). Следующие законы показывают, каким образом процесс P один участвует в событии а, Q один участвует в b, а с и d требуют одновременного участия P и Q.
L1A. (c->P) || (c->Q)=c->(P || Q).
LlВ. (c->P) || (d->Q)=СТОП
L2A. (a->P) || (c->Q)=a->(P || (c->Q)).
L2B. (c->P) || (b->Q)=b->((c->P) || Q)..
L3. (a->P) || (b->Q)=.(a->P || (b->)) | b->((a->P) || )).
эти законы можно обобщить для общего случая оператора выбора:
L3. Пусть P = (х: А -> P(х)), Q = (у: В -> Q(y)).
Тогда
P || Q = (z: С -> (Р' || Q’)), где С = (А ∩ В) U (А - Q) U (В -
Р),
P' = P(z), если z А, иначе Р' = Р, а Q’ = Q(z), если z
В, иначе Q’ = Q.
с помощью этих законов можно переопределить процесс, удалив из его описания параллельный оператор, как это показано в следующем примере.
Пример 3.17.
Пусть P= {a, е},
Q= {b, c}, P=(a-> с ->P), Q=(c -> b -> Q).
Тогда
P|| Q=(a->c->P) || (c -> b -> Q)=a -> ((c->P) || (c->b->Q)) по L2A
= а -> с -> (Р || (b->Q)), по LlА и (1)
а (P || (b->Q)) = а -> ((c->P) || (b->Q)) | b -> (Р || Q) по L3
= а -> b -> ((c-> Р) || Q) | b-> (Р || Q) по L2B
= а -> b -> с -> (P || (b->Q)) | b->a->c->(P||(b->Q))
=
μX(a-> b->c->X | b->a->c->X). по L1A и (1)Отсюда следует, что
P|| Q=a-> c-> μX.(a-> b -> с -> Х | b -> а -> с -> Х). по (1)
Реализация операции || выводится непосредственно из закона L3. Алфавиты операндов представляются конечными списками символов A и В.
Пусть t - протокол (P || Q). Тогда все события из t, принадлежащие алфавиту P, являлись событиями в жизни P, а все события из t, не принадлежащие
Р, происходили без участия Р. Таким образом, (t ↑
Р) - это протокол всех событий, в которых участвовал процесс Р, и поэтому он является протоколом Р. По тем же соображениям (t ↑
Q) является протоколом Q. Более того, каждое событие из t должно содержаться либо в
P, либо в
Q. эти рассуждения позволяют сформулировать закон
Ll. протоколы(P || Q) = {t | (t↑P)
протоколы(Р)
AND (t↑Q)
протоколы(Q) AND t ↑ (
Р U
Q)*}.
Рассмотрим ещё одну трактовку задачи, предложенной Дейкстрой об обедающих философах. В некоем пансионе нашли пристанище пять философов. У каждого философа была своя комната, где он мог предаваться размышлениям. Была у них и общая столовая с круглым столом, вокруг которого стояли пять стульев, каждый помеченный именем того философа, которому он предназначался. В центре стола стояла большая миска спагетти, содержимое которой постоянно пополнялось. На столе также лежало пять вилок, по одной между соседними посадочными местами.
Звали философов ФИЛ0, ФИЛ1, ФИЛ2, ФИЛ3, ФИЛ4 и за столом они располагались в этом же порядке, против часовой стрелки. Почувствовав голод, философ шёл в столовую, садился на свой стул, брал сначала слева от себя вилку, затем справа и приступал к еде. Закончив трапезу, он клал на место обе вилки, выходил из-за стола, и возвращался к своим размышлениям. Разумеется, одной вилкой философы могли пользоваться только по очереди. Если вилка требовалась другому философу, ему приходилось ждать, пока она освободится.
Теперь построим математическую модель этой системы. Сначала надо выбрать множества событий. Для ФИЛi определим это множество как
ФИЛ; = {i.садится, i.встаёт, i.берет вил.i, i.берет вил.(i +51),
i. кладёт вил. i, i. кладёт вил. (i +5 l)},
где +5 - сложение по модулю 5.
Заметим, что алфавиты философов друг с другом не пересекаются, а возможность взаимодействия между ними исключена.
Другие “действующие лица” - это пять вилок, каждая из которых имеет тот же номер, что и философ, которому она принадлежит. Вилку берет и кладет на место или сам этот философ, или его сосед слева. Алфавит i-й вилки определим как
ВИЛКАi= {i.берет вил.i, (i -5 1).берет вил.i, i.кладёт вил.i,
(i -5 1).кладёт вил.i},
где -5 - обозначает вычитание по модулю 5.
Таким образом, каждое событие, кроме садится и встает, требует участия ровно двух соседних действующих лиц - философа и вилки.
Помимо не учитываемых нами процессов размышления и еды, жизнь каждого философа представляет собой повторение цикла из шести событий:
ФИЛi = (i.садится -> i.берет вил.i -> i.берет вил.(i +5 1)->
i.кладет вuл.i -> i.кладет вuл.(i +51) à i.встаёт à ФИЛi).
Вилку циклически берёт и кладёт на место кто-нибудь из соседних с ней философов:
ВИЛКАi = (i.берет вил.i, -> i.кладёт вил.i -> ВИЛКАi | (i -5 1).берет вил .i->
(i -5 1 ).кладёт вил. i -> ВИЛКАi.
Поведение всего пансиона можно описать как параллельную комбинацию поведения компонент:
ФИЛОСОФЫ = (ФИЛ0 // ФИЛ1 || ФИЛ2|| ФИЛ3|| ФИЛ4)
ВИЛКИ = (ВИЛКА0 || ВИЛКА1 || ВИЛКA2 || ВИЛКА3 || ВИЛКA4)
ПАНСИОН = (ФИЛОСОФЫ || ВИЛКИ).
В одном из интересных вариантов этой историй философы могут брать и класть обе вилки в любом порядке. Рассмотрим поведение каждой руки философа в отдельности.
ЛЕВAЯi = {i.садится, i.встаёт, i.берет вил.i, i.кладёт вил.i}.
ФИЛi = {i.садится, i.встаёт, i.берет вил.(i +5 1), i.кладёт вил.(i +5 1)}.
ЛЕВAЯi = (i.садится -> i.берет вил.i -> i.кладет вил.i -> i.встаёт->ЛЕВАЯi).
ПРАВАЯi = (i.садится -> i.берет вил.(i +51) -> i.кладет вил.(i +5 1)->
i.встаёт -> ПРАВАЯi).
ФИЛi = (ЛЕВАЯi || ПРАВАЯi).
Синхронизацией процессов ЛЕВАЯi и ПРАВАЯi в момент, когда i-тый философ садится или встаёт, достигается то, что он не может поднять вилку, если не сидит за столом, и не может встать из-за стола, пока не положит вилку. Помимо этого, операции с обеими вилками произвольно чередуются.
Построенная математическая модель позволяет обнаружить опасность возникновения тупиковой ситуации, когда каждый из философов, сев за стол, возьмёт вилку в левую руку и потянется за второй, которой уже нет на месте. Несмотря на то, что каждый из участников способен к дальнейшим действиям, ни одна пара участников не в состоянии договориться о том, какое действие совершить следующим.
Одним из решений этой проблемы явилось введение в систему слуги. Слуге даётся указание следить за тем, чтобы за столом никогда не оказывалось больше четырех философов одновременно. Алфавит его определяется как С UВ, где
С = {0.садится, ... , 4.садится}, В = {0.встаёт, ... , 4.встаёт}.
Поведение слуги проще всего описать с помощью взаимной рекурсии. Пусть СЛУГАj определяет поведение слуги, когда за столом сидят j философов:
СЛУГА0 =(х: С -> СЛУГА1),
СЛУГАj =(х: С -> СЛУГАj+i) | у: B -> СЛУГАj-i), для j {1,2.3}.
СЛУГА4 =(у: В -> СЛУГА3).
Пансион, свободный от тупика, определяется как
НОВПАНСИОН = ((ПАНСИОН || СЛУГА0).
3.2.3.4. Доказательство беступиковости
Докажем утверждение, что НОВПАНСИОН свободен от тупиков. Для этого достаточно доказать, что любой протокол s этой системы можно продолжить некоторым собьтием так, что бы снова получить протокол этой же системы. Строго, это можно сформулировать как . .
s,
z (s
протоколы(НОВПАНСИОН) AND z
НОВПАНСИОН =>
s^z протоколы(НОВПАНСИОН).
Доказательство можно осуществлять двумя способами.
Первый из них предполагает применение (насколько это возможно) приведённых выше законов.
Второй способ доказательства состоит в составлении компьютерной программы для исследования протоколов системы в поисках тупика. Такая программа сможет дать интересующий нас ответ за конечное время, если система имеет конечное число состояний, как в нашем случае НОВПАНСИОН. Достаточно рассмотреть только те протоколы, длина которых не превышает известной верхней границы числа состояний. (Каждому протоколу соответствует некоторое состояние системы, в которое систему приводит из начального состояния последовательность событий, описываемая этим протоколом.)
Число состояний в системе НОВПАНСИОН не превышает 1,8 млн. Но, т. к. в каждом состоянии возможны не меньше двух событий, то количество протоколов, которые надо проверить, будет превышать два в степени 1,8 млн. Трудно представить, что компьютер когда-нибудь сумеет исследовать все возможные случаи. Таким образом, доказательство отсутствия тупиковых ситуаций, как правило, входит в обязанности разработчика параллельных систем.
Помимо тупика обедающего философа подстерегает опасность бесконечного перехвата инициативы. Предположим, что левая рука у сидящего философа сочень медлительна, в то время как его левый сосед очень проворен. .
Всякий раз, когда философ пытается дотянуться до своей левой вилки, его левый сосед мгновенно перехватывает ее. Таким образом, может оказаться, что сидящий философ никогда не приступит к еде.
При строгом подходе эта проблема неразрешима. Однако, если важно гарантировать, чтобы сидящий философ смог поесть, нужно изменить поведение слуги: проводив философа до его места, он ждет, пока философ не возьмет обе вилки, и только после этого позволяет есть его соседям.
Таким образом, добиваться, чтобы любое желаемое и возможное событие обязательно наступило в пределах разумного интервала времени, становится задачей реализатора системы.
Помечать процессы особенно полезно при создании групп сходных процессов, которые в режиме параллельной работы представляют некоторые идентичные услуги их общему окружению, но никак не взаимодействуют друг с другом. Это означает, что все они должны иметь взаимно непересекающиеся алфавиты. Чтобы этого достичь, снабдим каждый процесс отдельным именем; каждое событие помеченного процесса помечено тем же именем. Помеченное событие l.х, где х - его имя, а l - метка.
Процесс P с меткой l обозначают l: Р. Он участвует в событии l.х, когда по определению P участвует в х.
Пример 3.18. Два работающих рядом торговых автомата
(лев: ТАП) || (прав: ТАП).
Алфавиты этих процессов не пресекаются, и каждое происходящее событие помечено именем того устройства, на котором оно происходит. Если перед их параллельной установкой устройства не получили имен, каждое событие будет требовать участия их обоих, и тогда пара машин будет неотличима от одной. Это является следствием того, что (ТАП || ТАП) = ТАП
Пометка позволяет использовать процессы наподобие локальных переменных в языке высокого уровня, описанных в том блоке программы, где они используются.
Определение пометки можно расширить, позволив помечать каждое событие любой меткой l из некоторого множества L. Если P - процесс, определим(L : Р) как процесс. ведущий себя в точности как P с той разницей, что он участвует в событии l.x (где l L, x
Р), если по определению P участвует в х.
Пример 3.19. Лакей - это младший слуга, который имеет одного хозяина, провожает его к столу и из-за стола и прислуживает ему, пока тот ест:
ЛАКЕЙ = {садится, встает}
ЛАКЕЙ = (садится ->встает -> ЛАКЕЙ)
Лакея, обслуживающего всех пятерых философов по очереди определим: L = {0, 1,2,3, 4}
ОБЩИЙ ЛАКЕЙ = (L: ЛАКЕЙ)
Общего лакея можно нанимать на период отпуска слуги для предохране-ния обедающих философов от тупиковой ситуации. Конечно, в течение этого времени философам придется поголодать, ибо находиться за столом они смогут только по очереди.
назад | содержание | вперед