Струйный принтер

Содержание

 

1. Задание

2. Описание вычислительного процесса

3. Построение метамодели "асинхронный процесс"

Определение асинхронного процесса

Компоненты

Ситуации

Отношение непосредственного следования

Множество инициаторов и результантов

Анализ свойств метамодели "асинхронный процесс"

Операции над процессами

4. Редукция

Определение редукции

Композиция

Определение композиции

5. Предметная интерпретация асинхронного процесса

Исходный асинхронный процесс

Граф разметок и дерево достижимости

6. Анализ свойств сети Петри

Заключение

Литература

1. Задание

1.       Выбрать вычислительный процесс и на его примере:

-       построить метамодель "асинхронный процесс" и определить свойства исходного процесса на основе анализа метамодели;

-       выполнить операции над процессом: репозиция, редукция, композиция, и оценить полученные результаты с практической точки зрения;

-       построить предметную интерпретацию метамодели на основе сети Петри и сделать вывод о динамических характеристиках исходного процесса.

2.       Оформить отчет.

2. Описание вычислительного процесса

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

Головка вместе с емкостями для чернил закрепляется на каретке, которая по специальной направляющей совершает возвратно-поступательное движение поперек листа бумаги.

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

Синхронное взаимодействие всех механизмов принтера, а также его связь с системным блоком ПК обеспечивается устройством управления. Это сложное электронное устройство, представляющее собой мини-компьютер. Именно оно осуществляет двухсторонний обмен информацией с ПК, хранение и необходимые преобразования информации, формирование управляющих сигналов на рабочие органы принтера.

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

.        На принтер подаются данные для печати, которые записываются в память принтера.

2.       Осуществляется проверка на наличие чернил.

.        Если чернил нет, то выводится соответствующее сообщение.

.        Осуществляется проверка на наличие бумаги.

.        Если бумаги нет, то выводится соответствующее сообщение, и принтер ожидает установки бумаги в лоток.

.        После всех проверок осуществляется печать.

.        Диспетчер печати может отменить задание печати.

3. Построение метамодели "асинхронный процесс"

Определение асинхронного процесса

Асинхронным процессом называется четверка <S, F, I, R>, где

S - непустое множество ситуаций,

F - отношение непосредственного следования, определенного на множестве S ´ S,

I - множество инициаторов,

R - множество результантов.

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

 

Компоненты

1.       M - память (M = 1 - занята, M = 0 - свободна).

2.       R - система валиков (R = 1 - работает, R = 0 - ожидает).

3.       H - печатающая головка (H = 1 - движется и наносит чернила на бумагу, H = 0 - в исходном положении).

4.       E - система обработки ошибок (E = 1 - работает, E = 0 - ожидает).

5.       I - чернила (I = 1 - есть, I = 0 - нет).

6.       S - системная обработка, например, выдача сообщения об ошибке, ожидание системной информации (S = 1 - выполняется, S = 0 - не выполняется).

 

Ситуации

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

S	Компоненты						Физический смысл
	M	I	E	R	H	S
s1	1	1	0	0	0	0	На принтер подаются данные для печати, которые записываются в память принтера
s2	1	1	1	0	0	0	Идёт проверка на наличие чернил
s3	0	0	1	0	0	1	Выводится сообщение об отсутствии чернил
s4	1	1	1	1	0	0	Проверка на наличие бумаги
s5	1	1	1	0	0	1	Выводится соответствующее сообщение об отсутствии бумаги
s6	1	1	0	0	0	1	Ожидание установки бумаги в лоток
s7	1	1	0	1	1	0	Печать листа
s8	0	1	0	0	0	0	Напечатанный лист выходит из принтера и память принтера освобождается
s9	0	1	0	1	0	0	Принудительное удаление задания диспетчером печати

Таким образом, получили множество ситуаций S = {s₁, s₂, s₃, s₄, s₅, s₆, s₇, s₈, s₉}.

 

Отношение непосредственного следования

Отношение непосредственного следования F задается графом:

 

Множество инициаторов и результантов

Пусть множество инициаторов I = {s₁}.

