|
часть глобального состояния системы.
Обозначим через E = Ei множество всех событий, происходящих при выполнении распределенной системы. Событие , такое что е = (Р, s, s', m, С), считается допустимым в глобальном состоянии S тогда и только тогда, когда (1) в глобальном состоянии S процесс Р находится в состоянии s и (2) если ребро, соответствующее каналу С, направлено к вершине с процессом Р, и сообщение m находится в канале С и может быть принято из него. Обозначим через e(S) глобальное состояние распределенной системы непосредственно после наступления события e в глобальном состоянии S. Состояние e(S) определено только в случае, если событие е допустимо в глобальном состоянии S. Тогда e(S) будет отличаться от состояния S только состоянием процесса Р и, возможно, состоянием канала С.
В глобальном состоянии e(S) процесс Р будет находиться в состоянии s'.
Если ребро, соответствующее каналу С, направлено к вершине с процессом Р, то в глобальном состоянии e(S) состояние канала С
будет совпадать с его состоянием в S за исключением сообщения m, удаленного из этого канала.
Если ребро, соответствующее каналу С, направлено от вершины с процессом Р, то в глобальном состоянии e(S) состояние канала С будет совпадать с его состоянием в S за исключением сообщения m, добавленного в этот канал.
Последовательность событий e0, e1, … ex, ex+1, … будем называть выполнением распределенной системы тогда и только тогда, когда событие ex допустимо в глобальном состоянии Sx, S0 – начальное глобальное состояние распределенной системы, и для каждого x ≥ 0 выполняется соотношение Sx+1 = ex(Sx). Выполнение всей распределенной системы будем обозначать через R. Глобальное состояние S называется достижимым в выполнении R, если для этой последовательности событий существует такое k ≥ 0, что ek(Sk) = S.
Для иллюстрации выполнения распределенной системы рассмотрим следующий пример передачи маркера (англ. token). Пусть распределенная система состоит из двух процессов Р1 и Р2 и двух каналов С12 и С21, см. рис. 2.1.
Рис. 2.1. Пример распределенной системы из двух процессов.
Маркер – это уникальный объект, который процессы передают друг другу с помощью сообщения. Каждый процесс может находиться в одном из двух состояний s или s', где s – состояние, в котором процесс не владеет маркером, а s' – состояние, в котором процесс обладает маркером. Пусть начальное состояние процесса Р1 – s', а начальное состояние процесса Р2 – s, т.е. маркер находится в процессе Р1. В каждом процессе могут происходить только два события: (1) событие отправки маркера по каналу с переходом процесса из состояния s' в состояние s и (2) событие получения маркера из канала с переходом процесса из состояния s в s'. Диаграмма переходов процесса из одного состояния в другое показана на рис. 2.2.
Рис. 2.2. Диаграмма состояний процесса.
Глобальные состояния распределенной системы и переходы между ними представлены на рис. 2.3. На этой диаграмме выполнению распределенной системы соответствует путь из начального глобального состояния S0 в одно из других глобальных состояний S. Примерами выполнения распределенной системы могут служить следующие последовательности событий: (1) пустая последовательность или (2) последовательность "Р1 отправляет маркер, Р2 получает маркер, Р2 отправляет маркер". Последовательность "Р1 отправляет маркер, Р2 отправляет маркер" не может являться выполнением распределенной системы, т.к. событие "Р2 отправляет маркер" недопустимо в глобальном состоянии, в котором Р2 находится в состоянии s.
Рис. 2.3. Глобальные состояния и переходы между ними.
В представленном выше примере передачи маркера в каждом глобальном состоянии распределенной системы допустимо ровно одно событие. Для иллюстрации недетерминированного выполнения распределенных систем рассмотрим систему с такой же топологией (см.
рис. 2.1), но в которой состояния процессов Р1 и Р2 и переходы между ними определяются согласно рис. 2.4. Начальное состояние процесса Р1 – s1, начальное состояние процесса Р2 – s2.
Рис. 2.4. Диаграмма состояний (а) процесса Р1 и (б) процесса Р2.
Пример выполнения такой системы показан на рис. 2.5. Легко видеть, что в некоторых глобальных состояниях допустимо более одного события и, соответственно, более одного перехода из этого глобального состояния.
Рис. 2.5. Глобальные состояния и переходы между ними.
Например, в начальном глобальном состоянии S0 могут произойти оба события "Р1 отправляет m" и "Р2 отправляет m' ". Важно отметить, что глобальные состояния, в которые система может перейти из состояния S0 при наступлении одного из этих событий, различны. А именно, при наступлении события "Р1 отправляет m" система перейдет из состояния S0 в состояние S1, в котором Р1 находится в состоянии s1', Р2 – в состоянии s2,
канал С12 содержит сообщение m, а канал С21 пуст. В свою очередь при наступлении события "Р2 отправляет m' " система перейдет из состояния S0 в другое глобальное состояние S1', в котором Р1 находится в состоянии s1, Р2 – в состоянии s2', канал С12 пуст, а канал С21 содержит сообщение m'. Поэтому выполнение такой распределенной системы может представлять собой другую по сравнению с рис. 2.5 последовательность событий и, как следствие, последовательность других глобальных состояний.
Do'stlaringiz bilan baham: |
