Задание
1. Выбратьвычислительный процесс и на его примере:
a. построитьметамодель «асинхронный процесс» и определить свойства исходного процесса наоснове анализа метамодели;
b. выполнитьоперации над процессом: репозиция, редукция, композиция, и оценить полученныерезультаты с практической точки зрения;
c. построитьпредметную интерпретацию метамодели на основе сети Петри и сделать вывод одинамических характеристиках исходного процесса.
2. Оформитьотчет.
Описаниепроцесса
операция асинхронный метамодель процесс
Предлагаетсярассмотреть процессы и ситуации происходящие при чтении / записи с CD-R – устройств. CD-R (устройство считывания изаписи компакт-дисков) – напоминают обычные дисководы. Однако кроме приводовшпинделя и головки они имеют еще и механизм загрузки диска и более сложнуюголовку считывания. Считывающая головка состоит из лазерного излучателя,фотоприемника и наклонного зеркала, зафиксированных на подвижной кареткеголовки. Для записи используются специальные диски, иногда называемые мишенями(Target). При записи луч лазерав нужных местах дорожки выжигает ямки в слое краски. За счет разницыкоэффициента отражения ямок и невыжженных участков поверхности при считываниивозникает модуляция яркости принятого луча, которая и несет полезнуюинформацию. Обмен данными с памятью происходит без участия центральногопроцессора, для этого используется канал прямого доступа к памяти – DMA (Direct Memory Access).
Практическивсе устройства CD-Rпозволяют воспроизводить и аудио-диски, для чего они имеют встроенные ЦАПы(цифроаналоговые преобразователи) и аналоговый интерфейс с линейным выходомстереосигнала. Чтобы аудиоплейер не пытался воспроизводить установленный поошибке диск с данными (это угрожает стереосистемам и ушам слушателя), длятрека, содержащего данные, устанавливается флаг Data. Этот флаг проставляетсяв первом секторе диска.
Построениеметамодели «асинхронный процесс»
Компонентыпроцесса p1=1 есть диск в лотке
p2=1 если диск не пустой
p3=1 если аудио диск
p4=1 ЦАП в работе (есть данные)
p5=1 головка считывает
p6=1 головка записывает
p7=1 аналоговый интерфейс включен
p8=1 канал DMA в работе
Множествоситуаций процесса.
S1 – в лоток вставлен диск;
S2 – считывание аудиоинформации;
S3 – перевод цифровых данныхв аналоговые;
S4 – вывод сигнала ваналоговый интерфейс;
S5 – считывание данных;
S6 – вывод данных в канал DMA;
S7 – получение данных изканала DMA;
S8 – запись данных на диск.
Таблицавекторов ситуаций Ситуация Вектор
P1
P2
P3
P4
P5
P6
P7
P8
S1 1
S2 1 1 1 1
S3 1 1 1 1
S4 1 1 1 1
S5 1 1 1
S6 1 1 1
S7 1 1
S8 1 1
Инициаторы: I={S1,S2, S3, S5, S7}.
S1 – ситуация, при которойв лоток вставлен диск, что свидетельствует о готовности устройства к выполнениюсвоих основных функций, то есть непосредственно инициирует данный процесс;
S2 – ситуация, при которойпроисходит считывание аудиоинформации, что влечет за собой работу саудиоданными;
S3 – ситуация, при которойпроисходит перевод цифровых данных в аналоговые, что влечет за собой вывод этихданных в аналоговый интерфейс;
S5 – ситуация считыванияданных инициирует вывод данных в канал DMA;
S7 – ситуация чтения данныхиз канала DMA, инициирует запись их на диск.
Результанты: R={S4, S6, S8}.
S4, S6, S8 – ситуации являютсярезультатом функционирования устройства, а именно: вывод сигнала в аналоговыйинтерфейс, вывод данных в канал DMA и запись данных на диск, соответственно.
Графпроцесса.
/>
Свойстварассматриваемого процесса.
Классыэквивалентности:
Начальнымклассом эквивалентности является класс {S1, S2, S5, S7}.
Конечнымиклассами эквивалентности являются классы: {S8}, {S4}, {S6}.
Допустимыетраектории: />
Где: S1 à S7 à S8 – запись информации надиск;
S1 à S2 à S3à S4 – проигрываниеаудио диска;
S1 à S5 à S6 – чтение информации сдиска.
1) АП является эффективным,т.к. из инициаторов все траектории ведут в результанты, и каждая из траекторий,приводящая к результантам, начинается в каком-либо инициаторе; в процессе нетциклов;
2) АП не являетсяуправляемым, так как траектории из инициаторов ведут в различные заключительныеклассы {S8}, {S4}, {S6};
3) АП не является простым, т.к.из инициатора />существуетпереход к инициаторам />/>не выполняется />.
Операциинад процессами
Репозицией асинхронного процесса P = (S, F, I, R) называется эффективныйасинхронный процесс P’ = (S’, F’, I’, R’), такой что S’ Í Í (I È R È SD), I’ Í R, R’ Í I.
Репозиция – это возобновлениепроцесса, его повторная активации. Практически все процессы в реальныхтехнических и вычислительных системах имеют репозицию, в них имеет место эффектвозобновляемости. В случае с процессом работы CD-ROMа репозиция будетвыполняться при повторном считывании аудио информации (считывании новоготрека).
/>
/>
/>
/>
Объединенныйграф основного процесса и репозиции:
/>
В результатепроведения операции репозиции над процессом получили новый процесс, в которомсчитывание аудиоинформации может происходить требуемое число раз, что болееприближено к реальным условиям.
Отношение />задает траекторию переходаот элемента из множества I’ к элементам множества R’. Т.к. I’R, R’Iи F’, то репозиция являетсячастичной.
Редукция позволяетвыделить отдельные ветви процесса, что характерно при рассмотрении отдельныхситуаций. Таким образом, редукция может быть полезна для изучения отдельныхэлементов процесса.
Проведемредукцию нашего процесса так, чтобы в результате из процесса выделились ветвичтения и записи на диск.
Ситуацииисходного процесса.
S1 – в лоток вставлен диск;
S2 – считывание аудиоинформации;
S3 – перевод цифровых данныхв аналоговые;
S4 – вывод сигнала ваналоговый интерфейс;
S5 – считывание данных;
S6 – вывод данных в канал DMA;
S7 – получение данных изканала DMA;
S8 – запись данных на диск. Ситуация Вектор
P1
P2
P3
P4
P5
P6
P7
P8
S1 1
S2 1 1 1 1
S3 1 1 1 1
S4 1 1 1 1
S5 1 1 1
S6 1 1 1
S7 1 1
S8 1 1 /> /> /> /> /> /> /> /> /> />
Инициаторы ирезультанты исходного процесса:
I={S1,S2, S3, S5, S7}.
R={S4,S6, S8}.
В качествевходной компоненты выберем 1, 2 и3 элементы векторов ситуаций.
S1’ />
Выделимвходную компоненту X*={100,110}. Берём такие компоненты, так как именно этим входнымкомпонентам соответствуют ситуации, имеющие непосредственное отношение к чтению /записи.
Тогдаредукцией P (X*) будет являться:
S* = {S1, S5, S6, S7, S8};
Для каждогоинициатора процесса P построим множество ситуаций SiI, S(Si), встречающихся натраекториях процесса P ведущих из указанного инициатора.
1:S1 à S2 à S3à S4
2:S1 à S7 à S8
3:S1 à S5 à S6
4: S2 à S3 à S4
5: S7 à S8
6: S5 à S6
Образуеммножество S(X*), как объединение техмножеств S(Si), для которых справедливоS(Si)S*.
S(X*)={S1,S5, S6, S7, S8};
/>;
/>;
R(X*)={S6,S8}.
Построим графпроцесса редукции:
/>
Такимобразом, в результате редукции были выделены ветви, которые соответствуютчтению и записи на диск. То есть из исходного процесса выделили более простойподпроцесс.
Рассмотримдва АП. Один из них исходный процесс />, другой– вновь построенный />:
В качестведополнительного процесса построим вспомогательный процесс, управляющий лотком CD-ROM’а.
Компонентыпроцесса />:
p1’– лоток закрыт;
p2’– диск в лотке.
Ситуациипроцесса />:
1. Лотокоткрыт, диска нет, устройство к работе не готово
p1’– p2’–
2. Лотокзакрыт, диск есть, устройство готово к работе
Выделим висходном процессе первую (лоток) компоненту в качестве входной. Выбираемналичие диска в лотке, так как оно является основным показателем того, чтоустройство функционирует. Выбираем в исходном процессе ситуации, при которых влотке имеется диск (первая компонента; т.е. все ситуации). Таким образом,получаем исходный процесс целиком. Это соответствует действительности, так какна всех стадиях работы устройства в нем имеется диск.
Очевидно, чторедукцией процесса /> по определеннойвыше компоненте (назовем ее />) будетявляться весь исходный процесс, т.е.: />.
Выделим вдополнительном процессе выходную компоненту. Это компонента p2’ – диск в лотке. X2 = {0,1}
В качестве /> выберем все наборы входнойкомпоненты дополнительного процесса. X2* = {0,1}
Дополнительныйпроцесс />представлен простойлинейной структурой, которая не нуждается в дополнительном упрощении.
Сцеплениепроцессов будет происходить по компоненте {1}. То есть выходная компонентапроцесса />соответствует входнойкомпоненте />.
Построимкомпозицию исходного процесса /> идополнительного />.
/>
S31=(S1,S1’);
S32=(S1,S2’);
S33=(S2,S2’);
S34=(S3,S2’);
S35=(S4,S2’);
S36=(S5,S2’);
S37=(S6,S2’);
S38=(S7,S2’);
S39=(S8,S2’);
S3={(10000000),(10000000), (11101000), (11110000), (11100010), (11001000), (11000001), (10000001),(10000100)};
F3= {(S31)à(S32)à (S38)à (S39),
(S31)à(S32)à (S33)à (S34)à (S35),
(S31)à(S32)à (S36)à (S37)};
I3= {(S31), (S32), (S33),(S34), (S36), (S38)};
R3 = {(S35), (S37), (S39)}.
Граф композиции:
/>
Обеспеченыусловия 1, 2, 3, 4:
1)/>,/>:/>
2) выходныекомпоненты /> ситуаций из /> равны входной компоненте /> ситуации из />
3) если в /> компонента />, то />
4) если />, то />.
Такимобразом, выбрав в качестве дополнительного процесса небольшой подпроцесс,предшествующий основному процессу, построили композицию этих процессов путёмвыделения входных и выходных компонент соответствующих процессов и последующегоих (процессов) сцепления. Исходный процесс не стали упрощать с помощьюрепозиции, так как по смыслу данной композиции модель должна сохранить своюцелостность. Получившийся процесс /> представляетсобой несколько усложнённый исходный процесс.
Предметнаяинтерпретация асинхронного процесса
Сетью Петриназывается пятёрка/>.
/> – конечное непустоеколичество условий;
/> – конечное непустоеколичество событий;
/> — функция инцидентности;
/> — функция инцидентности;
/> — начальная разметка.
P= {p1, p2, p3, p4, p5, p6, p7, p8}
/> — в лоток вставлен диск;
/> – диск не являетсячистым;
/> — диск саудиоинформацией;
/> — работает ЦАП;
/> — происходит считываниеданных;
/> — происходит записьданных;
/> — включен аналоговыйинтерфейс;
/> — канал DMA в работе.
T= {t1, t2, t3, t4, t5, t6, t7}
/> – переход к считываниюданных;
/> – переход к считываниюаудиоинформации;
/> – переход к получениюданных через канал DMA;
/> – переход к состояниюперевода цифровых данных в аналоговые;
/> – переход к состояниювывода данных в канал DMA;
/> – переход к записиданных на диск;
/> – переход к выводуинформации в аналоговый интерфейс.
F(p1, t1) = 2
F(p1, t2) = 2
F(p1, t3) = 2
F(p2, t4) = 1
F(p2, t5) = 2
F(p3, t4) = 1
F(p5, t4) = 1
F(p5, t5) = 2
F(p4, t7) = 1
F(p8, t6) = 2
H(t1, p1) = 1
H(t1, p2) = 2
H(t1, p5) = 2
H(t2, p1) = 1
H(t2, p2) = 1
H(t2, p3) = 1
H(t2, p5) = 1
H(t3, p8) = 2
H(t4, p4) = 1
H(t5, p2) = 1
H(t5, p8) = 1
H(t6, p6) = 1
M0= {2,0,0,0,0,0,0,0}
Графразметок:/> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
Замечание:одна или две фишки в данном графе соответствуют единице в ситуациях исходногопроцесса.
Свойства сетиПетри:
1) Ограниченностьсети.Места p1, p2, p3, p4, p5, p6, p7, p8 являются ограниченными(существует число /> достижимой всети разметки Mсправедливо />)/> вся сеть являетсяограниченной;
2) Безопасностьсети.Места p1, p2, p8 не являются безопасными(для этих мест не выполняется условие />)/> вся сеть не являетсябезопасной;
3) Живостьсети.При />переходы t1, t2, t3, t4, t5, t6, t7 являются потенциальноживыми в сети, но эти же переходы не являются живыми при любой достижимой всети разметке/>сеть не является живой;
4) Устойчивостьсети.Сеть не является устойчивой, так как существуют переходы, которые, сработав,могут лишить другой переход этой возможности: переходы />, /> и t3 взаимно блокируются;
Вывод.
1) Системавыполняет те функции, для которых она предназначена;
2) Даннаясистема функционирует эффективно;
3) Висходном АП ошибки и аварийные ситуации возникнуть не могут;
4) Системуупростить нельзя, т. к. она уже является достаточно упрощённой.
На основепостроенной модели была создана сеть Петри для заданного процесса. В качествеситуаций были взяты компоненты исходного процесса. Между ситуациями былирасставлены переходы, а также установлена начальная разметка. После былпостроен граф разметок, который полностью совпал с исходным графом процесса,что свидетельствует о правильности построения и функционирования сети Петри.
Заключение
t6
t3 Вданной работе были рассмотрены процессы и ситуации происходящие при чтении /записи с CD – устройств. Процесс представлен в очень упрощенном виде. Былоустановлено, что АП, построенный на основе данного вычислительного процесса,является эффективным, не является управляемым и не является простым.Врезультате проведения операции репозиции над процессом получили новый процесс,в котором считывание аудиоинформации может происходить требуемое число раз. Врезультате проведения операции редукции были выделены ветви, которые соответствуютчтению и записи на диск. Т.о. был выделен более простой подпроцесс. Вследствиепоследовательной композиции исходного и вспомогательного процесса получилиновый несколько усложненный процесс. Описаны составляющие модели «асинхронныйпроцесс», используя понятия модели «сеть Петри». Проведён анализ свойств местсети Петри на ограниченность и безопасность: сеть ограниченная и не безопасная.Проведён анализ свойств переходов сети Петри на живость и устойчивость: сеть неявляется потенциально живой, и не является устойчивой.
Можно утверждать, чтосистема функционирует эффективно и выполняет те функции, для которых онапредназначена.