НОУ ІНТУЇТ | лекція | Обробка даних

Основні завдання аналізу процесів обробки, можуть бути вирішені з використанням мереж Петрі

В процесі функціонування мережі Петрі деякі її місця можуть накопичувати необмежену кількість фішок. Прикладом такого місця може служити місце в мережі на ріс.8.6 . Якщо інтерпретувати місця як

Мал.8.7.

Граф розміток мережі Петрі

накопичувачі (буфери) даних, сигналів або деталей в модельованих системах, то природно вимагати, щоб при будь-якому варіанті функціонування цих систем не відбувалося переповнення накопичувачів, які в реальних ситуаціях мають кінцеву, фіксовану ємність. Наступні поняття формалізують такі вимоги.

Визначення. Місце в мережі Петрі називається обмеженим, якщо існує число , Таке що для будь-якої досяжною в мережі розмітки справедливо нерівність . Мережа називається обмеженою мережею, якщо будь-який її місце обмежена.

Ясно, що безліч досяжних розміток звичайно, якщо і тільки якщо - обмежена мережа. У мережі на ріс.8.6 місця , і обмежені, так як кожне з них може містити не більше однієї фішки. У той же час місце необмежена, і тому ця мережа не є обмеженою.

Визначення. Місце називається безпечним, якщо для будь-якої досяжною розмітки виконується нерівність ; відповідно, мережа безпечна, якщо всі її місця безпечні.

Будь-яка досяжна в безпечної мережі розмітка являє собою вектор з 0 і 1. Мережа, показана на ріс.8.6 , Не є безпечною.

Родинним поняттям обмеженою і безпечної мережі Петрі є поняття консервативної, або зберігає, мережі.

Визначення. Мережа, в якій сума фішок у всіх її місцях залишається постійною в процесі роботи мережі, тобто

називається зберігає (консервативної).

Умова збереження числа фішок в мережі - це дуже сильне обмеження. Наприклад, з нього негайно випливає, що число входів в кожен перехід має дорівнювати числу виходів (з урахуванням кратності). Якби це було не так, запуск переходу змінив би число фішок в мережі.

Часто фішки в мережі Петрі моделюють різні ресурси. Однак взаємно однозначної відповідності між фішками і ресурсами немає. Фішка може представляти як один ресурс, так і кілька ресурсів відразу. У другому випадку фішка може використовуватися для створення кратних фішок (по одній на ресурс) шляхом запуску переходу з великим числом виходів, ніж входів. Тому визначення якості зберігання мережі доцільно зробити більш загальним, замінивши просту суму фішок на суму з вагами. Фішках, які не є важливими, можна привласнити нульову вагу; іншим фішках можна привласнити ваги 1, 2, 3 або будь-яке інше позитивне число.

Визначення. Мережа Петрі називається зберігає (консервативної) по відношенню до вектора ваг , де - число місць в мережі, якщо

Яка зберігає мережу Петрі є зберігає по відношенню до вектора ваг . Слід виключити з розгляду нульовий вектор ваг, оскільки всі мережі є вони бережуть по відношенню до нульового вектору ваг.

Переходи в мережах Петрі, як правило, моделюють деякі дії (події), які можуть відбуватися в реальних процесах обробки. Тому питання, що стосуються можливості спрацьовування тих чи інших переходів, представляють інтерес при аналізі мереж Петрі.

Перехід в мережі може спрацювати при певних умовах, пов'язаних з розміткою його вхідних місць. Може виявитися, що для деякого переходу умова його спрацьовування ніколи не виконується, як би не функціонувала мережа. Такий перехід - зайвий в мережі, його можна виключити без шкоди для роботи мережі. Може трапитися також, що після деякої послідовності спрацьовувань переходів мережі і відповідних змін її розмітки деякі переходи, в тому числі ті, які вже спрацьовували, більше ніколи не спрацюють, які б варіанти досяжних в мережі розміток не виникали. Це означає, що в модельованих системах можуть з'являтися ситуації, тупикові для деяких подій. Наприклад, в операційних системах подібні випадки відбуваються при взаємних блокувань процесів (deadlocks) при недоступності необхідних ресурсів. Таким чином, переходи в мережі Петрі можуть мати різну активністю, і їх можна розбити на категорії за рівнем активності.

Рівень 0: перехід володіє активністю рівня 0 і називається мертвим, якщо він ніколи не може бути запущений.

Рівень 1: перехід володіє активністю рівня 1 і називається потенційно живим, якщо існує така розмітка , що дозволений в . Рівень 2: перехід володіє активністю рівня 2, якщо для будь-якого цілого існує послідовність запусків, в якій присутній принаймні раз.

Рівень 3: перехід володіє активністю рівня 3, якщо існує нескінченна послідовність запусків, в якій присутній необмежено часто.

Рівень 4: перехід володіє активністю рівня 4 і називається живим, якщо для будь-якої перехід є потенційно живим для мережі Петрі з початковою маркуванням .

Мережа Петрі називається живою, якщо всі її переходи є живими.

Як приклад, що ілюструє рівні активності, розглянемо мережу Петрі на ріс.8.8 . перехід не може бути запущений ніколи; він мертвий. перехід можна запустити лише один раз; він володіє активністю рівня 1. Перехід може бути запущений довільне число раз, але це число залежить від числа запусків переходу . Якщо ми хочемо запустити п'ять разів, ми запускаємо п'ять разів , потім і після цього п'ять разів . Однак, як тільки запуститься ( повинен бути запущений до того, як буде запущений ), Число можливих запусків стане фіксованим. отже, володіє активністю рівня 2, але не рівня 3. З іншого боку, перехід можна запускати нескінченне число разів, і тому він має активність рівня 3, але не рівня 4, оскільки, як тільки запуститься , перехід більше запустити буде не можна.

Мал.8.8.

Мережа Петрі, що ілюструє різні рівні активності переходів

Багато прикладні завдання аналізу систем і процесів в термінах мереж Петрі можуть бути сформульовані як завдання про досяжності заданої розмітки мережі. Ця розмітка може відповідати цільовим станом, в яке бажано перевести систему або процес, або навпаки, описувати стан, попадання в яке краще уникнути (аварійне, збиткове і т.п.). Важливість завдання про досяжності полягає також в тому, що до неї зводяться деякі інші завдання аналізу мереж Петрі.

Формально задача про досяжності полягає в наступному: для мережі Петрі з початковою розміткою і заданої розмітки встановити справедливість включення . Іншими словами, потрібно з'ясувати, чи існує допустима послідовність спрацьовувань переходів , Яка переводить мережу Петрі з початковоїрозмітки в задану розмітку , тобто .

Близькою за змістом до задачі про досяжності є завдання про покриваемості. Вона полягає в тому, щоб для даної мережі Петрі з початковою маркуванням і заданої маркування визначити, чи існує така досяжна маркування , що .

Нагадаємо, що ставлення істинно, якщо кожен елемент маркування не менше відповідної елемента маркування .