Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Розробка та верифікація моделей систем із використанням мереж Петрі Вступ

Розробка та верифікація моделей систем із використанням мереж Петрі Вступ




Сторінка1/2
Дата конвертації10.01.2020
Розмір0.57 Mb.
  1   2


Розробка та верифікація моделей систем із використанням мереж Петрі

Вступ

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

Створення моделі – кропіткий і творчий процес, що вимагає від дослідника не тільки глибоких теоретичних знань з різних математичних та технічних дисциплін, але й творчого підходу до розв’язання задач, уміння генерувати певні евристики, що відповідають глибинній суті досліджуваного об’єкта.

В наш час все більшого поширення набула проблема паралельного обчислення. Разом з нею і виникло багато інших проблем серед яких і моделювання розподілених обчислень.  При моделюванні розподілених обчислень розглядаються класичні мережі Петрі.

Мережа Петрі – це графічний і математичний засіб моделювання систем і процесів. Як правило, мережами Петрі моделюють паралельні(синхронні та асинхронні) системи і процеси. Спочатку запропоновані в докторській дисертації Карла Петрі в 1962 році вони одержали подальший розвиток у роботах таких вчених як Тадао Мурата, Курт Йенсен, Віталій Котов, Анатолій Слєпцов. В останні часи проводиться щорічна конференція «Застосування і теорія мереж Петрі», видається в Боні інформаційний бюлетень «Новини мереж Петрі» (Petri Net Newsletter), відомо кількасот моделюючих систем для різних програмно-апаратних платформ, існують реалізації процесорів мереж Петрі. Галузі застосування мереж Петрі включають дослідження телекомунікаційних мереж, мережних протоколів, обчислювальних систем і обчислювальних процесів, виробничих і організаційних систем.



Постановка задачі

Створити модель системи, змоделювати модель за допомогою математичного апарату Мереж Петрі та дослідити її роботу. Маніпулюючи моделлю системи, можна отримати нові знання про неї. Після моделювання, виконаємо верифікацію моделі, за допомогою СPN Tools (спеціальна моделююча система, яка використовує мову мереж Петрі для опису моделей).

Та розробити графічну програму , яка візуально продемонструє роботу розробленої моделі.

Мережі Петрі

Мережа Петрі є орієнтованим дводольним графом, який має чотири базових елементи: вузли, або місця (places), переходи (transitions), дуги (arcs) і маркери (tokens). Вузли позначаються кружками і визначають стан, в якому може знаходитись мережа або її частина. Переходи - це активні елементи мережі, які позначають дії, виконувані під час спрацювання переходів. Для того щоб перехід міг спрацювати, необхідне виконання певних умов, які визначаються наявністю маркерів у вузлах мережі, з'єднаних з переходом. Якщо умови настання подій виконано, то вважають, що перехід збуджений. Переходи позначаються короткими вертикальними або горизонтальними лініями.

Вузли та переходи з'єднуються орієнтованими ребрами (дугами). Вузли, з яких виходять дуги до певного переходу, називаються вхідними вузлами переходу, а вузли, до яких ведуть дуги з певного переходу, - вихідними. Два вузли або два пере­ходи з'єднуватись дугами не можуть. Кожний перехід може бути з'єднаним з вуз­лом тільки однією дугою (вхідною або вихідною).

Застосування мереж Петрі

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

Моделювання залізничних мереж

Оскільки МП це компактна, формальна і графічна мова з вбудованою паралельністю, вона дуже зручна для моделювання ж/д систем. Однак одержувані моделі настільки об'ємні, що необхідно абстрагуватися від деталей. Рішенням є введення ієрархії МП моделей.

Моделювання комп'ютерних атак

Створення моделі комп'ютерної атаки, яку можна застосовувати для синтезу мережевого трафіку атакуючого впливу, повинна відображати як статичні, так і динамічні складові мережевого трафіку.

