Знакомство с моделью М/М/1

Существует ветвь прикладной математики, предметом которой являются процессы образования очередей. Эта дисциплина так и называется — теория очередей. Мы не будем углубляться в математические основы этой теории, приведем только некоторые ее выводы, существенные для рассматриваемой нами проблемы QoS.

На рис. 7.3 показана наиболее простая модель теории очередей, известная под названием М/М/1^[17].

запросов Очередь Обслуживающее устройство Рис. 7.3. Модель М/М/1

 

Основными элементами модели являются:

□ входной поток абстрактных заявок на обслуживание;

□ буфер;

□ обслуживающее устройство;

□ выходной поток обслуженных заявок.

Заявки поступают на вход буфера в случайные моменты времени. Если в момент поступления заявки буфер пуст и обслуживающее устройство свободно, то заяв­ка сразу же передается в это устройство для обслуживания. Обслуживание так­же длиться случайное время.

Если в момент поступления заявки буфер пуст, но обслуживающее устройство занято обслуживанием ранее поступившей заявки, то заявка ожидает его завер­шения в буфере. Как только обслуживающее устройство завершает обслужива­ние очередной заявки, она передается на выход, а прибор выбирает из буфера следующую заявку (если буфер не пуст). Выходящие из обслуживающего уст­ройства заявки образуют выходной поток. Буфер считается бесконечным, то есть заявки никогда не теряются из-за того, что исчерпана емкость буфера.

Если прибывшая заявка застает буфер не пустым, то она становится в очередь и ожидает обслуживания. Заявки выбираются из очереди в порядке поступле­ния, то есть соблюдается дисциплина обслуживания первым пришел — первым обслужен (First-In, First-Out, FIFO).

Теория очередей позволяет оценить для этой модели среднюю длину очереди и среднея время ожидания заявки в очереди в зависимости от характеристик входного потока и времени обслуживания.

Будем считать, что нам известно, что среднее время между поступлениями зая­вок равно Т. Это значит, что интенсивность поступления заявок, которая тради­ционно обозначается в теории очередей символом X, равна

X = 1/Т заявок в секунду.

Случайный процесс поступления заявок описывается в этой модели функцией распределения интервалов между поступлениями заявок. Для упрощения полу­чения компактных аналитических результатов обычно считают, что эти интерва­лы описываются так называемым марковским распределением (другое назва­ние — пуассоновское), плотность которого показана на рис. 7.4. Из рисунка видно, что входной поток является существенно пульсирующим, так как есть не­нулевая вероятность того, что интервал между заявками будет очень небольшим, близким к нулю, а также того, что он будет очень большим. Среднее отклонение интервалов также равно Т, так что стандартное отклонение равно Т/Т = 1.

Рис. 7.4. Плотность распределения входного потока

 

Будем также считать, что среднее время обслуживания заявки равно Ь. Это озна­чает, что обслуживающий прибор способен продвигать заявки на выход с интен­сивностью 1/Ь = ц. Опять же для получения аналитического результата считают, что время обслуживания — это случайная величина с пуассоновской плотностью распределения.

Принятие таких предположений дает простой результат для среднего времени ожидания заявки в очереди, которое мы обозначим w:

w=p-^-. (1)

1-р

Здесь через р обозначено отношение

Параметр р называют коэффициентом использования (utilization) обслуживаю­щего прибора. Для любого периода времени этот показатель равен отношению времени занятости обслуживающего прибора к величине этого периода.

Зависимость среднего времени ожидания заявки w от р иллюстрирует рис. 7.5. Как видно из поведения кривой, параметр р играет ключевую роль в образова­нии очереди. Если значение р близко к нулю, то и среднее время ожидания очень близко к нулю. А это означает, что заявки почти никогда не ожидают обслужива­ния в буфере (в момент их прихода он оказывается пустым), а сразу попадают в обслуживающее устройство. И наоборот, если р приближается к 1, то время ожи­дания растет очень быстро и нелинейно (и в пределе равно бесконечности). Та­кое поведение очереди интуитивно понятно, ведь р — это отношение средней ин­тенсивности входного потока к средней интенсивности его обслуживания. Чем ближе средние значения интервалов между пакетами к среднему времени обслу­живания, тем сложнее обслуживающему устройству справляться с нагрузкой.

Рис. 7.5. Зависимость среднего времени ожидания заявки от коэффициента использования ресурса