Имитационное моделирование в исследовании и разработке информационных систем Лекция 6 Элементы теории систем массового обслуживания. - презентация

1 Имитационное моделирование в исследовании и разработке информационных систем Лекция 6 Элементы теории систем массового обслуживания

2 Системы массового обслуживания (или системы с очередями – queuing systems) Часто применяемые на практике модели Аналитическое и имитационное моделирование 2

3 Система с очередями: основные элементы Входящий поток заявок Прибор(ы) обслуживания; время обслуживания Очередь заявок; длина; дисциплина обслуживания A|B|s|q (пример: M|M|1|) ([1], с.30) [2], c. 14 A – закон распределения вх. заявок B – закон распред. времени обслуживания s – число обслуживающих приборов q – максимальная длина очереди 3

4 Пример (1) web-сервер 4

5 5

6 Характеристики производительности Средняя длина очереди Среднее время пребывания заявки в системе (или в очереди) Характеристики выходного потока (обслуженных заявок или отказов в обслуживании) 6

7 Входящий поток Z k – интервал между событиями (заявкоми) λ(t) – количество событий к моменту t 7

8 Формула Литтла (связь между х-коми произвести) L = aV L – среднее число заявок в системе a – интенсивность поступления заявок V – среднее время пребывания заявки в системе N = aW N – средняя длина очереди W – среднее время пребывания в очереди 8

9 Пуассоновский поток P(z a – интенсивность 9 распределение Пуассона λ(a1,t)+λ(a2,t) ~ λ(a1+a2,t) просеивание λ(a,t) с вероятностью z ~ λ(za,t)

10 Сведение к марковским процессам (1) Состояние – число заявок в системе Диаграмма переходов состояний Дифф. ур-я для состояний Условия наличия предельного распределения вероятностей состояний Переход к алгебраическим ур-ям для предельных вероятностей для состояний. Расчёт характеристик системы 10

11 M|M|1| ρ = λ/μ Вероятность, что в системе k заявок: P(k) = (1- ρ) ρ k Среднее число заявок в системе: ρ/(1- ρ) Средняя длина очереди: ρ 2 /(1- ρ) Загрузка обслуживающего прибора ρ 11

12 Сведение к марковским процессам (2) Цепь Маркова с непрерывным временем 12

13 M|M|1|K Согласно [2]: P 0 = (1- ρ)(1- ρ K +1) или 1/(K+1) Загрузка прибора U s = 1- P 0 Среднее число заявок ρ(1-(K+1)ρ K +Kρ K+1 )/((1- ρ)(1- ρ K+1 )) K/2, если ρ=1 13

14 Имитационное моделирование СМО При многократных экспериментах – не переинициализировать датчик сл.в.! Для оценки установившегося режима – отбрасывание начальных наблюдений см. [3], п

15 Литература 1. Матвеев В., Ушаков. Системы массового обслуживания // М.: Изд-во МГУ. – – 240 с. 2. Dr. János Sztrik. Basic Queueing Theory. University of Debrecen, Faculty of Informatics. // [Электронный ресурс] on/16/SOR_Main_Angol.pdf 3. [Лоу, Кельтон]

16 16 Спасибо за внимание!