Главная > Разное > Теоретические основы проектирования компьютерных сетей
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

1.5 Однолинейные марковские системы массового обслуживания

Наиболее хорошо исследованными являются однолинейные системы массового обслуживания с простейшим входящим потоком или показательным распределением времени обслуживания. Это объясняется тем, что процессы, которые в первую очередь интересуют исследователей, а именно: число запросов в системе в момент t, время ожидания запроса, который поступит (или может поступить) в момент времени t и др., являются одномерными и, кроме того, либо являются марковскими, либо легко подвергаются марковизации за счет рассмотрения их только во вложенные моменты времени или расширения фазового пространства процесса.

1.5.1 Система типа М\М\1

Рассмотрим систему М\М\1, то есть, однолинейную СМО с ожиданием (буфером неограниченной емкости), в которую поступает простейший поток запросов интенсивности , а время обслуживания запросов имеет показательное распределение с параметром .

Анализируя поведение этой системы, мы легко устанавливаем, что процесс - число запросов в системе в момент t - является процессом гибели и размножения с параметрами:

Поэтому для него справедливы Утверждения 8 и 9. При этом в формулировках этих утверждений мы должны задать параметры как: . Таким образом, величина в формулировке. Утверждения 9 определяется как где .

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

Проверяя условие существования стационарного распределения процесса данное в формулировке Утверждения 9, мы легко убеждаемся, что стационарное распределение числа запросов в рассматриваемой системе существует, если выполняется условие:

Будем далее считать это условие выполненным.

Отметим, что для большинства однолинейных систем массового обслуживания условие существования стационарного распределения числа запросов в системе также имеет вид (1.20), что хорошо согласуется с интуитивными соображениями: для того, чтобы в системе не накапливалась бесконечная очередь, необходимо, чтобы в среднем запросы в системе обслуживались быстрее, чем они туда поступают.

Итак, мы можем сформулировать следующее следствие Утверждения 9.

Утверждение 10. Стационарное распределение числа запросов в системе М\М\1 определяется следующим образом:

Отсюда следует, что вероятность того, что в произвольный момент времени система простаивает, равна , а среднее число L запросов в системе определяется формулой

Средняя длина очереди определяется формулой:

В ситуациях, когда распределение интервалов во входящем потоке и распределение времени обслуживания неизвестны, а известны только их средние значения, формулы (1.22) и (1.23) иногда используют для (грубой) оценки среднего числа запросов в системе и средней длины очереди в произвольный момент времени.

Как отмечалось выше, интересной характеристикой СМО является также распределение времени ожидания (то есть, времени с момента поступления в систему до момента начала обслуживания) запроса, поступившего в момент

Обозначим стационарное распределение процесса

Предполагаем, что запросы обслуживаются в порядке их поступления в систему. Иногда такая дисциплина выбора из очереди для краткости кодируется как FIFO (First In - First Out — первым пришел - первым обслужен) или, что означает то же самое, FCFS (First Came - First Served).

Утверждение 11. Стационарное распределение времени ожидания запроса в системе М\М\1 определяется следующим образом:

Доказательство. Время ожидания начала обслуживания произвольным запросом зависит от числа запросов, присутствующих в системе в момент его прихода. Для данной системы М\М\1 распределение числа запросов в системе в произвольный момент поступления запроса и в произвольный момент времени совпадают и задаются формулой (1.21). Запрос, заставший систему свободной (вероятность этого есть ), имеет нулевое время ожидания.

Запрос, заставший в системе i запросов (вероятность этого есть ) ждет в течение времени, имеющего эрланговское распределение с параметрами Последний факт следует из того, что, во-первых, в силу свойства отсутствия последействия у показательного распределения оставшееся к моменту прихода время обслуживания обслуживаемого запроса имеет то же показательное распределение с параметром что и полное время обслуживания, а во-вторых, в силу того, что сумма независимых показательно распределенных с параметром случайных величин есть эрланговская случайная величина с параметрами

Из приведенных рассуждений и (1.21) следует, что:

Отсюда непосредственно следует (1.24). Утверждение 11 доказано.

Среднее время ожидания W запроса в системе вычисляется следующим образом:

Среднее время V пребывания запроса в системе (то есть, времени с момента поступления в систему до момента окончания обслуживания на приборе) задается формулой:

Сравнивая выражение (1.25) для среднего времени ожидания W и формулу (1.23) для средней длины очереди в системе, а также формулу (1.26) для среднего времени V пребывания запросов с формулой (1.22) для среднего числа L запросов в системе, видим, что:

Отметим, что эти формулы справедливы и для многих более общих, чем рассматриваемая система М\М\1, систем массового обслуживания и называются формулами Литтла.

Практическая значимость этих формул состоит в том, что они избавляют от необходимости непосредственного вычисления величин W, V при известном значении величин и наоборот.

<< Предыдущий параграф Следующий параграф >>
Оглавление