мережі петрі

Мережі Петрі - апарат для моделювання динамічних дискретних систем (переважно асинхронних паралельних процесів). Мережа Петрі визначається як четвірка. де і - кінцеві безлічі позицій і переходів, і - множини вхідних і вихідних функцій. Іншими словами, мережа Петрі є двочастковий орієнтований граф, в якому позиціях відповідають вершини, зображувані кружками, а переходах - вершини, зображувані потовщеними рисками; функціям відповідають дуги, спрямовані від позицій до переходів, а функцій - від переходів до позицій.

Як і в системах масового обслуговування, в мережах Петрі вводяться об'єкти двох типів: динамічні - зображуються мітками (маркерами) всередині позицій і статичні - їм відповідають вершини мережі Петрі.

Розподіл маркерів по позиціях називають маркуванням. Маркери можуть переміщатися в мережі. Кожна зміна маркування називають подією, причому кожна подія пов'язано з певним переходом. Вважається, що події відбуваються миттєво і різночасно при виконанні деяких умов.

Кожному умові в мережі Петрі відповідає певна позиція. Здійсненню події відповідає спрацьовування (збудження або запуск) переходу, при якому маркери з вхідних позицій цього переходу переміщаються в вихідні позиції. Послідовність подій утворює моделюється.

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

На рис. 1 показаний приклад розподілу маркерів по позиціях перед спрацьовуванням, це маркування записують у вигляді (2,2,3,1). Після спрацьовування переходу маркування стає іншою: (1,0,1,4).

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

Мал. 1. Фрагмент мережі Петрі

Якщо затримки є випадковими величинами, то мережу називають стохастичною мережею Петрі. В стохастичних мережах можливе введення ймовірностей спрацювання порушених переходів. Так, на рис. 2 представлений фрагмент мережі Петрі, який ілюструє конфліктну ситуацію - маркер в позиції може запустити або перехід. або перехід. У стохастичною мережі передбачається імовірнісний вибір спрацьовує переходу в таких ситуаціях.

Мал. 2. Конфліктна ситуація

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

У багатьох задачах динамічні об'єкти можуть бути декількох типів, і для кожного типу потрібно вводити свої алгоритми поведінки в мережі. У цьому випадку кожен маркер повинен мати хоча б один параметр, що позначає тип маркера. Такий параметр зазвичай називають кольором; колір можна використовувати як аргумент в функціональних мережах. Мережа при цьому називають кольоровий мережею Петрі.

Серед інших різновидів мереж Петрі слід згадати інгібіторні мережі Петрі. характеризуються тим, що в них можливі забороняють (інгібіторні) дуги. Наявність маркера у вхідній позиції, пов'язаної з переходом ингибиторной дугою, означає заборону спрацьовування переходу.

Введені поняття пояснимо на наступних прикладах.

Потрібно описати за допомогою мережі Петрі роботу групи користувачів на єдиній робочій станції WS при заданих характеристиках потоку запитів на користування WS і характеристиках надходять завдань. Мережа Петрі представлена ​​на рис. 3.

Тут переходи пов'язані з наступними подіями: - надходження запиту на використання WS, - заняття станції, - звільнення станції, - вихід обслужених заявки; позиція використовується для відображення стану WS: якщо в є мітка, то WS вільна і прийшла заявка викликає спрацьовування переходу; поки ця заявка не буде обслужена, мітки в не буде, отже, що прийшли в позицію запити змушені очікувати спрацьовування переходу.

Мал. 3. Мережа Петрі для прикладу 1

На рис. 4 представлена ​​мережа Петрі, відповідна організації паралельних обчислень на основі асинхронного message passing interface (MPI) [1].

Мал. 4. Мережа Петрі для прикладу 2

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

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

Очевидно, що при непорожній позиції перехід спрацьовує, але із затримкою, рівною обчисленому випадковому значенню моделируемого відрізка часу між відмовами. Після виходу маркера з він потрапляє через ст. якщо є мітка в позиції. це означає, що обслуговує систему бригада фахівців вільна і може приступити до пошуку виниклої несправності. У переході мітка затримується на час, що дорівнює випадковому значенню тривалості пошуку несправності. Далі маркер виявляється в і, якщо є запасний блок (маркер в), то запускається перехід. з якого маркери вийдуть в. і в через відрізок часу, необхідний для заміни блоку. Після цього в імітується відновлення несправного блоку.

Мал. 5. Мережа Петрі для прикладу 3

Вже згадана модель описує функціонування системи в умовах, коли відмови можуть виникати і в робочому, і в несправному станах системи. Тому не виключені ситуації, при яких більш ніж один маркер виявиться в позиції Список літератури