Оглавление
1. Задание
2. Описание процесса
3. Построение метамодели«асинхронный процесс»
4. Свойства процесса
4.1Эффективность
4.2Управляемость
4.3 Простота
5. Операции надпроцессом
5.1Репозиция
5.2 Редукция
5.3Композиция
6. Построение сетиПетри
7. Анализ свойствмест с. Петри на ограниченность и безопасность
8. Анализ свойствпереходов с. Петри на живость и устойчивость
9. Заключение
Список использованной литературы
1. Задание
Целью расчетно-графического заданияявляется получение опыта в конструировании метамодели «асинхронный процесс» имодели «сеть Петри» и в исследовании их свойств.
Предлагается выполнить следующее:
1. Выделитькомпоненты рассматриваемого процесса.
2. Сформироватьмножество ситуаций рассматриваемого процесса.
3. Описать модель«асинхронный процесс».
4. Определитьтраектории выполнения процесса и классы эквивалентности ситуаций и сделатьвывод о свойствах рассматриваемого процесса (эффективность, управляемость,простота).
5. Определитьмножество дополнительных ситуаций для возобновления процесса (если они есть) ипостроить полную или частичную репозицию процесса.
6. Выделить входныеили выходные компоненты асинхронного процесса, выбрать требуемые и построить наих основе редукцию процесса.
7. Определить два подпроцессана базе исследуемого, выбрать удобный вид композиции (последовательную илипараллельную) и построить ее.
8. Описатьсоставляющие модели «асинхронный процесс», используя понятия модели «сетьПетри».
9. Провести анализсвойств мест сети Петри на ограниченность и безопасность.
10. Провести анализсвойств переходов сети Петри на живость и устойчивость.
2. Описание процесса
асинхронный репозицияредукция сеть пери
В качестве вычислительного процессабыл выбран процесс со следующим названием: «Запись информации на магнитныйноситель». Кратко опишем его суть.
Процесс записи на магнитный дискявляется достаточно сложной задачей и составить метамодель «асинхронныйпроцесс» во всех деталях соответствующую реальному процессу не представляетсявозможным, так как неизбежны сильная детализация, а так же повышение сложностимодели.
Процесс записи опишем следующейпоследовательностью команд и операций: магнитный диск вставлен в дисковод иготов для записи (часть магнитной поверхности уже может содержать какую-либоинформацию). Дисковод состоит из множества механических деталей и механизмов,управление которыми осуществляет микроконтроллер – устройство, которое получаеткоманды от центрального процессора и выполняет их.
Запись информации производитсяспециальной записывающей головкой, которая подводится к соответствующей дорожкеи сектору с помощью системы позиционирования головки. Запись информациипроисходит посекторно. Количество секторов для записи содержится в специальномрегистре контроллера и декрементируется после записи очередного сектора.
После того как очередной секторзаписан, головка позиционируется на следующий сектор. Очередная порция данных(для записи) считывается по шине данных.
После того, как данные записаны,производится контроль записи (верификация или CRC (проверка контрольнойсуммы)). Такая операция необходима для проверки правильности записаннойинформации. В случае ошибки записи, специальный регистр (Data Error Register)устанавливается в единицу и запись прекращается. Головки при этом отводятся отповерхности.
Успешная запись всех секторовзавершается сбрасыванием в 0 регистра ошибок данных. Регистр, содержащийколичество секторов для записи так же обнуляется. Головки отводятся отповерхности магнитного носителя и контроллер выдает сигнал по шине данныхпроцессору об окончании операции ввода/вывода.
3. Построение метамодели «асинхронныйпроцесс»
Прежде всего, выделим компонентырассматриваемого процесса:1. N 2. Обозначение 3. Описание 4. 1 5. K 6. Микроконтроллер дисковода. Работает (K+) 7. 2 8. S 9. Свободное место. Есть в наличии (S+) или нет (S-) 10. 3 11. E 12. Регистр, сигнализирующий ошибку. Произошла ошибка (E+) 13. 4 14. P 15. Механизм позиционирования головки записи. Задействован (P+) 16. 5 17. W 18. Головка записи. Записывает информацию (W+) 19. 6 20. C 21. Блок контроля правильности записи (crc check). Проводится проверка (C+) 22. 7 23. F 24. Fat таблица. Обновление fat таблицы после записи (F+)
Для описания процессов и задания ихвзаимодействия требуется структурирование ситуаций. Структурируем ситуации попервому способу, при котором каждая из ситуаций представляется двоичнымвектором, размерность которого равна числу семантически задаваемых компонент, ачисло единиц вектора соответствует числу истинных в этой ситуации предикатов.
Используя выделенные компоненты,опишем ситуации, возникающие в процессе записи информации на магнитныйноситель:25. Ситуация 26. K 27. S 28. E 29. P 30. W 31. C 32. F 33. Описание 34. S1 35. 1 36. 0 37. 0 38. 0 39. 0 40. 0 41. 0 42. Контроллер активен и ожидает команду от процессора на запись 43. S2 44. 1 45. 1 46. 0 47. 0 48. 0 49. 0 50. 0 51. Есть свободное место для записи 52. S3 53. 1 54. 0 55. 1 56. 0 57. 0 58. 0 59. 0 60. Места нет. Регистр ошибки устанавливается в код ошибки. 61. S4 62. 1 63. 1 64. 0 65. 1 66. 0 67. 0 68. 0 69. Головка подводится на нужный сектор 70. S5 71. 1 72. 1 73. 0 74. 0 75. 1 76. 0 77. 0 78. Запись информации в сектор 79. S6 80. 1 81. 1 82. 0 83. 0 84. 0 85. 1 86. 0 87. Проверка валидности записанных данных 88. S7 89. 1 90. 1 91. 0 92. 1 93. 0 94. 0 95. 1 96. Успешная запись, головки отводятся от поверхности, обновляется таблица fat. 97. S8 98. 1 99. 1 100.1 101.0 102.0 103.0 104.0 105.Некорректная запись информации.
Назовем асинхронным процессомчетверку , в которой: S — непустое множество ситуаций;
F — отношение непосредственногоследования ситуаций, определенное на множестве S´S (FÌ S´S);
I — множество инициаторов (IÌS), т.е. таких ситуаций из S, для которых если iFSk, iÎI, SkÎI, то из SkFSl следует, что SlÏI;
R — множество результантов (RÌS), т.е. таких ситуаций из S, для которых, если rFS, rÎR, то SÎR.
Согласно этому определению, имеем длярассматриваемого процесса:
/>
P=
S={/> }
I={/>},
Где />-инициирует запись
/>-инициирует проверку записанныхданных
R={ />}, где
/>-нет места для записи
/>-успешная запись
/>-ошибка записи информации
Выпишем все возможные траекториипроцесса:
/> - не хватает места для записи
/> - успешный процесс записи
/> - ошибка записи
/> - неудачная проверка записанныхданных
/> - удачная проверка записанных данных
4. Свойства процесса
Рассмотрим свойства асинхронногопроцесса.
4.1 Эффективность
Пусть задан АП, у которого :
1. для любого sÎS \ R найдется rÎRтакой, что sMr;
2. для любого sÎS \ I найдется iÎIтакой, что iMs;
3. не найдетсяситуации Si и Sj таких, что (SiÏR)&(SjÏR)&(SiMSj)&(SjMSi).
АП, удовлетворяющий свойствам 1 — 3,будет называться эффективным, т.е. из инициаторов эффективного процесса всетраектории ведут в результанты (свойство 1 и 3), и каждая из траекторий,приводящих к результанту, начинается в каком-либо инициаторе (св. 1 и 2).Эффективность АП оставляет место недетерминированности, т.е. возможно, что изнекоторого инициатора процесс попадает в разные результанты, но он не содержиториентированных циклов вне ситуаций, принадлежащих I и R.
Вывод: данный процесс не являетсяэффективным (не выполняется свойство 3), так как процесс содержит цикл /> вне ситуаций, принадлежащих I и R.
4.2 Управляемость
Если в эффективном АП каждаядопустимая последовательность классов ведет из начального класса в один итолько один заключительный класс, то такой процесс называется управляемым.Таким образом, в управляемом АП вводится ограничение на степень недетерминизма:все траектории из любого инициатора ведут в один заключительный класс.
Для определения того факта, является процесс управляемым илинет, разобьем множество ситуаций S наклассы эквивалентности.
/>/>/>/>
/>/> ,
где класс /> - начальный, а классы /> - заключительные.
Вывод: данный процесс не является управляемым, так как из начальногокласса /> можно попасть в заключительный класс />, а также в класс />. То есть не выполняется условиедетерминированности.
4.3 Простота
Пусть в эффективном АП:
1. для любых iÎI и sÎS из iFs Þ sÏI;
2. для любых sÎS и rÎR из sFr Þ sÏR
(т.е. из инициатора (результанта)нельзя попасть в другой инициатор (результант) т.е. каждая траектория содержитв точности по одному инициатору и результанту). АП, удовлетворяющий свойствам 1и 2 будет называться простым.
Вывод: процесс не является простым.Траектории
/>
/>
содержат по 2 инициатора (отмечены подчеркиванием)
5. Операции над процессами
5.1 Репозиция
Репозицией АП задается механизмперехода от результанта к инициаторам
Репозицией АП P = назовем эффективный АП P' = ,такой, что S' Í IÈRÈSD, I' Í R, R' Í I.
Ситуации S' репозиции могут содержать лишь те ситуации из исходногопроцесса, которые являются лишь инициаторами или результантами, и, кроме того,некоторые дополнительные ситуации из SD, отсутствующие в описании исходного АП.
Отношение F' задает траектории переходов от элементов из I' Í R к элементам R' Í I, возможно через дополнительные ситуации из SD.Если I' = R, R' = I, то репозицию назовем полной. Если F' = Æ, то репозиция не существует, в остальных случаях онаназывается частичной.
Для рассматриваемого процесса имеем:
/>
P' =
S' Í I È R È SD = { /> }SD = Æ
I'={ />}R'={ /> }
F':/>(повторить процесс записи сначала)
/>(повторить проверку записи данных)
Траектории переходов, которые задаетотношение F' показаны на рисунке пунктирной стрелкой.
Вывод: таким образом, построена частичнаярепозиция асинхронного процесса, суть которой – получение механизма еговозобновления. Семантически репозиция означает повтор операции записи (приуспешной записи) и повтор операции проверки записанных данных (в случаевозникновения ошибки записи).
5.2 Редукция
Операция редукции состоит в сведенииданного АП к более простому. Такая операция необходима тогда, когда из полногоописания процесса хочется выделить некоторую его часть, рассмотрение которойинтересно по тем или иным причинам.
Пусть задан неприведенный АП Р = , ситуации которогоструктурированы по 2-му способу. Образуем р-блочное разбиение множества S процесса Р, в ситуациях каждогоблока которого входная компонента принимает фиксированное значение xj, 1jp.
Выберем r
Для каждого инициатора siÎI постоим множество ситуаций S(si), встречающихся на траекторияхпроцесса Р, ведущих из указанного инициатора.
Образуем множество S(X*), как объединение тех множеств S(si),для которых справедливо
S(si)S*, т.е. S(X*) = />
Построим также F(X*) = F Ç (S(X*)´S(X*)),I(X*) = I Ç S(X*), R(X*) = R Ç S(X*).
Назовем процесс P(X*) = редукцией неприведенногопроцесса P = по выбранному множеству Х* значений входной компоненты.
Для рассматриваемого процесса имеем:106.Ситуация 107.K 108.S 109.E 110.P 111.W 112.C 113.F 114.S1 115.1 116.0 117.0 118.0 119.0 120.0 121.0 122.S2 123.1 124.1 125.0 126.0 127.0 128.0 129.0 130.S3 131.1 132.0 133.1 134.0 135.0 136.0 137.0 138.S4 139.1 140.1 141.0 142.1 143.0 144.0 145.0 146.S5 147.1 148.1 149.0 150.0 151.1 152.0 153.0 154.S6 155.1 156.1 157.0 158.0 159.0 160.1 161.0 162.S7 163.1 164.1 165.0 166.1 167.0 168.0 169.1 170.S8 171.1 172.1 173.1 174.0 175.0 176.0 177.0
S={/> }
Выберем в качестве значений входнойкомпоненты первые три элемента вектора.
Выпишем множество X={ 100, 110, 101, 111 }
Редукцию сделаем по следующемумножеству X*={100, 101}, то есть семантическирассмотрим ситуацию, когда нет свободного места для записи.
Тогда S* = { />}.
Рассмотрим траектории процесса:
/> (подходит, так как ситуации принадлежатS*)
/> (не подходит, т.к. /> не принадлежат S*)
/> (не подходит)
/> (не подходит)
/> (не подходит)
Образуем множество S(X*)={ />}, I(X*)={/>},R(X*)= {/>}
F(X*):/>
/>
Вывод: построив редукцию данного процессапо выбранным значениям входной компоненты, мы упростили процесс и рассмотрелитолько ту часть его, в которой складывается ситуация нехватки места на диске. Витоге получаем одну ветвь процесса, в которой фиксируется ошибка и код еезаносится в регистр ошибок.
5.3 Композиция
Обозначим исходный процесс как P2. Для него имеем:
S2={ /> }I2={/>}R2={ />}
Рассмотрим новый процесс P1, состоящий из следующих компонент:178.N 179.Обозначение 180.Описание 181.1 182.K 183.Контроллер дисковода 184.2 185.P 186.Дисковод работает. Есть электропитание (P+) 187.3 188.D 189.Диск вставлен в дисковод (D+)
/>
190.Ситуация 191.K 192.PW 193.D 194.S1 195.1 196.1 197.0 198.S2 199.1 200.1 201.1
Для процесса P1 имеем: S1={ /> }I1={ /> }R1={ /> }
Построим последовательную композициюпроцессов P1 и P2.
Х*={1}
Построим редукцию процесса P2 по X*.
S2*={ />}
Траектории:
/>(подходит)
/>(подходит)
/>(подходит)
/>(подходит)
/>(подходит)
/>
Следовательно: S2 (X*) = { />} I2 (X*) = { />} R2 (X*)= {/> }
/>
Далее построим редукцию процесса P1 по X*.
S1*={ /> }
Траектории:
/>
Следовательно: S1(X*) = { />} I1 (X*) = { /> } R1 (X*)= {/> }
Теперь построим процесс P3.
Для процесса P3 имеем: S3={ /> I3={ /> }R3={ /> }202.Ситуация 203.K 204.S 205.E 206.P 207.W 208.C 209.F 210.PW 211.D 212.S1 213.1 214.0 215.0 216.0 217.0 218.0 219.0 220.1 221.0 222.S2 223.1 224.0 225.0 226.0 227.0 228.0 229.0 230.1 231.1 232.S3 233.1 234.0 235.0 236.0 237.0 238.0 239.0 240.1 241.1 242.S4 243.1 244.1 245.0 246.0 247.0 248.0 249.0 250.1 251.1 252.S5 253.1 254.0 255.1 256.0 257.0 258.0 259.0 260.1 261.1 262.S6 263.1 264.1 265.0 266.1 267.0 268.0 269.0 270.1 271.1 272.S7 273.1 274.1 275.0 276.0 277.1 278.0 279.0 280.1 281.1 282.S8 283.1 284.1 285.0 286.0 287.0 288.1 289.0 290.1 291.1 292.S9 293.1 294.1 295.0 296.1 297.0 298.0 299.1 300.1 301.1 302.S10 303.1 304.1 305.1 306.0 307.0 308.0 309.0 310.1 311.1
Вывод: таким образом построенапоследовательная композиция процессов P1 и P2. Семантически ситуации процесса P1 предшествуют ситуациям процесса P2. Их суть – процесс подготовкиносителя к записи информации.
6. Построение сети Петри
Сетью Петри называется пятерка N = , где
Р = {p1,...,pn} — конечное непустое множество условий
T = {t1,...,tm} — конечное непустое множество событий
/> - функция инцидентности
М0: Р ® {0, 1, 2,...} — начальная разметка.
Сеть Петри есть модельнаяинтерпретация АП.Ситуациями в сети является начальная разметка М0ивсе разметки, достижимые от М0, т.е. МÎR(N). Отношение F для любой возможной разметки Мзадает все разметки, которые могут непосредственно следовать за М. Очевидно,что на множестве R(N) можно определить отношениеэквивалентности разметок и задать отношение F непосредственного следования для классов эквивалентности.
/>
Построим сеть Петри для следующейтраектории рассматриваемого процесса:
/>, что семантически соответствуетуспешному процессу записи данных.
Выпишем значения компонент.Компонента E во всех ситуациях равна 0, поэтомуэта компонента не учитывается при построении сети Петри.312. 313.K 314.S 315.W 316.P 317.C 318.F
319./> 320.1 321.0 322.0 323.0 324.0 325.0
326./> 327.1 328.1 329.0 330.0 331.0 332.0
333./> 334.1 335.1 336.1 337.0 338.0 339.0
340./> 341.1 342.1 343.0 344.1 345.0 346.0
347./> 348.1 349.1 350.0 351.0 352.1 353.0
354./> 355.1 356.1 357.0 358.0 359.0 360.1
/>
Формальное описание:
N=>
/>
/>
/>
/>/>
/>/>
/>
/>/>
/>/>
/>/>
/>
7. Анализ свойств мест с. Петри наограниченность и безопасность
Место (условие) р в сети N = (P,T,F,W,M0) называется ограниченным, еслисуществует число n такое, что длялюбой достижимой в сети разметки М справедливо неравенство М(р) n. Сеть называется ограниченной, если любое ее местоограниченно.
Множество достижимых разметок R(N) конечно, если и только если N — ограниченная сеть.
Место р называется безопасным, еслидля любого МÎ R(N): М(р) 1, соответственно сеть безопасна, если все ее местабезопасны. Любая достижимая в безопасной сети разметка представляет собойвектор из 0 в 1.
Ограниченность и безопасностьхарактеризуют емкость условий: в дискретной информационной системе,моделирующей соотношением систем, можно ограничить емкость накопителей,необходимых для хранения условий наступления событий.
Изобразим граф разметок. (см. рис.).
/>
Вывод:
Все места в сети ограничены, так какдля любого места p: M(p)£n (n=1). Следовательно сеть ограниченная.
Все места являются безопасными, таккак для любого места p: M(p) £1. Следовательно сеть безопасная (это значит, что всеразметки состоят из 0-ей и 1-иц).
8. Анализ свойств переходов с. Петрина живость и устойчивость
Переход t в сети Петри N = (P,T,F,W,M0) называется потенциально живым при разметке МÎR(N), если существует M’ÎR(N,M): M’³ F(p,t), т.е. существует достижимая от Мразметка М’, при которой переход tможет работать.
Если М = М0, то t называется потенциально живым в сетиN.
Переход t – мертвый при М, если он не является потенциально живым приМ. Переход t — мертвый, если он мертвый при любойдостижимой в сети разметке.
Переход t в сети Петри называется живым, если для любого MÎR(N) cсуществует M’Î R(N,M): M ³ F(p,t), т.е. он потенциально живой прилюбой достижимой в сети разметке. Сеть называется живой, если все ее переходыживы.
Переход t называется потенциально мертвым, если существует MÎR(N), такая, что при любой разметке M’ÎR(N,M) переход t неможет работать.
Переход t называется устойчивым в сети N, если />t’ÎT \ {t}, />MÎR(N): (M ³ F(p,t)) Ç (M ³ F(p,t’))Þ(M ³ (F(p,t)+F(p,t’))), т.е. если переход t может сработать, то никакой другойпереход не может сработав, лишить его этой возможности.
Сеть N устойчива, если все ее переходы устойчивы.
Вывод:
Все переходы сети потенциально живы(то есть существует разметка, достижимая от текущей разметки, при которойпереход t может сработать), следовательно всясеть N является живой.
Сеть устойчива, так как все еепереходы являются устойчивыми ( это значит, что если переход t может сработать, то никакой другойпереход не может сработав, лишить его этой возможности).
9. Заключение
Вданном РГЗ была построена модель АП записи на магнитный диск. Для болееподробного исследования к данному процессу были применены следующие операции:репозиция, редукция и параллельная композиция. С помощью репозиции мырассмотрели механизм возобновления процесса нажатия клавиши. С помощью редукциимы упростили процесс и вычленили его отдельную ветвь. Также была построена сетьПетри и изучены ее свойства.
Список использованной литературы
1. Конспект лекций по ТВП;
2. А.В. Гордеев, А.Ю. Молчанов,Системное программное обеспечение.