Задание

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

   1. построить метамодель «асинхронный процесс» и определить свойства исходного процесса на основе анализа метамодели;

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

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

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

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

операция асинхронный метамодель процесс

Предлагается рассмотреть процессы и ситуации происходящие при чтении / записи с CD-R – устройств. CD-R (устройство считывания и записи компакт-дисков) – напоминают обычные дисководы. Однако кроме приводов шпинделя и головки они имеют еще и механизм загрузки диска и более сложную головку считывания. Считывающая головка состоит из лазерного излучателя, фотоприемника и наклонного зеркала, зафиксированных на подвижной каретке головки. Для записи используются специальные диски, иногда называемые мишенями (Target). При записи луч лазера в нужных местах дорожки выжигает ямки в слое краски. За счет разницы коэффициента отражения ямок и невыжженных участков поверхности при считывании возникает модуляция яркости принятого луча, которая и несет полезную информацию. Обмен данными с памятью происходит без участия центрального процессора, для этого используется канал прямого доступа к памяти – DMA (Direct Memory Access).

Практически все устройства CD-R позволяют воспроизводить и аудио-диски, для чего они имеют встроенные ЦАПы (цифроаналоговые преобразователи) и аналоговый интерфейс с линейным выходом стереосигнала. Чтобы аудиоплейер не пытался воспроизводить установленный по ошибке диск с данными (это угрожает стереосистемам и ушам слушателя), для трека, содержащего данные, устанавливается флаг Data. Этот флаг проставляется в первом секторе диска.

Построение метамодели «асинхронный процесс»

Компоненты процесса

p₁=1

есть диск в лотке

p₂=1

если диск не пустой

p₃=1

если аудио диск

p₄=1

ЦАП в работе (есть данные)

p₅=1

головка считывает

p₆=1

головка записывает

p₇=1

аналоговый интерфейс включен

p₈=1

канал DMA в работе

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

S₁ – в лоток вставлен диск;

S₂ – считывание аудио информации;

S₃ – перевод цифровых данных в аналоговые;

S₄ – вывод сигнала в аналоговый интерфейс;

S₅ – считывание данных;

S₆ – вывод данных в канал DMA;

S₇ – получение данных из канала DMA;

S₈ – запись данных на диск.

Таблица векторов ситуаций

Ситуация

Вектор

P₁

P₂

P₃

P₄

P₅

P₆

P₇

P₈

S₁

1

0

0

0

0

0

0

0

S₂

1

1

1

0

1

0

0

0

S₃

1

1

1

1

0

0

0

0

S₄

1

1

1

0

0

0

1

0

S₅

1

1

0

0

1

0

0

0

S₆

1

1

0

0

0

0

0

1

S₇

1

0

0

0

0

0

0

1

S₈

1

0

0

0

0

1

0

0

Инициаторы: I={S_1, S_2, S_3, S_5, S₇}.

S₁ – ситуация, при которой в лоток вставлен диск, что свидетельствует о готовности устройства к выполнению своих основных функций, то есть непосредственно инициирует данный процесс;

S₂ – ситуация, при которой происходит считывание аудиоинформации, что влечет за собой работу с аудиоданными;

S₃ – ситуация, при которой происходит перевод цифровых данных в аналоговые, что влечет за собой вывод этих данных в аналоговый интерфейс;

S₅ – ситуация считывания данных инициирует вывод данных в канал DMA;

S₇ – ситуация чтения данных из канала DMA, инициирует запись их на диск.

Результанты: R={S_4, S_6, S₈}.

S₄, S₆, S₈ – ситуации являются результатом функционирования устройства, а именно: вывод сигнала в аналоговый интерфейс, вывод данных в канал DMA и запись данных на диск, соответственно.

Граф процесса.

S₁

S₅

S₂

S₃

S₄

S₆

S₇

S₈

Свойства рассматриваемого процесса.

Классы эквивалентности:

Начальным классом эквивалентности является класс {S_1, S_2, S_5, S₇}.

Конечными классами эквивалентности являются классы: {S₈}, {S₄}, {S₆}.

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

Где: S₁  S₇  S₈ – запись информации на диск;

S₁  S₂  S₃ S₄ – проигрывание аудио диска;

S₁  S₅  S₆ – чтение информации с диска.

1. АП является эффективным, т.к. из инициаторов все траектории ведут в результанты, и каждая из траекторий, приводящая к результантам, начинается в каком-либо инициаторе; в процессе нет циклов;

2. АП не является управляемым, так как траектории из инициаторов ведут в различные заключительные классы {S₈}, {S₄}, {S₆};

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

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