Пусть множество результантов R = {s₃, s₈, s₉}.

Допустимые траектории

1.       s₁ ® s₂ ® s₄ ® s₇ ®s₈. Печать листа осуществлена успешно.

2.       s₁ ® s₂ ® s₃. После проверки на наличие чернил выводится сообщение об ошибке, т.к. чернила отсутствуют.

3.       s₁ ® s₂ ® s₄ ® s₅ ® s₆ ® s₄ ® s₅ ® s₆ ® … ® s₆ ® s₇ ® s₈. После проверки на наличие бумаги выводится сообщение об ошибке, т.к. бумага отсутствует, и принтер ожидает установки бумаги в лоток. Далее выполнена печать листа.

4.       s₁ ® s₂ ® s₄ ® s₅ ® s₆ ® s₄ ® s₅ ® s₆ ® … ® s₆ ® s₉. Зацикливание операции ожидания бумаги, принудительное удаление задания диспетчером печати.

5.       s₁ ® s₂ ® s₉, s₁ ® s₂ ® s₄ ® s₇ ® s₉, s₁ ® s₂ ® s₉. Удаление задания из различных состояний печати.

Примечание: цветом выделены части траекторий, означающие зацикливание прохождения ситуаций s₄, s₅ и s₆. Допустимо прохождение как одной итерации цикла, так и большого количества итераций, однако выход из цикла рано или поздно произойдет.

Анализ свойств метамодели "асинхронный процесс"

Асинхронный процесс P является эффективным, если выполняются условия:

. " ситуации s Î S \ R найдется ситуация r Î R / s M r;

. " ситуации 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).

Рассматриваемый асинхронный процесс не является эффективным, так как не выполняется условие 3:  ситуации s₄ и s_5/ (s₄ Ï R) & (s₅ Ï R) & (s₄ M s₅) & (s₅ M s₄).

Асинхронный процесс по определению называется простым, если

1.       он является эффективным,

2.       " i Î I, s Î S: (i F s) Þ (s Ï I),

.        " s Î S, r Î R: (s F r) Þ (s Ï R),

Рассматриваемый асинхронный процесс не является простым, т.к. не выполняется условие 1.

Для оценки управляемости асинхронного процесса, множество ситуаций необходимо разбить на классы эквивалентности. Для некоторого подмножества ситуаций вводится отношение эквивалентности E:

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).

В рассматриваемом асинхронном процессе получаем семь классов эквивалентности: K₁ = {s₁}, K₂ = {s₂}, K₃ = {s₃}, K₄ = {s₄, s₅, s₆}, K₅ = {s₇}, K₆ = {s₈}, K₇ = {s₉}. Допустимые последовательности классов: K₁ ® K₂ ® K₄ ® K₅ ® K₆, K₁ ® K₂ ® K₃, K₁ ® K₂ ® K₇, K₁ ® K₂ ® K₄ ® K₇, K₁ ® K₂ ® K₄ ® K₅ ® K₇. Таким образом, имеем начальный класс эквивалентности K₁ и заключительные классы эквивалентности K₃, K₆, K₇.

Асинхронный процесс по определению называется управляемым, если

.        он является эффективным,

2.       каждая допустимая последовательность классов ведет из начального в один и тот же заключительный класс.

Рассматриваемый асинхронный процесс не является управляемым, т.к. не выполняется условие 1.

Выводы:

Таким образом, удалось представить физический процесс печати одного листа на струйном принтере в виде метамодели "асинхронный процесс", т.е. была выделена четверка <S, F, I, R>.

Также были проанализированы свойства процесса. Рассмотренный асинхронный процесс не является ни эффективным, ни простым, ни управляемым, содержит 7 классов эквивалентности, из которых один начальный, а три заключительных.

 

Операции над процессами

Репозиция

Определение репозиции

Репозицией асинхронного процесса P=<S,F, I,R> называется эффективный асинхронный процесс P'=<S',F', I',R'> такой, что S' Í IÈRÈS^Д, I' Í R, R' Í I.

Выполнение операции репозиции

Построим репозицию P' процесса P. Пусть множество инициаторов репозиции I' = {s₃, s₈, s₉}, а множество результантов R' = {s₁}. Введем дополнительные ситуации, составляющие множество S^Д = {s₁₀, s₁₁}.

SД	Компоненты						Физический смысл
	M	I	E	R	H	S
s10	0	1	1	0	0	1	Ожидание поступления данных для печати очередного листа
s11	1	0	0	0	0	1	Ожидание установки картриджа

Тогда множество ситуаций репозиции S' = {s₁, s₃, s₈, s₉, s₁₀, s₁₁}. Зададим отношение непосредственного следования F' ситуаций репозиции: s₃ F' s₁₁, s₁₁ F' s₁, s₈ F' s₁₀, s₉ F' s₁₀, s₁₀ F' s₁. В построенном асинхронном процессе допустимы траектории: s₃ ® s₁₁ ® s₁, s₈ ® s₁₀ ® s₁, s₉ ® s₁₀ ® s₁.

Объединим исходный асинхронный процесс с его репозицией.

 

Анализ свойств репозиции

Если I' = R и R' = I репозиция называется полной по определению. Если F' отсутствует, то репозиция не существует. В остальных случаях репозиция называется частичной.

Объединение полной репозиции и асинхронного процесса образует автономный процесс P^А = <S^А, F^А> такой, что S^А = SÈS^Д, F^А = FÈF'.

Проанализируем свойства построенной репозиции. I' = R и R' = I, следовательно репозиция является полной. Объединение процессов P и P' позволяет получить автономный процесс P^А, т.к. репозиция P' является полной.

Выводы по выполнению операции репозиции

струйный принтер асинхронный процесс

Операция репозиции задает механизм перехода от результантов к инициаторам. Он необходим для получения эффекта возобновления асинхронного процесса или его повторной реактивации.

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

4. Редукция

Определение редукции

Пусть задан неприведенный АП P = <S, F, I, R>, множество ситуаций которого представимо упорядоченной тройкой S = (X, Y, Z), где X, Y и Z - соответственно множества значений (символов) входной компоненты, выходной компоненты и компоненты, не являющей ни входной ни выходной.

Образуем p-блочное разбиение p множества S ситуаций процесса P, в ситуациях каждого блока которого входная компонента принимает фиксированное значение x_j, 1 £ j £ p. Выберем r < p различных значений входной компоненты (составляющих множество X* Ì X). Ситуации, входящие в те блоки разбиения p, которые соответствуют выбранным значениям входной компоненты, составляют подмножество S*, S* Ì S.

Для каждого инициатора s_i Ì I построим множество ситуаций S (s_i), встречающихся на траекториях процесса P, ведущих из указанного инициатора. Образуем множество S (X*) как объединение тех множеств S (s_i), для которых справедливо S (s_i) Í S*, т.е.

.

Построим также F (X*) = F Ç (S (X*) ´ S (X*)), I (X*) = I Ç S (X*), R (X*) = R Ç S (X*). Назовем процесс P (X*) = <S (X*), F (X*), I (X*), R (X*) >, редукцией неприведенного процесса P = <S, F, I, R> по выбранному множеству X* значений входной компоненты.

Процесс P

Рассмотрим процесс P = <S, F, I, R> из §1, отношение непосредственного следования которого:

Пусть ситуации этого процесса структурированы с выделением входной компоненты. Представим его более наглядно (цветом выделена входная компонента x, инициаторы и результанты помечены символами i и r соответственно):

 

Порядок выполнения редукции

Определим порядок действий, которые необходимо выполнить для получения редукции процесса P.

.        Определить множество X* входных компонент, по которым проводится редукция.

2.       Определить множество S* ситуаций, подходящих для редукции.

.        Определить множество S (X*) ситуации редукции.

.        Определить отношение F (X*) непосредственного следования ситуации редукции.

.        Определить множество I (X*) инициаторов редукции.

.        Определить множество R (X*) результантов редукции.

Выполнение операции редукции

1.       Определим множество X*.

X = {00, 01, 11}. Пусть X* = {11}.

.        Определим множество S*.

