Міністерство освіти і науки України Національний університет «Львівська політехніка» Львів, 2006р. ЗВІТ До лабораторної роботи №1 На тему «Властивості мереж Петрі.» З курсу СА
 1. МЕТА РОБОТИ Мета роботи – ознайомититися з основними властивостями мереж Петрі.. 2. КОРОТКІ ТЕОРЕТИЧНI ВIДОМОСТI Модель — це представлення, як правило, у математичних термінах найхарактерніших рис об'єкту або системи, що вивчається. Для побудови складних систем обробки інформації та моделювання асинхронних інформаційних потоків потрібна математична модель, зручна в описі керування роботою таких систем. Історично першою для такого моделювання використовувалася теорія автоматів. Автомати застосовують для моделювання послідовних алгоритмічних систем — коли система (автомат) послідовно переходить зі стану в стан відповідно до заданої функції переходу і здійснює наступний крок алгоритму. Але існують і неалгоритмічні паралельні системи з недетермінованою поведінкою, в якій компоненти функціонують незалежно і взаємодіють час від часу. Прикладами таких систем є багатопроцесорні обчислювальні машини, паралельні програми, що моделюють паралельні дискретні системи, мультипрограмні операційні системи. Такі системи не описуються адекватно в термінах класичної теорії автоматів. Наприклад, неможливо описати ці системи за допомогою таких термінів, як стан автомату, глобальна функція переходу. Мережі Петрі (МП) це інструмент для математичного моделювання і дослідження складних систем. Мета представлення системи у вигляді мережі Петрі і подальшого аналізу цієї мережі полягає в отриманні важливої інформації про структуру і динамічну поведінку модельованої системи. Ця інформація може використовуватися для оцінки модельованої системи і вироблення пропозицій по її удосконаленню. Вперше мережі Петрі запропонував німецький математик Карл Адам Петрі [1]. 2.1. Природа систем, які моделюються мережами Петрі. Мережі Петрі призначені для моделювання систем, які складаються з безлічі компонент, які взаєодіють між собою. При цьому компонента сама може бути системою. Діям різних компонент системи властивий паралелізм. Прикладами таких систем можуть бути обчислювальні системи, у тому числі і паралельні, комп'ютерні мережі, програмні системи, що забезпечують їх функціонування, а також економічні системи, системи управління дорожнім рухом, хімічні системи тощо. Мережі Петрі притаманні такі риси: МП використовується для опису модельованої системи, і це може бути застосовано для специфікацій (для побудови систем) або опису системи. Поведінку МП можна проаналізувати як моделюванням (що еквівалентно виконанню програми та її налагодженню), так і формальнішими методами аналізу (що відповідає програмній перевірці). Процес створення опису та виконання аналізу допомагає краще зрозуміти модельовану систему самому моделювальнику. 2.2. Підходи до проектування систем за допомогою МП. Мережі Петрі використовуються, як допоміжний інструмент аналізу в одному з підходів до проектування і аналізу систем. Тут для побудови системи використовуються загальноприйняті методи проектування. Потім побудована система моделюється за допомогою мереж Петрі, і модель аналізується. Якщо в ході аналізу у проекті знайдені недоліки, то з метою їх усунення проект модифікується. Модифікований проект потім знову моделюється і аналізується. Даний цикл повторюється доти, доки аналіз, що проводиться, не приведе до успіху. Інший підхід передбачає побудову проекту одразу у вигляді мереж Петрі. Методи аналізу застосовуються мережі для створення проекту, що не мережі помилок. Потім мережі Петрі перетвориться в реальну робочу систему. У першому випадку необхідна розробка методів моделювання систем мережами Петрі, а у другому випадку повинні бути розроблені методи реалізації мереж Петрі системами. ОСНОВНІ ВИЗНАЧЕННЯ 2.3. Теоретико-множинне визначення мереж Петрі. Нехай мультимножина це множина, яка допускаєе входження декількох екземплярів одного і того самого елемента. Визначення 2.1. Мережа Петрі PN є четвіркою PN=(P,Т,I,O), де P={p1, p2,...,pn} — скінчена множина позицій, n0; T={t1, t2,...,tm} — скінчена множина переходів, m0; I: T  P* — вхідна функція, яка співставляє переходу мультимножину його вхідних позицій (графічно представляється вхідними дугами переходу); О: T  P* — вихідна функція, яка співставляє переходу мультимножину його вихідних позицій (графічно представляється вихідними дугами переходу). Позиція pP називається входом для переходу tT, якщо pI(t). Позиція pP називається виходом для переходу tT, якщо pO(t). Структура мережі Петри визначається її позиціями, переходами, вхідною і вихідною функціями. Приклад 2.1. Мережа Петрі. PN =(P,T,I,O), P={p1, p2, p3, p4, p5} T={t1, t2, t3, t4, t5} I(t1)={ p1}, O(t1)={ p2, p3}, I(t2)={ p2}, O(t2)={p4}, I(t3)={ p3}, O(t3)={p5}, I(t4)={ p4}, O(t4)={p2}, I(t5)={ p4, p5}, O(t5)={p1}. Використовування мультимножини вхідних і вихідних позицій переходу, а не множин, дозволяє позиції бути кратним входом і кратним виходом переходу відповідно. При цьому кратність визначається кількістю екземплярів позиції у відповідній мультимножині. 2.4. Графи мереж Петрі. Найнаочнішим представленням мережі Петрі є її графічне представлення. Графічне представлення МП - дводольний орієнтований граф. Нагадаємо, що дводольний граф - це такий граф, безліч вершин якого розбивається на дві підмножини і не існує дуги, що сполучає дві вершини з однієї підмножини. Граф мережі Петрі володіє двома типами вузлів: круг , який представляє місце мережі Петрі; і планка , яка представляє перехід мережі Петрі. Орієнтовані дуги цього графа (стрілки) сполучають перехід з його вхідними і вихідними позиціями. При цьому дуги направлені від вхідних позицій до переходу і від переходу до вихідних позицій. Кратним вхідним і вихідним позиціям переходу відповідають кратні вхідні і вихідні дуги. Приклад  2.2. Граф мережі Петрі, яка визначена у прикладі 2.1.
