85 находится 1 заявка) для стационарного режима определяются из выражений для вероятностей состояний процесса гибели и размножения, который был рассмотрен в предшествующей теме:
0
p
1
p
Из этих выражений можно определить показатели одноканальной
СМО. В частности, вероятность отказа в обслуживании
отк
p
:
1
отк
p
p
(1) поскольку запрос получает отказ в случае, когда обслуживающий прибор занят, и относительную пропускную способность
q
, которая представляет собой отношение среднего числа обслуженных заявок за единицу времени к среднему числу всех поступивших заявок за тоже время:
0
q
p
(2)
Поскольку
0
p есть вероятность того, что в момент t канал свободен, или вероятность того, что заявка, пришедшая в момент t, будет обслужена.
Зная q легко найти абсолютную пропускная способность А, которая определяется как среднее число заявок, которое может обслужить СМО в единицу времени. Эти показатели связаны очевидным соотношением
A
q
(3)
Вопрос 3. Оптимизация показателей многоканальной СМО с
отказами.
В многоканальной СМО имеется n каналов обслуживания, которые функционируют независимо друг от друга. Очередь отсутствует, т.е., заявки, заставшие все каналы занятыми обслуживанием, получают отказ, и уходят из системы. Входной поток заявок и поток обслуживания
86 заявок являются пуассоновскими. Интенсивность поступления заявок равна
, интенсивность обслуживания
СМО может находиться в следующих состояниях:
S0 - в СМО 0 заявок (все каналы свободны);
S1 - в СМО 1 заявка (один канал занят, остальные свободны);
Sk - в СМО n заявок (k каналов заняты, остальные свободны);
Sn - в СМО n заявок (все каналы заняты).
Рис. 171. ГСП многоканальной СМО с отказами
Если система находится в состоянии S1, то поток, переводящий систему в состояние S0, будет иметь интенсивность μ.
Если система находится в состоянии S2, то поток, переводящий систему в состояние S1, будет иметь интенсивность 2μ. (два канала порождают поток с интенсивностью в два раза большей).
Если система находится в состоянии Sk, то поток, переводящий систему в состояние Sk-1, будет иметь интенсивность kμ. (k каналов порождают поток с интенсивностью в k раз большей).
Процесс, показанный на рис. 17, представляет собой частный случай процесса гибели и размножения.
Уравнения Колмогорова для вероятностей состояний системы P0 ,
P1 , ... , Pn будут иметь следующий вид:
0 0
1 1
1 1
( )
( )
( )
( )
( )
(
)
( )
(
1)
( )
( )
( )
( )
k
k
k
k
n
n
n
dp t
p t
p t
dt
dp t
p
t
k
p t
k
p
t
dt
dp t
p
t
np t
dt
(4)
Предельные вероятности имеют вид
87 2
1 0
0 1
(1
)
1!
2!
!
!
n
k
N
k
P
n
k
0
,
1, ... n
!
k
k
P
P
k
k
(5) где
Соотношения
0
,
1, ... n
!
k
k
P
P
k
k
(5) называются
формулами Эрланга. С их помощью можно найти предельные вероятности в зависимости от значений параметров λ и μ.
Характеристики стационарного режима таковы.
Вероятность отказа. Заявка получает отказ, если все каналы заняты. Вероятность этого равна:
0
!
n
отк
n
P
P
P
n
(6)
Относительная пропускная способность есть вероятностьтого, что заявка будет принята к обслуживаниюи может быть найдена как дополнение
отк
P
до 1:
1
отк
q
P
(7)
Абсолютная пропускная способность находится как
(1
)
n
A
q
P
(8)
Среднее число заявок в системе (среднее число занятых
каналов) можно вычислить через вероятности P0, P1, …, Pk,… Pn, по формуле
0 1
0 1
s
n
n
P
P
n P
(9) как математическое ожидание дискретной случайной величины.
Однако, проще выразить среднее число занятых каналов через абсолютную пропускную способность А, которая уже известна.
Действительно, А есть среднее число заявок, обслуживаемых в единицу
88 времени; один занятый канал обслуживает в среднем μ заявок в единицу времени; среднее число занятых каналов получается делением А на
(1
)
n
s
A
P
n
или, переходя к обозначению
:
(1
)
s
n
n
P
Посмотрим, как может применяться описанная модель для
решения оптимизационной задачи проектирования системы. Пускай нам требуется определить наиболее предпочтительный (в смысле экономического эффекта) вариант многоканальной СМО с отказами.
Для этого необходимо определить число обслуживающих приборов n, при котором достигается максимум функции
,
n
n
n
P
I
C
(10) где
n
P – величина получаемой прибыли;
n
I – получаемый в результате эксплуатации системы доход;
n
C – стоимость эксплуатации приборов (все величины приведены к единице времени).
Будем искать решение при таких предположениях:
средний интервал времени между заявками в потоке (
a
t ) составляет 5 мин;
заявка обрабатывается в среднем 5 мин (
s
t );
затраты на эксплуатацию одного прибора (
C
) составляют
1 рублей/мин;
доход от одной обслуженной заявки ( I ) равен 80 рублей.
Значение функции
( )
I n
находится как произведение величины абсолютной пропускной способности на величину дохода от обслуживания одной заявки:
n
n
I
A I
89
Значение функции
n
C находится как произведение затрат на эксплуатацию одного прибора на число приборов:
n
C
C n
Поэтому, подставляя в
,
n
n
n
P
I
C
(10), получаем
n
n
P
A I
C n
(11)
Сначала определим значение
:
1 / 5 1
1 / 5
мин
мин
Далее по формуле
A
q
(3) находим величину абсолютной пропускной способности для нескольких значений n: n=1:
По формуле
0
q
p
(2) находим q
1 5
0,5 1
1 5
5
q
и по формуле
A
q
(3)
1
A
1 1
1 5
0,5 0,1 1
1 5
5
A
мин
n=2:
По формулам
0
,
1, ... n
!
k
k
P
P
k
k
(5) находим сначала
0
P
90 0
2 1
0, 4 1
1 1
1!
2!
P
затем по формуле
(6)
отк
P
2 1
0, 4 0, 2 2!
отк
P
и по формуле
(1
)
n
A
q
P
(8)
2
A
1 2
1
(1 0, 2)
0,16 5
A
мин
Аналогично получаем: n=3:
0 2
3 1
0,375 1
1 1
1 1!
2!
3!
P
3 1
0,38 0,0625 3!
отк
P
1 2
1
(1 0,0633)
0,1875 5
A
мин
n=4:
0 2
3 4
1 0,3692 1
1 1
1 1
1!
2!
3!
4!
P
4 1
0,3692 0,0154 4!
отк
P
1 2
1
(1 0,0154)
0,1969 5
A
мин
n=5:
91 0
2 3
4 5
1 0,3681 1
1 1
1 1
1 1!
2!
3!
4!
5!
P
5 1
0,3681 0,0031 5!
отк
P
1 2
1
(1 0,0031)
0,1994 5
A
мин
Подставляя найденные значения в
n
n
P
A I
C n
(11) находим:
1 7,0
/
P
руб мин
2 10,8
/
P
руб мин
3 12,0
/
P
руб мин
4 11,75
/
P
руб мин
5 10,95
/
P
руб мин
График зависимости P от n имеет вид:
Рис. 18. Зависимость величины приведенной прибыли от числа приборов
Как видим, максимум прибыли в единицу времени достигается для числа обслуживающих приборов равного трем.
92
Вопрос 4. Обслуживание с очередями.
В системах с ожиданием заявки, заставшие обслуживающий прибор в момент прихода занятым, в отличие от систем с отказами не покидают систему, а остаются ждать в очереди вместе с другими ждущими заявками (рис. 15).
Для описания таких систем используются показатели, характеризующие длину очереди и время ожидания заявками обслуживания. В частности, если временной интервал между появлением заявок распределен по экспоненциальному закону
(пуассоновский поток), то среднее время ожидания заявки в очереди
w
t можно найти по формуле Хинчина-Полачека:
2
(1
)
,
2(1
)
s
s
w
t
c
t
(12) где
s
t — среднее время обслуживания заявки;
σ
s
— среднеквадратическое (стандартное) отклонение времени обслуживания в приборе;
ρ — коэффициент использования прибора
s
a
t
t
;
a
t — средний интервал времени между поступлением заявок;
c
s
— коэффициент вариации времени обслуживания
s
s
t
Число заявок, ожидающих обслуживания (среднюю длина очереди), можно найти, умножив
w
t на величину λ:
2
(1
)
2(1
)
s
s
w
w
t
c
n
t
(13) что, с учетом равенства
w
t
дает
2 2
(1
)
2(1
)
s
w
c
n
(14)
93
Формула Хинчина-Полачека используется для оценивания длин очередей при проектировании информационных систем. Она применяется в случае экспоненциального распределения времени поступления при любом распределении времени обслуживания и любой дисциплине управления, лишь бы выбор очередного сообщения для обслуживания не зависел от времени обслуживания.
При проектировании систем встречаются такие ситуации возникновения очередей, когда дисциплина обслуживания выбирается в зависимости от времени обслуживания. Например, в некоторых случаях для первоочередного обслуживания могут выбираться более короткие сообщения с тем, чтобы получить меньшее среднее время обслуживания
(среднее время пребывания в заявки системе). При управлении линией связи (каналом Интернет) можно присвоить входным сообщениям более высокий приоритет, чем выходным, поскольку первые короче. В таких случаях уже необходимо использовать не уравнение Хинчина —
Поллачека или производные от него, а более сложные уравнения или использовать метод имитационного моделирования, рассматриваемы далее.
Особый интерес для практических применений представляют два случая.
1) Время обслуживания постоянно.
При регулярном характере потока рассеяние отсутствует, поэтому среднеквадратическое отклонение
0
s
, и формулы
(12), (13) преобразуются в выражения
2 2
2
(1
)
2(1
)
2(1
)
s
w
c
n
(15) и
2(1
)
s
w
t
t
(16)
2) Время обслуживания имеет экспоненциальное
распределение.
В случае экспоненциального распределения, как известно, среднеквадратическое отклонение
1
s
, поэтому (12), (13) принимают вид:
2 2
2
(1
)
2(1
)
(1
)
s
w
c
n
(17) и
94
(1
)
s
w
t
t
(18)
Большинство значений времени обслуживания в информационных системах лежит где-то между этими двумя значениями. Времена обслуживания, равные постоянной величине, встречаются редко. Даже время доступа к твердому диску непостоянно из-за различного положения массивов с данными на поверхности. Одним из примеров, иллюстрирующих случай постоянного времени обслуживания может служить занятие линии связи для передачи сообщений фиксированной длины.
С другой стороны, разброс времени обслуживания обычно не так велик, как в случае произвольного или экспоненциального распределения, т.е.,
s
редко достигает значений
s
t . Этот случай иногда считают наихудшим и потому пользуются формулами, относящимися к экспоненциальному распределению времени обслуживания. Такой расчет может дать несколько завышенные размеры очередей и времен ожидания в них, но эта ошибка, по крайней мере, не опасна.
Экспоненциальное распределение времен обслуживания не наихудший случай, с которым приходится иметь дело в действительности. Однако, если времена обслуживания, полученные при расчете очередей, оказываются распределенными хуже, чем времена с экспоненциальным распределением, то его можно рассматривать как предостережение разработчику. Если стандартное отклонение больше среднего значения, то обычно возникает необходимость в коррекции расчетов.
Покажем, каким образом можно использовать формулу (13) для
улучшения характеристик СМО. Пусть имеются шесть типов сообщений, требующих для своего обслуживания соответственно 15, 20,
25, 30, 35, 40 и 300 временных единиц. Число сообщений каждого типа одинаково. Стандартное отклонение указанных времен несколько выше их среднего. Значение последнего времени обслуживания намного больше других. Это приведет к тому, что сообщения будут находиться в очереди значительно дольше, чем, если бы времена обслуживания были одного порядка. В таком случае при проектировании целесообразно принять меры для уменьшения длины очереди. Например, если указанные значения связаны с длинами приходящих сообщений, то, возможно, очень длинные сообщения стоит разделить на части.
Получим количественную оценку системных показателей для первоначального варианта организации информационного обмена и для двух вариантов, в которых длины сообщений передаваемых сообщений выровнены.
Вычислим величины, входящие в формулу для средней длины очереди. Будем считать, что средняя продолжительность для всей
95 группы сообщений составляет 600 временных единиц. Тогда коэффициент загрузки
15 20 25 30 35 40 300 0,775 600
математическое ожидание времени обслуживания
15 20 25 30 35 40 300 66, 43 7
s
t
среднеквадратическое отклонение времени обслуживания
2 2
2 2
2 2
2 2
2 2
[
]
[ ]
(15 20 25 30 35 40 300 ) / 7 66, 43 9155,1 95,68
s
s
s
M T
M T
коэффициент вариации времени обслуживания
95,68 1, 44 66, 43
s
c
Подставляя в (13) получаем средний размер очереди в первоначальном варианте:
2 2
0,775 (1 1, 44 )
4,10 2(1 0,775)
w
n
Вычислим теперь этот показатель для случая, когда последнее сообщение разбивается на два сообщения одинаковой длины. Поступая аналогичным образом, будем иметь (очевидно, что значение ρ остается тем же):
58,13
s
t
53,56
s
0,92
s
c
2 2
0,775 (1 0,92 )
2, 47 2(1 0,92)
w
n
96
Разбивая длинное сообщение теперь уже на три части, получаем для средней длины очереди значение
1,94
w
n
Видим, что прибегая к разбиению длинного сообщения на три сообщения одинаковой длины можно сократить среднюю длину образующейся в системе очереди более чем вдвое.
Помимо моделей теории массового обслуживания для решения задач, связанных с анализом и проектированием информационных систем, структура которых может рассматриваться как СМО, применяются также и имитационные модели, которые рассматриваются далее.
Вопрос 5. Многоканальная СМО сограниченной очередью.
Входящий поток заявок на обслуживание - простейший поток с интенсивностью λ.
Интенсивность потока обслуживания равна μ. Длительность обслуживания – случайная величина, подчиненная показательному закону распределения. Поток обслуживаний является простейшим пуассоновским потоком событий. Размер очереди допускает нахождение в ней m заявок.
СМО может находиться в следующих состояниях:
S0 - в СМО 0 заявок (все каналы свободны, очереди нет);
S1 - в СМО 1 заявка (1 канал занят, очереди нет);
S2 - в СМО 2 заявки (2 канала заняты, очереди нет);
Sk - в СМО k заявок (k каналов заняты, очереди нет);
Sn - в СМО n заявок (n каналов занято, очереди нет);
Sn+1 - в СМО n+1 заявка (n каналов занято, 1 заявка в очереди);
Sn+r - в СМО n+r заявок (n каналов занято, r заявок в очереди);
Sn+m - в СМО n+ m заявок (n каналов занято, m заявок в очереди).
ГСП системы показан на рис. 19. ГСП многоканальной СМО с ограниченной очередью:
S
0
S
1
S
n
S
k
S
n+1
S
n+m
λ
λ
λ
λ
λ
nμ
λ
λ
λ
μ
2μ
kμ
(k+1)
μ
nμ
nμ
nμ
Рис. 19. ГСП многоканальной СМО с ограниченной очередью