Приклад 6.2

Розглянемо мережу, до якої надходять вимоги, як від пристроїв для обчислення (замкнена частина) так і ззовні.

Нехай, М = 40 пристроїв для обчислення. Середній час обчислення кожним пристроєм Z = 15c.

Відомо такі дані:

1) Середній час перебування вимог, які надходять до мережі від 40 пристроїв для обчислення = 5 с (R*).

2) Середній час обчислення вимоги у вузлі t = b_t = 40 мс.

3) Кожна вимога, яка надходить від кожного з M пристроїв для обчислення породжує 10 вимог, що надходять до вузла t.

4) Кожна вимога, що надходить до системи ззовні породжує 5 вимог, що йдуть до вузла t.

5) Завантаження вузла t – 90% (u_z = 0.9).

Визначити нижню межу часу перебування у мережі вимог, які надходять від М пристроїв з інтенсивністю вхідного потоку х₀* і від зовнішнього джерела вимог з інтенсивністю х_t, тобто визначити пропускну здатність вузла t.

Змінні, що стосуються вимог, що надходять від М пристроїв позначатимемо *.

З формули (14.14) знаходимо:

х₀* = М/(Z+R*) – інтенсивність вхідного потоку від пристроїв.

х₀* = 40/(15+5) = 2 вимоги/с.

Інтенсивність потоку вимог до вузла t визначаємо як суму інтенсивностей потоків від пристроїв та інтенсивності потоку зовнішніх вимог до вузла t (х₀* + x_t) тоді згідно з виразом (14.6) (баланс потоків) або вимог/с. За формулою (14.8) знаходимо інтенсивність вхідного потоку зовнішніх вимог до мережі:

х₀ = 2,5/5 = 0,5 вимог/с.

Припустимо, що початкові умови змінились та інтенсивність вхідного потоку зовнішніх вимог збільшилось в 3 рази, тобто х₀ = 1,5 вимог/с.

Тоді, х_t = v_t∙x₀=7.5 вимог/с.

Якщо середній час обробки вимог у вузлі t не змінився, то при завантаженості вузла t на 100% максимально можлива інтенсивність обслуговування вимог у вузлі t 1/s_t = 25 вимог/с.

Таким чином, інтенсивність обслуговування вимог у вузлі t не може перевищувати (25-7,5) = 17,5 вимог/с

З огляду на це маємо:

вимог/с.

Отже, згідно з (14.14) нижня межа часу перебування вимог у мережі, які надходять від 40 пристроїв для обчислення становить:

Таким чином, збільшення інтенсивності потоку зовнішніх вимог у 3 рази приведе до збільшення середнього часу перебування вимог у мережі, які надходять від 40 пристроїв на 2,9 с.

 

6.2 Мережі Петрі

Мережі Петрі (МП) – це математична модель, яка використовується для моделювання динамічних потоків.

МП є орієнтованим дводольним графом, який має 4 базові елементи: вузли або місця, переходи, дуги і маркери.

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

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

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

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

а) спрацювання переходу б) після переходу

Рисунок 6.3 - Проста мережа Петрі

 

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

Якщо одночасно збуджується кілька переходів мережі, виникає невизначеність, тому одночасне спрацювання кількох переходів у МП неможливе, тобто переходи спрацьовують послідовно, миттєво. Незважаючи на те, що маркери змінюють своє положення у вузлах, прості МП – це статичні моделі, в яких не враховується динаміка в часі (зміна станів мережі не залежить від моментів часу). Для того щоб за допомогою МП відтворити динаміку системи, треба зазначити моменти часу спрацювання переходів.

 

Розмітка МП

Розмітка М мережі Петрі – це функція, яка ставить у відповідність маркерам вузлів цілі додатні числа. Суть розмітки полягає в приписуванні кожному вузлу певної кількості маркерів. Наприклад, якщо позначити через N – саму мережу Петрі, через Р – множину вузлів у мережі N, через n (Р) – кількість вузлів, то кожному вузлу цієї мережі можна поставити у відповідність число із послідовностей {1,2,…n(Р)}. Таким чином, розмітку M можна зобразити за допомогою вектора n(P) елементів в якому і-ий елемент визначає кількість маркерів у і-му вузлі. У загальному випадку кількість маркерів може бути > 1.

 

 

Рисунок 6.4 – Мережа Петрі, яка може бути заблокованою

 

На рисунку 15.2 зображено МП, яка може перейти, в такий стан, коли жоден з переходів не буде збудженим. Мережа в такому стані називається заблокованою. Розмітка задається так М = [2, 0, 0]; Р = { 1, 2, 3}; n(P) = 3; а,b,c,d – переходи.

Переходи a, b можуть бути збудженими, а переходи c,d – ні. У результаті збудження та спрацювання переходу а отримаємо розмітку m¹=[1, 1, 0], за якою збуджується переходи а, b, c. У разі спрацювання переходу с отримаємо мережу з новою розміткою m² = [2, 0, 0], а якщо b – то [0, 1 ,1] – заблоковано.

У МП паралельне спрацювання переходів обмежується тільки кількістю маркерів у вузлах, тобто для спрацювання переходів мають бути маркери у всіх вхідних вузлах.

Перехід, в якого немає жодного вхідного вузла завжди є збудженим і може генерувати маркери. Перехід, який немає жодної вихідної дуги, і має тільки 1 вхідну дугу збуджений тільки тоді, якщо вхідний вузол містить маркер. Такий перехід може знищувати маркери.