Навігація
Головна
 
Головна arrow Інформатика arrow Обчислювальні системи, мережі та телекомунікації. Моделювання мереж
< Попередня   ЗМІСТ   Наступна >

МЕРЕЖІ ПЕТРІ

Часто аналітики в задачах моделювання і аналізу складних паралельних і асинхронних систем звертаються до формальних систем, заснованим на використанні математичного апарату мереж Петрі. Формальна частина теорії мереж Петрі, заснована на початку 60-х років німецьким математиком Карлом Петрі, в даний час містить велику кількість моделей, методів і засобів аналізу, мають велике кількість додатків практично у всіх галузях обчислювальної техніки [14].

Прикладна теорія мереж Петрі пов'язана головним чином із застосуванням мереж Петрі до моделювання систем, їх аналізу і що виходять в результаті цього глибоким проникненням в модельований системи [14].

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

Таким чином, структура мережі Петрі здасться орієнтованим дводольним мультиграфом, в якому одне безліч вершин складається з позицій, а інше безліч - з переходів [14], причому безліч вершин цього графа розбивається на дві підмножини і не існує дуги, що з'єднує дві вершини з одного підмножини .

Отже, мережа Петрі - це набір

(3.14)

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

У мережах Петрі вводяться об'єкти двох типів: динамічні - зображуються мітками (маркерами) всередині позицій і статичні - їм відповідають вершини мережі Петрі.

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

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

Переходи в мережі Петрі є подіями, які змінюють стану в реальній системі. На рис. 3.2 наведено приклад інтерпретації мережі Петрі.

Таблиця 3.1

Елементи мереж Петрі

Назва елемента

зображення елемента

Позиція (Ρ)

Перехід (Τ)

дуга

Інтерпретація мережі Петрі

Мал. 3.2. Інтерпретація мережі Петрі

Формальний апарат мереж Петрі призначений для моделювання систем різного роду і відображає стану досліджуваної системи станом мережі. Стан мережі Петрі визначається сс маркуванням. Кількість і розподіл фішок мережі визначають динаміку досліджуваної системи. Мережа Петрі виконується за допомогою запусків переходів в результаті видалення фішок з його вхідних позицій і додавання їх у вихідні позиції переходу. Послідовність спрацьовувань переходів повністю визначає поведінку мережі. Таким чином, мережа Петрі описує структуру системи, її стан і поведінку [14].

При введенні ряду додаткових правил і умов в алгоритми моделювання отримують різні різновиди мереж Петрі. Це необхідно для визначення модельного часу, яке дозволить моделювати не тільки послідовність подій, але і їх прив'язку до часу. В даний час виділяють наступні різновиди мереж Петрі:

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

Основними властивостями мережі Петрі є:

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

Серед достоїнств апарату мереж Петрі можна вказати наступні:

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

Однак формальна модель мереж Петрі, в силу своєї універсальності, має ряд недоліків, що ускладнюють практичне застосування для моделювання складних систем. До основних таких недоліків можна віднести наступні:

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

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

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

  • • необхідність знання розробником специфічної мови опису моделей [6];
  • • відсутність використання принципів об'єктно-орієнтованого підходу;
  • • низьку гнучкість і трудомісткість опису систем в разі їх декомпозиції до рівня деяких елементарних операцій.

Розфарбовані мережі Петрі досі часто застосовуються для моделювання мереж.

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

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

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

Висновки до розділу

У цьому розділі розглянуто основні поняття і види моделювання обчислювальних мереж, а саме два його основних типи: аналітичне та імітаційне. Описано переваги і недоліки кожного типу моделювання, переваги використання кожного типу моделювання для вирішення певних завдань.

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

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

 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >
 
Дисципліни
Агропромисловість
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Нерухомість
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Природознавство
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Техніка
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук