Материал: Московский финансовопромышленный университет Синергия Кафедра Информационных систем и технологий

97
ГСП есть схема процесса размножения и гибели, для него можно использовать общее решение для предельных вероятностей.
0,
1, 2 ...
!
k
k
P
P k
n
k



0,
1, 2 ...
!
n i
n i
i
P
P i
m
n n





1 2
1 2
0 2
1 1!
2!
!
!
!
!
n
n
n
n m
m
P
n
nn
n n
n n
 










  



 





1 1
2 1
1!
2!
!
!
1
m
n
n
n
n
n
n
n


 







 



 
 


  
 








(19) где




(использовано выражение для суммы геометрической прогрессии со знаменателем
n

).
Вероятность отказа в обслуживании заявки.
Отказ произойдет в случае, если все n каналов заняты и в очереди находятся m заявок: n+m
0
!
n m
отк
m
P
P
P
n n




(20)
Относительная пропускная способность:
0 1
1
!
n m
отк
m
q
P
P
n n


 
 
Абсолютная пропускная способность:
0 1
!
n m
m
A
P
n n











Среднее число занятых каналов.

98
Для СМО с очередью среднее число занятых каналов не совпадает
- в отличие от СМО с отказами - со средним числом заявок в системе.
Отличие равно числу заявок, ожидающих в очереди.
Каждый занятый канал обслуживает в среднем μ заявок в единицу времени, а СМО в целом – А заявок в единицу времени. Разделив А на μ получим
0 0
1 1
!
!
n m
n m
s
m
m
A
n
P
P
n n
n n




 



















Среднее число находящихся в очереди заявок.
Найдем среднее число ожидающих в очереди заявок:


1 2
1 2
0 0
0 2
2 1
1 1
2 1
0 0
1 2
1 2
!
!
!
1 2 3
1 2 3
!
!
n
n
n m
w
n
n
n m
m
m
n
n
m
n
P
P
m P
P
P
m
P
nn
n n
n n
P
m
P
m
nn
n
n
n
nn





















 
 
  


 



 
 



 



 


 
 


 
 


(21) где

=
n

Выражение в скобках можно трактовать (как и ранее) как производную по ρ от суммы геометрической прогрессии и получить выражение:
1 0
2 1
(
1
)
!
(1
)
n
m
w
P
m
m
n
nn






 


(22) которым можно пользоваться во всех случаях кроме

=0.
Среднее число находящихся в системе заявок.
Поскольку среднее число находящихся в системе заявок
n

w
s
n
n
n



Среднее время ожидания заявки в очереди.
Рассмотрим возможные ситуации, в которых пришедшая заявка может застать СМО.
Если заявка приходит в систему в какой-то момент времени и какой-то канал не занят, то она не будет ждать в очереди.

99
Если заявка приходит в систему в момент, когда заняты все каналы, а очереди нет, то она будет ждать в очереди в среднем 1/nμ
(поток освобождения n каналов имеет интенсивность nμ).
Если заявка приходит в систему в момент, когда заняты все каналы, а в очереди одну заявку, то она будет ждать в очереди в среднем
2/nμ (по 1/nμ на каждую впередистоящую заявку).
Если заявка приходит в систему в момент, когда заняты все каналы, а в очереди стоят k заявок, то она будет ждать в очереди в среднем k/nμ.
Если заявка приходит в систему в момент, когда заняты все каналы, а в очереди стоят m заявок, то она не будет ждать, так как покинет систему.
Среднее время ожидания определим из выражения
1 1
1 1
0 0
0 1
2 1
0 1
2 1
2
!
!
!
1 2 3
!
n
n
n m
w
n
n
n m
m
m
n
m
t
P
P
P
P
P
m
P
n
n
n
n
n
nn
n
n
P
m
n n
n
n
n













 

 










 







 
 



 


 
 


 
 


(23)
Это выражение отличается от выражения для средней длины очереди только множителем 1/ρμ=λ, откуда
1
w
w
w
n
t
n




т.е., результат, вытекающий из формулы Литтла, или
0 2
1
(
1
)
!
(1
)
n
m
w
P
m
m
t
n n






 


(24)
Среднее время пребывания заявки в системе.
Так же как и в случае с одноканальной СМО имеем:
w
w
s
n
q
t
t
t



  

(25)
Пример 0-1.
В парикмахерской работают 3 мастера, для очереди
посетителямив в зале ожидания предусмотрены 3 места. Клиенты
приходят в среднем один раз в 4 минуты, обслуживание длится в
среднем 15 мин. Требуется определить относительную и абсолютную
пропускные способности парикмахерской, среднее число клиентов,

100
ждущих обслуживани,я, и среднее время нахождения клиента в
парикмахерской.
Решение:
Имеем:
n=3,
m=3,

=1/4=0,25,

=1/15,
ρ =15/4=3,75,
χ=ρ /n=1,25.
Находим
0
P :
1 3 1 2
3 3
0 3,75 3,75 3,75 3,75 3,75 3,75 3
3 1
0,016 3,75 1!
2!
3!
3!
1 3
P















 











и вероятность отказа в обслуживании.
3 3 0
3 3,75 0,275 3 3!
отк
P
P




Относительная пропускная способность парикмахерской:
1 1 0,275 0,725
отк
q
P
 
 

Абсолютная пропускная способность:
1 0,25 0,725 0,181
A
q
мин


  


Среднюю длину очереди находим на основе формулы
0 2
1
(
1
)
!
(1
)
n
m
w
P
m
m
t
n n






 


(24):
3 1 3
0 2
3,75 1 1, 25 (3 1 3 1, 25)
1, 440 3 3!
(1 1, 25)
w
P
n


  





101
Среднее время нахождения клиента в парикмахерской
определяется с помощью
w
w
s
n
q
t
t
t



  

(25):
1, 440 0,725 16,64 0, 25 1 / 15
t
мин




Выводы:
1. Многие задачи анализа и проектирования можно решить с использованием моделей систем массового обслуживания. Это дает возможность применять модели теории с тем же названием, многие из моделей которой получены на основе теории марковских процессов.
2. Основными показателям моделей систем с отказами являются относительная и абсолютная пропускная способность, а также вероятность отказа в обслуживании. Эти показатели для стационарного режима могут быть найдены на основе математических выражений.
3. Важными показателями для системы с ожиданием являются показатели, характеризующие нахождение заявок в очереди. Анализ таких систем может производиться в случае пуассоновского входящего потока на основе формулы Хинчина-Полачека.
4. Модели СМО можно применять для решения разнообразных практических задач. В частности, на примерах данной темы показано, как с помощью модели многоканальной СМО отказами можно решить задачу оптимизации числа каналов по критерию величины прибыли, а с помощью модели СМО с очередью определить требования к размерам заявок для уменьшения размера очереди и связанного с ней размера буферного накопителя.
Вопросы для самопроверки:
1. Приведите примеры СМО с отказами.
2. Дайте краткое описание модели СМО с отказами.
3. Как получаются выражения для характеристик СМО с отказами?
4. Что такое относительная пропускная способность СМО с отказами?
5. Что такое абсолютная пропускная способность?
6. Как рассчитывается вероятность
0
p одноканальной СМО?
7. Как рассчитывается вероятность
1
p одноканальной СМО?
8. Чему равна вероятность отказа обслуживания заявки в многоканальной СМО с отказами?
9. Как подсчитывается среднее число заявок в многоканальной системе с отказами?

102 10. Как можно определить структуру (число каналов) многоканальной СМО по критерию максимума получаемой прибыли?
11. Какими показателями характеризуется функционирование одноканальной СМО с неограниченной очередью?
12. Что такое дисциплина обслуживания? Назовите примеры наиболее известных дисциплин.
13. Что позволяет определить формула Хинчина-Полачека? Для каких случаев справедлива формула?
14. Какие распределения времени обслуживания в одноканальной
СМО с неограниченной очередью представляют наибольший интерес для практики? Опишите эти случаи.
15. Какие основные факторы влияют на значения показателей одноканальной СМО с неограниченной очередью?
16. Каким образом можно улучшить характеристики функционирования одноканальной СМО с неограниченной очередью?
Литература по теме:
1. Емельянов А.А. Модели процессов массового обслуживания //
Прикладная информатика, 2008, № 5 (17), с. 92-130.
2. Емельянов А.А. Стохастические сетевые модели массового обслуживания // Прикладная информатика, 2009, № 5 (23), с. 103-111.
Практические задания:
Задание 1.
Рассчитайте значения показателей
отк
p
, q, A одноканальной системы с отказами, для которой
7
поступления
Т
с

,
5
обслуживания
Т
с

Ответ:
0,416;q
0,584;A
0,0834
отк
p



Задание 2.
На вход системы из четырех серверов, поступает входящий поток с интенсивностью 6 запросов в минуту. Один сервер тратит на обслуживание 20с. В случае занятости всех серверов заявка получает отказ. Руководство ИТ-отдела планирует заменить четыре сервера на один с четырехкратной производительностью. Как это отразится на показателях системы?
Ответ: Вариант 1:
0,111; q
0,889; A
5, 33
отк
p



Вариант 2:
0,333;q
0,667;A
2,0
отк
p



Задание 3.
К базе данных сервера онлайновой продажи авиабилетов поступает в период пиковой нагрузки в течение минуты в среднем 5 запросов на поиск информации о рейсах и ценах на билеты. Время обработки каждого запроса составляет 10 секунд. Запрос, поступивший

103 в момент обработки одного из ранее поступивших запросов, ставится в очередь. Считая время обслуживания постоянным, а поток запросов пуассновским определить среднюю длину очереди и среднее время ожидания запросом обслуживания.
Ответ:
2,08
оч
n

;
25
ож
t
c

Тесты для самопроверки:
1. Относительная пропускная способность системы массового обслуживания с отказами означает … . а) реальную эффективность системы по сравнению с максимально возможной б) долю обслуженных заявок из общего числа приходящих в систему в) число обслуженных заявок за некоторый период наблюдения г) число обслуженных заявок за единицу времени
2. Граф состояний и переходов одноканальной системы массового обслуживания с отказами содержит … узлов. а) 1 б) 2 в) 3 г) 4 3. Формула Хинчина-Полачека позволяет найти … . а) реднее число занятых каналов обслуживания б) интенсивность выходящего потока в) реднюю длину очереди заявок г) приоритетность обслуживания заявок
4. Система массового обслуживания с очередью характеризуется такими показателями как … . а) среднее время ожидания заявки б) средняя длина очереди в) относительная пропускная способность г) абсолютная пропускная способность

104

105
Рассмотрение имитационных моделей начнем с метода статистических испытаний.
Статистическое моделирование является разновидностью имитационного моделирования и состоит в обработке данных о системе
(модели) с целью получения статистических характеристик системы.
Чаще всего оно применяется как способ исследования процессов поведения систем в условиях, когда внутренние взаимодействия в системах неизвестны, и построение аналитической модели явления затруднено или вовсе неосуществимо. Метод может применяться и на этапе системного анализа информационных систем, но основными для его применения являются задачи исследования операций, массового обслуживания и многие другие, связанные со случайными процессами.
Эти задачи возникают в основном на этапах системного проектирования и разработки.
Смысл метода Монте-Карло состоит в том, что исследуемый процесс моделируется путем многократных повторений его случайных реализаций (рис. 20).
Рис. 20. Блок-схема метода Монте-Карло
Единичные реализации называются
статистическими
испытаниями, в силу чего метод называется также методом статистических испытаний.
Пусть, например, нам требуется найти значение числа π.
Изобразим на декартовой плоскости две фигуры – квадрат и сектор круга, как это показано рис. 21: