Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лекції ПРО
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних технологій, автоматики та метрології
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Конспект лекцій
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
паралельні та розподілені обчислення
Практична робота № 1
Тема:
МЕРЕЖІ ПЕТРІ
Мережі Петрі були вперше запроваджені німецьким математиком Карлом Петрі в 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.
Синхронізація за допомогою цієї мережі Петрі є високонадійною, тому що в кожний момент часу тільки один процес перебуває в активному стані. Таким чином, в разі одночасного запиту процеси з паралельних перетворюються в послідовні і блокування їх виникнути не зможе.
09.04.2013 02:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора