Примеры графического представления фрагментов асинхронных процессов

Рис.1.1 Рис.1.2

Асинхронный процесс может быть описан направленным графом, вершинами которого являются ситуации, а дуги представляют отношение непосредственного следования. На рис.1.1 представлен вариант, когда за s₁ может непосредственно следовать s₃.; на рис. 1.2 – вариант, когда s₁ F s₂, s₂ F s₃. То есть изучение семантики процесса может показать, что из ситуации s₁ в ситуацию s₃ процесс попадает только через ситуацию s₂, хотя s₁ является причиной и s₂, и s₃.

Введем новые термины и понятия.

Пусть имеется последовательность (возможно, бесконечная) ситуаций s(1)...s(i)s(i+1)..., где s(i) - элемент, стоящий в последовательности на i -ом месте. (Место именно в этой последовательности, а не в процессе, напр., s₁,s₂,s₄,s_{5 ,} где s_i – обозначение ситуации в процессе, будет представлено в последовательности s₁(1),s₂(2),s₄(3),s₅(4)).

Определение 1.2. Для АП можно составить множество последовательностей ситуаций, в которых для любого места i, кроме последнего, справедливо s(i) F s(i+1) и таких, что ни одна из последовательностей не является частью другой.

Такие последовательности называются допустимыми.

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

Из этого следует, что можно построить отношение М, соответствующее отношению F, такое что, если для пары ситуаций s_i, s _j существует траектория s_i в s_j, то s_i М s_j.

Отношение М – еще один способ описания асинхронного процесса, определенный на S´S. Запись s_j М s_k равносильна логической возможности перехода из s_j в s_k. Это свойство сохраняет недетерминированный характер асинхронного процесса: если для некоторой s_j существует единственная s_k, такая что s_j М s_k, то логическая возможность означает также и логическую необходимость. Отношение М можно изображать орграфом.

Пример: Рассмотрим АП Р= <S, F, I, R>,

Где S={ s₁,s₂,s₃,s₄,s₅,s₆ } множество ситуаций, для которых отношение F задается графом

Рис.1.3

Рассмотрим последовательности ситуаций s(1), s(2), s(3), s(4):

допустимые –	недопустимые –
s1, s3, s4, s5 s2, s3, s4, s6 s2, s3, s4, s5 s1, s3, s4, s6	s3, s4, s6 s1, s3, s4
или
допустимые –	недопустимые –
s1, s3, s4, s5 s2, s3, s4, s5 s3, s4, s6	s1, s3, s4, s6 s1, s3, s4

Определение траектории как допустимой последовательности ситуаций осуществляется исходя из семантики процесса.

Пусть задан АП, у которого:

1) для любой sÎS \ R найдется rÎR такая, что s M r;

2) для любой sÎS \ I найдется iÎI такая, что i M s;

3) не найдется ситуаций s_i и s_j таких, что (s_iÏR)&(s_jÏR)&(s_i M s_j)&(s_j M s_i).

Определение 1.3. АП, удовлетворяющий свойствам 1) - 3), будет называться эффективным.

То есть из инициаторов эффективного процесса все траектории ведут в результанты (свойство 1), 3)), каждая из траекторий, приводящих к результанту, начинается в каком-либо инициаторе (свойство 1), 2)) и он не содержит ориентированных циклов вне ситуаций, принадлежащих множеству R (свойство 3)).

Эффективность АП оставляет место недетерминированности, т.е. возможно, что из некоторого инициатора процесс попадает в разные результанты.

Пример: Рассмотрим АП Р= <S, F, I, R>,

Где S={ s₁,s₂,s₃,s₄,s₅,s₆ } множество ситуаций, для которых отношение F задается графом

Рис.1.4

Если для этого АП

I = {s₁, s₄}, R = {s₅},

то АП не является эффективным, т.к. не выполняется свойство 1).

Если

I = {s₁}, R = {s₂, s₃, s₅, s₆},

то АП не является эффективным, т.к. не выполняется свойство 2).

Если

I = {s₁, s₄}, R = {s₅, s₆},

то АП не является эффективным, т.к. не выполняется свойство 3).

Заметим, что если

I={s₁,s₄}, R= {s₃,s₅,s₆},

то не выполняется ограничение определения АП: s₃ F s₂, но s₃ÎR, а s₂ÏR.

Вариант эффективного АП: I={s₁, s₄}, R={s₂,s₃,s₅,s₆}. Конец примера.

Для некоторых подмножеств множества ситуаций S можно определить отношение Е:

1) для s_i, s_jÎS имеет место отношение Е: s_i E s_j, если s_i M s_j и s_j M s_i;

2) для любых sÎS: s E s.

Условие 1) обеспечивает симметричность и транзитивность отношения Е (транзитивность Е следует из транзитивности М), а 2) - рефлексивность Е, следовательно, Е - отношение эквивалентности.

Отношение Е позволяет построить разбиение =(S₁,...,S_p) множества S на классы эквивалентности.

Для классов эквивалентности определим отношение F непосредственного следования классов.

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

На основании введенных понятий можно сформулировать следующие утверждения:

1. Если некоторая ситуация s является инициатором и sÎS(j), где S(j) - класс эквивалентности, стоящий на j -ом месте в некоторой допустимой последовательности, все ситуации классов S(1),...,S(j) в этой последовательности является инициатором.

2. Если некоторая ситуация s является результантом и sÎS(j), то все ситуации из классов S(j),S(j+1),...,S(q), где S(q) - заключительный класс, являются результантами.

3. Для эффективного АП любой начальный класс состоит только из инициаторов, а любой заключительный класс только из результантов.

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

Определение 1.4. Если в эффективном АП каждая допустимая последовательность классов ведет из начального класса в один и только один заключительный класс, то такой процесс называется управляемым.

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

Пример: Рассмотрим АП с множеством ситуаций S={s₁,s₂,...,s₁₀} и отношением F, заданным на рисунке 1.5:

Рис.1.5

Рис.1.6

Разбиение АП на классы эквивалентных ситуаций. На рисунке 1.6 показано отношение F для классов эквивалентности множества ситуаций этого АП.

Если I={s₁,s₂,s₃,s₄}, R={s₇,s₈,s₉,s₁₀}, легко убедиться, что этот процесс является управляемым. Если отношение F дополнить парой s₂ F s₄, то полученный АП становится неуправляемым (но остается эффективным).

Введем понятия, которые окажутся полезными при рассмотрении некоторых АП.

Определение 1.5. Если ситуации s_i и s_k некоторого АП связаны отношением s_iМs_k (s_i Fⁿ s_k), то фрагмент процесса, содержащий все части траекторий, ведущие из s_i в s_k, назовем переходом s_i - s_k.

В дальнейшем также будет использоваться следующий класс АП.

Пусть в эффективном АП:

1) для любых iÎI и sÎS из iFs Þ sÏI;

2) для любых sÎS и rÎR из sFr Þ sÏR

(то есть каждая траектория содержит в точности по одному инициатору и результанту).

Определение 1.6. АП, удовлетворяющий свойствам 1),2) будет называться простым.

Определение 1.7. Протоколом простого АП будет называться отношение

Q Í I´R

Протокол простого АП можно рассматривать как простой АП, в котором за каждым инициатором непосредственно следует результант. Поэтому в протоколе простого АП множество ситуаций состоит лишь из инициаторов и результантов:

S = IÈR

При переходе от простого АП к его протоколу для каждой пары (i,r) пучки траекторий, ведущих из i в r, возможно через промежуточные ситуации, заменяются одной дугой.

Протокол является удобной формой "вход-выходного" описания АП.