Теория Массового Обслуживания

В предыдущих постах мы обсуждали зависимости, которые были получены экспериментальным путем. К слову сказать, существует и теоретическая база для всего этого наукообразия. Она называется Теория Массового Обслуживания (Queuing Theory). Первые задачи данной теории были рассмотрены сотрудником Копенгагенской телефонной компании Агнером Эрлангом (Agner Krarup Erlang 1878-1929) еще в начале прошлого века. Этот в высшей степени выдающейся человек решил задачу упорядочивания работы телефонной станции, рассчитав параметры качества обслуживания потребителей в зависимости от количества используемых устройств.
В наше время Теория Массового Обслуживания активно используется для решения широкого спектра задач. С ее помощью можно достаточно точно оценить необходимое количество кассиров, требуемых в разное время для обслуживания посетителей супермаркета, или требования к производительности работы международного аэропорта.

Как и любая другая математическая теория, Queuing Theory требует основательного знания математики. Я не буду утомлять себя и читателя выкладками серьезных формул. Для тех, кто хочет глубоко в этом разобраться существуют многочисленные специализированные книги и статьи. Да и с прикладной точки зрения необходимости в этом нет. На широких просторах сети не сложно найти уже готовые таблицы Excel, которые очень удобно использовать для простых оценок. Расчеты и графики из этого поста можно взять здесь.

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

Одним из очень упрощенных следствий модели является следующая формула:

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

Интересны еще несколько зависимостей, следующих из модели M/M/m. При постоянном Service Time увеличение количества каналов обслуживания очереди (m) ведет к “сдвигу” точки перегиба в право. Это означает, например, что увеличение пунктов досмотра багажа пассажиров, стоящих в единой очереди терминала аэропорта, при возрастании общего пассажиропотока позволит заметно увеличить эффективную утилизацию этих пунктов.

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

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

Внимательный читатель скажет: “А ведь я уже видел такие сдвиги и растяжения графиков", и будет прав. Посмею сделать утверждение, доказательство которого оставлю на совести гуру Теории Массового Обслуживания. Добавление кэша или количества дисковых накопителей в определенных случаях можно промоделировать при помощи увеличения количества каналов обслуживания. А уменьшение Request Size опосредованно ведет к снижению Service Time и также, с некоторыми оговорками, вписывается в рамки модели M/M/m.

Для желающих подробнее познакомиться с Теорией Массового Обслуживания предлагаю несложную задачку с решением.
Администрация вокзала решила внедрить новую систему обслуживания пассажиров и установить автоматические кассы-терминалы по продаже билетов. Количество пассажиров, встающих в очередь, - в среднем 3 чел./мин. Максимальное время, которое пассажир готов стоять в очереди, а не дождавшись поехать без билета - 5 мин. Рассматривается вопрос о приобретении 4 касс. На выбор есть кассы с производительностью обслуживания 1 чел./мин. и 1,3 чел/мин..
Необходимо выбрать наиболее оптимальный из двух вариантов, который поможет сократить количество тех, кто не дождался своей очереди и поехал без билета. Вариант I - организовать в каждую кассу отдельную очередь. Вариант II - организовать единую очередь ко всем кассам. Причем, во втором варианте для интереса мы будем учитывать использование более производительных касс. Решение задачки можно проанализировать все в той же таблице.

Даже несмотря на то, что в варианте II предполагается использование более производительных касс, вариант I все же будет лучше. Интересно отметить, что если количество пассажиров, встающих в очередь, уменьшится до 0,5 или увеличится до 4, более предпочтительным станет второй вариант (см. график). Вот такие интуитивно-непонятные выводы... :)