Коротко про мережі Петрі
Мережі Петрі – інструмент дослідження систем. Нині мережі Петрі застосовуються переважно у моделюванні. У багатьох областях досліджень явище вивчається безпосередньо, а побічно, через модель. Модель – це уявлення, зазвичай, у математичних термінах те, що вважається найбільш характерним у досліджуваному об'єкті чи системі. Маніпулюючи моделлю системи, можна отримати нові знання про неї, уникаючи небезпеки, дорожнечі або незручності аналізу самої реальної системи. Зазвичай моделі мають математичну основу.
Розвиток теорії мереж Петрі проводилося за двома напрямками. Формальна теорія мереж Петрі займається розробкою основних засобів, методів і понять, необхідні застосування мереж Петри. Прикладна теорія мереж Петрі пов'язана головним чином із застосуванням мереж Петрі до моделювання систем, їх аналізу та глибоким проникненням, що виходить в результаті цього в моделювані системи.
Моделювання в мережах Петрі складає подійному рівні. Визначаються, які дії відбуваються у системі, які стан передували цим діям та які стану прийме система після виконання дії. Виконання подієвої моделі у мережах Петрі визначає поведінка системи. Аналіз результатів виконання може сказати у тому, у яких станах перебувала чи перебувала система, які стану у принципі недосяжні. Однак такий аналіз не дає числових характеристик, що визначають стан системи. Розвиток теорії мереж Петрі призвело до появи, про, “кольорових” мереж Петрі. Поняття кольоровості в них тісно пов'язане з поняттями змінних, типів даних, умов та інших конструкцій, наближених до мов програмування. Незважаючи на деякі подібності між кольоровими мережами Петрі та програмами, вони ще незастосовувалися як мову програмування.
Незважаючи на описані вище переваги мереж Петрі, незручності застосування мереж Петрі як мову програмування укладені у процесі виконання у обчислювальної системі. У мережах Петрі немає суворо поняття процесу, який можна було б виконувати на зазначеному процесорі. Немає також однозначної послідовності виконання мережі Петрі, оскільки вихідна теорія представляє нам мову описи паралельних процесів.
Найкращими можливостями опису паралельних систем мають мережі Петрі. Вони не менш потужні, ніж PVM, MPI, SDL та інші, але щоб їх виконувати на процесорах необхідно зробити з опису паралельного розподілу.
Мережа першого роду – це кольорова мережа Петрі, описана мовою розпоряджень.
Мережа другого роду – це мережа, подана у вигляді ієрархічної композиції об'єктів.
Теорія мереж Петрі є добре відомим та популярним формалізмом, призначеним для роботи з паралельними та асинхронними системами. Заснована на початку 60-х років німецьким математиком К.А.Петрі, в даний час вона містить велику кількість моделей, методів та засобів аналізу, що мають велику кількість додатків практично у всіх галузях обчислювальної техніки і навіть поза нею.
Даний розділ містить систему понять, визначень та позначень, які безпосередньо будуть потрібні надалі.
Мережа Петрі з трьох елементів: безліч місць, безліч переходів та відношення інцидентності.
Визначення: Проста мережа Петрі
1. - безліч місць;
2. - безліч переходів таких, що .
3. - відношення інцидентності таке, що
Умови у пункті 3 кажуть, щодля кожного переходу існує єдиний елемент, що задає для нього вхідне мультимножина місць та вихідне мультимножина. Дамо визначення вхідного та вихідного мультимножини.
Визначення: Вхідне та вихідне мультимножини місць та переходів
1. Якщо для деякого переходу маємо, то будемо позначати;
Будемо говорити, що - вхідні, а - вихідні місця переходу. Таким чином, згідно з визначенням, справедливо . Далі будемо говорити, що місце інцидентне переходу або .
Розширимо функції і на мультимножини переходів. Нехай є безліч переходів таке, що . Тоді покладемо
Мережі Петрі мають зручну графічну форму уявлення як графа, у якому місця зображуються кружками, а переходи прямокутниками. Місця і переходи, причому місце з'єднується з переходом і з'єднується з для деякого натурального числа . Тут число називається кратністю дуги, яке графічно зображується поруч із дугою. Дуги, що мають одиничну кратність, позначатимуться без приписування одиниці.
Приклад. Приклад мережі
У графічній формі мережу представлено на Рис.1. Мережа має чотири місця та три переходи. Ставлення задає дуги мережі. Так, наприклад, елемент задає чотири дуги: з і з з кратностями 2, з і з з одиничними кратностями. Для переходу справедливо та . Для місця можна обчислити та .
Мал. 1: Приклад графа мережі Петрі
Саме собою поняття мережі має статичну природу. Для завдання динамічних показників використовується поняття маркування мережі, тобто. функції , зіставляє кожному місцю ціле число. Графічно маркування зображується у вигляді точок, званих мітками (tokens ), і що знаходяться вгуртках, які відповідають місцям мережі. Відсутність міток дещо свідчить про нульове маркування цього місця.
Визначення: Маркована мережа Петрі
2. - Початкове маркування.
Приклад. Приклад маркованої мережі.
Мал. 2: Приклад маркованої мережі Петрі
Мережі Петрі були розроблені та використовуються для моделювання паралельних та асинхронних систем. При моделюванні в мережах Петрі місця символізують стан системи, а перехід символізують якісь дії, що відбуваються в системі. Система, перебуваючи в якомусь стані, може породжувати певні дії, і, навпаки, виконання якоїсь дії переводить систему з одного стану до іншого.
Поточне стан системи визначає маркування мережі Петрі, тобто. розташування міток (токенів) у місцях мережі. Виконання дії у системі, в мережах Петрі визначається як спрацювання переходів. Спрацювання переходів породжує нове маркування, тобто. породжує нове розміщення міток (токенів) у мережі. Визначимо функціонування маркованих мереж, заснований на спрацюванні окремих переходів.
Визначення: Правило спрацьовування переходів
Нехай маркована мережа.
1. Перехід вважається збудженим при маркуванні, якщо;
2. Перехід, збуджений під час маркування, може спрацювати, призвівши до нового маркування, яке обчислюється за правилом: . Спрацювання переходу позначається як .
Іншими словами, перехід вважається збудженим при певному маркуванні, якщо у кожному йоговхідному місці є кількість міток не менше кратності відповідних дуг. Збуджений перехід може спрацювати, причому при спрацьовуванні з кожного його вхідного місця вилучається, а кожне вхідне додається кілька міток, що дорівнює кратності відповідних дуг. Якщо одночасно порушено кілька переходів, може спрацювати будь-який з них або будь-яка їх комбінація. Наприклад, нехай у мережі малюнку 2 спрацюють переходи і . Отримаємо мережу представлену малюнку 3.
Мал. 3: Нова мережа з маркуванням.
Композиційний підхід до побудови мереж Петрі передбачає можливість побудови складніших мереж із менш складних складових. Для цього вводяться точки доступу, які дозволяють об'єднувати прості мережі шляхом синхронізації подій та станів (переходів та місць).
Визначення: Визначення T-точки доступу.
Нехай задана мережа та певний алфавіт. Т-точкою доступу називається набір , де
1. - ім'я (ідентифікатор) t-точки доступу;
2. – деякий алфавіт;
3. - помітна функція, де . Запис позначає множину всіх кінцевих і непустих мультимножин, визначених на множині .
Визначення: Визначення S точки доступу
Нехай задана мережа. Тоді s-точкою доступу мережі N називається набір , де
1. - ім'я (ідентифікатор) s-точки доступу;
2. - множина така, що .
Введені поняття точок доступу надають можливість запровадити дві основні операції над мережами Петрі для побудови композиційних мереж:
1. Операція злиття переходів - дозволяє породжувати та описувати синхронізацію паралельних процесів (tmerge);
2. Операція злиття місць – дозволяє застосовувати до мереж операції послідовної композиції, вибору, ітерації та інші (s merge).
Мал. 4: Приклад операції злиття переходів
Мал. 5 : Приклад операції злиття місць
Наведені операції мають такий зміст:
При злитті місць визначається набір станів у мережі, які ідентифікуються, як стан мережі, визначений ім'ям s-точки доступу. Злиття різних мереж проводиться так, що якщо в одній мережі досягнуто описаний стан, то в іншій мережі цей стан також досягається;
При злитті переходів визначається алфавіт подій, видимих з t-точки доступу. Кожен перехід у мережі позначається або невидимою подією, або комбінацією подій з алфавіту точки доступу. Злиття по переходах проводиться так, що якщо при спрацьовуванні однієї мережі виникає деяка комбінація подій, то ця комбінація подій відбувається в другій мережі.
Розширення простих мереж у кольорові полягає у додаванні інформації до елементів мережі, ґрунтуючись на якій, за певних умов, можна перетворити кольорові мережі на прості ([8]).
1. Токени замість простого позначення вмісту місця перетворюються на об'єкт, який може містити один або більше параметрів, кожен з яких може приймати дискретний набір значень. Відповідно до цього токени розрізняються за типами параметрів (змінних). Щоб відрізняти токени різних типів, їх можна фарбувати в різні кольори (тому мережі називають кольоровими).
2. До місць додається інформація про типи токенів, які можуть знаходитися в цьому місці.
3. До дуг, що виходять із місць, додається інформація про типи токенів, які можуть брати участь у порушенні переходів, інцидентних цим дугам.
4. До переходів може бути додана інформація з предикатом порушення переходу, залежно від змінних, що містяться втокені.
5. До дуг, що виходять із переходів, додається інформація про типи токенів, що виходять із переходу та про перетворення змінних.
6. До початкового маркування мережі додається інформація про значення змінних, що містяться в токенах.
У графічному поданні інформацію, яку можна однозначно добудувати із супутньої інформації, можна пропускати. Наведемо приклад кольорової мережі Петрі (Рис. 6)
Мал. 6: Приклад кольорової мережі Петрі (черга)
На перший погляд здається, що уявлення кольорової мережі виглядає так, що кожна з дуг, що виходить із переходу, містить певну дію. Насправді ж, при перетворенні кольорової мережі на просту, всі дії переходять у структуру мережі. Це досягається розбиттям місць і переходів на кількість, що дорівнює декартову добутку безлічі всіх значень усіх типів даних, що відповідають цим місцям і переходам. При цьому всі змінні мережі виходять вже заданими і замість дуг кольорової мережі малюються дуги, що з'єднують місця і переходи, відповідно до своїх "кольорових" описів.
В описі кольорових мереж немає принципового обмеження на змінні, що використовуються. Проте перетворення кольорової мережі на просту можливе лише тоді, коли всі змінні мають дискретний спектр значень.
Точки доступу у кольоровій мережі.
S-точка доступу. Як видно з визначення s-точки доступу, вона задається безліччю маркувань, які вважаються еквівалентними в сенсі настання станів, визначених цими маркуваннями, в мережах, що синхронізуються по s-точці доступу. При заданні s-точки доступу в кольоровій мережі, маркування можуть містити місця, в які можуть надходити токени різних типів. Такі місця при перетворенні на просту мережу розбиваються на безліч місць,кількість яких дорівнює потужності безлічі значень токенів допустимих тут. Відповідно до змісту операції ми зобов'язані будемо в синхронізованій мережі роздробити ці місця, щоб задовольнити безлічі значень токенів у другій мережі. Виходить, що при синхронізації місць однакового типу (з однаковими допустимими типами токенів) значення параметрів однієї мережі ніяк не впливає на значення параметрів іншої, тобто значення операції в кольорових та простих мережах можна розуміти по-різному. Щоб цього уникнути, треба визначити s-точку доступу:
Нехай задані: кольорова мережа N та С – безліч типів токенів у цій мережі. Тоді s-точкою доступу мережі N називається набір , де
1. - ім'я (ідентифікатор) s-точки доступу;
2. – деякий алфавіт;
3. - множина така, що .
4. де, причому якщо. - помітна функція місць, що ставить у відповідність кожному типу токена у місці унікальне ім'я з алфавіту.
В операції злиття кольорових мереж по місцях необхідно прибрати розщеплення місць по токенах з певними іменами. Фактично це означає перевизначення операції злиття по одній s-точці доступу в простих мережах в операцію злиття серії точок доступу кольорових мереж, пронумерованих значеннями параметрів з іменами. Можна показати, що змінена таким чином операція не змінює своїх властивостей.
Мал. 7 : Приклад злиття кольорових мереж Петрі по S-точці доступу
T-точка доступу. При синхронізації по t-точці доступу використовується інформація про позначку переходів, що беруть участь у синхронізації. При перетворенні кольорових мереж у прості переходи розщеплюються на кількість, що дорівнює потужності безлічі значень, що приймаються всіма токенами, що надходять у перехід. У зв'язку з цим виникає можливість параметризації позначки переходувиразами, що містять змінні вступники в перехід.
Мал. 8 : Приклад злиття кольорових мереж по T-точці доступу
На наведеному нижче прикладі видно, як параметризований перехід, перетворюється на прості мережі.
Мал. 9: T -злиття простих мереж з малюнка 8.
Мал. 10: Подання композиційних мереж Петрі лише на рівні взаємодії мереж.