Композиция процессов

Рассмотрим два АП: процесс P₁ = <S₁, F₁, I₁, R₁> (необязательно приведенный) и приведенный процесс P₂^п = <S₂, F₂, I₂, R₂>, ситуации которых структурированы: в ситуациях Р₁ выделено множество Y₁выходных компонент, а в ситуациях P₂^п – множество X₂входных компонент.

Пусть все или некоторые значения выходных компонент у¹ ситуации из S₁ соответствует всем или некоторым значениям входных компонент х² ситуации из S₂.

Обозначим проекции множества пар соответствующих друг другу значений компонент на множествах Y₁ и X₂ через Y₁* и Х₂* соответственно. По множествам Y₁* и Х₂* построим редукции Р₁(Y₁*) и P₂^п(Х₂*) процессов Р₁ и Р₂.

Пусть P₂^п(Х₂*) – получился полностью приведенный процесс и Y₁** = Y₁*,

Х₂** = Х₂*.

Построим, если это возможно, процесс P₃= <S₃, F₃, I₃, R₃>, ситуации которого представимы в виде пар s³ = (s¹ , s²), такой что:

1) s¹ÎS₁(Y₁*), s²ÎS₂(X₂*), т.е. S₃Í S₁(Y₁*)´ S₂(X₂*);

2) выходная компонента у¹ ситуации s¹ равна входной компоненте х² ситуации s² : у¹=х²;

3) если в s³ компонента s²ÎI₂(X₂*), то s¹ÎR₁(Y₁*);

4) если (s_i¹, s_j²) F₃(s_k¹, s_l²),

то либо (s_i¹F₁ s_k¹) & (s_j²F₂s_l²), либо (s_i¹F₁ s_k¹) & (s_j² = s_l²), либо (s_i¹ = s_k¹) & (s_j²F₂s_l²).

Определение 1.14. Назовем последовательной композицией АП Р₁ и P₂^п асинхронный процесс Р₃, образованный отождествлением значений входной и выходной компонент ситуаций редуцированных процессов Р₁(Y₁*) и P₂(Х₂*) соответственно при выполнении перечисленных выше ограничений 1) - 4).

Смысл ограничения 1) состоит в том, чтобы при функционировании процесса P₂^пв составе Р₃ в редукции P₂^п(Х₂*) не встречались ситуации, не принадлежащие множеству S₂(X₂*).

Ограничение 4) говорит о том, что для редукции P₂^п(Х₂*) процесса Р₂ в составе Р₃ не может возникнуть новых траекторий.

Из определения следует, что:

1) если ситуации s³ÎS₃ строятся из пар вида

(s¹ = (x¹, y¹, z¹), s² = (x², y², z²)), то компоненты

s³ = (x³, y³, z³) определяются как: х³ = х¹, у³ = у², z³ = (z¹, y¹ = x², z²).

Таким образом, S₃Í S₁(Y₁*)´ S₂(X₂*), причем проекции S₃ на S₁(Y₁*) и S₂(X₂*) равны соответственно S₁(Y₁*) и S₂(X₂*);

2) I₃ Í (I₁(Y₁*)´I₂(X₂*)) Ç S₃, причем проекции I₃ на I₁(Y₁*) и I₂(X₂*) равны соответственно I₁(Y₁*) и I₂(X₂*);

3) R₃ Í (R₁(Y₁*)´R₂(X₂*)) Ç S₃, причем проекции R₃ на R₁(Y₁*) и R₂(X₂*) равны соответственно R1(Y1*) и R2(X2*).

Пример: попытаемся построить композицию рассмотренного выше процесса печати с помощью лазерного принтера и процесса подготовки к такой печати.

В качестве процесса P₁ = <S₁, F₁, I₁, R₁> представим процесс подготовки к печати.

Ситуации этого процесса будут структурированы с помощью следующих компонент:

1. К – микроконтроллер

+ контролирует процесс печати и работу всех механизмов принтера;

- бездействует.

2. М – память:

+ содержит задание на печать;

- свободна.

3. P – бумага для печати:

+ имеется;

- отсутствует.

В результате множество S₁ будет представлено следующими ситуациями:

1. Загрузка данных для печати в память принтера:

K+ M+ P-

