Материал: Моделирование, анализ и оценка надежности информационных систем и технологий. Некравцева Т.А., Толстых Т.О
70
Системами массового обслуживания называются математические модели систем, которые предназначены для обслуживания требований (заявок), поступающих через случайные промежутки времени, причем длительность обслуживания в общем случае также случайна. Обобщенная структурная схема СМО приведена на рис 5.1.
Рис. 5.1. Обобщенная структурная схема СМО
Первопричина заявок, какова бы ни была ее физическая природа, называется источником заявок, совокупность заявок всех типов - входящим потоком СМО.
(замкнутая СМО) |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
Прибор1 |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Прибор1 |
|
|
|
|
||
Поток |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|||
заявок на |
|
|
|
|
|
|
Поток об- |
(разомкну-тая |
||
обслуживание |
|
|
|
|
|
|
служенных |
СМО) |
||
|
|
|
|
|
|
|
|
|
заявок |
|
|
Накопитель |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(очередь) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Источник заявок на Прибор1
обслуживание
Поток необслуженных заявок Узел
обслуживания
Узел обслуживания содержит одно или несколько обслуживающих устройств, называемых приборами или каналами обслуживания. Если в момент поступления заявки в систему все приборы заняты, то заявка попадает в накопитель (очередь), где ожидает, пока не освободится какой-либо прибор. Если в накопителе нет свободного места или ожидание оказывается слишком долгим, а заявка имеет ограничение на время ожидания, то заявка покидает систему необслуженной (получает отказ).
Если обслуженные заявки возвращаются в источник заявок и через некоторое время могут вновь появиться во входящем потоке, то СМО называется замкнутой. В разомкнутых СМО поведение источника заявок не связано
71
с состоянием СМО ни в данный, ни в какой-либо из предшествующих моментов времени.
Примеры СМО:
Покупатели |
Продажа товаров |
Продавцы |
|
|
|
Самолеты |
Посадка |
Взлетно-посадочные полосы |
|
|
|
|
|
|
Телефонные вызовы |
Разговор |
Телефонные линии |
|
|
|
Программы пользовате- |
Выполнение |
Центральный процессор, |
лей ЭВМ |
программы |
каналы ввода-вывода |
|
|
|
Предмет теории СМО: построение математических моделей, связывающих заданные условия работы СМО (число каналов, их производительность, правила работы, характеристики потока заявок) с характеристиками СМО, описывающими ее способность справляться с потоком заявок.
Простейший входящий поток заявок
Пусть t1, t2, ..., tn - моменты поступления заявок в систему, 1, 2, ..., n - промежутки времени между моментами поступления заявок , т.е. i=ti-ti-1.
Поток заявок называется простейшим (пуассоновским), если СВ 1, 2,
..., n независимы и одинаково распределены по показательному закону с па-
раметром . Тогда средний промежуток времени |
|
M |
|
1 |
. |
||
ср |
|
||||||
|
|
|
|
i |
|||
Следовательно, |
1 |
, т.е. - среднее число заявок, поступающих за |
|||||
|
|||||||
ср
единицу времени (интенсивность входящего потока). Основные свойства простейшего потока:
1. Стационарность: закон распределения числа заявок, поступивших в промежуток [a, a+t], не зависит от a (начало промежутка), а зависит только от t (длина промежутка).
2. Ординарность: |
lim |
P 1 |
(t) |
, |
t |
0 |
|||
|
t 0 |
|
|
|
|
|
|
|
т.е. вероятность поступления за время t более одной заявки есть бесконечно малая более высокого порядка, чем t (одновременное или за малое время поступление нескольких заявок маловероятно, заявки приходят по одной).
3. Отсутствие последействия: СВ а1(t1) и a2(t2) независимых для любых непересекающихся отрезков [a1, a1+t1] и [a2, a2+t2].
72
Всякий простейший поток обладает свойствами 1-3 и, наоборот, если входящий поток обладает свойствами 1-3, то он простейший.
Марковские случайные процессы
Случайный процесс (t) называется марковским, если его будущее не
зависит |
от |
прошлого, а |
определяется настоящим, |
точнее t1<t2<...<tn<t, |
x1,...,xn |
R и любого измеримого промежутка A числовой оси |
|||
P{ |
(t) |
A/ (t1)=x1, ..., |
(tn-1)=xn-1, (tn)=xn}=P{ (t) |
A/ (tn)=xn}. |
Примерами марковских процессов являются при определенных предположениях процессы функционирования СМО.
Введем обозначения.
Пусть S1, S2, ..., Sn - возможные состояния марковского процесса с дискретным множеством состояний.
Pi(t)=P{ (t)=Si} - вероятность нахождения процесса в момент t в состоянии Si
Pij(t, t+ )=P{ (t+ )=Sj/ (t)=Si} - вероятность перехода из Si в Sj за время [t,t+ ]. Если эти числа не зависят от t, то процесс называется однородным.
|
(t) lim |
Pij (t, t |
) |
при i j - интенсивность перехода из Si |
в Sj в мо- |
ij |
|
|
|||
0 |
|
|
|
|
|
|
|
|
|
|
мент t.
Графом состояний марковского процесса называется схема, составленная из кругов, помеченных именами состояний, и стрелок, проведенных от Si к Sj в случае ij 0, помеченных значением интенсивности перехода ij.
Пример:
|
13 |
|
|
|
12 |
|
|
|
|
|
34 |
S1 |
S2 |
S3 |
S4 |
21 |
|
32 |
|
Теорема 4. Функции Pi(t), i=1, ..., n удовлетворяют системе линейных дифференциальных уравнений А.Н. Колмогорова
d Pi (t) |
ij(t) P j (t) |
ij(t) Pi (t) |
для |
всех |
i=1,...,n |
|
dt |
||||||
i j |
i j |
|
|
|
(5.1)
73
и начальным условиям Pi(0)=Piнач, где Piнач, i=1,...,n - вероятности состояний в начальный момент времени.
Для приведенного примера система дифференциальных уравнений имеет вид
|
d P1 |
|
21 P2 |
|
|
P1 |
|||
|
dt |
12 |
13 |
||||||
|
|
|
|
|
|
|
|||
d P2 |
|
|
P1 |
32 P3 |
|
21 P2 |
|||
|
dt |
12 |
|
||||||
|
|
|
|
|
|
|
|||
|
d P3 |
|
|
|
P1 |
|
|
P3 |
|
|
dt |
13 |
32 |
34 |
|||||
|
|
|
|
|
|
|
|||
|
d P4 |
|
|
P3 |
|
|
|
||
|
dt |
34 |
|
|
|
||||
|
|
|
|
|
|
|
|||
Если процесс определенно в начальный момент находится в состоянии
S1, то P1(0)=1, P2(0)=P3(0)=P4(0)=0 - начальные условия.
Замечание. Первая группа слагаемых в формуле (5.1) соответствует стрелкам, направленным к кругу, изображающему состояние Si, а вторая группа - стрелкам, выходящим из этого круга.
Простейший поток как пример марковского процесса
Пусть (t) - число заявок, поступивших за время [0,t] в простейшем потоке с интенсивностью .
Случайный процесс (t) является марковским, поскольку простейший поток обладает свойством отсутствия последействия. Его возможные значения 0, 1, 2, ... обозначим через S0, S1, S2, ... . В данном случае вероятность перехода Pij(t,t+ ) равна нулю при i>j и совпадает с вероятностью поступления k=j-i заявок за промежуток длины при i j.
По формуле Пуассона
|
|
k |
|
Pi,i k t, t |
|
|
e |
k! |
|
||
|
|
|
|
Отсюда из формулы, определяющей ij, следует, что i,i+k=0 при k>1, i,i+1= . Таким образом, граф состояний простейшего потока имеет вид
|
|
… |
… |
S1 |
S2 |
S3 |
Sn |
74
Соответствующая система дифференциальных уравнений А.Н. Колмогорова
Характеристики накопителя заявок и узла обслуживания
1. Предельно допустимая длина очереди m.
Если m = 0, то говорят, что СМО с потерями (отказами), m = , то СМО с ожиданием,
0 < m < , то СМО с ограничением на длину очереди.
2.Дисциплина ожидания в очереди определяет правила управления очередью. Возможны следующие бесприоритетные дисциплины ожидания:
а) Заявки принимаются в очередь в порядке их поступлений Если в момент прихода очередной заявки очередь заполнена, то заявка получает отказ, т.е. теряется системой.
б) То же, что и в предыдущем случае, только при переполнении очереди последняя заявка вытесняет из очереди самую «старую» заявку, т.е. дольше всех находящуюся в очереди.
Если по каким-либо причинам заявки некоторых типов должны обслуживаться СМО быстрее, то заявкам приписывается некоторое положительное число, называемое приоритетом. Одна из возможных приоритетных дисциплин ожидания:
в) Заявки принимаются в очередь в порядке их поступления, при переполнении очереди вновь поступившая заявка выталкивает из очереди заявку
оболее низким приоритетом (самую старую из самых низкоприоритетных). Если очередь заполнена более приоритетными заявками, то вновь поступившая заявки получает отказ.
3.Число каналов обслуживания n.