Мережі Петрі - Створення програми для керування гнучкою виробничою системою
Призначення мереж Петрі
Мережі Петрі являють собою графічний і математичний засіб моделювання, що застосовується до систем різних типів. Системи можуть містити велику кількість взаємодіючих елементів, кожен елемент, у свою чергу, може бути системою з безліччю компонентів, які взаємодіють один з одним складним чином. Прикладами таких систем можуть бути економічні системи, юридичні, хімічні, біологічні системи, і навіть системи управління.
Вони є перспективним інструментом опису та дослідження мультипрограмних, асинхронних, розподілених, паралельних, недетермінованих та/або стохастичних систем обробки інформації. Як графічний засіб мережі Петрі можуть використовуватися для наочного уявлення моделі, що моделюється, подібно блок-схем, структурним схемам і мережевим графікам. Поняття фішок, що вводиться в цих мережах, дозволяє моделювати динаміку функціонування систем і паралельні процеси. В якості математичного засобу аналітичне уявлення мережі Петрі дозволяє складати рівняння стану, рівняння алгебри та інші математичні співвідношення, що описують динаміку систем. Нині мережі Петрі застосовуються переважно у моделюванні. У багатьох областях досліджень явище вивчається безпосередньо, а побічно, через модель. Модель - це уявлення, зазвичай, у математичних термінах те, що вважається найбільш характерним у досліджуваному об'єкті чи системі. Маніпулюючи моделлю системи, можна отримати нові знання про неї, уникаючи небезпеки, дорожнечі або незручності аналізу самої реальної системи. Зазвичай моделі мають математичну основу.
Розвиток теорії мереж Петрі проводилося за двома напрямками.Формальна теорія мереж Петрі займається розробкою основних засобів, методів і понять, необхідні застосування мереж Петри. Прикладна теорія мереж Петрі пов'язана головним чином із застосуванням мереж Петрі до моделювання систем, їх аналізу та глибоким проникненням, що виходить в результаті цього в моделювані системи.
Моделювання в мережах Петрі складає подійному рівні. Визначаються, які дії відбуваються у системі, які стан передували цим діям та які стану прийме система після виконання дії. Виконання подієвої моделі у мережах Петрі визначає поведінка системи. Аналіз результатів виконання може сказати у тому, у яких станах перебувала чи перебувала система, які стану у принципі недосяжні. Однак такий аналіз не дає числових характеристик, що визначають стан системи. Незважаючи на описані вище переваги мереж Петрі, незручності застосування мереж Петрі як мову програмування укладені у процесі виконання у обчислювальної системі. У мережах Петрі немає суворо поняття процесу, який можна було б виконувати на зазначеному процесорі. Немає також однозначної послідовності виконання мережі Петрі, оскільки вихідна теорія представляє нам мову описи паралельних процесів. Мережі Петрі є одним із найпоширеніших сучасних формалізмів для моделювання та аналізу паралельних розподілених систем. В даний час ведеться велика кількість теоретичних та практичних досліджень для розробки розподілених алгоритмів, заснованих на мережах Петрі. Разом з тим, фахівцями відчувається необхідність розвитку формалізму з метою більш адекватного та зручного представлення систем зі складною структурою. Ведуться дослідження з розширення мереж Петрі за рахунокдодавання конструкцій, що відображають модульність та ієрархічність систем, а також підтримують покрокову розробку шляхом послідовної деталізації.
Визначення Мережі Петрі
Мережа Петрі (Малюнок 3) визначається як дводольний орієнтований граф, всі вершини графа відносяться до одного з двох класів:
Позиції зображаються колами, переходи – відрізками прямої. Дуги в мережах Петрі – спрямовані.
Мережа Петрі складається з 4-х елементів:
P = - Безліч позицій.
T = - Безліч переходів.
Вхідна функція «I»: відображення вхідних позицій переходів.
Вихідна функція «O»: відображення вихідних позицій переходів.
Елементарна мережа Петрі зображено на рис. 3.
Малюнок. 3. Елементарна мережа.
Маркування мереж Петрі
Маркування використовується для моделювання динамічних властивостей системи.
Маркування M - це надання фішок позиціям мережі. Фішка - це базове поняття мереж Петрі (подібно до позицій і переходів). Фішки присвоюються позиціям, проте їх кількість та положення при виконанні мережі Петрі можуть змінюватись.
На графі мережі Петрі фішки зазвичай зображуються маленькою точкою у гуртку-позиції. Наведемо приклад графічного представлення маркованої мережі Петрі:
Малюнок 4..Маркування мереж Петрі.
Маркування (мітка) мережі Петрі - це функція, що відображає безліч позицій у безліч негативних цілих чисел.
Маркування може визначатися як -вектор: де і кожне () є . Вектор визначає для кожної позиції мережі Петрі кількість точок (маркерів, фішок) у цій позиції.
Мережа Петрі з маркуванням називається маркованою. Маркована мережа Петрі є сукупність мережі Петрі та маркування: . Маркування длямережі , , , .
Маркування характеризує динаміку зміни станів системи, причому динаміка зміни станів моделюється рухом точок за позиціями мережі. Маркування може змінюватися внаслідок запуску переходів. Перехід маркованої мережі з маркуванням називається дозволеним, якщо , тобто в кожній вхідній позиції знаходиться не менше точок, ніж з цієї позиції виходить дуг . Будь-який дозволений перехід може запуститися. В результаті запуску переходу маркування мережі змінюється на нову: з будь-якої вхідної позиції переходу видаляється стільки точок, скільки дуг веде з , а в кожну вихідну позицію міститься стільки точок, скільки дуг веде з . Послідовність запусків переходів називається виконанням мережі.
Нехай позиції й утримують по одній точці. Розглянемо виконання такої маркованої мережі. У цьому маркуванні дозволено лише перехід. При його запуску точка вилучиться з , а потім у позиціях і з'явиться по точці, тобто в результаті запуску з'явиться точка ще й у .
Тепер стають дозволеними переходи та . Оскільки запуститись може будь-який дозволений перехід, припустимо, що запускається перехід . Після його запуску з позиції і точки видалятися, а позиції з'явиться одна точка. У маркуванні, що вийшло, не дозволено жоден перехід. У цьому виконання мережі Петрі закінчується.
Маркування називається безпосередньо досяжним з , якщо знайдеться такий перехід , дозволений у , що з його запуску виходить маркування , тобто .
Маркування називається досяжним з маркування, якщо існує послідовність переходів, спрацьовування яких переводить мережу з маркування на маркування, тобто.
Багато досяжних з маркувань мережі Петрі називається безліччю досяжності і позначається.
Інтерпретація мереж Петрі ґрунтується на поняттях умови та події. Стан системи описується сукупністю умов. Функціонування системи – здійснення послідовності подій. p align="justify"> Для виникнення події необхідне виконання деяких умов, званих передумовами.
Виникнення події може призвести до порушення передумов і появи деяких нових умов, які називаються постумовами. У мережі Петрі умови моделюються позиціями, події – переходами. Передумови події є вхідними позиціями відповідного переходу, постумови - вихідними позиціями. Виникнення події моделюється запуском переходу. Виконання умов є наявністю точок у відповідних позиціях, невиконання - їх відсутністю.
Правила виконання мереж Петрі
Мережа Петрі виконується за допомогою запусків переходів. Запуск переходу управляється фішками у його вхідних позиціях і супроводжується видаленням фішок з цих позицій і додаванням нових фішок у його вихідні позиції.
Перехід може запускатися лише у тому випадку, коли він дозволено. Перехід називається дозволеним, якщо кожна з його вхідних позицій містить число фішок, не менше ніж число дуг, що ведуть з цієї позиції в перехід (або кратності вхідної дуги).
Запуски можуть здійснюватися до тих пір, поки існує хоча б один дозволений перехід. Коли залишиться жодного дозволеного переходу, виконання припиняється.
Малюнок 5.Виконання мережі Петрі.
Властивості мереж Петрі
Безпека. Позиція мережі Петрі з початковим маркуванням є безпечною, якщо будь-який . Іншими словами, позиція мережі Петрі є безпечною, якщо кількість точок у ній ніколи не перевищує 1. Мережа Петрі безпечна, якщо безпечні всіпозиції мережі.
Обмеженість. Розширення якості безпеки. Безпека – необов'язкова вимога. Позиція мережі Петрі з початковим маркуванням -обмежена чи -безпечна, якщо всім , тобто позиція є -обмеженою, якщо кількість точок у ній вбирається у ціле число . 1-безпечна позиція – просто безпечна позиція.
Мережа, звісно, може містити позиції, безпека яких різна. Однак, якщо позиція – безпечна, то вона і – безпечна для всіх. Тому мережа Петрі безпечна, якщо кожна її позиція безпечна, де верхня межа безпеки її позицій.
Часто важливо знати, чи є точок у позиції обмеженим чи ні, а чи не конкретне значення кордону. Позиція називається обмеженою, якщо кількість точок у ній звичайно. Мережа Петрі обмежена, якщо її позиції обмежені. Обмежену мережу можна реалізувати апаратно, мережу з необмеженими позиціями у випадку реалізувати апаратно не можна.
Збереження. Маркування позицій мережі Петрі може моделювати деякі об'єкти чи ресурси. Для таких мереж важливою властивістю є збереження. Необхідно, щоб точки, що представляють ресурси, при спрацьовуванні переходів не зникали і не створювалися, тобто загальна кількість точок мережі повинна залишатися постійним.
Мережа Петрі з початковим маркуванням називається суворо зберігає, якщо має місце
де - Число позицій у мережі.
Живітість. Мережа Петрі називають «живою» при заданому початковому маркуванні, якщо:
1. Для будь-якої пари маркувань (), що належать безлічі, має місце, тобто існує послідовність переходів, спрацьовування яких переводить мережу з маркування в маркування.
2. Для будь-якого переходу в безлічі існує така пара маркувань (), що , тоє спрацьовування переходу переводить мережу з маркування на маркування.
Живі та безпечні мережі називаються правильними мережами.
активність. При моделюванні систем предметом багатьох досліджень є глухий кут. Безвихідь в мережі Петрі - це перехід або безліч переходів, які не можуть бути запущені в певному маркуванні і наступних з маркуваннях. Перехід називається активним, якщо він не глухий (не заблокований). Це не означає, що він дозволений, скоріше він може бути дозволеним.
Існують пов'язані з активністю поняття, наприклад, рівні активності. Їх можна визначити для мережі з маркуванням таким чином:
Рівень 0: Перехід має активність рівня 0, якщо він ніколи не може бути запущений. Перехід, що має активність рівня 0, називається пасивним.
Рівень 1: Перехід має активність рівня 1, якщо він потенційно запустимо, тобто якщо існує така , що дозволено в .
Рівень 2: Перехід має активність рівня 2, якщо існує послідовність запусків, в якій є принаймні разів.
Рівень 3: Перехід має активність рівня 3, якщо існує нескінченна послідовність запусків, в якій є необмежено часто.
Рівень 4: Перехід має активність рівня 4, якщо він дозволений у будь-якому маркуванні .
Мережа Петрі має активність рівня, якщо кожен її перехід має активність рівня не нижче.