S* = {110000, 111000, 111100, 111001, 110001, 110110} = {s₁, s₂, s₄, s₅, s₆, s₇}.

.        Определим множество S (X*).

S (X*) = S* = {110000, 111000, 111100, 111001, 110001, 110110} = {s₁, s₂, s₄, s₅, s₆, s₇}.

.        Определим отношение F (X*) = F Ç (S (X*) ´ S (X*)).

.        Определим множество I (X*).

I = {s₁}, S (X*) = {s₁, s₂, s₄, s₅, s₆, s₇} Þ (X*) = I Ç S (X*) = {s₁} = {110000} = I.

.        Определим множество R (X*).

R = {s₃, s₈, s₉},(X*) = {s₁, s₂, s₄, s₅, s₆, s₇} Þ= R Ç S (X*) = Æ.

Выводы по выполнению операции редукции

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

Полученный в результате редукции асинхронный процесс описывает часть физического процесса печати одного листа на струйном принтере, для которой характерно наличие данных для печати в памяти принтера и наличие чернил, т.к. в качестве входной компоненты были выбраны значения компонент M = 1 и I = 1.

 

Композиция

Определение приведенного асинхронного процесса

Приведенным асинхронным процессом называется процесс P^П = <S^П, F^П, I^П, R^П> такой, что S^П = SÈS^Д, F^П = FÈ (F'\ (F'Ç (S'´I))), I^П Í I, R^П = RÈS^Д.

Таким образом, приведенный процесс является объединением АП и его репозиции, в котором из отношения F' выброшены пары, задающие переходы к инициаторам процесса.

 

Определение композиции

Рассмотрим два АП - процесс P₁ = <S₁, F₁, I₁, R₁> (необязательно приведенный) и приведенный процесс P^П₂ = <S₂, F₂, I₂, R₂>, ситуации которых структурированы: в ситуациях P₁ выделена выходная, а в ситуациях P^П₂ - входная компоненты. Пусть все или некоторые значения выходной компоненты y¹ ситуаций S₁ соответствуют всем или некоторым значениям входной компоненты x² ситуаций S₂. Обозначим проекции множества пар соответствующих друг другу значений компонент на множества Y₁ и X₂ через Y*₁ и X*₂ соответственно. По множествам Y*₁ и X*₂ построим редукции P₁ (Y*₁) и P^П₂ (X*₂) процессов P₁ и P^П₂. Пусть P^П₂ (X*₂) - полностью приведенный процесс и Y**₁ = Y*₁, X**₂ = X*₂.

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

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

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

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

4)      если , то либо , либо , либо .

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

Процесс P₁

Рассмотрим жизненный цикл любого процесса (потока) ОС. Он представлен в виде графа состояний процесса (потока):

Диспетчер печати струйного принтера, выполняясь в ОС, может состоять из нескольких потоков, каждый из которых отвечает за выполнение какой-то элементарной задачи. Допустим, что один из потоков отвечает за распечатку одного документа на струйном принтере.

Представим жизненный цикл такого потока в виде асинхронного процесса P₁ = <S₁, F₁, I₁, R₁>. Множество ситуаций S₁ = {s¹₁, s¹₂, s¹₃, s¹₄, s¹₅}. Множество инициаторов I₁ = {s¹₁}. Множество результантов R₁ = {s¹₂, s¹₃, s¹₄, s¹₅}. Ситуации структурированы (R - процесс имеет в распоряжении все ресурсы, P - процесс ожидает выбора планировщиком задач, N - разделяемая ячейка памяти, доступная как диспетчеру печати, так и принтеру, она несет управляющую информацию), кроме того, выделена выходная компонента y¹ (N = y¹). Отношение непосредственного следования F₁ задано графом.

S1	Компоненты			Физический смысл
	R	P	N = y1
s11	0	0	1	Создание процесса
s12	0	1	0	Готовность к выполнению
s13	1	0	0	Выполнение
s14	1	0	1	Ожидание (состояние блокирования)
s15	0	0	1	Завершение работы процесса

Представим процесс P₁ более наглядно (цветом выделена выходная компонента y¹, инициаторы и результанты помечены символами i и r соответственно):

 

Процесс P^П₂

Пусть задан АП из §1. Ранее мы получили его объединение с репозицией.

Согласно определению приведенного асинхронного процесса из отношения F' уберем пары, задающие переходы к инициаторам процесса. Получим процесс P^П₂ = <S₂, F₂, I₂, R₂>. Множество ситуаций S₂ = {s²₁, s²₂, s²₃, s²₄, s²₅, s²₆, s²₇, s²₈, s²₉, s²₁₀, s²₁₁}. Множество инициаторов I₂ = {s²₁}. Множество результантов R₂ = {s²₃, s²₈, s²₉, s²₁₀, s²₁₁}. Отношение непосредственного следования F₂ представлено графом:

Пусть множество ситуаций S₂ структурировано с выделением входной компоненты x¹ (N - разделяемая ячейка памяти, доступная как диспетчеру печати, так и принтеру, она несет управляющую информацию):

S2	Компоненты							Физический смысл
	N = x2	M	I	E	R	H	S
s21	0	1	1	0	0	0	0	На принтер подаются данные для печати, которые записываются в память принтера
s22	1	1	1	1	0	0	0	Идёт проверка на наличие чернил
s23	0	0	0	1	0	0	1	Выводится сообщение об отсутствии чернил
s24	1	1	1	1	1	0	0	Проверка на наличие бумаги
s25	1	1	1	1	0	0	1	Выводится соответствующее сообщение об отсутствии бумаги
s26	1	1	1	0	0	0	1	Ожидание установки бумаги в лоток
s27	1	1	0	1	1	0	Печать листа
s28	0	0	1	0	0	0	0	Напечатанный лист выходит из принтера и память принтера освобождается
s29	0	0	1	0	1	0	0	Принудительное удаление задания диспетчером печати
s210	0	0	1	1	0	0	1	Ожидание поступления данных для печати очередного листа
s211	0	1	0	0	0	0	1	Ожидание установки картриджа

Представим процесс P ^П₂ более наглядно (цветом выделена входная компонента x², инициаторы и результанты помечены символами i и r соответственно):

 

Последовательность выполнения композиции

Определим порядок действий, которые необходимо выполнить для получения композиции процессов P₁ и P^П₂.

.        Определить множества Y*₁ и X*₂ - проекции множества пар соответствующих друг другу значений выходной компоненты процесса P₁ и входной компоненты процесса P₂ на множества Y₁ и X₂ соответственно.

2.       По множествам Y*₁ и X*₂ построить редукции P₁ (Y*₁) и P₂ (X*₂) процессов P₁ и P^П₂.

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

.        Построить процесс P₃ согласно ограничениям композиции.

.        Определить инициаторы процесса P₃: I₃ Í (I₁ (Y*₁) ´ R₂ (X*₂)) Ç S₃.

.        Определить результанты процесса P₃: R₃ Í (R₁ (Y*₁) ´ R₂ (X*₂)) Ç S₃.

Построение композиции

1.       Определяем множества Y*₁ и X*₂.

1.1.    Y₁ = {0, 1} Þ Y*₁ = {0, 1}.

1.2.    X₂ = {0, 1} Þ X*₂ = {0, 1}.

2.       Строим редукции P₁ (Y*₁) и P₂ (X*₂).

.1       Редукция P₁ (Y*₁) процесса P₁: Y*₁ = Y₁ Þ P₁ (Y*₁) = P₁ Þ S₁ (Y*₁) = S₁, F₁ (Y*₁) = F₁, I₁ (Y*₁) = I₁, R₁ (Y*₁) = R₁.

2.2     Редукция P₂ (X*₂) процесса P^П₂: X*₂ = X₂ Þ P₂ (X*₂) = P^П₂ Þ S₂ (X*₂) = S₂, F₂ (X*₂) = F₂, I₂ (X*₂) = I₂, R₂ (X*₂) = R₂.

3.       Определяем множества Y**₁ и X**₂.

3.1     Y**₁ = {0, 1} = Y*₁.

3.2     X**₂ = {0, 1} = X*₂.

4.       Строим процесс P₃ согласно ограничениям композиции.

.1       Для этого построим таблицу:

S1 S2		s11	s12	s13	s14	s15
		001	010	100	101	001
s21	0110000			100110000
s22	1111000				101111000
s23	0001001		010001001
s24	1111100				101111100
s25	1111001				101111001
s26	1110001				101110001
s27	1110110				101110110
s28	0010000		010010000
s29	0010100		010010100
s210	0011001		010011001	100011001
s211	0100001		010100001	100100001

4.2     Получаем композицию процессов:

4.3     Отношение непосредственного следования представлено на графе:

4.4     Докажем, что выполняется требование 3) композиции, т.е. если в S³ компонента s² Î I₂ (X*₂), то s¹ Î R₁ (Y*₁):

