Поняття кінцевого автомата є зручною математичної схемою для опису функціонування тих об'єктів і систем, для яких характерна наявність дискретних станів і дискретний характер роботи в часі. Однак для моделювання ряду об'єктів, наприклад засобів обчислювальної техніки і обчислювальних мереж, використання абстрактно-автоматної математичної схеми зустрічає труднощі, незважаючи на те, що дані об'єкти можуть бути представлені як дискретні перехідні системи. Це пояснюється тим, що кінцевий автомат є послідовною алгоритмічної схемою, а названі об'єкти можуть виконувати свої функції паралельно і асинхронно, незалежно один від одного, за винятком деяких заданих точок, які називаються точками взаємодії паралельних процесів. Опис функціонування з використанням кінцевого автомата в таких випадках теоретично можливо, однак вимагає розгляду великої кількості станів і збільшення складності моделі. Даного недоліку позбавлені мережі Петрі.
Мережа Петрі це орієнтований граф, що містить позиції (вершини), що визначають умови, наявні в системі, і переходи, що відображають пов'язані з цими умовами дії. У позиціях проставляються мітки, якщо відповідне умова виконана. Пересування міток по мережі визначає послідовність зміни станів об'єкта, що моделюється. Позиції зображуються кружками, переходи - планками. Позиції з'єднують дугою з переходом, якщо виконання заданої умови є необхідним для запуску пов'язаного з даними переходом дії. Перехід з'єднують дугою з позицією, якщо пов'язане з ним дію породжує виконання умови, представленого цією позицією. З'єднання дугою позиції з позицією або переходу з переходом не допускається.
Мережі Петрі функціонують в безперервному часу. Динаміка функціонування визначається правилами спрацьовування переходів. Зміна стану мережі пов'язано з механізмом зміни маркувань позицій. У разі простою тимчасової мережі Петрі:
- спрацьовує тільки активний перехід, т. е. такий, у всіх вхідних позиціях якого є мітки;
- спрацьовування переходу настає через заданий кінцевий проміжок часу після його активізації, причому якщо виникає конфлікт - одночасна активізація кількох переходів, що мають спільні вхідні вершини, то спрацьовує равновероятно тільки один з конфліктних переходів;
- в результаті спрацьовування переходу число міток в кожної вхідної позиції зменшуються на одиницю, а число міток у всіх вихідних позиціях збільшуються на одиницю.
ПРИКЛАД зміни маркувань простий мережі Петрі при вирішенні конфлікту.
Крім графічного використовують табличне опису мережі Петрі. Виділяють два типи таблиць: перша для кожної вершини мережі задає список її послідовників, друга визначає ваги дуг мережі. Число колонок таблиці визначає ступінь паралелізму моделі.
Елементарний цикл обслуговування моделюється простий тимчасової мережею Петрі, представленої на рис. 16.
З переходами на рис. 16 пов'язані часи виконання наступних дій: t1 -надходження заявки на обслуговування до вхідної черги; t2 - початок обслуговування; t3 - кінець обслуговування; t4-вихід заявки з циклу обслуговування. Позиції цієї мережі Петрі відповідають умовам: Р1 - наявність заявки, яка чекає на обслуговування, у вхідній черзі; Р2 - наявність заявки на обслуговуванні в процесорі; Р3 - процесор вільний; Р4 - наявність обслужених заявки в вихідний черги. Маркування мережі Петрі, показаної на рис. 16, відповідає початковому стану системи обслуговування: заявок, які очікують обслуговування, у вхідній черзі немає, і процесор вільний (вершина P3 містить мітку).
Інша маркування мережі Петрі, що моделює елементарний цикл обслуговування, показана на рис. 17.
Маркування, показана на рис. 17, відповідає наступного стану: заявка очікує обслуговування і процесор вільний: вершини Р1 і P3 містять мітки, і, отже, перехід t2 активізований. Моделювання подальших подій в покроковому режимі показано на рис. 18.
Після спрацьовування переходу t2 мітки з його вхідних вершин Р1 і P3 будуть вилучені, а у вихідний вершині Р2 мітка з'явитися, що відповідає наявності заявки на обслуговування в процесорі. Мітка в вершині Р2 активізує перехід t3. який спрацює по закінченню часу обслуговування. В результаті спрацьовування переходу t3 мітка вилучається з вершини Р2. а в вершинах Р4 і P3 мітки з'являються. Спрацьовування переходу t4. відповідне видалення обслужених заявки з циклу, вилучить мітку з вершини Р4. і система повернеться до початкової маркування (див. рис. 16).
У загальному випадку в позиції може бути більше однієї позначки. Тоді, для спрацьовування переходу виду n / m потрібна наявність у вхідних позиціях сумарної кількості міток не менше n. При спрацьовуванні переходу з усіх вхідних позицій за кількістю вихідних дуг видаляються в сумі n міток, а у всіх вихідних позиціях по числу вихідних дуг з'являються m міток (див. Рис. 19).
Для зручності в графічному поданні мереж Петрі та в програмному забезпеченні моделювання, як правило, при завданні переходів типу n / m замість множинних дуг використовують одну, задаючи її вага. Також з міркувань зручності кількість міток в вершині більше 2-х можна вказувати числом замість безлічі міток. У такому поданні приклад, наведений на рис. 19, буде мати вигляд, показаний на рис. 20.
Переходи типу n / m використовуються для моделювання процесів, супроводжуваних зміною типу модельованого ресурсу. Наприклад, для моделювання процесів складання в технологічній системі, процесів пакетування заявок в обчислювальної мережі (в цьому випадку n> m) або процесу поділу матеріальних потоків, процесу створення копій заявок (в цьому випадку n Приклади мереж Петрі для моделювання процесу пакетування заявок і синхронного моделювання елемента І-НЕ. Для моделювання засобів обчислювальної техніки і процесів обробки інформації використовуються різновиди мереж Петрі, що розрізняються способами вирішення конфліктів. В стохастичних мережах Петрі додатково вводяться випадкові затримки або ймовірності спрацьовування активних переходів. У прикладі на рис. 21-а спрацює або перехід t1 (c ймовірністю р1), або t2 (c ймовірністю 1-р1). У пріоритетних мережах конфліктні ситуації вирішуються введенням різних пріоритетів для гілок. Конфлікт, показаний в прикладі на рис. 21-б, завжди буде вирішуватися на користь переходу t1. так як він має пріоритет, а перехід t2 зможе спрацювати тільки в тому випадку, якщо, при наявності міток в вершинах Р2 і Р3. мітки в вершині Р1 не опиниться. Особливою різновидом мереж Петрі є інгібіторні мережі, які на додаток до звичайних дуг (гілок) графа мережі містять забороняють, так звані інгібіторні гілки. Така гілка забороняє активацію переходу при наявності достатньої кількості міток у вхідних вершинах звичайних дуг до тих пір, поки в її вхідний вершині є мітки. У фрагменті мережі Петрі, наведеному на рис.22-а, гілка а забороняє запуск переходу t1 при наявності мітки в позиції P1. Приклад реалізації найпростішого циклу обслуговування з використанням інгібіторної мережі Петрі представлений на рис.22-б. Тут перехід t2 при наявності мітки в позиції Р2 буде «замкнений» не дивлячись на наявність мітки в вершині Р1 до тих пір, поки мітка не покине Р2 через перехід t3. що еквівалентно завершенню чергового обслуговування. Розглянемо приклади моделювання мережами Петрі різних процесів і систем. Мережа Петрі для моделювання магістрального каналу передачі даних. Нехай до загального каналу зв'язку підключені N абонентів і можливий зв'язок будь-яких абонентів один з одним. Абонент-відправник здійснює спробу зв'язку в випадковий момент часу Т1. Якщо канал зайнятий передачею інформації від іншого абонента, це виявляється за наявністю сигналів несучої частоти в каналі зв'язку. Абонент затримує передачу на час t1. є реалізацією рівномірно розподіленим в заданому діапазоні випадкової величини t. Якщо в момент часу (Т1 + t1) канал зв'язку знову зайнятий, то передача затримується за тим же правилом. Якщо два абонента або більше намагаються почати передачу одночасно, можливі конфлікти. Одночасність описується умовою DТ У модельній реалізації (див. Рис. 23) джерело (відкритий перехід t2) імітує потік заявок на передачу від всіх абонентів. Якщо канал вільний і конфлікту немає, заявка проходить через t3. t6. t7. t10. t11 і виходить із системи обслужених, причому в t6 відбувається затримка на час e. а в t10 - на час (Тп -e), де Тп - час передачі пакета. Якщо канал зайнятий (заявка затримана в t10), то спроба іншого абонента почати передачу призводить до проходження заявки за маршрутом t3. t6. t9. і далі в один з переходів t12. tn. Спрацьовування переходу t9. а не t7. відбувається тому, що попередня заявка, що пройшла через t7 і ще не вийшла з t10. вилучила мітку з позиції р9. Тим самим перехід t7 виявився забороненим, а t9 дозволеним. Переходи t12. tn моделюють затримку пакетів на час ti. Через час ti заявка переходить до р3. т. е. робиться нова спроба передачі повідомлення. Конфлікти виникають, якщо нова заявка приходить в позицію р3. коли попередня ще не покинула перехід t6. Тому мітка не може пройти перехід t3. але може пройти через перехід t4 в позицію Р6. Тепер вийшла з t6 заявка зможе пройти через t8 на переходи t12. tn. де обидві заявки будуть затримані на випадкові відрізки часу перед повторними спробами передачі. Щоб мітка з р8 перейшла в t8. а не в t9. гілки, що веде в t8. присвоюється більш високий пріоритет. Перехід t5 спрацьовує в разі, якщо в конфлікт увійшло більше двох заявок [3, 20-23]. Приклади мереж Петрі різних систем і процесів та їх реалізації в програмі IngProject - см. Лабораторну роботу №7 Мережа Петрі для моделювання процесів виникнення відмов і усунення несправностей в технологічній системі з запасним блоком і додатковим резервом. Нехай в технологічній системі експлуатуються три робочих блоку. З певною періодичністю в будь-якому з робочих блоків може наступити відмову. Для заміни відмовив блоку спочатку є один запасний. При настанні відмови несправний блок замінюється запасним, після чого несправний блок піддають відновленню (ремонту) і він стає запасним. В системі крім запасного блоку є ще один, резервний. Його використання дозволено тільки в разі відмови всіх трьох основних робочих блоків. Якщо резервний блок використаний - він повинен бути відновлений в першу чергу. Всі тимчасові характеристики системи (час відмови, час заміни, час відновлення) є випадковими величинами. При функціонуванні даної системи можуть мати місце такі ситуації: - всі три робочих блоку справні, запасний і резервний блоки готові до використання; - один з робочих блоків відмовив і запасний готовий до використання (в цьому випадку буде проведена заміна і відмовив блок буде відправлений на відновлення для подальшої передачі в запас); - якщо запасний блок не готовий до використання, т. е. знаходиться на відновленні, можливі ситуації послідовного наступу відмов одного і другого робочих блоків без заміни; - якщо запасний блок не готовий до використання, т. е. знаходиться на відновленні, а відмовляють послідовно всі три робочих блоку, то для заміни буде використаний резервний блок; - якщо резервний блок вже використаний, то після завершення відновлення чергового відмовив блоку він буде переданий не в запас, а в резерв, так як відновлення резерву виконується в першу чергу; - якщо резервний блок вже відновлено, то черговий відмовив блок буде відправлений на відновлення і, далі, в запас. Задану систему моделює інгібіторна пріоритетна мережа Петрі, представлена на рис. 24. У таблиці 10 представлено опис всіх позицій (вершин) мережі з точки зору умов, які з ними пов'язані, т. Е. Виконуються при наявності в вершині мітки-маркера. Наявність в системі справного, готового до використання для заміни резервного блоку. Початкова маркування мережі, представлена на рис. 24, відповідає наявності в системі трьох справних робочих блоків; справного, готового до використання для заміни запасного блоку і справного, готового до використання для заміни резервного блоку. Опис всіх переходів з точки зору пов'язаних з ними подій представлено в таблиці 11. ПРИКЛАД мережі Петрі для моделювання процесів виникнення відмов і усунення несправностей в технологічній системі з додатковим резервом (другий варіант). Виконання заміни несправного блоку на запасний або резервний (час випадково). Відновлення несправного блоку (час випадково). Два ідентичних переходу реалізовані для моделювання відновлення запасного і резервного блоків. Так як при необхідності відновлення резервного блоку має здійснюватися в першу чергу, відповідний перехід має більший пріоритет (позначений на рис. 24 «пр.») І в разі конфлікту спрацює саме він. Відправлення на відновлення одного з відмовили блоків без заміни. Даний перехід необхідний, так як в разі першочергового відновлення резерву мітка в вершині Р3 відсутня і перехід t2 спрацювати не може. У нормальному режимі роботи, коли в системі є запасний блок (мітка в вершині Р3) для вирішення конфлікту переходу t2 присвоєно більший пріоритет (позначений на рис. 24 «пр.»).Схожі статті