Контрольная работа: Імітація процесів гнучких виробничих систем за допомогою апарата мереж Петрі

1.1 Визначення мережі

Мережа Петріє двочастковий орієнтований граф. Двочастковий граф - це такий граф, множина вершин якого розбивається на дві підмножини й не існує дуги, що з'єднує дві вершини з однієї підмножини. Отже, мережа Петрі - це набір

N = (T,P,A), T Ç Р = Ø, (1.1)

де Т = {t₁ ,t₂ ,...,t_n } - підмножина вершин, що називаються переходами; Р = {p₁ , р₂ , ..., p_m } - підмножина вершин, що називаються (подіями)місцями; АÍ (T×P) – множина орієнтованих дуг.

По визначенню, дуга з'єднує або місце з переходом, або перехід з місцем.

Приклад

На рис. 1.1 наведений приклад мережі Петрі в графічному поданні. Переходи позначені рисками, а місця - окружностями. Кожен перехід t має набір вхідних in {t} і набір вихідних out {t} дуг. Мережі Петрі можуть представлятися також у формі продукційних правил (рис. 1.1,б).

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

Рис 1.1 Приклад мережі Петрі в графічному поданні

1.2 Розмітка мережі

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

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

Фішка свідчить про те, що змінна/буфер має значення, а якщо місце має, приміром, 3 фішки, те це може інтерпретуватися як наявність трьох різних значень у буфері.

Якщо місце містить фішку, то місце маркіроване й мережа називається маркірованою. Початковий розподіл фішок задає початкове маркування М₀ мережі. Маркування мережі визначає її поточний стан.

Мережа на рис.1.2 у початковому стані містить одну фішку в місці р₃ .

Рис 1.2 Послідовність станів мережі Петрі

Маркування формально задається функцією М: Р → I, I = {0,1,2,..}, а функція М представляється вектором, у якому i-й компонент задає маркування місця p_i .

Наприклад, початкове маркування мережі на рис. 1.2 представляється вектором М₀ = {1,0,0}.

На рис. 1.2 показана послідовність станів мережі Петрі в ході спрацьовування переходів. Початкова розмітка М₀ = (1,0,0) показана на рис1.2,а.

У цьому стані може спрацювати тільки перехід t₁ . Розмітка мережі M₁ = (1,1,1) після спрацьовування t₁ показана на рис.1.2,б. Остання дозволяє одночасно спрацювати переходам t₁ й t₂ , розмітка М₂ = (1,2,3) після їхнього спрацьовування показана на рис.1.2,в.

Мережа переходить із одного стану в інше (від одного маркування до іншого), коли відбувається подія – спрацьовування переходу.

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

Рис 1.3 Схема спрацьовування переходів

Спрацьовування переходу складається з того, що із всіх вхідних місць забирається по одній фішці й в усі вихідні місця додається по одній фішці.

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

В іншій інтерпретації перехід може представляти деякий пристрій. Пристрій може (але не повинен) спрацювати, якщо виконалися всі вхідні умови.