S₃ = { (s¹₃, s²₁), (s¹₄, s²₂), (s¹₂, s²₃), (s¹₂, s²₁₁), (s¹₃, s²₁₁), (s¹₄, s²₄), (s¹₄, s²₅), (s¹₄, s²₆), (s¹₄, s²₇), (s¹₂, s²₈), (s¹₂, s²₉), (s¹₂, s²₁₀), (s¹₃, s²₁₀) },₁ (Y*₁) = {s¹₂, s¹₃, s¹₄, s¹₅},₂ (X*₂) = {s²₁},

Выберем из S³ все ситуации s³ = (s¹, s²) такие, что s² = s²₁: (s¹₃, s²₁). Очевидно, что s¹ = s¹₃ Î R₁ (Y*₁)

.        Определяем инициаторы процесса P₃: I₃ Í (I₁ (Y*₁) ´ R₂ (X*₂)) Ç S₃

I₁ (Y*₁) = {s¹₁}, R₂ (X*₂) = {s¹₃, s¹₈, s¹₉, s¹₁₀, s¹₁₁},₃ = { (s¹₃, s²₁), (s¹₄, s²₂), (s¹₂, s²₃), (s¹₂, s²₁₁), (s¹₃, s²₁₁), (s¹₄, s²₄), (s¹₄, s²₅), (s¹₄, s²₆), (s¹₄, s²₇), (s¹₂, s²₈), (s¹₂, s²₉), (s¹₂, s²₁₀), (s¹₃, s²₁₀) },₃ Í (I₁ (Y*₁) ´ R₂ (X*₂)) Ç S₃ = Æ Þ, I₃ = Æ.

