WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Технологія розробки мереж Петрі та вирішення проблем які виникають при їх використанні - Дипломна робота

Технологія розробки мереж Петрі та вирішення проблем які виникають при їх використанні - Дипломна робота

розмітці М можливе спрацювання переходу t і після нього виникає нова розмітка М , то будемо говорити, що М слідує за М, і писати М?М .
Означення 23 Розмітку будемо називати просто досяжною, якщо вона досяжна із початкової розмітки М0 з допомогою деякої послідовності переходів. Через R(N) позначимо множину всіх розміток які можна досягти в мережі N. При неформальній інтерпретації поняття досяжності визначає, в які стани може потрапити система яка описана даною мережею. Наприклад, якщо в R(N) входить тупикова розмітка, то це значить, що системі загрожує дедлок. Тому знанняінформації про множину R(N) дуже важливі.
Аналогічне означення можна ввести і для переходів. Так мова L(N) яка породжена мережею N, по означенню є множиною послідовностей, які можуть спрацювати із початкової розмітки.
Означення 24 Перехід називається живим, якщо він досяжний із любої розмітки множини R(N). Мережа N - жива якщо всі переходи в ній живі.
На рис. 13, зображена мережа, в якій перехід а не є живим. Єдина фішка може переміщатися в ній по верхньому циклу, але може провалитися в нижній. Після цього на верхній рівень вона уже потрапити не може, і перехід а більше ніколи не спрацює. В той же час перехід b є живим.
Поняття живості має дуже важливу роль в різного роду додатках. Дійсно ми вже говорили, що мережі Петрі використовують в основному для моделювання операційних систем (ОС) і відповідних керуючих відповідним апаратних блоків. Із яких би модулів така система не складалася, по її характеру не повинно бути так, що до якогось із з якогось моменту не буде звертань. Потік оброблюваних завдань достатньо однорідний , і кожен модуль ОС, якщо тільки він не виконує допоміжну роль, наприклад завантажувальної функції, або він не відключається на профілактику або ремонт, повинен на ньому більш-менш рівномірно задіяний. "Відмирання" якоїсь частини системи свідчить, що вона не є правильною. Правильність функціонування в цьому смислі і відображає поняття живості.
рис. 13. Приклад живості переходу b, та не живості а
Назвемо місце р k-обмеженим, якщо , тобто в цьому місці при любому ході обчислення не може бути більше фішок ніж k. Місце називається просто обмеженим, якщо воно k-обмежене для деякого k. Мережа N k-обмежена, якщо всі її місця k-обмежені. В якості прикладів обмежених мереж можна привести мережу яку зображено на рис. 12. вона обмежена при к=1. Приклад необмеженої дає рис. 14. в місці р2 може накопичитися довільна кількість фішок. Неформально властивість обмеженості виражає властивість "не накопичувати черги" необмеженої довжини.
Зазвичай при керуванні мережею Петрі дії зображаються переходами, тобто мова L(N) являється множиною всіх процесів, які генеруються мережею N. Природним чином вводяться наступні означення еквівалентності мереж Петрі. Мережа N еквівалентна мережі N , якщо L(N)=L(N ). Таким чином мережі називаються еквівалентними якщо породжують одну і ту ж множину процесів, тобто неформально системи які вони моделюють виконують одну і ту ж роботу. Наприклад, мережа, яка зображена на
рис. 15, а, еквівалентна мережі, яка зображена на рис. 15, б. Із порівняння цих двох мереж видно, що відношення еквівалентності могло б використовуватися як інваріант при спрощуючи перетвореннях мереж: перша мережа має на одне місце та дві стрілки менше ніж друга, з цього випливає, що вона краща.
рис. 14. Необмежена мережа Петрі
І так нами введено різні властивості мереж, які відображають ту чи іншу практичну сторону системи яку ми модулюємо. Любий формалізм оцінюється серед всього іншого і по тому, на скільки багато отримано в ньому позитивних результатів.
2.3 ПРОБЛЕМИ РОЗВ'ЯЗНОСТІ МЕРЕЖ ПЕТРІ
Спираючись на введені означення, можна сформулювати наступні проблеми розв'язності для мереж Петрі:
1. Проблема досяжності (тупикової) розмітки.
2. Проблема досяжності переходу.
3. Проблема життєвості.
4. Проблема еквівалентність.
5. Проблема рівності R(N)=R(N ).
6. Проблема k-обмеженості.
7. Проблема обмеженості.
рис. 15. Приклад двох еквівалентних мереж
Ці проблеми мають різну важкість, вони взаємо зв'язні. Наприклад, розв'язок 1-го автоматично дає розв'язок 2 та 3-го. Але нажаль, для всього класу мереж на сьогоднішній день відомо розв'язок лише двох останніх, досить простих, проблем. Решта проблем залишаються відкритими або доведена їх нерозв'язність. Більш точно доведено нерозв'язність проблем 4 та 5. що до перших трьох, то доведено їх рівносильність і розв'язність для класу мереж, які мають не більше 5-ти місць.
Проблеми 6 та 7 розв'язуються з допомогою техніки, яка розвинена в формалізмі так званих систем векторного складення. Введемо для цих цілей необхідні означення.
Означення 25 Деревом досяжних розміток d(N) мережі N називається дерево в смислі теорії графів з поміченими дугами, в корні якого знаходиться розмітка М0, і з кожної вершини М виходять дуги в вершини-приймачі , такі, що М?Мі.
Перше питання яке можна задати відносно d(N) - це в яких випадках воно скінчене. На це питання є наступний результат.
Лема 6.1
Дерево d(N) скінчене тоді і тільки тоді, коли нема досяжної розмітки М та не порожньої послідовності переходів , таких, що М?М. Таким чином, якщо мережа допускає цикл по переходам, то дерево d(N) буде рости до безкінечності.
Нетривіальні мережі Петрі зазвичай мають цикли, оскільки вони і створені для моделювання деяких нескінченних процесів, тому, якщо ми хочемо працювати з d(N), потрібно шукати способи його кінцевого представлення.
Теорема 6.1
Процес побудови графа g(N) досяжних розміток обривається, і в побудованому графі нема вершини-стану з компонентою, яка перевищує k тоді і тільки тоді, коли мережа N k-обмежена.
Доведення слідує з означення k-обмеженості і найпростішої оцінки: граф допустимих розміток k-обмеженої мережі містить тільки вершини , де ; таким чином, їх число не перевищує , де n - число місць.
Теорема 6.1 дає простий спосіб перевірки властивості k-обмеженості. Але тільки для фіксованого k. При невідомому k, тобто при перевірці обмеженості мережі, невідомо, коли обірветься ріст графа g(N). Тому введеними засобами ми можемо отримати лише рекурсивне перерахування, але не розв'язок проблеми. Для отримання розв'язку необхідно модифікувати означення графа допустимих розміток.
Означення 26 -деревом деревом допустимих розміток назвемо дерево, яке будується за наступними правилами:
1. Починається побудова з початкової розмітки М0.
2. Якщо побудована частина -дерева та М - деяка його вершина, тоді: а) в випадку існування розмітки М =М, яка знаходиться на деякому шляху із М0 в М, то М оголошується кінцевою вершиною;
б) якщо два довільних розмітки М та Мне співпадають, а - список всіх переходів, які можуть спрацювати із М і приводять до розміток , то із М випускаються дуги, які
Loading...

 
 

Цікаве