Моделі систем масового обслуговування. Класифікація систем масового обслуговування (стр. 2 из 2)

Мал. 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 існує стаціонарний режим і можна визначити вірогідність того, що в деякий випадковий момент сервер буде вільний, то

.