ТнАрІТС Технології та архітектура ІТС
Тема А07.01 Основи проектування Switch
Мережі Петрі мережі Петрі - одне з найбільш виразних засобів для моделювання процесів, в тому числі паралельних, синхронних і асинхронних. Вони відображають логічну послідовність подій, дозволяють відстежувати потоки даних, відпрацьовують взаємодію процесів. Мережа Петрі задається графом, вершини якого розбиті на дві підмножини. На рис. *** показаний приклад такого уявлення мережі.
Одне з цих підмножин представляє вузли-позиції (позначаються кружечками і розмічаються символами Pi), інше вузли-переходи (позначаються рисками і розмічаються символами ti). Вершини пов'язані спрямованими дугами, що не позначаються.
Входи і виходи як такі в мережі Петрі можуть не позначатися. Її позиції маркуються (позначаються всередині заштрихованої точкою) і це розглядається як початкова розмітка. Ще це називають розміщенням по позиціях фішок. Кількість фішок в позиції може змінюватися від 0 до нескінченності. Нескінченність зазвичай позначається як .
Мережа Петрі виконується за допомогою запусків переходів, який управляється фішками.
У кожен конкретний момент може запускатися тільки один з переходів в тому випадку, якщо він дозволений (активний). В принципі, можуть бути активними кілька переходів. Але запуститися може один.
Перехід називається дозволеним, якщо кожна з його вхідних позицій містить число фішок не менш числа дуг, що ведуть з цієї позиції в перехід.
Для з'ясування принципу функціонування мережі Петрі розглянемо більш змістовний приклад, показаний на рис. ***
Тут поміченими є позиції P1 і P3. що позначається як маркування (1010). Тобто, якщо в позиції знаходиться фішка, то вона маркується як (1), в іншому випадку як (0). Маркування всіх вершин представляється у вигляді вектора (1. 2. ..., n), де I терм i-й позиції, а n - число позицій в мережі. Переходи даної мережі представлені у вигляді наступного деорева.
Як вузлів дерева виступають ті маркування, які реалізуються в ході виконання мережі Петрі.
Початкова маркування є вершиною дерева. При цьому активною є тільки перехід t3. Запуск переходу t3 здійснюється тим, що спочатку фішка вилучається з неї, а потім поміщається в позицію p4. Це і констатує нове маркування (1001).
Далі активним стає перехід t2. Але в цьому випадку запуск цього переходу супроводжується тим, що вилучається одна фішка з позиції p4. а розміщується дві - одна в позицію p2. а інша в позицію p3.
Після цього активними стають вже два переходи t1 і t3. У цій ситуації може запускатися один з них.
Якщо ми підемо по гілці t3. то повторимо вже пройдені кроки. Це означає, що мережа Петрі потрапляє в цикл. При цьому в позиції p2 будуть накопичуватися фішки. Причому, таке накопичення нічим не обмежена, що і позначається як .
Якщо ми підемо по гілці t1. то потрапляємо в глухий кут. Справа в тому, обнуляється позиція p3. А, отже, перехід стає t1 забороненим
Це робить більш багатими моделюють властивості мережі Петрі.
Правильна мережу Петрі називається автоматної, якщо всі її переходи мають не більше однієї вхідної та не більше однієї виходить дуги, а в її початковій маркуванні є не більше однієї позначки.
Завдання для самостійної роботи. Побудуйте і досліджуйте автоматну мережу Петрі.
2.3.2.Моделірованіе систем на основі мереж Петрі.
Подання системи мережею Петрі засновано на двох основоположних поняттях: події та умови. Виникненням подій управляє стан системи, яке може бути описано безліччю умов. Умова може приймати або значення «істина», яке значення «брехня».
Виникнення події в системі можливо, якщо виконуються певні умови - передумови події. Виникнення події може привести до виконання інших умов - постусловіем події. Як приклад розглянемо наступну нижче завдання моделювання.
Приклад. Моделювання послідовної обробки запитів сервером бази даних. Сервер знаходиться в стані очікування до тих пір, поки від користувача не надійде запит, який він обробляє і відправляє результат такої обробки користувачеві.
Для наведеного опису можна скласти відповідну специфікацію подій і умов. а також таблицю їх перед- і постусловіем.
Умовами для даної системи є:
б. запит надійшов і чекає;
в. сервер обробляє запит;
м запит оброблений.
Подіями для цієї системи є:
1. Запит надійшов.
2. Сервер починає обробку запиту.
3. Сервер закінчує обробку запиту.
4. Результат обробки відправляється.
В даній мережі Петрі умови моделюються позиціями, події - переходами. При цьому входи переходу є передумовою відповідного події; виходи - постусловіем. Виникнення події моделюється запуском відповідного переходу. Виконання умови представляється фішкою в позиції, що відповідає цій умові. Запуск переходу видаляє фішки, що представляють виконання передумов і утворює нові фішки, які представляють виконання постусловіем.
Приклад. Одночасність і конфлікт. Розглянемо мережу Петрі.
Два переходи даної мережі знаходяться в конфлікті тобто запуск одного з них видаляє фішку із загальної вхідний позиції і тим самим забороняє запуск іншого. Таким чином моделюються взаємовиключні події.
Приклад. Реалізація алгоритму обчислення Y! І твір всіх парних чисел на відрізку [1, Y] для довільного позитивного цілого Y.
Програма на абстрактному мовою.
2.4. Моделювання взаємодій процесів мережами Петрі.
Існують різні види взаємодії (синхронізації) процесів, в тому числі: взаємодія за допомогою загальною (що розділяється) пам'яті; за допомогою передачі повідомлень різних видів.
Їх моделювання здійснюється вже здобув популярність графо-аналітичними конструкціями на основі мереж Петрі.
Далі покажемо, як мережі Петрі можуть моделювати різні механізми синхронізації процесів на основі вирішення завдань, що стали класичними в цій області їх застосування.
Завдання про взаємне виключення. Нехай два процеси поділяють загальну змінну, запис, файл або інший елемент даних.
Для поновлення елементу, даних процес повинен спочатку вважати старе значення, потім обчислити нове і, нарешті, записати його на те саме місце. Якщо два процеси P1 і P2 в один і той же час намагаються виконати таку послідовність дій, то може виникнути спотворення даних.
Для виключення подібних проблем використовується метод взаємного виключення, заснований на понятті критичної секції. Критична секція - це ділянка коду процесу, на якому він здійснює доступ до поділюваного об'єкта даних. Перш ніж виконати свою критичну секцію, процес чекає, поки інший процес не закінчить виконання власної критичної секції (якщо таке виконання має місце). Потім він входить в критичну секцію і блокує доступ для будь-якого іншого процесу до своєї критичної секції. Після виконання процесом критичної секції деблокується доступ для інших процесів до разделяемому об'єкту даних.
Наступна нижче мережу Петрі моделює механізм взаємного виключення для двох процесів P1 і P2.
Завдання про виробника / споживача. У цьому завданні також має місце розділяється об'єкт - буфер, за допомогою якого реалізується взаємодія через асинхронну передачу повідомлень. Процес-виробник створює повідомлення, які поміщаються в буфер. Споживач чекає, поки сполучення не буде поміщено в буфер, витягує його звідти і використовує. Така взаємодія може бути промоделювати наступній нижче мережею Петрі.
Позиція В являє буфер, кожна фішка відповідає повідомленням, яке вироблене, але ще не використано.
Питання про обідають мудреців. Питання про обідають мудреців була запропонована Дейкстрой і пов'язана з п'ятьма мудрецями, які поперемінно то думали, то їли.
Мудреці сидять за круглим столом, на якому багато страв китайської кухні. Між сусідами лежить одна паличка для їжі. Для прийому китайської їжі необхідно дві палички. Тому кожен мудрець повинен спочатку взяти паличку зліва і паличку праворуч, а потім приступити до їжі. Можлива ситуація, коли кожен мудрець візьме паличку зліва, а потім чекатиме, коли звільниться паличка з правого боку. Так вони будуть чекати, поки не помруть з голоду. Тим самим, цей стан для системи «обідають мудреці» є тупиковим.
Проблема тупика в цій системі може бути вирішена шляхом наступної модифікації її правил поведінки: Нехай мудрець при переході зі стану роздумів в стан прийому їжі захоплює не по черзі, а одночасно обидві палички (зліва і справа), якщо вони вільні. Ця ситуація моделюється наступної мережею Петрі.
У цій мережі Петрі позиції ni. i представляє умова «i-я паличка вільна». У початковій маркуванні кожна з цих позицій має фішку. Кожному мудреця i відповідає дві позиції: позиція дi - представляє умова «i-й мудрець думає»; і позиція еi - представляє умова «i-й мудрець їсть». У початковій маркуванні кожна позиція дi містить фішку, а кожна позиція еi порожня.
Кожному мудреця також відповідає два переходи: перехід начi - представляє подія «початок прийому їжі i-м мудрецем»; і перехід завi - представляє подія «завершення прийому їжі i-м мудрецем».
Для продовження скачування необхідно зібрати картинку: