Репозиция процесса
В рамках введенных выше понятий и определений не уточнялся механизм перехода от результантов к инициаторам. Между тем, описание такого механизма необходимо для получения эффекта возобновления АП, его повторных активизаций.
Такой механизм задается репозицией АП.
Определение 1.8. Репозицией АП P = <S, F, I, R> назовем эффективный АП
P' = <S', F', I', R'> такой, что
S' Í IÈRÈSD , I' Í R, R' Í I.
Множество ситуаций S' репозиции могут содержать лишь те ситуации из исходного процесса, которые являются инициаторами или результантами, и, кроме того, некоторые дополнительные ситуации из SD, отсутствующие в описании исходного АП (SD Ç S ¹ Æ).
Отношение F' задает траектории переходов от элементов из I' Í R к элементам R' Í I, возможно через дополнительные ситуации из SD.
Если I' = R, R' = I, то репозицию назовем полной.
Если F' = Æ , то репозиция не существует, в остальных случаях она называется частичной.
Определение 1.9. Объединение АП и его полной репозиции образует автономный процесс
Pa = <Sa, Fa>, Sa = S È SD, Fa = F È F'.
Пример: построим репозицию АП для рассмотренного выше процесса работы лазерного принтера.
Возможной репозицией описанного выше процесса P будет являться эффективный процесс
P’=<S’, F’, I’, R’>,
где S’ = {S1, S2, S3, S7, S8Д, S9Д},
{S1, S2, S3, S7} Í S,
S8Д = {1,1,0,0,0,0,0} – пополнение лотка бумагой
S9Д = {0,0,0,0,0,0,0} – завершение печати задания, находящегося в памяти
F’ = {(S7, S1), (S7, S2), (S7,S9),(S9,S1),(S3, S8),(S8, S2)}
I’ = {S3, S7 },
R’ = {S1, S2}.
Граф отношения F’:
 |
Рис.1.8
ВЫВОД: репозиция данного асинхронного процесса является полной и описывает процесс возобновления печати:
- с нового сектора на барабане,
- с нового листа,
- с нового задания в памяти,
- при добавлении бумаги в стартовый лоток.
Построим объединение асинхронного процесса и его репозиции:
 |
Рис.1.9
Конец примера.
Таким образом, объединение процесса и его репозиции переводит процесс в разряд постоянно возобновляющихся, при этом теряет свой смысл выделение ситуаций инициаторов и результантов. И, как следствие, становится невозможным использование введенных ранее свойств АП (эффективность, управляемость и т.д.). Для решения этой проблемы вводится следующее понятие.
Определение 1.10. Приведенным асинхронным процессом назовем процесс
Рп = < Sп , Fп , Iп , Rп > такой, что
Sп = SÈ Sд, Fп = FÈ(F’ (F’Ç (S’´I))),
IпÍI, Rп = RÈ Sд.
Иными словами, приведенный процесс является объединением АП и его репозиции, в котором из отношения F’ выброшены пары, задающие переходы к инициаторам процесса (образующие пары F’Ç(S’´I)). Указанное пересечение необходимо, чтобы задать не все возможные пары S’´I, а только те, которые есть в F’(хотя вычесть из F’ того, чего нет – невозможно, но корректность записи требует указанную оговорку).
Для приведенного процесса со структурированными путем выделения входной и выходной компонент ситуациями понятия результанта и инициатора можно конкретизировать следующим образом:
Ситуацию отнесем к результантам, если в ситуациях, принадлежащих всем траекториям, проходящим через данную ситуацию, после нее сохраняется то же значение выходной компоненты, что и в самой этой ситуации.
Ситуацию отнесем к инициаторам, если они образованы из результантов такой заменой значений входной компоненты, что полученная ситуация не относится к результантам.
Таким образом, множество результантов приведенного процесса может увеличиться за счет дополнительных ситуаций репозиции, а вот множество инициаторов может уменьшиться за счет изменения оценки входных компонент.
В зависимости от того, какую репозицию имеет процесс Р, соответствующий приведенный процесс Рп будет называться полностью или частично приведенным.
Если для АП репозиции не существует, то он называется неприводимым.
Построим приведенный процесс на базе процессов P и P’.
Pп =<Sп, Fп, Iп, Rп >, где
Sп = {S1, S2, S3, S4, S5, S6, S7, SД8 , SД9},
S1 = {1,0,0,0,0,0,0}
S2 = {1,1,0,0,0,0,1}
S3 = {1,0,0,0,0,0,1}
S4 = {1,1,1,0,1,0,0}
S5 = {1,1,0,1,1,0,0}
S6 = {1,1,0,0,1,1,0}
S7 = {1,1,0,0,1,0,1}
SД8 = {1,1,0,0,0,0,0}
SД9 = {0,0,0,0,0,0,0}
Fп = {(S1, S2), (S1, S3), (S3, S8), (S2, S4), (S4, S5), (S5, S6), (S6, S7), (S7,S9)},
Iп = { S1, S2 },
Rп = { S3, S7 , S8, S9}.
ВЫВОД: данное объединение для модели АП является автономным процессом. В реальном процессе работы лазерного принтера его автономность можно рассматривать, если предположить, что имеет место автоматическое пополнение стартового лотка бумагой, как только в этом возникает потребность, и в память подается новое задание.
Введем понятие конвейерного процесса, для чего рассмотрим некоторые классы репозиций АП.
Определение 1.11. Полные репозиции простого и непростого АП будут называться соответственно тривиальной и нетривиальной.
Из этого определения и определения простого АП следует, что при нетривиальной репозиции в качестве инициаторов АП репозиции могут служить результанты исходного АП, не обязательно принадлежащие заключительному классу эквивалентности.
Обозначим через R3 объединение заключительных классов эквивалентности ситуаций некоторого АП, а через St - множество ситуаций АП, принадлежащих траектории t.
Пусть задан управляемый АП P = <S,F,I,R> такой что:
1. для каждого его заключительный класс эквивалентности ситуаций состоит из одного результанта rj (rj Î R3);
2. вместе с нетривиальной репозицией АП образует автономный процесс Pa = < Sa, Fa >, на множестве Sa ситуаций которого определена функция g: Sa ® R3 такая, что если в исходном управляемом АП i M r, iÎI, rÎR3, то в соответствующем автономном процессе из iÎSt следует, что существует sÎSt, i Ma s и g(s) = r.
Определение 1.12. Автономный АП, удовлетворяющий свойствам 1), 2) и имеющий фрагменты траекторий вида ...i1...i2...s1...s2..., где g(s1) = r1, g(s2) = r2, называют конвейерным АП.
Понятие конвейерного АП позволяет изучать конвейерный принцип обработки информации, в основе которой лежит идея такой повторной инициации АП, при которой АП еще не достиг результата из заключительного класса эквивалентности ситуаций.
Аналогия: наклонный желоб, по которому скатываются шарики. Когда пущен шарик, на верхний конец желоба можно поместить другой, третий шарик может догнать предыдущий: догнав его, он может катиться дальше не быстрее предыдущего.
Конец дополнительного материала.