1 Моделі однолінійних систем масового обслуговування
1.1 Основні поняття і визначення. Дисципліна обслуговування.
В локальних мережах використовують протоколи канального рівняння, які організовують доступ до середовища і ґрунтується на колективному використанні декількома вузлами ресурсів такого середовища, за рахунок розподілу в часі. В цьому випадку, як і в усіх випадках розподілу ресурсів з випадковим потоком запитів, можуть виникати черги.
Прикладом простої схеми (рис. 1.1) з чергою може слугувати сервер, який надає іншим елементам системи деякі послуги. На сервер поступають запити на обслуговування, Якщо сервер вільний від обслуговування, то запит, який поступив у систему обробляється негайно. Інакше запит поміщається у чергу. Коли сервер закінчить обробку запиту, то він покидає чергу. Якщо у цей момент у черзі є неопрацьовані запити, один із них тут же вибирається сервером із черги.
Рисунок 1.1 – Структура черги у системі з одним сервером
Потік заявок, який поступає на обслуговування є випадковим процесом і правильний його математичний опис є одною із основних задач при моделюванні комп’ютерних систем і мереж.
Під процесом обслуговування слід розуміти те, що необхідно затратити деяку кількість роботи, виконати деяку кількість операцій, затратити деякий час на переробку, видозміну та обслуговування деякого об’єкта.
У вхідному потоці,
заявки на обслуговування поступають у
дискретні моменти часу
. Будемо позначати
тривалість часу між моментами поступлення
- го і
-го запитів і
- число моментів
,
які лежать лівіше точки
(
).
Для опису випадкового потоку необхідно
знати спільний розподіл
,
для будь-якого
,
або спільний закон розподілу величин
для всіх
значень
,
.
Якщо розподіл числа запитів, які поступили у систему за певний інтервал часу, залежить лише від довжини цього інтервалу і не залежать від розміщення такого інтервалу на осі часу, то такий потік заявок називається стаціонарним.
Потік називають одинарним, якщо імовірність поступлення однієї заявки за нескінченно малий інтервал часу дорівнює нулю
.
Останню рівність можна трактувати як неможливість одночасного поступлення двох запитів.
Якщо число заявок, які поступили за інтервали часу, що не перетинаються, є незалежними у сукупності випадковими величинами, то говорять, що такий потік є потоком без наслідків.
Випадковий потік
називають потоком
з обмеженими наслідками,
якщо величини
незалежні у сукупності для всіх значень
.
У тому випадку, коли є потік з обмеженими наслідками і величини , однаково розподілені для всіх значень , то такий потік носить назву рекурентного. Рекурентний потік повністю визначений, якщо відома його функція розподілу.
При моделюванні стаціонарних потоків заявок найчастіше використовують такі функції розподілу:
• експоненціальний
розподіл
.
Величина
- інтенсивність стаціонарного потоку,
яка визначається як середнє число
заявок, що поступили у систему за одиницю
часу
,
;
•
гіперекспоненціальний розподіл
.
Параметр
називають порядком
розподілу Ерланга;
•
пуасоновський розподіл
.
Потік заявок, який підпорядкований
пуасоновському закону розподілу,
називають простим.
Такий потік – стаціонарний і без
наслідків. Справедливо наступне
твердження: для того, щоб потік був
простим необхідно і достатньо, щоб він
був стаціонарним пуасоновський. Величина
визначає імовірність прибуття
елементів на протязі кінцевого проміжку
часу
.
Середнє число елементів, які прибувають
за час
-
.
Якщо потік має пуасоновський розподіл,
то проміжки часу між прибуттям пакетів
розподілені за експоненціальним законом.
В опис процесу обслуговування повинні входити і опис правил порядку, у відповідності з яким відбувається обслуговування. Правила обслуговування визначаються дисципліною обслуговування, у відповідності з якою здійснюється вибір заявки (повідомлення) для обслуговування. Розрізняють пріоритетні і без пріоритетні дисципліни обслуговування.
Найпростішою без пріоритетною дисципліною обслуговування є правило, у відповідності з яким першим прийшов — перший обслужений (FCFS — First Come First Served). У відповідності з цим правилом заявка, яка поступила в систему МО, стає в кінець черги, якщо всі прилади зайняті і терміново обслуговується якщо вільний хоча б один прилад.
Прикладом пріоритетних дисциплін є правило “останній прийшов —перший обслужений“ (LCFS — Last Come First Server).