МЕРЕЖІ ПЕТРІ
Мережі Петрі були розроблені ще в 1962 р. і призначалися для того, щоб представити координацію асинхронних подій. Мережі Петрі дуже часто застосовуються для описування взаємовідносин між паралельними процесами та їх синхронізації.
За визначенням мережа Петрі - це орієнтований, дводольний граф з мітками (марками). Це визначення треба розуміти так (рис.1):
Рис.1 Елементи мережі Петрі
Кожна мережа Петрі є графом, який має у своєму розпорядженні дві різні групи вершин: вузли та переходи. Між вузлами та переходами можуть міститися орієнтовані ребра (дуги), але два вузли або два переходи не можуть з’єднуватися ребрами. Між кожною парою вузол/перехід може існувати максимально одне ребро від вузла до переходу (ребро входу) і максимально одне ребро від переходу до вузла (ребро виходу). Вузли можуть бути вільними або зайнятими міткою (маркованими); переходи не можуть бути маркованими. Вузли, що є стартовими пунктами одного ребра до одного переходу t , називаються далі вхідними вузлами переходу t. Вузли, що є кінцевими пунктами ребра від переходу t, називаються відповідно вихідними вузлами переходу t.
На рис.2 показано просту мережу Петрі, що має один перехід, три ребра і три вузли, два з яких марковані і один не маркований. Кожен вузол зв'язаний з переходом за допомогою одного ребра. Спосіб функціонування цієї мережі Петрі стає зрозумілим, якщо взяти до уваги наступні визначення.
Рис. 2 Мережа Петрі
Прості мережі Петрі
Визначення:
Активізація (Стан): перехід t активізований, якщо всі вхідні вузли pi цього переходу марковані.
Таким чином, активізація - це залежна від часу властивість переходу і описує деякий стан. Перехід мережі Петрі на рис.2 активізований, бо обидва вузли ребер, що входять у перехід, марковані.
Ввімкнення (Подія): активізований перехід t може вмикатися.
Тоді зникають марки з усіх вхідних вузлів pi переходу t і маркуються всі вихідні вузли pj цього переходу.
Процес увімкнення переходу має передумовою його активізацію.
Як видно з рис.3, в процесі ввімкнення відбувається зміна маркування вузлів мережі Петрі: перехід активізований, бо обидва вузли вхідних ребер марковані. Після ввімкнення переходу маркування обох верхніх (вхідних) вузлів зникає, в той час як на нижньому (вихідному) вузлі з'являється нова марка. Загальна кількість маркувань у будь-якій мережі Петрі не залишається постійною. Якби на вихідному вузлі вже була марка, то вона б переписалася, тобто вузол як і раніше був би зайнятий маркою.
Рис.3 Перемикання переходу
Невизначеність: якщо одночасно активізовані декілька переходів, то не зовсім зрозуміло, який з них перемикається першим.
Зроблені вище визначення не дають уявлення про порядок перемикання декількох активізованих переходів. Одночасне перемикання їх неможливе! Як показано на рис.4, у цьому випадку можуть відбуватися два процеси і який з них фактично має місце, в мережі Петрі визначити не можна. У зв'язку з тим, що ввімкнення одного або іншого переходу не може бути здійснене за допомогою зовнішніх параметрів, мережа Петрі має в цьому випадку невизначеність.
Рис.4. Недетермінованість перемикань мережі Петрі
Стан: стан маркування (або, коротко, стан) мережі Петрі до деякого моменту часу Т визначено як сукупність маркувань кожного окремого вузла мережі.
У простих мережах Петрі стан маркування можна відобразити за допомогою деякої послідовності бінарних цифр (двоїчний рядок). Можливе перемикання переходу задається за допомогою переходу в послідовність стану (якщо за аналогією з показаним на рис.4 можуть перемикатися декілька переходів, то існують різноманітні можливі послідовності станів):
EMBED Word.Picture.8
У тому випадку, коли перемикання кожного переходу визначається цим правилом, всі послідовності станів одного заданого початкового стану можуть бути "обчислені" комп'ютером і можуть бути розпізнані вірогідні блокування (див. нижче).
Генерування марок: перехід, що не має жодного вхідного ребра, завжди активізований і може постійно видавати нові марки на вихідні вузли, що з'єднані з ним.
Знищення марок: перехід, що не має жодного вихідного ребра і має тільки одне вхідне ребро, завжди активізований тоді, коли це місце марковано і він може постійно знищувати марку.
Рис.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. Багаторазове маркування
Кожен вузол може мати будь-яку кількість маркувань (при зображенні мережі Петрі допускається маркування коротко позначати числом). Правила активізації та перемикань змінюються відповідно:
• перехід активізований тільки тоді, коли число, що відповідає кількості маркувань кожного його вхідного вузла, є більшим за одиницю або дорівнює їй;
• якщо активізований перехід перемикається, то числа-маркування усіх вхідних вузлів цього переходу зменшуються на одиницю, а усіх вихідних вузлів - збільшуються на одиницю.
За цим способом кількість маркувань одного вузла може бути як завгодно великою, але відповідне число не може бути меншим від нуля.
Дуги-заперечення
Дуги-заперечення в мережах Петрі зображаються кружечком на кінці замість стрілки (рис.9) і не мають дугової ваги; дуги, що були визначені раніше, розглядаються як позитивні дуги.
Рис.9. Дуга-заперечення
Вони завжди можуть бути направлені тільки від деякого вузла до деякого переходу, зворотного напрямку не дозволяється. Введення дуг-заперечень зумовлює оновлені пристосування правил активізації та перемикань:
• перехід активізований тільки тоді, коли кількість маркувань кожного вхідного вузла з позитивною дугою більша або дорівнює одиниці і коли кількість маркувань кожного вхідного вузла з дугою-запереченням дорівнює нулю (на рис.9 перехід t активізований, якщо Р1 маркований і Р2 не маркований).
• якщо активізований перехід перемикається, то кількість маркувань усіх вхідних вузлів з позитивними дугами цього переходу зменшується на одиницю, в той час як кількість маркувань вхідних вузлів з дугами-запереченнями залишається незмінною. Числа, що відповідають кількості маркувань усіх вихідних вузлів, як і раніше, збільшуються на одиницю.
2.3. Вага дуг
Кожна дуга, що не є дугою-запереченням, може мати постійну цілочислову вагу, що більша або дорівнює одиниці ( число, що використовується за умовчанням, рис.10).
Рис.10. Вага дуг
Для активізації і перемикання переходу діє правило:
• перехід активізований тільки тоді, коли кількість маркувань кожного його вхідного вузла більше або дорівнює відповідній вазі дуги, а для дуги-заперечення дорівнює нулю;
• при перемиканні переходу кількість маркувань кожного вхідного вузла зменшується на вагу відповідної вхідної дуги (вона залишається незмінною для дуг-заперечень); кількість маркувань кожного вихідного вузла збільшується на вагу відповідної вихідної дуги.
Приклади мереж Петрі
Наведемо ряд прикладів розширених мереж Петрі, які частково базуються на прикладах з роботи [Krishnamurthy 89]. В принципі можна кожну програму, написану на будь-якій мові програмування, представити у формі розширеної мережі Петрі. При цьому треба мати на увазі, що "пам'ять маркувань" деякого вузла може містити тільки додатне число або нуль. Від'ємні числа можуть, наприклад, представлятися додатковим вузлом, що визначає знаки чисел. Кожна наведена тут мережа має спеціальний "стартовий" вузол, з якого починається обчислення, і вузол "готовності", який маркується тоді, коли обчислення повністю завершено і з'явився результат. Спеціальні старт-і готовність-вузли особливо важливі тоді, коли треба скласти розширену мережу Петрі із наявних елементів.
Суматор
Суматор (рис.11) має полічити маркування від пункту Y до маркувань в Z, тобто створити суму Z+Y. Тут маємо спеціальний стартовий вузол, який на початку операції зайнятий маркуванням "1". Після перемикання переходу s ця марка зникне з місця старту, а марка у вузлі готовності з'явиться тільки тоді, коли закінчиться процес складання і сума буде у вузлі Z.
Після перемикання стартового переходу s. маркується середній вузол мережі Петрі. Крок за кроком, перемикаючи перехід t, одне маркування береться з вузла Y (вхід) і одночасно вводиться у вузол Z (вихід). Середній вузол залишається при цьому маркованим, бо він містить у собі як вихідну, так і вхідну дуги (1-1+1=1). Одначе цей вузол не є зайвим, бо він дбає про те, щоб операція складання відбувалась як результуюча після розблокування стартового вузла. В кінці операції, коли Y=0, сума з'являється у вузлі Z і перехід t більше не активізується. Для завершення операції призначений перехід й, що тепер активізований; якщо він перемикається, то марка із середнього вузла виводиться і генерується марка у вузлі готовності, що сигналізує про закінчення обчислення.
У цьому та наступних прикладах треба мати на увазі, що початкове числове значення Y знищується (у нашому випадку стає нулем) і не може використовуватися для можливих подальших операцій. Якщо змінна Y потрібна для інших операцій, що відбуваються після одержання суми, то мережу Петрі треба будувати так, щоб в ній відновлювалося значення величини Y.
Рис.11. Мережа Петрі як суматор
Пристрій для віднімання
Простий пристрій для віднімання (рис.12 зліва) можна побудувати із суматора (рис.11), в якому змінено напрямок дуги від Z (штрихова стрілка). На кожному кроці тепер маркування не йде на місце Z, a навпаки, виводиться з Z. Ця методика функціонує, правда, за тих умов, що Z?Y; в інших випадках віднімання зупиняється без маркування кінця операції у вузлі готовності! Це, звичайно, не має сенсу, тому на рис.12 праворуч показано розширений пристрій, який обчислює симетричну різницю.
Рис.12. Мережа Петрі для операції віднімання
При симетричному відніманні різниця Z-Y заноситься в Z, якщо Z?Y, а різниця Y-Z заноситься в Y, якщо Y>Z. У зв'язку з цим мережа Петрі доповнюється симетрично переходом ?.
Пристрій для множення
Пристрій для множення (рис.13) має складнішу будову, але в переходах s, t і ? можна впізнати основні елементи суматора.
Рис.13. Мережа Петрі для операції множення
Це змінює одночасно принцип роботи перемножувача: під час кожного проходу X зменшується на одиницю і Y покроково складається з Z. У вузлі "пам'ять" копіюється початкова величина Y, і в кінці операції через перехід н на Y робиться нова копія, щоб Y можна було використати в наступних розрахунках. Новий обчислювальний цикл починається, якщо "пам'ять" дорівнює нулю; потім перехід знову активізується через дугу заперечення. Цикли, в яких величина Y складається з Z, виконуються доти, поки X стане дорівнювати нулю, тобто добуток X*Y буде складено з Z.
Багато з виконуваних обчислювальних операцій можуть бути легко розміщені у вигляді ланцюга активізацій, в якому їхні стартові і фінішні вузли зв'язуються між собою послідовно відповідно до порядку обчислень або також паралельно. При багаторазовому доступі зчитування з одного і того самого елемента пам'яті обчислення мають вестися послідовно. Крім цього, усі операції мають відновлювати вихідну величину, що була в елементі пам'яті. Ця умова виконана в наведених прикладах тільки для змінної величини Y в пристрої для множення і в разі потреби має доповнюватись.
На рис.14 показано можливість розмноження значень змінної величини. На рис.15,16 наведено приклади складних мереж Нетрі, які скомпоновані з більш простих модулів за методом чорного ящика.
Рис.14. Розмноження значень змінної X
Послідовні обчислення
Рис.15. Послідовне використання мережі Петрі
Паралельні обчислення
