Теория массового обслуживания (англоязычное название - queue-ing theory - теория очередей) возникла в начале 20 века. Ее основоположником считается датский ученый А.К. Эрланг, работавший в шведской телефонной компании и занимавшийся вопросами проектирования телефонных сетей. В дальнейшем теория получила интенсивное развитие и применение в различных областях науки, техники, экономики, производства. Это объясняется тем, что эта теория изучает широко распространенные в человеческой практике ситуации, когда имеется некоторый ограниченный ресурс и множество (поток) запросов на его использование, следствием чего являются задержки или отказы в обслуживании некоторых запросов. Стремление понять объективные причины этих задержек или отказов и по возможности уменьшить их воздействие является побудительным мотивом развития теории массового обслуживания.

Как правило, поступление запросов (или их групп) происходит в случайные моменты времени и для их удовлетворения требуется случайная часть ограниченного ресурса (или случайное время его использования). Поэтому изучение процесса удовлетворения потребности в ресурсе (процесса обслуживания) обычно проводится в рамках теории случайных процессов как специальной области теории вероятностей. Иногда исследование процесса обслуживания требует применения достаточно тонких математических методов и серьезного математического аппарата. Это делает полученные результаты практически недоступными инженеру, потенциально заинтересованному

2 - 7659

в их применении к исследованию реального объекта. Что, в свою очередь, лишает автора математического результата обратной связи , важной для правильного выбора направления для дальнейшего обобш,ения результатов и объектов исследования. Эта серьезная проблема подмечена в обзоре [273] известного специалиста Р.Сиски, от-мечаюш,его опасность возможности распада единой теории массового обслуживания на абстрактную и инженерную. Прямым следствием этой проблемы при написании книги обычно является вопрос выбора языка и соответствующего уровня строгости изложения результатов. Данная книга ориентирована как на специалистов в области теории массового обслуживания, так и на специалистов в области ее приложения к исследованию реальных объектов (в первую очередь, компьютерных сетей). Поэтому в данной главе приведем краткий обзор методов анализа систем массового обслуживания на среднем уровне строгости. Предполагается знакомство читателя с теорией вероятностей в рамках курса для технического вуза. При необходимости, некоторые сведения приводятся непосредственно в тексте.

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

входящий поток запросов (заявок, требований, сообщений, вызовов);

количество и типы обслуживающих устройств (приборов);

емкости накопителей (буферов), где запросы, заставшие все приборы занятыми, ожидают начала обслуживания;

времена обслуживания запросов на приборах;

дисциплина обслуживания (она определяет порядок обработки запроса в системе, начиная с момента его поступления в систему и до момента, когда он покидает СМО).

Согласно символике Дж. Кендалла, введенной в 1953 году, в теории массового обслуживания принято кодирование (краткое описание) основных СМО в виде совокупности четырех символов, разделенных вертикальными чертами: Л5пт. Символ п, п > 1 задает число идентичных параллельных обслуживающих устройств. Символ т,т>0 задает число мест для ожидания в буфере. Если m = оо,

то четвертый символ в описании СМО может отсутствовать. Символ А описывает входящий поток запросов, а символ В - распределение времен обслуживания запросов. Некоторые возможные значения этих символов будут приведены и пояснены в следующем разделе.

1.2 Входящий поток, время обслуживания

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

Во входящем (случайном) потоке, запросы поступают в систему в некоторые случайные моменты времени ti,t2, . ,tn, Будем обозначать = tk - tk-i длину интервала между моментами поступления {к - 1)-го и к -го запросов. А; > 1 (*о полагается равным 0) и ж< - число моментов tk, лежащих на временной оси левее точки t,t > 0.

Случайный поток считается заданным, если задано совместное распределение величин Тк,к = 1,..., п для любого п, п > 1 или задано совместное распределение величин xt для всех значений t,t > 0.

Определение 1. Случайный поток называется стационарным, если для любого целого числа т и любых неотрицательных чисел ui,...,UTn совместное распределение величин {xt+u~xt), к = I,... ,т не зависит от величины t.

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

Определение 2. Случайный поток называется ординарным, если для любого t имеет место соотношение

lim {+А --t>l} до Д

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