Мал. 2. Діаграма интенсивностей переходів для процесу розмноження і загибелі
Овалам тут відповідають дискретні стани, а стрілки визначають інтенсивності потоків вірогідності (а не вірогідність!) переходів від одного стану до іншого.
Має місце своєрідний «закон збереження»:
Різниця між сумою интенсивностей, з якою система потрапляє в стан до і сумою интенсивностей, з якою система покидає цей стан повинна дорівнювати інтенсивності зміни потоку в цей стан (похідної за часом).
Застосування закону збереження дозволяє одержувати рівняння для будь-якої підсистеми Марківського ланцюга типу процесу «загибелі-розмноження. Особливо ефективною виявляється побудова рішень в стаціонарному, сталому режимі, коли можна вважати що вірогідність в довільний, достатньо віддалений момент часу, залишаються постійними.
Прирівнюючи похідну за часом нулю, одержуємо систему різницевих рівнянь
Вважаючи, що інтенсивності л‑1 =л-2 = л‑3=.0; м0 = м‑1 = м‑2 = м‑3=.=0, друге рівняння виписувати не буде окремо далі потрібно. Отже, стаціонарний режим в ланцюзі Маркова описуватиметься системою різницевих рівнянь і умовою нормування для вірогідності
Неважко бачити, що ці рівняння легко виводяться із закону збереження интенсивностей вірогідності. В стаціонарному режимі різниця потоків рівна нулю і отримані вище рівняння придбавають значення рівнянь рівноваги або балансу, як їх і називають.
.Інтенсивність потоку вірогідності в стан до рівна інтенсивності потоку з цього стану.
Вирішувати рівняння балансу можна, спочатку визначивши при до =0 значення
.Потім, побудувавши систему рівнянь для до =1, можна отримати
.Далі одержуємо
З умови нормування:
.Система, описувана отриманими вище виразами, матиме стаціонарну вірогідність станів, коли вона ергодична. Ця умова може бути виражений через співвідношення интенсивностей. Необхідно і достатньо, щоб існувало деяке значення до, починаючи з яким виконувалася нерівність
.Для більшості реальних систем масового обслуговування ця нерівність виконується.
Класифікація систем масового обслуговування
Використовується трьох -, чотирьох -, шести – компонентне символічне позначення системи масового обслуговування, запропоноване Кендаллом (Candall) і розвинуте в роботах Г.П. Барашина.
а/b/c:d/e/f
а – розподіл потоку запитів, що поступає.
b – закон розподілу часу обслуговування.
Типові умовні позначення:
М – експоненціальний (Марківське) розподіл
D – детермінований розподіл
Тіньк– ерланговський розподіл к-гопорядку
HMk– гиперекспониціональне
HEk– гиперерлангівське розподіл порядку до
GI – довільний розподіл незалежних проміжків між заявками
G – довільний розподіл тривалостей обслуговування.
з – структура системи обслуговування (звичайно число серверів).
d – дисципліна обслуговування (параметри після двокрапки іноді опускають).
Звичайно використовується скорочене символічне позначення, наприклад FF замість FIFO, LF, PR і т. п.
e – максимальне число запитів, сприймане системою, може вживатися символ ¥.
f – максимальне число запитів до системи обслуговування.
В деяких публікаціях останніми символами відображають якісні характеристики системи обслуговування. Деякі загальні результати і основи математичного апарату, необхідного для аналізу можна отримати, розглядаючи системи G/G/m.
Формула Літтла (Little)
Розглянемо тимчасову діаграму роботи системи масового обслуговування (мал. 3), відобразити на ній послідовність надходження вимог, приміщення вимог в чергу і обробки серверами системи.
Тимчасова діаграма роботи системи масового обслуговування.
В загальному випадку ясно, що із збільшенням числа вимог росте час очікування. Встановимо співвідношення між середнім числом вимог в системі, інтенсивністю потоку і середнього часу перебування в системі. Позначимо число поступають в проміжку часу (0, t) вимог як функцію часу б(t).
Число витікаючих з системи заявок (обслужених) на цьому інтервалі позначимо д(t). На малюнку 4 показані приклади функціональної залежності цих двох випадкових процесів від часу.
Мал. 4. Залежність між середнім числом вимог в системі, інтенсивністю потоку і середнім часу перебування в системі
Число вимог, що знаходяться в системі у момент t буде рівний:
.Площа між двома даними кривими від 0 до t – дає загальний час, проведений всіма заявками в системі за час t.
Позначимо цю накопичену величину г(t). Якщо інтенсивність вхідного потоку рівна л, а середня інтенсивність за час t:
, той час, проведений однією заявкою в системі, усереднене по всіх заявках буде рівне: .Нарешті, визначимо середнє число вимог в системі в проміжку (0, t):
.З останніх трьох рівнянь виходить, що:
(де ).Якщо в СМО існує стаціонарний режим, то при t>?, матимуть місце співвідношення:
Останнє співвідношення означає, що середнє число заявок в системі рівно твору інтенсивності надходження вимог в систему на середній час перебування в системі. При цьому не накладається ніяких обмежень на розподіли вхідного потоку і часу обслуговування. Вперше доказ цього факту дав Дж. Литтл і це співвідношення носить назву формула Літтла.
Цікаво, що як СМО можна розглянути тільки чергу із заявок в буфері. Тоді формула Літтла придбаває інше значення – середня довжина черги рівна твору інтенсивності вхідного потоку заявок на середній час очікування в черзі:
.Якщо навпаки розглядати СМО тільки як сервери, то формула Літтла дає:
,де
– середнє число заявок в серверах, а – середній час обробки в сервері.У будь-якому випадку:
.Одним з основних параметрів, які використовуються при описі СМО, є коефіцієнт використовування (utilization factor). Це фундаментальний параметр, оскільки він визначається як відношення інтенсивності вхідного потоку до пропускної спроможності системи. Оскільки пропускна спроможність СМО містить m серверів може бути визначений як:
, то коефіцієнт використовування може бути визначений як .Неважко бачити, що коефіцієнт використовування рівний в точності інтенсивності навантаження, якщо СМО з одним сервером і в m раз менше для систем з m серверами. Величина коефіцієнта використовування рівна середньому значенню від частки зайнятих серверів і
.Якщо в СМО типа G/G/1 існує стаціонарний режим і можна визначити вірогідність того, що в деякий випадковий момент сервер буде вільний, то
.