Міністерство освіти і науки України Національний університет «Львівська Політехніка» Кафедра САПР ЗВІТ Про виконання лабораторної роботи №2 з курсу: “Системний аналіз” на тему: АНАЛІЗ МЕРЕЖ ПЕТРІ МЕТА РОБОТИ Ознайомититися з основними властивостями мереж Петрі. ТЕОРЕТИЧНІ ВІДОМОСТІ Класифікація мереж Петрі Автоматні мережі Петрі (state machine) − мережі у яких перехід має не більше одного входу і не більше одного виходу. Такі мережі звичайно описують послідовні процеси із розгалуженням по умові. Якщо мережа має тільки одну мітку, то мережа є, по суті, графом автомата, який послідовно переходить з одного стану в інший. Марковані мережі (MG-мережі або market graph) − мережі, у яких кожна позиція має не більше одного входу і не більше одного виходу. За їх допомогою моделюють послідовно-паралельні процеси. MG-мережі називають також синхрографами. Мережі вільного вибору (FC-мережі або free choice) − мережі у яких кожна дуга, що виходить з позиції, є або єдиним виходом з неї, або єдиним входом в перехід. FC-мережі використовуються для опису процесів керування.. Прості мережі − (SN-мережі або Simple nets) − мережі, у яких кожен перехід може мати не більше за одну загальну позицію з іншими переходами. Ординарні мережі − (ON-мережі або Ordinary nets) − мережі, які не мають обмежень, окрім однієї −кратність дуг повинна бути не більше за одиницю. Між вузлами прокладається рівно один зв’язок. Неординарна мережа може бути перетворена в ординарну. Кольорові мережі - (CPN- мережі або Coloured Petri Nets) − мережі, у яких кожна мітка має свій певний колір і перехід, пов’язаний з деякою умовою, що визначає наявність пов’язаних з ним вхідних позицій міток певного кольору. Колір мітки прийнято позначати деякою буквою. Часові мережі Петрі − (Time Petri Nets) − мережі, у яких з кожним переходом зв’язують деяку тривалість (час). Для визначеності вважають, що вилучення фішок з вхідних позицій відбувається миттєво, а передача фішок здійснюється за встановлений час. У реальності це може відповідати роботі технічних пристроїв і підрозділів організації. Потокові мережі − мережі, які моделюють потокові системи, в яких здійснюється управління даними. Операції виконуються одразу при готовності даних. У потоковій мережі Петрі переходи інтерпретуються як оператори або обчислювальні функції, місця інтерпретуються як черги, а дані − як фішки Властивості мереж Петрі Обмеженість. Позиція називається обмеженою, якщо вона є k- обмеженою для деякого цілого значення k. Мережа Петрі обмежена, якщо всі її позиції обмежені. Обмеженість – кількість міток в будь-якій позиції не може перевищувати певного значення k. При проектуванні автоматизованих систем визначення k дозволяє обґрунтовано вибирати ємкості нагромаджувачів. Можливість необмеженого зростання кількості міток свідчить про небезпеку необмеженого зростання довжин черг. Безпечність Позиція р мережі Петрі PN =(P,Т,I,O) з початковим маркуванням М є безпечною, якщо вона є 1-обмеженою. Мережа Петрі безпечна, якщо безпечні всі позиції мережі. Активність Активність мережі Петрі визначається можливістю спрацювання будь-якого переходу при функціонуванні об'єкту моделювання. Відсутність активності означає або надлишковості апаратури у спроектованій системі, або свідчить про можливість виникнення зациклень, тупиків, блокувань. Тупик в мережі Петрі — це перехід (або множина переходів), які не можуть бути запущені. У зв’язку із поняттям тупика визначимо для мережі Петрі PN із початковим маркуванням М наступні рівні активності переходів: Рівень 0: Перехід t володіє активністю рівня 0 і називається мертвим, якщо він ніколи не може бути запущений. Рівень 1: Перехід t володіє активністю рівня 1 і називається потенційно живим, якщо існує таке М’R(PN,М), що t є дозволеним в М’. Рівень 2: Перехід t володіє активністю рівня 2 і називається живим, якщо для будь-якого М’R(PN,М) перехід t є потенційно живим для мережі Петрі PN з початковим маркуванням М’. Мережа Петрі називається живою, якщо всі її переходи є живими. Дедлоки Мережі Петрі виявилися зручним засобом для аналізу такої властивості паралельної системи, як наявність або відсутність дедлоків. Стан дедлока виникає, коли запит ресурсів у системі не може бути задоволений і система зупиняється (жоден з переходів не може спрацювати). Це може бути нормальною зупинкою мережі, а може бути і наслідком конкуренції за ресурси. Граф досяжності В основі дослідження перерахованих у п.2.2. властивостей мереж Петрі лежить аналіз досяжності. Один з методів аналізу досяжності будь-якого маркування з стану М0 — побудова графа досяжності. Початкова вершина графа відображає М0, а решта вершин відповідають маркуванням. Дуга з Мi в Мj означає подію Mi ((Mj і відповідає спрацюванню перехода t. У складних мережах граф може містити надзвичайно велику кількість вершин і дуг. Проте при побудові графа можна не відображати всі вершини, оскільки багато з них є дублями (дійсно, від маркування Mk завжди породжується один і той самий підграф не залежно від того з якого стану система прйишла в Мk). Тупики виявляються за відсутністю дозволених переходів з будь-якої вершини, тобто за присутністю листків — термінальних вершин. Необмежене зростання кількості маркерів в будь-якій позиції свідчить про порушення обмеженості. ЗАВДАННЯ ДО ЛАБОРАТОРНОЇ РОБОТИ Дослідити властивості наступних мереж Петрі: Варіант 3

Ця мережа Петрі не є кольоровою мережею і часовою мережею і маркованою мережею. Кожен перехід має не більше одного входу і одного виходу. Кожна дуга, що виходить з позиції є єдиним входом в перехід. Кожен перехід має не більше ніж одну загальну позицію з іншими. Кратність дуг не більша за одиницю. Мережа є обмеженою оскільки кількість міток в будь якій позиції не перевищує певного значення. Це безпечна мережа, бо вона 1-обмежена.


ВИСНОВОК На цій лабораторній роботі я повинен був ознайомитися із основними властивостями мереж Петрі. У ході виконання лабораторної роботи я ознайомився із теоретичними відомостями та навчився аналізувати мережі Петрі. Спочатку я спробував проаналізувати мережу самостійно, а потім проаналізував її в системі. Навів результати виконання роботи.