Задание
1. Выбратьвычислительный процесс и на его примере:
- построитьметамодель «асинхронный процесс» и определить свойства исходного процесса наоснове анализа метамодели;
- выполнитьоперации над процессом: репозиция, редукция, композиция, и оценить полученныерезультаты с практической точки зрения;
- построитьпредметную интерпретацию метамодели на основе сети Петри и сделать вывод одинамических характеристиках исходного процесса.
2. Оформить отчет.
Выполнениезадания
1. Выделитькомпоненты рассматриваемого процесса.
2. Сформироватьмножество ситуаций рассматриваемого процесса.
3. Описать модель«асинхронный процесс».
4. Определитьтраектории выполнения процесса и классы эквивалентности ситуаций и сделатьвывод о свойствах рассматриваемого процесса (эффективность, управляемость,простота).
5. Определитьмножество дополнительных ситуаций для возобновления процесса (если они есть) ипостроить полную или частичную репозицию процесса.
6. Выделить входныеили выходные компоненты асинхронного процесса, выбрать требуемые и построить наих основе редукцию процесса.
7. Определить дваподпроцесса на базе исследуемого, выбрать удобный вид композиции(последовательную или параллельную) и построить ее.
8. Описатьсоставляющие модели «асинхронный процесс», используя понятия модели «сетьПетри».
9. Провести анализсвойств мест сети Петри на ограниченность и безопасность.
10. Провести анализсвойств переходов сети Петри на живость и устойчивость.
Постановказадания
Рассмотретьпроцесс печати с использованием струйного принтера Hewlett Packard (термоструйная печать). Построитьметамодель «асинхронный процесс» и модель «сеть Петри». Исследовать ихсвойства.
Описаниепроцесса
Струйныепринтеры Hewlett Packard используют технологию термоструйной печати. В струйныхпринтерах имеется термоголовка, нижняя часть которой находится на небольшомрасстоянии (около 1 мм и меньше) от листа бумаги. В нижней части головки нанебольшом расстоянии друг от друга находятся несколько сопел (металлическиепластинки, разделенных тончайшими щелями), объединенных в прямоугольнуюматрицу. Каждое сопло оборудовано одним или двумя нагревательными элементами(микроскопическими тонкопленочными резисторами). Сосуды с краской, сопла инагревательные резисторы зачастую объединяются в один блок ─ картридж.
Специальныемеханизмы перемещают бумагу и каретку, в которой в специальных держателяхустановлены печатающие картриджи.
Приподаче напряжения резистор за несколько микросекунд нагревается до температурыоколо 500°, краска вскипает. В кипящих чернилах постепенно образуется пузыреквоздуха, рост которого приводит к выдавливанию чернил из сопла. Спустяприблизительно 3 микросекунды пузырек лопается и происходит отрыв, ипоследующий выброс уже сформировавшейся капли. После разрушения пузырька ивыброса капли силы поверхностного натяжения втягивают новую порцию чернил вкамеру.
Т.к.расстояние между соплом и бумагой невелико, то капля краски попадает в строгоопределенное место на листе бумаги. Затем печатающая головка перемещается нанекоторое расстояние и процесс повторяется.
Построениеметамодели «асинхронный процесс».
Компоненты
1. K – устройство управления
K+ — контролирует работу печати и всехэлементов принтера
K– — бездействует
2. M – память
M+ — содержит задания на печать
M– — свободна
3. P – бумага
P+ — содержится в лотке
P– — отсутствует
4. V – система валиков для подачи бумаги
V+ — работает (перемещает бумагу)
V– — ожидает (покоится)
5. C– каретка с печатающими картриджами
C+ — перемещается
C– — покоится
6. R – нагревательный элемент(тонкопленочный резистр)
R+ — нагрет
R– — охлажден
7. S– сопло
S+ — выбрасывает каплю чернил
S– — бездействует
8. H – камера
H+ — содержит чернила
H– — пуста
9. B – пузырь
B+ — есть
B– — отсутствует
Ситуации,возникшие в процессе печати
1. Принтер включен.Задание печати.
K+M + P– V– C– R – S – H + B –
2. В начале печати –проверка на наличие бумаги. Ее подача. При повторении печати – прокруткабумаги.
K+M + P+ V+ C– R – S – H + B –
3. Отсутствиебумаги. Вывод сообщения об ошибке.
K+M + P– V+ C– R – S – H + B –
4. Кареткаперемещается.
K+M + P+ V– C+ R – S – H + B –
5. Пропускается ток.Резистр осуществляет быстрый нагрев чернил, находящихся в небольшой камере, дотемпературы их кипения.
K+M + P+ V– C– R + S – H + B –
6. Образуетсяпузырек воздуха, который постепенно растет. Из выходного отверстия соплавыдавливаются пузырем чернила. Ток отключается. Нагревательный элементостывает.
K+M + P+ V– C– R – S – H + B +
7. Пузырек лопается.Происходит отрыв и последующий выброс уже оформившейся капли на бумагу. Силыповерхностного натяжения втягивают новую порцию чернил в камеру.
K+M + P+ V– C– R – S + H + B –
8. С помощью системы валиков бумагавыходит из принтера.Память принтера освобождается.
K+M – P– V + C– R – S – H + B –
s1= (1,1,0,0,0,0,0,1,0)
s2= (1,1,1,1,0,0,0,1,0)
s3= (1,1,0,1,0,0,0,1,0)
s4= (1,1,1,0,1,0,0,1,0)
s5= (1,1,1,0,0,1,0,1,0)
s6= (1,1,1,0,0,0,0,1,1)
s7= (1,1,1,0,0,0,1,1,0)
s8= (1,0,0,1,0,0,0,1,0)
Ситуации: S={s1, s2,s3, s4, s5, s6, s7, s8}
Инициаторы: I= {s1, s2,s4}
Результанты: R={s3, s7, s8}
Ситуация s1 описывает начальный этап процесса, то есть заданиепечати.
Ситуация s2 описывает ситуацию, когда происходитпроверка на наличие бумаги в лотке. Она инициирует два возможных результата –дальнейшее продолжение печати, либо ее прекращение после вывода сообщения обошибке.
Ситуация s4 инициирует непосредственно началопроцесса печати (то есть процесса нанесения чернил на бумагу).
Ситуация s3 описывает возможный результат в случае отсутствия бумаги.
Ситуация s7 описывает непосредственно результат печати.
Ситуация s8 описывает завершение работы принтера после печати.
Граф,отражающий отношение непосредственного следования
/>
Траекториивыполнения процесса, классы эквивалентности ситуаций и свойстварассматриваемого процесса
В данномслучае имеем следующие траектории:
S1 → S2 → S4 → S5 → S6 → S7 → S8 – полный процесс, включающий все этапы работыструйного принтера (от задания печати и вплоть до освобождения памяти принтера,при условии, что в лотке содержится бумага).
S4 → S5 → S6 → S7 – процесс,включающий основные этапы работы струйного принтера, а именно сам механизмпечати.
S2 → S3 – процесс,осуществляемый в случае отсутствия бумаги в лотке.
Пусть задан асинхронный процесс, укоторого:
1. для любойситуации s, не являющейся инициатором, найдетсятакой инициатор i, что (iMs),
2. для любойситуации s, не являющейся результантом,найдется такой результантr, что (sMr),
3. не найдется двухситуаций si и sj, таких что: (siÏR) & (sjÏR) & (siMsj) & (sjMsi).
Такойасинхронный процесс называется эффективным. То есть все ситуацииэффективного процесса ведут из инициаторов в результанты, а также не должнобыть ориентированных циклов, за исключением циклов, состоящих только изрезультантов.
Бинарное отношениеэквивалентности ситуаций, обозначаемое буквой E означает, что либо si = sj, либо (si F sj) и (sj F si). Отношение эквивалентностипозволяет построить разбиение множество ситуаций на непересекающиеся классыэквивалентности, такие, что любые две ситуации из одного классаэквивалентны, а любые две ситуации из разных классов не эквивалентны. Дляклассов эквивалентности определено отношение непосредственного следования F. В допустимых последовательностяхклассов можно выделить начальные и конечные элементы, которые будем называтьсоответственно начальными и заключительными классами эквивалентности.Для эффективного АП начальные классы могут состоять только из инициаторов,заключительные — только из результантов.
Дляэффективного АП любой класс эквивалентности ситуаций, не принадлежащийрезультантам, состоит из одной ситуации.
Если вэффективном асинхронном процессе каждая допустимая последовательность классовэквивалентности ведет из каждого начального класса в один и только одинзаключительный класс, то такой процесс называется управляемым.
В процессе печати струйного принтеравсе ситуации лежат на пути из инициаторов в результанты, то есть выполняются 1и 2 свойства; и нет циклов, то есть выполняется свойство 3. Следовательно,можно сделать вывод о том, что данный процесс является эффективным.
В данном процессе начальный классэквивалентности содержит одну ситуацию s1, а конечных класса два и они содержат соответственно две ситуацииs7 и s8 и одну ситуацию s3, все остальные классы эквивалентности содержат поодному элементу.
Так как некоторые допустимыепоследовательности классов эквивалентности ведут из начальных классов не водин, а в два заключительных класса, то данный процесс не является управляемым.
Пусть вэффективном асинхронном процессе выполнены следующие условия:
1) для " i Î I и " s Î S: (i F s) Þ (s Ï I);
2) для " r Î R и " s Î S: (s F r) Þ (s Ï R);
т.е. изинициатора (результанта) нельзя попасть в другой инициатор (результант). Инымисловами каждая траектория содержит в точности один инициатор и один результант.
Асинхронныйпроцесс, удовлетворяющий свойствам 1, 2 называется простым.
/>Данный процесс не удовлетворяет первому и второмусвойствам, поэтому не является простым.
Вывод: рассматриваемый процесс печатиструйного принтера является эффективным, но не является ни управляемым, нипростым.
Операции надпроцессами.
Репозиция.
Репозиция — это возобновление процесса,механизм перехода от результантов к инициаторам.
В данномслучае множество дополнительных ситуаций репозиции SD вводить не нужно.
Репозициейданного процесса можно считать:
1. возобновление печати на новомлисте.
Инициатор:s8
Результант:s1
2. Циклическое повторение нагревачернил, образования пузыря и выброс капли на бумагу
Инициатор:s7
Результант:s4
3. Возобновление печати после выводасообщения об отсутствии бумаги
Инициатор:s3
Результант:s1
Такимобразом, репозиция данного процесса имеет вид />, где
/> = {s1,s3, s4, s7, s8},
/> = {s3,s7, s8},
R' = {s1, s4},
/> ={(s8, s1), (s7, s4), (s3, s1)}
Объединениепроцесса и его репозиции:
/>
Вывод: репозиция позволяет повторитьпроцесс после его выполнения. Для данной модели это означает, что печать можетпроисходить не один раз, а столько, сколько необходимо в рамках поставленнойзадачи.
Репозициярассматриваемого процесса является частичной, так как I' совпадает с R, но R' несовпадаетс I.
Редукция
Редукция процессасостоит в сведении данного асинхронного процесса к более простому.
Составим редукцию репозиции нашего процесса.
Пусть процесс задан диаграммой переходов:
/>
Три первыхэлемента вектора выберем в качестве входной компоненты.
Образуем p-блочное разбиение множества S, p= 4:
X= {1001, 1100, 1101, 1110, 1111}
Выбираем r =2 (rp):
X* = {1110, 1111}
Образуеммножество, содержащее ситуации, входящие в те блоки разбиения, которыесоответствуют выбранным значениям входной компоненты:
S* = {111100010, 111010010, 111001010,111000011, 111000110}
Для каждогоинициатора /> построиммножество ситуаций />встречающихся на траекторияхпроцесса />,ведущих из указанного инициатора. Образуем множество /> как объединение тех множеств />, для которыхсправедливо />:
1: 110000010→111100010→111010010→111001010→111000011→
→111000110→100100010
2: 111100010→110100010
3: 111010010→111001010→111000001→111000110
Ситуации изтраектории 3:
S(X*) = {111010010, 111001010, 111000011, 111000110}
I(X*) = {111010010}
R(X*) = {111000110}
ПостроимF(X*):
/>
Вывод: редукция позволяет из полногоописания процесса выделить некоторую его часть, рассмотрение которой интереснопо тем или иным причинам.
В данном случае, в результатередукции была выделена ветвь, которая соответствует механизму печати струйногопринтера (перемещение каретки, нагрев чернил, образование пузыря, выброс каплина бумагу и наполнение камеры чернилами).
Композиция
Рассмотримпоследовательную композицию двух процессов с ситуациями, структурированными повторому способу: в ситуациях p1выделена выходная компонента; в ситуациях p2 выделена входная компонента.
p1 – подготовки к печати, состоит издвух ситуаций;
p2– непосредственно сама печать;
Компонентыпроцесса p1:
1. K – устройство управления
K+ — контролирует работу печати и всехэлементов принтера
K– — бездействует
2. P – бумага
P+ — содержится в лотке
P– — отсутствует
3. M – память
M+ — содержит задания на печать
M– — свободна
Ситуациипроцесса p1:
1. Принтер включен.Задание печати.
K+P– M +
2. Проверка наналичие бумаги.
K+P+ M + K P M
s11 = 1 1
s22 = 1 1 1
Инициатор: I = { s11}
Результант:R={ s12}
Выделим в процессе первую(контроллер) и вторую (бумага) компоненты в качестве выходных. Выбираемконтроллер, так как он является основным показателем работоспособностиустройства, и бумагу (вспомогательную компоненту), так как процесс подготовки кпечати основывается на подготовку бумаги.
Y1 ={10,11}
Компонентыпроцесса p2:
1. K – устройство управления
K+ — контролирует работу печати и всехэлементов принтера
K– — бездействует
2. P – бумага
P+ — содержится в лотке
P– — отсутствует
3. V – система валиков для подачи бумаги
V+ — работает (перемещает бумагу)
V– — ожидает (покоится)
4. C– каретка с печатающими картриджами
C+ — перемещается
C– — покоится
5. R – нагревательный элемент(тонкопленочный резистр)
R+ — нагрет
R– — охлажден
6. S– сопло
S+ — выбрасывает каплю чернил
S– — бездействует
7. H – камера
H+ — содержит чернила
H– — пуста
8. B – пузырь
B+ — есть
B– — отсутствует
Ситуациипроцесса p2:
1. Проверка наналичие бумаги. Ее подача.
K+P+ V+ C– R – S – H + B –
2. Кареткаперемещается.
K+P+ V– C+ R – S – H + B –
3. Пропускается ток.Резистр осуществляет быстрый нагрев чернил, находящихся в небольшой камере, дотемпературы их кипения.
K+P+ V– C– R + S – H + B –
4. Образуетсяпузырек воздуха, который постепенно растет. Из выходного отверстия соплавыдавливаются пузырем чернила. Ток отключается. Нагревательный элементостывает.
K+P+ V– C– R – S – H + B +
5. Пузырек лопается.Происходит отрыв и последующий выброс уже оформившейся капли на бумагу. Силыповерхностного натяжения втягивают новую порцию чернил в камеру.
K+P+ V– C– R – S + H + B –
6. С помощью системы валиков бумагавыходит из принтера.
K+P– V + C– R – S – H + B – K P V C R S H B
s21 = 1 1 1 1
s22 = 1 1 1 1
s23 = 1 1 1 1
s24 = 1 1 1 1
s25 = 1 1 1 1
s26 = 1 1 1
Инициатор: I= { s21}
Результант: R={ s25 , s26}
Выделим в процессе первую (контроллер)и вторую (бумага) компоненты в качестве входных.
X2 = {10,11}.
Таким образомY1 = X2
Редуцированныепроцессы P1(X*) и P2(X*), где X*= {11,10}.
Процесс p1: K P M
s11 = 1 1
s22 = 1 1 1
Процесс p1: K P V C R S H B
s21 = 1 1 1 1
s22 = 1 1 1 1
s23 = 1 1 1 1
s24 = 1 1 1 1
s25 = 1 1 1 1
s26 = 1 1 1
Композициядвух процессов выглядит следующим образом:
/>
I3 = {( s1)};
R3 = {( s26}. M K P V C R S H B
s31 = 1 1
s32 = 1 1 1 1 1
s33 = 1 1 1 1 1
s34 = 1 1 1 1 1
s35 = 1 1 1 1 1
s36 = 1 1 1 1 1
s37 = 1 1 1 1
Граф композиции:
/>
Вывод: композиция необходима для объединения нескольких процессов водин. В данном случае использовалась последовательная композиция, чтобысмоделировать процесс печати в целом, состоящий из полготовки к печати инепосредственно самой печати. Получившийся процесс /> представляет собой несколькоупрощенный исходный процесс.
Предметнаяинтерпретация асинхронного процесса.
Построениесети Петри.
Сеть Петридля данного процесса – пятерка N= P, T, H, F, M>, где
P= {K, M, P, V, C, R, S, H, B} – множество условий;
T= {t1, t2, t3, t4, t5, t6, t7} – множество событий;
M= (1,1,0,0,0,0,0,1,0) – начальная разметка;
FиH– функции инцидентности, описывающие наличие дуги K M P V C R S H B
s1 = 1 1 1
s2 = 1 1 1 1 1
s3 = 1 1 1 1
s4 = 1 1 1 1 1
s5 = 1 1 1 1 1
s6 = 1 1 1 1 1
s7 = 1 1 1 1 1
s8 = 1 1 1
F(K, t1) = 1
H(t1, K) = 1
F(M, t1) = 1
H(t1, M) = 1
F(H, t1) = 1
H(t1, H) = 1
F(P, t2) = 1
H(t1, P) = 1
F(V, t2) = 1
H(t1, V) = 1
F(V, t3) = 1
H(t2, V) = 1
F(P, t4) = 1
H(t3, P) = 1
F(C, t4) = 1
H(t3, C) = 1
F(P, t5) = 1
H(t4, P) = 1
F(R, t5) = 1
H(t4, R) = 1
F(P, t6) = 1
H(t5, P) = 1
F(B, t6) = 1
H(t5, B) = 1
F(P, t7) = 1
H(t6, P) = 1
F(S, t7) = 1
H(t6, S) = 1
F(M, t7) = 1
H(t7, V) = 1
/>
Граф разметок сети
/>
Покрывающеедерево выглядит аналогичным образом.
Свойства построенной сети Петри
Ограниченность ибезопасность:
ü сеть ограничена, так как все ееусловия ограничены (ни одна вершина покрывающего дерева не содержит символаω);
ü сеть является безопасной, т.к. все ееусловия безопасны (любая достижимая в сети разметка представляет собой векториз 0 и 1).
Живость иустойчивость:
ü сеть не является живой, т.к. все её переходы живы при />, но не являются живыми при любойдругой достижимой в сети разметке;
ü сеть не является устойчивой, т.к. переход t2 не является устойчивым.
Вывод: построенная сеть Петри дает представление о функционированиикомпонент процесса. Она является ограниченной и безопасной, но не являетсяустойчивой и живой.
Заключение
В данном РГЗ была построена модель «асинхронный процесс» печати струйногопринтера. Полученный асинхронный процесс является эффективным, неуправляемым инепростым.
Над процессом были произведены операции: редукции, репозиции ипараллельной композиции.
Репозицияисходного процесса показывает, что нет необходимости использоватьдополнительные ситуации для повторного возобновления процесса работы принтера вситуациях:
ü возобновление печати на новомлисте;
ü циклическое повторение нагревачернил, образования пузыря и выброс капли на бумагу;
ü возобновление печати после выводасообщения об отсутствии бумаги.
Репозиция является частичной.
Редукция позволяет существенно упростить рассматриваемый процесс, сведяего к механизму печати струйного принтера (перемещение каретки, нагрев чернил,образование пузыря, выброс капли на бумагу и наполнение камеры чернилами).
Композиция необходима для объединения нескольких процессов в один, длядальнейшего рассмотрения поведения этих процессов в системе. В данном случаеиспользовалась параллельная композиция.
Для данного процесса была построена сеть Петри. Она является ограниченной и безопасной,но не является устойчивой и живой.
модель печать струйный принтер
Литература
1. Лазарева И.М. Конспектлекции по теории вычислительных процессов.