МЕРЕЖІ ПЕТРІ Мережі Петрі були розроблені ще в 1962 р. і призначалися для того, щоб представити координацію асинхронних подій. Мережі Петрі дуже часто застосовуються для описування взаємовідносин між паралельними процесами та їх синхронізації. За визначенням мережа Петрі - це орієнтований, дводольний граф з мітками (марками). Це визначення треба розуміти так (рис.1):
Рис.1 Елементи мережі Петрі Кожна мережа Петрі є графом, який має у своєму розпорядженні дві різні групи вершин: вузли та переходи. Між вузлами та переходами можуть міститися орієнтовані ребра (дуги), але два вузли або два переходи не можуть з’єднуватися ребрами. Між кожною парою вузол/перехід може існувати максимально одне ребро від вузла до переходу (ребро входу) і максимально одне ребро від переходу до вузла (ребро виходу). Вузли можуть бути вільними або зайнятими міткою (маркованими); переходи не можуть бути маркованими. Вузли, що є стартовими пунктами одного ребра до одного переходу t , називаються далі вхідними вузлами переходу t. Вузли, що є кінцевими пунктами ребра від переходу t, називаються відповідно вихідними вузлами переходу t. На рис.2 показано просту мережу Петрі, що має один перехід, три ребра і три вузли, два з яких марковані і один не маркований. Кожен вузол зв'язаний з переходом за допомогою одного ребра. Спосіб функціонування цієї мережі Петрі стає зрозумілим, якщо взяти до уваги наступні визначення.
Рис. 2 Мережа Петрі Прості мережі Петрі Визначення: Активізація (Стан): перехід t активізований, якщо всі вхідні вузли pi цього переходу марковані. Таким чином, активізація - це залежна від часу властивість переходу і описує деякий стан. Перехід мережі Петрі на рис.2 активізований, бо обидва вузли ребер, що входять у перехід, марковані. Ввімкнення (Подія): активізований перехід t може вмикатися. Тоді зникають марки з усіх вхідних вузлів pi переходу t і маркуються всі вихідні вузли pj цього переходу. Процес увімкнення переходу має передумовою його активізацію. Як видно з рис.3, в процесі ввімкнення відбувається зміна маркування вузлів мережі Петрі: перехід активізований, бо обидва вузли вхідних ребер марковані. Після ввімкнення переходу маркування обох верхніх (вхідних) вузлів зникає, в той час як на нижньому (вихідному) вузлі з'являється нова марка. Загальна кількість маркувань у будь-якій мережі Петрі не залишається постійною. Якби на вихідному вузлі вже була марка, то вона б переписалася, тобто вузол як і раніше був би зайнятий маркою.
Рис.3 Перемикання переходу Невизначеність: якщо одночасно активізовані декілька переходів, то не зовсім зрозуміло, який з них перемикається першим. Зроблені вище визначення не дають уявлення про порядок перемикання декількох активізованих переходів. Одночасне перемикання їх неможливе! Як показано на рис.4, у цьому випадку можуть відбуватися два процеси і який з них фактично має місце, в мережі Петрі визначити не можна. У зв'язку з тим, що ввімкнення одного або іншого переходу не може бути здійснене за допомогою зовнішніх параметрів, мережа Петрі має в цьому випадку невизначеність.
Рис.4. Недетермінованість перемикань мережі Петрі Стан: стан маркування (або, коротко, стан) мережі Петрі до деякого моменту часу Т визначено як сукупність маркувань кожного окремого вузла мережі. У простих мережах Петрі стан маркування можна відобразити за допомогою деякої послідовності бінарних цифр (двоїчний рядок). Можливе перемикання переходу задається за допомогою переходу в послідовність стану (якщо за аналогією з показаним на рис.4 можуть перемикатися декілька переходів, то існують різноманітні можливі послідовності станів):
У тому випадку, коли перемикання кожного переходу визначається цим правилом, всі послідовності станів одного заданого початкового стану можуть бути "обчислені" комп'ютером і можуть бути розпізнані вірогідні блокування (див. нижче). Генерування марок: перехід, що не має жодного вхідного ребра, завжди активізований і може постійно видавати нові марки на вихідні вузли, що з'єднані з ним. Знищення марок: перехід, що не має жодного вихідного ребра і має тільки одне вхідне ребро, завжди активізований тоді, коли це місце марковано і він може постійно знищувати марку.
Рис.5. Генерування та гасіння марок "Мертвий" стан: Мережа Петрі перебуває в "мертвому" стані (блокована), якщо жоден з переходів не активізований. Блокована мережа Петрі є статичною, тобто в ній немає нових послідовностей станів. Наприклад, обидві мережі Петрі, що показані на рис.4, блоковані. 'Живий" стан: мережа Петрі перебуває в "живому" стані (не блокована в жодному моменті часу), якщо хоча б один з її переходів активізований і це справедливо також для кожного наступного стану. Треба мати на увазі, що "живий" стан не є протилежністю "мертвого" стану. Мережа Петрі в "живому" стані не блокована і не перебуває в жодному із можливих послідовностей станів, в той час як не блокована мережа Петрі не обов'язково має бути в "живому" стані. Наприклад, блокування може відбутися тільки після багатьох послідовних кроків. На рис.6 показано два приклади мереж. Ліва мережа Петрі на рис.6 є "живою" тому, що її маркування змінюється від одного вузла до іншого, але не зникає; перехід завжди тут активізований. У правої мережі Петрі (рис.6) інша ситуація. По-перше, тут можуть перемикатись або перехід u (і тоді мережа негайно переходить у "мертвий" стан), або перехід s. Нарешті можуть перемикатись один раз переходи t і u, що веде також до "мертвого" стану мережі Петрі.
Рис.6.Діюча та блокуюча мережі Петрі Як уже згадувалося, за допомогою мереж Петрі може описуватися синхронізація асинхронних паралельно виконуваних процесів. Це може бути потрібним, щоб уникнути взаємоблокування процесів або виникнення суперечних даних у тих випадках, коли два процеси мають звернутися до однієї й тієї області даних (рис.7).
Рис.7. Доступ двох процесів Р1 , Р2 до загальних даних Процес р1 (виробник) генерує тут незалежно від процесу Р2 дані, записує їх у буферну область пам'яті і хоче без затримки працювати далі. Процес Р2 (споживач} читає дані із цього буфера і використовує їх паралельно з процесом Р2. Щоб уникнути суперечливих даних, треба виконати таку умову: одночасний доступ процесів в одну й ту саму область пам'яті має бути виключений. Це викликає потребу в синхронізації процесів, тобто один з них має деякий час почекати. На рис.8 показано простий приклад для випадку, коли процеси Р1 та Р2 мають бути синхронізовані, тому що вони, наприклад, хочуть користуватися одними й тими самими даними.
Рис.8.Мережа Петрі для синхронізації процесів Кожний процес має тут два стани -активний і пасивний, які символізуються двома вузлами. Процес перебуває в тому стані, який позначається відповідною маркою (це означає, що на рис. 8 обидва процеси пасивні). Кожен з двох процесів може змінювати свій стан з пасивного на активний і навпаки, перемикаючи відповідний перехід. Обидва цикли стану для Р1 і Р2 аналогічні простому контуру, що зображений зліва на рис.6, але ці цикли пов'язані між собою за допомогою так званого вузла-семафора S. Процес, що хотів би змінити свій стан з пасивного на активний (щоб звернутися до загальних даних), потребує для цього переходу маркування в S. Це означає, що він тількі тоді може змінити свій стан на активний, коли марка семафора не використовується іншим процесом (який в цей час перебуває в активному стані). При переході в активний стан семафор S звільняється від маркування; у тому випадку, коли інший процес запросить перехід з пасивного стану в активний (доступ до загальних даних), він має чекати, поки перший процес не перейде знову зі стану активного в пасивний і знову з'явиться семафор-марка S. Синхронізація за допомогою цієї мережі Петрі є високонадійною, тому що в кожний момент часу тільки один процес перебуває в активному стані. Таким чином, в разі одночасного запросу процеси з паралельних перетворюються в послідовні і блокування їх виникнути не зможе. Розширені мережі Петрі Прості мережі Петрі, що були тут представлені, повністю забезпечують цілий ряд різноманітних застосувань. Проте за допомогою трьох простих розширень вони стають суттєво продуктивнішими. Як показано Хопкрофтом і Ульманом, "розширені мережі Петрі" (навіть без додатково уведених нижче ваг дуг) за своєю ефективністю дорівнюють машині Тьюрінга [Hopcroft, Ullmann 69], тобто вони можуть застосовуватись як загальна модель обчислюваності. Розширення: 2.1. Багаторазове маркування
Кожен вузол може мати будь-яку кількість маркувань (при зображенні мережі Петрі допускається маркування коротко позначати числом). Правила активізації та перемикань змінюються відповідно: • перехід активізований тільки тоді, коли число, що відповідає кількості маркувань кожного його вхідного вузла, є більшим за одиницю або дорівнює їй; • якщо активізований перехід перемикається, то числа-маркування усіх вхідних вузлів цього переходу зменшуються на одиницю, а усіх вихідних вузлів - збільшуються на одиницю. За цим сп