.        Определяем результанты процесса P₃: R₃ Í (R₁ (Y*₁) ´ R₂ (X*₂)) Ç S₃

R₃ = { (s¹₂, s²₃), (s¹₂, s²₁₁), (s¹₃, s²₁₁), (s¹₂, s²₈), (s¹₂, s²₉), (s¹₂, s²₁₀), (s¹₃, s²₁₀) }.

Докажем, что R₃ Í (R₁ (Y*₁) ´ R₂ (X*₂)) Ç S₃:

R₁ (Y*₁) = {s²₂, s²₃, s²₄, s²₅},₂ (X*₂) = {s¹₃, s¹₈, s¹₉, s¹₁₀, s¹₁₁},₃ = { (s¹₃, s²₁), (s¹₄, s²₂), (s¹₂, s²₃), (s¹₂, s²₁₁), (s¹₃, s²₁₁), (s¹₄, s²₄), (s¹₄, s²₅), (s¹₄, s²₆), (s¹₄, s²₇), (s¹₂, s²₈), (s¹₂, s²₉), (s¹₂, s²₁₀), (s¹₃, s²₁₀) },

(R₁ (Y*₁) ´ R₂ (X*₂)) Ç S₃ = S_3,R₃ Î S₃ Þ₃ Í (R₁ (Y*₁) ´ R₂ (X*₂)) Ç S₃.

 

Выводы по выполнению операции композиции

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

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

 

Выводы:

Были исследованы основные операции над асинхронными процессами: репозиция, редукция и композиция. Где это было необходимо, доказано по определениям, что операции выполнены верно. В ходе выполнения операций были построены конкретные асинхронные процессы и объяснен их физический смысл.

 

5. Предметная интерпретация асинхронного процесса

Исходный асинхронный процесс

Для построения сети Петри интерпретируем множество ситуаций асинхронного процесса как множество допустимых разметок сети Петри. В качестве исходного возьмем асинхронный процесс P₁ из §2, представленный графом отношения непосредственного следования, в котором ситуации структурированы:

Построим таблицу допустимых разметок R (N) для сети Петри.

Ситуации	p1	p2	p3	R (N)
s11	0	1	1	M1
s12	0	1	0	M2
s13	1	0	0	M3
s14	1	0	1	M4
s15	0	0	1	M5

 

Сеть Петри

Построим сеть Петри, соответствующую данному асинхронному процессу с начальной разметкой M₁:

 

Граф разметок и дерево достижимости

Граф разметок будет выглядеть аналогично отношению непосредственного следования:

Дерево достижимости сети Петри:

6. Анализ свойств сети Петри

Свойства позиций

1.      Ограниченность. Каждая позиция p сети Петри является ограниченной, т.к. " p справедливо M (p) £ n, где n = 1, M (p) - функция, возвращающая количество фишек в позиции p. Следовательно, сеть в целом является ограниченной. Об ограниченности можно также судить по дереву достижимости, а именно, сеть является ограниченной, т.к. символ w отсутствует в ее дереве достижимости.

2.      Безопасность. Каждая позиция p сети Петри безопасна, т.к. " p справедливо M (p) £ 1. Следовательно, сеть в целом является безопасной.

3.      Консервативность. При работе сети сумма фишек во всех позициях не остается постоянной (1 или 2 фишки), т.е. не выполняется условие консервативности: " M₁, M₂ Î R (N) справедливо . Следовательно, сеть не является консервативной.

Свойства переходов

1.      Живость. Сеть Петри называется живой, если все ее переходы живы. Переход называется живым, если он является потенциально живым при любой достижимой в сети разметке. И, наконец, переход называется потенциально живым при разметке M, если $ разметка M' Î R (N), достижимая в сети N от разметки M / M'³ F (p,t). Таким образом, наша сеть не является живой, т.к. $ переход t₁₂, который не является потенциально живым при разметке M₅.

2.      Устойчивость. Переход называется устойчивым, если он может сработать, и никакой другой переход не может, сработав, лишить его этой возможности. Сеть называется устойчивой, если все ее переходы устойчивы. Для нашей сети $ переходы t₂₄ и t₂₃, которые не являются устойчивыми, в частности при разметке M₂. Таким образом, сеть не является устойчивой.

Выводы:

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

Свойствами позиций сети Петри являются ограниченность, безопасность и консервативность. Рассматриваемая сеть Петри является ограниченной, т.к. каждая ее позиция является ограниченной, и безопасной, т.к. каждая ее позиция является безопасной, но сеть не является консервативной, т.к. при переходе от одной разметки к другой число фишек для каждой разметки не одинаково.

Свойствами переходов являются живость и устойчивость. Данная сеть Петри не является живой, так как существуют переходы, которые не являются живыми, а также она не является устойчивой, т.к. существуют переходы, которые не являются устойчивыми.

Заключение

Целью этой работы является получение опыта по построению метамодели "асинхронный процесс" и ее модельной интерпретации в виде "сети Петри", а также по исследованию их свойств.

На основе реального физического процесса - печать листа на струйном принтере - была построена метамодель "асинхронный процесс". Был проведен анализ свойств процесса.

Над моделью были проведены основные операции (репозиции, редукция, композиция). Результату каждой операции был поставлен в соответствие конкретный физический процесс.

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

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

Литература

1.       Курс лекций по курсу "Теория вычислительных процессов" преподавателя кафедры ВМ и ПО ЭВМ МГТУ Лазаревой И. М.

2.       Автоматное управление асинхронными процессами в ЭВМ и дискретных системах. / Под ред. Варшавского.

.        Питерсон Дж. Теория сетей Петри и моделирование систем. - М.: Наука, 1984.

.        Гордеев А.В. Системное программное обеспечение: учеб. / Гордеев А.В., Молчанов А.Ю. - СПб.: Питер, 2001.