2.5. Маркування мереж Петрі. Маркування — це розміщення у позиціях мережі Петрі фішок, які зображені на графі мережі Петрі крапками. Фішки використовуються для визначення виконання мережі Петрі. Кількість фішок у позиції при виконанні мережі Петрі може змінюватися від 0 до безмежності. Визначення 2.2. Маркування М мережі Петрі N=(P,T,I,О) є функцією, яка відображає множину позицій P у множину невід’ємних цілих чисел Nat (де число з Nat позначає кількість фішок, які розміщуються у відповідну позицію). Маркування М, може бути також визначене як n-вектор М=<Мp1,Мp2…,М(pn)> где n=P – кількість позицій у мережі Петрі і для кожного 1in справедливоМ(pi)Nat. – кількість фішок у позиції pi. Визначення 2.3. Маркована мережа Петрі N=(P,Т,I,О,М) визначається сукупністю структури мережі Петрі (P,T,I,О) і маркування М. Приклад 2.3. Графічне представления маркованої мережі Петрі.
MPN =(P,T,I,O), P={p1, p2, p3, p4, p5} T={t1, t2, t3, t4, t5} I(t1)={ p1}, O(t1)={ p2, p3}, I(t2)={ p2}, O(t2)={p4}, I(t3)={ p3}, O(t3)={p5}, I(t4)={ p4}, O(t4)={p2}, I(t5)={ p4, p5}, O(t5)={p1}. M1 = (1, 0, 0, 0, 0) Множина всіх маркувань мереж Петрі бзмежне. Якщо фішок, які розміщуються у позицію надто багато, то зручніше не рисувати фішки у крузі цієї позиції, а вказувати їхню кількість. 2.6. Правила виконання мереж Петрі. Мережа Петрі виконується засобами запусків переходів. Запуск переходу керується фішками у його вхідних позиціях і супроводжується видаленням фішок з цих позицій і додаванням нових фішок у його вихідні позиції. Перехід може запускатися лише у тому випадку, коли він активізований. Перехід називається активізованим, якщо кожна з його вхідних позицій містить кількість фішок, яка не менша, ніж кількість дуг, які ведуть з цієї позиції у перехід (або кратності вхідної дуги). Нехай функція А: PTNat для довільних позицій pP і переходу tТ задає значення А(p,t), яке співпадає с кратністю дуги, яка веде з p у t, якщо така дуга існує, і з нулем, у протилежному випадку. Нехай функція А: T P Nat для довільних позицій pP і переходу tТ задає значення А(t,p), яке співпадає с кратністю дуги, яка веде з t у p, якщо така дуга існує, і з нулем, у протилежному випадку. Визначення 2.4. Перехід tT у маркованій мережі Петрі MPN=(P,T,1,О,M) активізований, якщо для всіх pI(t) справедливо МpА (p,t). Запуск активізованого переходу tT із своєї вхідної позиції pI(t) видаляє А(p,t) фішок, а у свою вихідну позицію p’O(t) додає А(t,p’) фішок. Приклад 2.5. Запуск активізованого переходу у мережі Петрі. Мережа Петрі до запуску переходу t1.
Мережа Петрі після запуску переходу t1.
Визначення 2.5. Перехід t у маркованій мережі Петрі з маркуванням М може бути запущений кожного разу, коли він активізований і у результаті цього запуску утворюється нове маркування М', яка визначається наступним співвідношенням: М'(p)= М(p) – А(p,t) + А(t,p). для всех pP. Запуски можуть здійснюватися доти, поки існує хоча б один активізований перехід. Коли не залишиться жодного активізованого переходу, виконання припиняється. Якщо запуск довільного переходу t перетворює маркування мережі Петрі в нове маркування М', то будемо говорити, що М' досяжна из М шляхом запуску перехода t і позначати цей факт, як М t М '. Це поняття очевидним чином узагальнюється для випадку послідовності запусків активізованих переходів. Через R(MPN,М) позначимо множину всіх досяжних маркувань із початкового маркування М у мережі Петрі MPN. Приклад 2.6. Преретворення маркування мережі Петрі у прикладі 2.5. Перехід t1 перетворює маркуванняМ=<6,2> у маркування М’=<3,4>. 3. АНАЛІЗ МЕРЕЖ ПЕТРІ Моделювання систем мережами Петрі, перш за все, зумовлене необхіднітю проведення глибокого дослідження їхньої поведінки. Для проведення такого дослідження необходні методи анализу властивостей самих мереж Петрі. Цей підхід передбачає зведення дослідження властивостей реальної системи до аналізу визначених властивостей моделюючої мережі Петрі. 3.1. Властивості мереж Петрі. Обмеженість. Визначення 3.1. Позиція pP мережі Петрі PN=(P,Т,I,O) з початковим маркуванням М є k-обмеженою, якщо М’(p)k для будь-якого досяжного маркування М’R(PN,М). Позиція називається обмеженою, якщо вона є k-обмеженою для певного цілого значення k. Мережа Петрі обмежена, якщо всі її позиції обмежені. Безпека. Визначення  3.2. Позиція pP мережі Петрі PN =(P,Т,I,O) з початковим маркуванням М є безпечною, якщо вона є 1-обмеженою. Мережа Петрі безпечна, якщо безопечні всі позиції мережі. Збереження. Визначення  3.3. Мережа Петрі PN =(P,Т,I,O) з початковим маркуванням М є зберігаючою, якщо для будь-якого досяжного маркування М’R(PN,М) справедливе наступне. EMBED Equation.3
М’(p) = EMBED Equation.3
М(p). Активність. Тупик в мережі Петрі — це перехід (або множина переходів), які не можуть бути запущені. У зв’язку із поняттям тупика визначимо для мережі Петрі PN із початковим маркуванням М наступні рівні активності переходів: Рівень 0: Перехід t володіє активністю рівня 0 і називається мертвим, якщо він ніколи не може бути запущений. Рівень 1: Перехід t володіє активністю рівня 1 і називається потенційно живим, якщо існує таке М’R(PN,М), що t є дозволеним в М’. Рівень 2: Перехід t володіє активністю рівня 2 і називається живим, якщо для бідь-якого М’R(PN,М) перехід t є потенційно живим для мережі Петрі PN з початковим маркуванням М’. Мережа Петрі називається живою, якщо всі її переходи є живими. Досяжність і покриваємість. Задача долсяжності: Для даної мережі Петрі з початковим маркуванням М і маркуванням М’ визначити: М’R(PN,М)? Задача покриваємості. Для даної мережі Петрі з початковим маркуванням М і маркуванням М’ визначити, чи існує таке досяжне маркування М”R(PN,М), що М"М’. (Відношення М"М’ є істинним, якщо кожний елемент маркування М" не менше відповідного елемента маркування М’.) Еквівалентність і включення. Мережі Петрі притаманна деяка поведінка, яка визначається множиною її можливих послідовностей запусків переходів або її множиною досяжних маркувань. Поняття еквівалентності мереж Петрі може бути визначене через рівеність множин досяжних маркувань. Визначення  3.5. Мережа Петрі PN=(P,Т,I,O) із початковим маркуванням М і мережа Петрі PN’=(P’,Т’,I’,O’) із початковим маркуванням М’ є еквівалентними якщо справедливо R(PN,М)=R(PN’,М’). Поняття еквівалентності мереж Петрі може бути визначено також через рівність множин можливих послідовностей запусків переходів. Слабшим, у порівнянні еквівалентністю, є властивість включення, визначення якого співпадає з визначенням еквівалентності, з точністю до заміни = на . ХІД РОБОТИ
ВИСНОВОК На даній лабораторній роботі ми ознайомилися з основними властивостями мереж Петрі.. І побудували свою мережу за допомогою проектувальних програм.