Операційний аналіз мереж систем масового обслуговування

Операційний аналіз стохастичних мереж базується на таких положеннях:

♦ усі припущення щодо властивостей вхідних і вихідних змінних системи можна перевірити шляхом вимірювань впродовж кінцевого проміжку часу пара метрів функціонування реальної системи або її моделі;

♦ у системі повинен існувати баланс потоків вимог: кількість вимог, які залишили систему протягом деякого періоду спостереження, має дорівнювати кількості вимог, що надійшли до системи за цей же період;

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

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

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

Операційні змінні

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

- q_0j — імовірність (частість) надходження зовнішніх вимог до будь-
якого вузла мережі, , де К — загальна кількість вузлів;

- q_kj — імовірність надходження вимог від вузла k до вузла ,

j -

- q_k0 — імовірність того, що після закінчення обслуговування у вузлі kвимоги залишать мережу;

- А_k — кількість вимог, які надійшли до вузла k, k=;

- Ckj — кількість вимог, які залишили вузол k і надійшли до вузла j,

k=; .

- T_k— загальний час обслуговування вимог у вузлі k, k=;

- θ — загальний час спостереження за системою або час моделювання.
Зовнішнє середовище мережі позначимо як вершину з номером 0. Тоді

параметри А_qj C_k0 набуватимуть відповідно значень кількості вимог, які надійшли до вузла j ззовні, та вимог, які залишили вузол k і мережу.

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

Для замкненої мережі виконується умова А₀ = С₀.

Уведені змінні називаються основними операційними змінними. Шляхом найпростіших операцій над ними отримують операційні змінні, що виводяться (наприклад, інтенсивність надходження вимог до вузла kвизначається як λ_k=A_k/θ).

Серед цих операційних змінних найчастіше застосовують

♦ коефіцієнт використання вузла к:

♦ сеpедній час обслуговування у вузлі k:

♦ інтенсивність вихідного потоку вимог віл вузла k:

♦ відносну частість переміщення вимог між вузлами к i j:

(8.4)

Використовуючи вирази (3.1) - (2.9), маємо

Вираз (8.5) — це закон коефіцієнта використання вузла, який виконується за умови, що A_k = C_kпротягом усього періоду спостереження Т(уцьому випадку λ_k = І_k).

Операційні залежності

Основні результати операційного аналізу формуються у вигляді співвідношень між операційними змінними. Ці співвідношення ґрунтуються на гіпотезі про баланс потоків у мережі: кількість вимог, що надійшли до деякого вузла протягом тривалого періоду часу θ, дорівнює кількості вимог, які залишили цей вузол. Ця гіпотеза визначає умови роботи мережі СМО в сталому режимі, тобто вважається, що вимоги завжди залишають вузли мережі, або розглядається досить довгий період часу. Баланс потоків вимог існує тільки для деякого періоду спостереження за системою, але це дуже непогане наближення у разі тривалого періоду часу θ, тому що відношення ( А_k – С_k)/С_k зазвичай незначне.

Гіпотеза про баланс дає змогу визначати залежність між операційними змінними для кожного вузла мережі, а також записати рівняння балансу потоків вимог:

(8.6)

Справедливість виразу (2.11) випливає з припущення про баланс потоків

вимог у мережі, тобто A_j = C_j, бо але за умови, що q_kj =C_kj/C_k знаходимо C _j= Поділивши останнє співвідношення (ліву та праву його частини) на загальний час спостереження Т, отримаємо вираз (8.6). Рівняння (8.6) буде мати єдиний розв'язок для замкненої мережі у разі заданого значення Х₀. Для розімкненої мережі рівняння (8.6) будуть лінійнозалежними, однак і в цьому випадку вони дають корисну інформацію про динаміку потоків мережі.

За допомогою виразу (8.5) знаходимо продуктивність вузла, тобто інтенсивність, з якою вимоги залишають вузол k:

(8.7)

Визначаємо коефіцієнт відвідування вузла kвимогами:

Рівняння балансу потоку можна записати як еквівалентну систему рівнянь в якій замість інтенсивності потоків використовуються коефіцієнти відвідування кожного вузла мережі.

Поділимо ліву і праву частини виразу (8.6) на Х₀:

= 1, (8.9)

Вираз (8.9) справедливий, якщо справедливе рівняння (8.6).

Зв'язок коефіцієнтів відвідування та продуктивності вузла визначаємо за формулою

Обчислимо середній час Г перебування вимог у стохастичній мережі. Позначимо час перебування вимог у окремих вузлах через Г_А. Введемо ще одну операційну змінну Δ_k, яка дорівнює сумарному часу чекання та часу обслуговування вимог у вузлі kпротягом часу θ:

Середній час перебування вимог у системі Г можна знайти через Г_k, і коефіцієнти відвідування окремих вузлів вимогами, тобто

(8.11)

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

Знайдемо середню кількість вимог у мережі N, яка визначається через середню кількість вимог у кожному вузлі n_k,

де n_k— операційна змінна, яку можна отримати з основних операційних змінних:

Для середнього часу перебування вимог у мережі справедливий закон Литтла, тобто середній час перебування вимог у k-му вузлі визначається через середню кількість вимог у ньому та інтенсивність потоку:

Обґрунтувати формулу Литтла можна. також із застосуванням операційного аналізу.

З виразу (8.12) знаходимо

Підставляємо отриману операційну змінну в рівняння (8.10):

Закон Литтла справедливий також для всієї мережі в цілому. Підставивши формули (8.8) і (8.13) у вираз (8.11), отримаємо

(8.14)

Покажемо, як можна використовувати основні співвідношення операційного аналізу для визначення часу перебування вимог у замкненій мережі (рис.8.5).

Рис. 8.5 Замкнена мережа СМО

Нехай є М пристроїв, час обслуговування вимоги кожним із них - Ω. Середній час перебування вимоги в мережі визначаємо за формулою

Вираз (8.15) випливає з таких міркувань. Середній час одного циклу взаємодії, який включає час обслуговування вимоги в зовнішній мережі та перебування в одному з М пристроїв, визначається сумою (Ω+Г). Якщо припустити, що виконується гіпотеза про баланс потоків, то для заданого циклу справедлива формула Литтла. Тому величина М =(Ω+Г)І₀ має визначати середню кількість зайнятих пристроїв або середню кількість працюючих пристроїв для системи з відмовами.

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

Приклад 8.1

Розглянемо замкнену мережу, яка має М= 20 пристроїв. Середній час обслуговування вимоги кожним пристроєм Ω= 25с (рис. 2.19). Для вузлів мережі l, g, n ймовірність переміщення вимог до вузла t становить відповідно: q_lt=0,5; q_gt = 0,7; q_nt = 0,85, а коефіцієнти відвідування цих вузлів — Ψ_t= 12, Ψ_g— 17, Ψ_n= 19. Вузол t завантажений на 50 %, середній час обслуговування вузлом t вимог, які надходять, становить 25 мс. Необхідно знайти середній час перебування Г і середню кількість вимог у мережі N.

Рис. 8.6 Приклад мережі СМО

Визначаємо коефіцієнт відвідування вузла t, використовуючи рівняння балансу потоків вимог (8.9), записані через коефіцієнти відвідування вузлів:

Ψ_t=12×0,5×17×0,7+19×0,85=34,05

Знаходимо інтенсивність I₀ надходження вимог у мережі:

У цей вираз входять відомі з початкових умов операційні змінні: Z_t = 50%
i S_t = 0,025 с. Тоді отримаємо

.

З виразу (8.14) знаходимо середній час перебування вимог у мережі:

Для визначення середньої кількості вимог у мережі скористаємося формулою Литтла:

N = Г І₀

N=9,072×0,587=5,33 вимоги.

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

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

Рис. 8.7 Мережа СМО, яка має замкнену та розімкнену частини

Нехай мережа має 40 пристроїв для обслуговування (М - 40). Середній час обслуговування вимог кожним пристроєм Ω = 15 с. Про мережу відомо такі дані (наприклад, у результаті дослідження реальної обчислювальної системи):

- середній час перебування вимог, які надходять до мережі від 40 пристроїв для обслуговування, дорівнює 5 с; середній час обслуговування будь-якої вимоги у вузлі t становить 40 мс;

- кожна вимога, яка надходить від кожного із М пристроїв для обслуговування, породжує 10 вимог, що надходять до вузла t,

- кожна вимога, яка надходить до системи ззовні, породжує 5 вимог, що надходять до вузла t,

- завантаження вузла t становить 90 %.

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

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

З виразу (8.15) знаходимо

де Г*— середній час перебування вимог, які надійшли до мережі від 40 пристроїв для обслуговування. Тоді І₀= 40/(15 + 5) = 2 вимоги/с.

Інтенсивність потоку вимог до вузла t визначаємо як суму інтенсивностей потоків вимог від пристроїв для обслуговування та інтенсивності потоку зовнішніх вимог, тобто(І*_t +I_t). Тоді, згідно з виразом (8.6), можна записати І*₀ +І_t =Z_t /П_t , або (I*₀ + I_t ) = 0,9/0,44 = 22,5 вимоги/с.

Використовуючи формулу (8.8), знаходимо I_t* =Ψ_t I₀ *; I_t*= 10 × 2 = 20 вимоги/с.

Звідси I_t = 2,5 вимоги/с.

Тепер можна знайти інтенсивність вхідного потоку зовнішніх вимог до мережі:

, вимоги/с.

Припустимо, що початкові умови змінилися та інтенсивність вхідного потоку зовнішніх вимог збільшилася втричі, тобто І₀ = 1,5 вимоги/с. Тоді І_t =Ψ_t І₀= 7,5 вимоги/с. Якщо середній час обробки вимог у вузлі t не змінився, то при завантаженні вузла t на 100 % максимально можлива інтенсивність обслуговування вимог у вузлі t становитиме 1/П_t = 25 вимоги/с. Таким чином, інтенсивність обслуговування вимог у вузлі t (пристроями для обслуговування, які знаходяться у вузлі і) не може перевищувати (25-7,5) = 17,5 вимоги/с.

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

.

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

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