8. Простой асинхронный процесс. Протокол простого ап.

Простой АП – это эффективный АП, удовлетворяющий условию:

если s_i F s_j, то s_j ∉ I и s_i∉ R,

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

АП на, у которого I={s1, s2} и R={s5}, является простым.

Протоколом простого АП<S, F, I, R> будем называть простой АП вида <I R, FП, I, R>, где s_iF^Пs_j, если s_iM s_j.

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

Протокол АП

9. Репозиция ап. Автономный асинхронный процесс.

Репозиция– механизм перехода от результантов к инициаторам, необходимый для возобновления АП.

РепозицияАП Р=<S, F, I, R> – это эффективный асинхронный процесс

Р' = <S', F', I', R'>, где S'=I' ∪ R' ∪ S^Д, I' ⊆ R; R' ⊆ I; S^Д ∩ S= ∅.

Таким образом, S^Д– это множество дополнительных ситуаций, отсутствующих в описании исходного АП. Отношение F' задает траектории переходов от ситуаций из I' (т.е. некоторых ситуаций из R) в ситуации из R' (т.е. в некоторые ситуации из I), возможно, через дополнительные ситуации из S^Д.

Если I'=R, R'=I, то репозиция называется полной.

Если I= ∅ или R =∅ , то репозициине существует.

В остальных случаях репозицию называют частичной.

Объединением АП Pи его репозицииР'будем называть АП

(Р ∪ Р')=<S ∪ S^Д, F'', I\R', R\I'>,

где F'' определяется следующим образом:

если s_iF s_j, то s_iF'' s_jи

если s_iF' s_j, то s_iF'' s_j.

АП и его полная репозиция образуют автономный асинхронный процесс.

Полная репозиция простого АП называется тривиальной.

Пример: АП, I={i₁}, R={r₁, r₂}.

А) Исходный АП

Б) Полная репозиция исходного АП, I'={r₁, r₂}, R'={i₁}

В) Частичная репозиция, I'={r₁}, R'={i₁}

Г) Автономный АП (объединение исходного АП и его полной репозиции)

10. Конвейерный принцип обработки информации.

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

Пример.На рис (а) представлен непростой эффективный процесс. ПустьI={i₁},R={r₁,r₂,r₃,r₄,r₅}, тогда получим шесть классов эквивалентностиe(1)={i₁},e(2)={s₁},e(3)={s₂},e(4)={r₁},e(5)={r₂,r₃,r₄},e(6)={r₅}. Для возобновления процесса воспользуемся репозицией, пусть она начинается с результантаr₁(дуга изображена с помощью прерывистой линии). Тогда в результате объединения исходного АП и его репозиции получим конвейер, который начинает обработку информации еще до того, как исходный АП завершит свою работу (б).

11. Редукция асинхронного процесса. Свойства редукции.

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

Подпроцессом АП Р=<S, F, I, R> по множеству ситуаций SП S назовем АП РП=<S^П, F^П, I^П, R^П>, где

I^П=I ∩ S^П, R^П=R ∩ S^П,

s_kF^Пs_p, если s_kFs_p и s_k, s_p ∈ S^П.

Пример подпроцесса(б) по для процесса (а) по множеству ситуаций

S^П = {i₁, s₂, s₃, s₄, r₁, r₂, r₃, r₅}

РедукцияАП Р=<S, F, I, R> по множеству ситуаций S*⊂ S – это подпроцесс, все ситуации которого принадлежат максимальным траекториям исходного АП, содержащимся в S* иначинающимся с инициаторов.

Пример редукции АП (а) по множеству ситуаций

S^П={i₁, s₂, s₃, s₄, r₁, r₂, r₃, r₅}

Свойства редукции:

1. Редукция эффективного процесса (если она существует) – всегда эффективный процесс, обратное неверно.

2. Редукция управляемого процесса (если она существует) – всегда управляемый процесс.

//TODO – доказательство свойств.