паралельні та розподілені обчислення Практична робота № 1 Тема: МЕРЕЖІ ПЕТРІ Мережі Петрі були вперше запроваджені німецьким математиком Карлом Петрі в 1962 році. На сьогоднішній день мережі Петрі в основному використовуються при моделюванні. В багатьох галузях досліджень деяке явище вивчається не безпосередньо, а через так звану „модель”. Модель – це представлення в математичних термінах того, що є найбільш характерне і властиве деякій системі чи явищу. Різні маніпуляції над моделлю дозволяють отримати нові знання про неї. Розвиток теорії мереж Петрі відбувався по двох напрямках. Формальна теорія мереж Петрі займалась розробленням основних засобів, методів і понять, необхідних для застосування мереж Петрі. Прикладна теорія мереж Петрі пов’язана в основному із застосуванням мереж Петрі при моделюванні систем, їх аналізу і глибоким проникненням в змодельовані системи. Моделювання в мережах Петрі відбувається на рівні подій. Визначається, які події проходять в системі, які стани передували цим подіям і в які стани система перейде після завершення цих подій. Виконання подій в мережі Петрі описує поведінку системи. Аналіз результатів виконання дає можливість дізнатись про те, в якому стані перебувала чи не перебувала система і які стани є в принципі неможливими. Однак, такий аналіз не дає числових характеристик, які визначають стан системи. Мережі Петрі призначаються для того, щоб представити координацію асинхронних подій. Мережі Петрі дуже часто застосовуються для описування взаємовідносин між паралельними процесами та їх синхронізації. Мережі Петрі – це потужний інструмент для дослідження паралельних і асинхронних систем. За визначенням мережа Петрі – це орієнтований, дводольний граф з мітками (марками). Це визначення треба розуміти так (рис.1):
Рис.1 Елементи мережі Петрі Кожна мережа Петрі є графом, який має у своєму розпорядженні дві різні групи вершин: вузли та переходи. Між вузлами та переходами можуть міститися орієнтовані ребра (дуги), але два вузли або два переходи не можуть з’єднуватися ребрами. Між кожною парою вузол/перехід може існувати максимально одне ребро від вузла до переходу (ребро входу) і максимально одне ребро від переходу до вузла (ребро виходу). Вузли можуть бути вільними або зайнятими міткою (маркованими); переходи не можуть бути маркованими. Вузли, що є стартовими пунктами одного ребра до одного переходу t , називаються далі вхідними вузлами переходу t. Вузли, що є кінцевими пунктами ребра від переходу t, називаються відповідно вихідними вузлами переходу t. На рис.2 показано просту мережу Петрі, що має один перехід, три ребра і три вузли, два з яких марковані і один не маркований. Кожен вузол зв’язаний з переходом за допомогою одного ребра. Спосіб функціонування цієї мережі Петрі стає зрозумілим, якщо взяти до уваги наступні визначення.
Рис. 2 Мережа Петрі Прості мережі Петрі Визначення: Активізація (Стан): перехід t активізований, якщо всі вхідні вузли pi цього переходу марковані. Таким чином, активізація - це залежна від часу властивість переходу і описує деякий стан. Перехід мережі Петрі на рис.2 активізований, бо обидва вузли ребер, що входять у перехід, марковані. Ввімкнення (Подія): активізований перехід t може вмикатися. Тоді зникають марки з усіх вхідних вузлів pi переходу t і маркуються всі вихідні вузли pj цього переходу. Процес увімкнення переходу має передумовою його активізацію. Як видно з рис.3, в процесі ввімкнення відбувається зміна маркування вузлів мережі Петрі: перехід активізований, бо обидва вузли вхідних ребер марковані. Після ввімкнення переходу маркування обох верхніх (вхідних) вузлів зникає, в той час як на нижньому (вихідному) вузлі з'являється нова марка. Загальна кількість маркувань у будь-якій мережі Петрі не залишається постійною. Якби на вихідному вузлі вже була марка, то вона б переписалася, тобто вузол як і раніше був би зайнятий маркою.
Рис.3 Перемикання переходу Невизначеність: якщо одночасно активізовані декілька переходів, то не зовсім зрозуміло, як...