Але застосування мереж Петрі також зустрічаються в різноманітних галузях, та тисячі задач для моделювання та діагностики, наприклад:


  • 1)Використання мереж для оцінки часу евакуації людей в будівлях і спорудах.

  • 2)Використання при проведенні аналізу живучості бортових інформаційно-керуючих систем.

  • 3) Використання мереж Петрі для моделювання процесів транспортно-експедиційного обслуговування.

  • 4)Застосування мереж для опису паралельних процесів.

  • 5)Застосування мереж Петрі для діагностування проблем синхронізації в обчислювальних системах із загальною пам'яттю.

Створення моделі

Змоделюємо простий процес, який ми часто виконуємо у повсякденному житті, це процес користування банкоматом. Коли спрацює перехід «клієнт підійшов до банкомату», у позиції « у черзі клієнтів є клієнт» з’явиться маркер. Наявність маркерів у позиціях « у черзі клієнтів є клієнт» та «банкомат вільний» означає, що виконані умови для події «клієнт розпочав виконувати операції». При запуску переходу «клієнт розпочав виконувати операції» маркери з позицій «у черзі клієнтів є клієнт» та «банкомат вільний» видаляються, а в позиції «клієнт обслуговується» маркер з’являється. Наявність маркеру в позиції «клієнт обслуговується» означає, що виконані умови для події «клієнт закінчив виконувати операції». При запуску цього переходу маркер з позиції «клієнт обслуговується» видаляється, а в позиції «банкомат вільний» та «є обслугований клієнт» маркери додаються.



Змоделюємо роботу торгового магазину , при покупці товару. Змоделюємо систему яка буде через деякий час t здійснювати замовлення. Представимо графічно цей процес купування товару мережею Петрі. Вона має вид , як на малюнку.

Наша схема має часткові тупики. Перший тупик який ми можемо зустріти під час обробки замовлень – це недостатня кількість товару, наше замовлення потрапляє в чергу на закупку певного товару. Далі замовивши товар, кількість товару на складі збільшується для обробки товару, і переходе в переходу достатня кількість товару. Наступний частковий тупик яка може статися під час роботи системи, недостатня кількість працівників для обробки та відправки товару до покупця. У такому разі система повертає замовлення до черги замовлень служби доставки. Де буде знову перевіряти на наявність вільних. Також при моделюванні нашої системи будемо враховувати часові затримки, при генерації замовлення, тобто кожне наступне замовлення буде генеруватись через деякий час, інші часові затримки, це при відправленні товару, та при поповненні складу , у разі недостатності товару для виконання замовлення.



Моделювання системи в CPN Тools

CPN Tools - це спеціальна моделююча система, яка використовує мову мереж Петрі для опису моделей. Ми будемо її використовувати для перевірки правильності роботи, та аналізу нашої системи. моделей. Система була розроблена в Університеті Орхуса в Данії і вільно поширюється для некомерційних організацій. Рівень сервісу дозволяє класифікувати CPN Tools як промислову систему. Вона була використана в великій кількості реальних проектів, особливо в галузі телекомунікації

Такий вигляд має модель магазину (рис.1.1) при замовлені деякого товару,вона нічим не відрізняється від раніше побудованої моделі. У цій моделі ми маємо декілька типів змінних , 1-й тип це товар, 2-й тип це робітники. За значення змінної при генеруванні замовлення ми беремо деяке число у діапазоні від 5 до 20. Тобто генерується деяке замовлення товару кількістю і. Якщо ж на складі не можливо виконати замовлення генерується інше замовлення на поповнення складу товаром, якого не вистачає. Також ми додали у систему так звані часові затримки, бачимо, що при генерації замовлення використовуємо її, а також при відправці замовлення , та поповнення запасу складу.



Рис 1.1 Модель роботи магазину

  1   2



  • Постановка задачі
  • Мережі Петрі
  • Застосування мереж Петр і
  • Створення моделі
  • Моделювання системи в CPN Тools