Системи масового обслуговування

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

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

Системи й процеси масового обслуговування мають такі загальні властивості:

- масовість обслуговування, тобто одночасне здійснення безлічі окремих ситуацій обслуговування;

- випадковий характер надходження вимог на обслуговування – із цієї причини їх можна описати лише на основі ймовірнісного підходу;

- заздалегідь невідомий зміст вимог;

- випадковий характер часу обслуговування вимоги.

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

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

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

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

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

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

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

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

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

Загальну структуру системи масового обслуговування наведено на рис. 4.

Рис. 4 Загальна структурна схема системи масового обслуговування

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

Якщо сигнали обслуговування в багатоканальній системі обслуговування однотипні, то таку систему називають однорідною (наприклад, метрополітен), у противному випадку – неоднорідною (наприклад, аеропорт).

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

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

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

- кожний канал обслуговує кілька вимог одночасно;

- та сама вимога обслуговується групою каналів.

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

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

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

Цю класифікацію можна розширити, якщо під час дослідження систем розглядати й вводити нові властивості.

У класичному випадку системи масового обслуговування прийнято поділяти на класи за допомогою позначень, що мають таку структуру:

, (5)

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

Рис. 5. Класифікація систем масового обслуговування

Стандартними позначеннями для типів розподілу вхідного й вихідного потоків (символи а і b) є такі:

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

D – детермінований (фіксований) інтервал часу між моментами послідовних надходжень у систему вимог, або детермінована тривалість обслуговування вимог;

Е_k – розподіл Ерланга (гамма-розподіл із цілочисловим параметром K) інтервалів часу (або розподіл суми незалежних випадкових величин, що мають експонентний розподіл);

GI – довільний (загальний) тип розподілу моментів надходження вимог на обслуговування;

G – довільний тип розподілу тривалості обслуговування вимог.

Для позначення дисципліни черги (символ d) використовують такі позначення:

FCFS – першим прийшов – першим обслужився;

LCFS – останнім прийшов – першим обслужився;

SIRO – випадковий відбір вимог;

GD – довільний тип дисципліни.

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