S¹₁= (1,1,0)

2. Принтер готов к печати:

K+ M+ P+

S¹₂= (1,1,1)

3. Принтер включен, память пуста:

K+ M- P-

S¹₃= (1,0,0)

4. Принтер отключен:

K- M- P-

S¹₄= (0,0,0)

Таким образом, имеем первый процесс:

P₁=<S₁, F₁, I₁, R₁>, где

S₁ = {S¹₁, S¹₂, S¹₃, S¹₄},

S¹₁= (1,1,0)

S¹₂= (1,1,1)

S¹₃= (1,0,0)

S¹₄= (0,0,0)

F₁ = {(S¹_1, S¹₂), (S¹_2, S¹₃), (S¹_3, S¹₄)},

I₁ = { S¹₁},

R₁ = { S¹₂, S¹₃, S¹₄}.

Структурируем ситуации этого процесса по выходным компонентам M, P: Y = {00,10,11).

Второй процесс в последовательной композиции должен быть приведенным и логически вытекающим из первого.

Построим приведенный процесс P₂^п на основе описанного выше процесса Р и его репозиции P’.

P₂^п =<S₂^п, F₂^п, I₂^п, R₂^п >, где

S₂^п = {S²₁, S²₂, S²₃, S²₄, S²₅, S²₆, S²₇, S²₈, S²₉},

S²₁=(1,0,0,0,0,0,0)

S²₂ =(1,1,0,0,0,0,1)

S²₃ =(1,0,0,0,0,0,1)

S²₄ =(1,1,1,0,1,0,0)

S²₅=(1,1,0,1,1,0,0)

S²₆ =(1,1,0,0,1,1,0)

S²₇ =(1,1,0,0,1,0,1)

S²₈=(1,1,0,0,0,0,0)

S²₉ = (0,0,0,0,0,0,0)

F₂^п = {(S²_1, S²₂), (S²_1, S²₃), (S²_3, S²₈), (S²_2,S ²₄), (S²_4, S²₅), (S²_5, S²₆), (S²_6, S²₇), (S²₇,S²₉)},

I₂^п = { S²₁, S²₂},

R₂^п = { S²₃, S²₇, S²₈, S²₉}.

Множества Y^* и X^* будет образовано совпавшими значениями компонент: в нашем примере совпали все значения компонент {00,10,11) и, следовательно, имеет место Y₁** = Y₁*, Х₂** = Х₂*.

При построении редукции по всем входным или выходным компонентам, она (редукция) совпадет с исходным процессом.

Таким образом, можно построить процесс Р₃= <S₃, F₃, I₃, R₃>, где

ситуации будут иметь компоненты K M P C L B T V.

Множество ситуаций

S³₁= ( S¹₁, S²₁) = (1,1,0,0,0,0,0,0) S¹₁= (1,1,0)

S³₂ = (S¹₂, S²₂) = (1,1,1,0,0,0,0,1) S¹₂= (1,1,1)

S³₃ = (S¹₁, S²₃) = (1,1,0,0,0,0,0,1) S¹₃= (1,0,0)

S³₄ = (S¹₂, S²₄) = (1,1,1,1,0,1,0,0) S¹₄= (0,0,0)

S³₅= (S¹₂, S²₅) = (1,1,1,0,1,1,0,0)

S³₆ = (S¹₂, S²₆) = (1,1,1,0,0,1,1,0)

S³₇ = (S¹₂, S²₇) = (1,1,1,0,0,1,0,1)

S³₈ = (S¹₂, S²₈) = (1,1,1,0,0,0,0,0)

S³₉= (S¹₃, S²₉) = (1,0,0,0,0,0,0,0)

S³₁₀= (S¹₄, S²₉) = (0,0,0,0,0,0,0,0)

(S¹₁ F¹ S¹₂) & (S²₁ F² S²₂) Þ ( S¹₁, S²₁) F³(S¹₂, S²₂) Þ S³₁ F³ S³₂

(S¹₁ = S¹₁) & (S²₁ F² S²₃) Þ ( S¹₁, S²₁) F³(S¹₁, S²₃) Þ S³₁ F³ S³₃

