ГЛАВА 1. Математические методы теории очередей

1.1 Общие положения и определения

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

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

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

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

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

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

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

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

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

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

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