Репозицией асинхронного процесса P = (S, F, I, R) называется эффективный асинхронный процесс P’ = (S’, F’, I’, R’), такой что S’   (I  R  S^D), I’  R, R’  I.

Репозиция – это возобновление процесса, его повторная активации. Практически все процессы в реальных технических и вычислительных системах имеют репозицию, в них имеет место эффект возобновляемости. В случае с процессом работы CD-ROMа репозиция будет выполняться при повторном считывании аудио информации (считывании нового трека).

Объединенный граф основного процесса и репозиции:

S₁

S₅

S₂

S₃

S₄

S₆

S₇

S₈

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

Отношение задает траекторию перехода от элемента из множества I’ к элементам множества R’. Т.к. I’R, R’I и F’0, то репозиция является частичной.

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

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

Ситуации исходного процесса.

S₁ – в лоток вставлен диск;

S₂ – считывание аудио информации;

S₃ – перевод цифровых данных в аналоговые;

S₄ – вывод сигнала в аналоговый интерфейс;

S₅ – считывание данных;

S₆ – вывод данных в канал DMA;

S₇ – получение данных из канала DMA;

S₈ – запись данных на диск.

Ситуация

Вектор

P₁

P₂

P₃

P₄

P₅

P₆

P₇

P₈

S₁

1

0

0

0

0

0

0

0

S₂

1

1

1

0

1

0

0

0

S₃

1

1

1

1

0

0

0

0

S₄

1

1

1

0

0

0

1

0

S₅

1

1

0

0

1

0

0

0

S₆

1

1

0

0

0

0

0

1

S₇

1

0

0

0

0

0

0

1

S₈

1

0

0

0

0

1

0

0

Инициаторы и результанты исходного процесса:

I={S_1, S_2, S_3, S_5, S₇}.

R={S_4, S_6, S₈}.

В качестве входной компоненты выберем 1, 2 и3 элементы векторов ситуаций.

S₁^’

Выделим входную компоненту X^*={100,110}. Берём такие компоненты, так как именно этим входным компонентам соответствуют ситуации, имеющие непосредственное отношение к чтению / записи.

Тогда редукцией P (X*) будет являться:

S^* = {S_1, S_5, S_6, S_7, S₈};

Для каждого инициатора процесса P построим множество ситуаций S_iI, S(S_i), встречающихся на траекториях процесса P ведущих из указанного инициатора.

1: S₁  S₂  S₃ S₄

2: S₁  S₇  S₈

3: S₁  S₅  S₆

4: S₂  S₃  S₄

5: S₇  S₈

6: S₅  S₆

Образуем множество S(X^*), как объединение тех множеств S(S_i), для которых справедливо S(S_i)S^*.

S(X^*)={S_1, S_5, S_6, S_7, S₈};

;

;

R(X^*)={S_6, S₈}.

Построим граф процесса редукции:

S₇

S₈

S₁

S₅

S₆

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

Рассмотрим два АП. Один из них исходный процесс , другой – вновь построенный :

В качестве дополнительного процесса построим вспомогательный процесс, управляющий лотком CD-ROM’а.

Компоненты процесса :

p₁^’ – лоток закрыт;

p₂^’ – диск в лотке.

Ситуации процесса :

1. Лоток открыт, диска нет, устройство к работе не готово

p₁^’ – p₂^’–

2. Лоток закрыт, диск есть, устройство готово к работе

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

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

Выделим в дополнительном процессе выходную компоненту. Это компонента p₂^’ – диск в лотке. X₂ = {0,1}

В качестве выберем все наборы входной компоненты дополнительного процесса. X₂^* = {0,1}

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

Сцепление процессов будет происходить по компоненте {1}. То есть выходная компонента процесса соответствует входной компоненте .

Построим композицию исходного процесса и дополнительного .

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₃={(10000000), (10000000), (11101000), (11110000), (11100010), (11001000), (11000001), (10000001), (10000100)};

F₃ = {(S₃¹)(S₃²) (S₃⁸) (S₃⁹),

(S₃¹)(S₃²) (S₃³) (S₃⁴) (S₃⁵),

(S₃¹)(S₃²) (S₃⁶) (S₃⁷)};

I₃ = {(S₃¹), (S₃²), (S₃³), (S₃⁴), (S₃⁶), (S₃⁸)};

R₃ = {(S₃⁵), (S₃⁷), (S₃⁹)}.

Граф композиции:

S₃²

S₃⁹

S₃⁸

S₃⁷

S₃⁵

S₃⁴

S₃³

S₃⁶

Обеспечены условия 1, 2, 3, 4:

1),:

2) выходные компоненты ситуаций из равны входной компоненте ситуации из

3) если в компонента , то

4) если , то .

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

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

Сетью Петри называется пятёрка.

– конечное непустое количество условий;

– конечное непустое количество событий;

- функция инцидентности;

- функция инцидентности;

- начальная разметка.

P = {p₁, p₂, p₃, p₄, p₅, p₆, p₇, p₈}

- в лоток вставлен диск;

– диск не является чистым;

- диск с аудиоинформацией;

- работает ЦАП;

- происходит считывание данных;

- происходит запись данных;

- включен аналоговый интерфейс;

- канал DMA в работе.

T = {t₁, t₂, t₃, t₄, t₅, t₆, t₇}

– переход к считыванию данных;

– переход к считыванию аудиоинформации;

– переход к получению данных через канал DMA;

– переход к состоянию перевода цифровых данных в аналоговые;

– переход к состоянию вывода данных в канал DMA;

– переход к записи данных на диск;

– переход к выводу информации в аналоговый интерфейс.

F(p₁, t₁₎ = 2

F(p₁, t₂₎ = 2

F(p₁, t₃₎ = 2

F(p₂, t₄₎ = 1

F(p₂, t₅₎ = 2

F(p₃, t₄₎ = 1

F(p₅, t₄₎ = 1

F(p₅, t₅₎ = 2

F(p₄, t₇₎ = 1

F(p₈, t₆₎ = 2

H(t₁, p₁₎ = 1

H(t₁, p₂₎ = 2

H(t₁, p₅₎ = 2

H(t₂, p₁₎ = 1

H(t₂, p₂₎ = 1

H(t₂, p₃₎ = 1

H(t₂, p₅₎ = 1

H(t₃, p₈₎ = 2

H(t₄, p₄₎ = 1

H(t₅, p₂₎ = 1

H(t₅, p₈₎ = 1

H(t₆, p₆₎ = 1

M₀ = {2,0,0,0,0,0,0,0}

Граф разметок:

2 0 0 0 0 0 0 0

1 0 0 0 0 1 0 0

1 0 0 0 0 0 0 2

1 1 1 0 0 0 1 0

1 1 1 1 0 0 0 0

1 1 1 0 1 0 0 0

1 1 0 0 0 0 0 1

1 2 0 0 2 0 0 0

t₆

t₁

t₂

Замечание: одна или две фишки в данном графе соответствуют единице в ситуациях исходного процесса.

Свойства сети Петри:

1. Ограниченность сети. Места p₁, p₂, p₃, p₄, p₅, p₆, p₇, p₈ являются ограниченными (существует число достижимой в сети разметки M справедливо ) вся сеть является ограниченной;

2. Безопасность сети. Места p₁, p₂, p₈ не являются безопасными (для этих мест не выполняется условие ) вся сеть не является безопасной;

3. Живость сети. При переходы t₁, t₂, t₃, t₄, t₅, t₆, t₇ являются потенциально живыми в сети, но эти же переходы не являются живыми при любой достижимой в сети разметкесеть не является живой;

4. Устойчивость сети. Сеть не является устойчивой, так как существуют переходы, которые, сработав, могут лишить другой переход этой возможности: переходы , и t₃ взаимно блокируются;

Вывод.

1. Система выполняет те функции, для которых она предназначена;

2. Данная система функционирует эффективно;

3. В исходном АП ошибки и аварийные ситуации возникнуть не могут;

4. Систему упростить нельзя, т. к. она уже является достаточно упрощённой.

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

Заключение

t₆

t₃

В данной работе были рассмотрены процессы и ситуации происходящие при чтении / записи с CD – устройств. Процесс представлен в очень упрощенном виде. Было установлено, что АП, построенный на основе данного вычислительного процесса, является эффективным, не является управляемым и не является простым. В результате проведения операции репозиции над процессом получили новый процесс, в котором считывание аудиоинформации может происходить требуемое число раз. В результате проведения операции редукции были выделены ветви, которые соответствуют чтению и записи на диск. Т.о. был выделен более простой подпроцесс. Вследствие последовательной композиции исходного и вспомогательного процесса получили новый несколько усложненный процесс. Описаны составляющие модели «асинхронный процесс», используя понятия модели «сеть Петри». Проведён анализ свойств мест сети Петри на ограниченность и безопасность: сеть ограниченная и не безопасная. Проведён анализ свойств переходов сети Петри на живость и устойчивость: сеть не является потенциально живой, и не является устойчивой.

Можно утверждать, что система функционирует эффективно и выполняет те функции, для которых она предназначена.