(S¹₂ = S¹₂) & (S²₂ F² S²₄) Þ ( S¹₂, S²₂) F³(S¹₂, S²₄) Þ S³₂ F³ S³₄

(S¹₂ = S¹₂) & (S²₄ F² S²₅) Þ ( S¹₂, S²₄) F³(S¹₂, S²₅) Þ S³₄ F³ S³₅

(S¹₂ = S¹₂) & (S²₅ F² S²₆) Þ ( S¹₂, S²₅) F³(S¹₂, S²₆) Þ S³₅ F³ S³₆

(S¹₂ = S¹₂) & (S²₆ F² S²₇) Þ ( S¹₂, S²₆) F³(S¹₂, S²₇) Þ S³₆ F³ S³₇

(S¹₁ F¹ S¹₂) & (S²₃ F² S²₈) Þ ( S¹₁, S²₃) F³(S¹₂, S²₈) Þ S³₃ F³ S³₈

(S¹₂ F¹ S¹₃) & (S²₇ F² S²₉) Þ ( S¹₂, S²₇) F³(S¹₃, S²₉) Þ S³₇ F³ S³₉

(S¹₃ F¹ S¹₄) & (S²₉ = S²₉) Þ ( S¹₃, S²₉) F³(S¹₄, S²₉) Þ S³₉ F³ S³₁₀

Рис.12

Множество инициаторов: I = { S³₁}.

Множество результантов: R = { S³₇, S³₈, S³₉, S³₁₀}

Конец примера.

Рассмотрим два АП (не обязательно приведенных) Р₁ и Р₂ со структурированными ситуациями: выделенными входными компонентами х¹и х².

Пусть все или некоторые значения входной компоненты х¹ситуаций из S₁ семантически эквивалентны всем или некоторым значениям входной компоненты х² ситуаций из S₂.

Обозначим проекции эквивалентных пар значений компонент на множества Х₁ и Х₂ через Х*. По Х* построим редукции Р₁(Х*) и Р₂(Х*) процессов Р₁ и Р₂. Пусть Х** = Х*.

Построим, если это возможно, процесс Р₃, ситуации S³ÎS₃ которого представимы в виде пар S³ = (S¹, S²), таких, что:

1) S¹ÎS₁(X*), S²ÎS²(X*), то есть S₃Í S₁(X*)´S₂(X*);

2) входные компоненты х¹ и х² ситуаций S¹ и S² эквивалентны: х¹ =х² = х.

Определение 1.15. Назовем параллельной композицией асинхронных процессов Р₁ и Р₂ процесс Р₃, образованный отождествлением значений входных компонент ситуаций редуцированных процессов Р₁(Х*) и Р₂(Х*) при выполнении ограничений 1) - 2).

Рассмотрим теперь приведенный АП Р^п = <S^п, F^п, I^п, R^п>, соответствующий некоторому процессу Р и его репозиции Р’.

Пусть ситуации процесса Р^п структурированы: в них выделены входная х и выходная у компоненты. И все или некоторые значения выходной компоненты у ситуаций этого процесса соответствуют всем или некоторым значениям входной компоненты х ситуаций того же процесса.

Обозначим проекцию множества эквивалентных пар значений компонент на множества Х и Y через Х* и Y* соответственно.

По множествам Х* и Y* построим редукции Р^п(Х*) и Р^п(Y*) процесса Р.

Построим автономный процесс Р³(Х*,Y*) = <S³, F³>, удовлетворяющий следующим ограничениям:

1) S³ Í S^п(Х*) Ç S^п(Y*);

2) выходная компонента у³ ситуации S³ эквивалентна компоненте х³: y³ = x³;

3) F³ = (F(X*) È F’(X*)) Ç (F’(Y*)ÈF(Y*)),

где F и F’ задают причинно-следственные связи для неприведенного процесса и его репозиции, соответствующих процессу Р^п.

Определение 1.16. Автономный процесс Р³, удовлетворяющий ограничениям 1) - 3), назовем замыканием процесса Р^п.

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

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

Современные ЭВМ и дисковые системы строятся на основе модульного (агрегатного) принципа: аппаратные средства, равно как и программное обеспечение, выполняются в виде отдельных функциональных и структурных единиц (модулей). Последние объединяются (композируются), образуя сложные системы.