§ 11. Системы массового обслуживания

Определения и обозначения

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

Заявка — объект или запрос, требующий обслуживания: например, телефонный вызов, автомобиль у кассы или задание для процессора. Заявки поступают не обязательно через равные промежутки времени, поэтому их появление часто считают случайным. Для каждой заявки можно задать момент поступления и длительность обслуживания.

Канал обслуживания — устройство или исполнитель, который обслуживает одну заявку за раз. Число каналов показывает, сколько заявок система может обслуживать одновременно: при двух каналах параллельно работают два устройства или сотрудника. От количества каналов зависят вероятность ожидания и скорость обработки потока.

Очередь — заявки, ожидающие свободного канала. В одной СМО ожидание разрешено без строгого ограничения, в другой длина очереди ограничена, а в системе с отказами ожидание вообще не допускается. Это правило определяет, сохранится ли занятая заявка до начала обслуживания.

Как это устроено

Работа СМО начинается с поступления заявок в определённые моменты времени. Если промежутки между ними различаются, образуется случайный входящий поток, поэтому заранее нельзя точно сказать, сколько заявок окажется в системе к нужному моменту. Для модели достаточно задать последовательность моментов поступления или правило их случайной генерации.

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

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

Время обслуживания заявок может быть разным, поскольку запросы требуют неодинакового объёма работы. Канал занят от момента начала обслуживания до его завершения, а не просто до следующего шага модели. Поэтому учитывают и число заявок, и момент освобождения каждого канала: именно эти данные показывают, когда появится возможность принять следующую заявку.

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

Сравнение систем массового обслуживания по правилам ожидания

Сначала определите, что происходит с заявкой при занятых каналах, а затем выберите нужный столбец. Для сравнения вариантов смотрите не на один показатель: малая доля отказов может сопровождаться слишком долгим ожиданием.

Разбор задач

Задача 1. Заявки в одноканальной системе

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

1. Для первой заявки запишите момент поступления и прибавьте к нему длительность обслуживания: получится момент освобождения канала.
2. Для каждой следующей заявки сравните её момент поступления с моментом освобождения канала. Если заявка пришла не раньше освобождения, она обслуживается сразу; иначе ждёт.
3. Для ожидающей заявки началом обслуживания будет момент освобождения канала, а новым моментом освобождения станет начало обслуживания плюс её длительность.

Ответ получают в виде последовательности заявок с моментами начала обслуживания. Например, если первая заявка освободила канал в момент 5, а следующая пришла в момент 3, она ждёт до 5. Такой последовательный расчёт учитывает, что один канал не может обслуживать две заявки одновременно.

Задача 2. Имитация одного канала

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

1. Создайте состояние канала: свободен он или занят до определённого момента, а также счётчики обслуженных заявок и отказов.
2. По очереди рассматривайте ближайшее событие поступления заявки и окончание текущего обслуживания. В момент поступления проверьте состояние канала и при свободном канале запишите время его освобождения.
3. Если канал занят, увеличьте счётчик отказов; если обслуживание завершилось, отметьте канал свободным и продолжайте имитацию до конца интервала.

После последнего события ответом будут два счётчика: число обслуженных заявок и число отказов. Если ожидание разрешить, вместо отказа пришлось бы добавлять заявку в очередь. Значит, одно изменение правила меняет алгоритм и итоговые показатели.

Задача 3. Сравнение двух вариантов системы

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

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

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

Типичные ошибки

Считать, что заявка обслуживается сразу после поступления. Так делают, забывая проверить занятость всех каналов. Проверьте перед началом обслуживания, есть ли свободный канал или место в очереди.

Освобождать канал в момент поступления заявки. Канал остаётся занятым до окончания обслуживания, а не до появления нового запроса. Для проверки храните момент освобождения и сравнивайте с ним время поступления.

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

Сравнивать варианты по одному случайному прогону. Один набор событий может случайно оказаться удобным для одной системы. Проведите серию прогонов с одинаковыми исходными потоками и сравните средние показатели.

Связь с другими темами

Для построения модели нужны алгоритмы, циклы и условные операторы. Цикл перебирает события, а условия определяют, ждать заявке, получить отказ или начать обслуживание. Состояние каналов и очереди удобно хранить в переменных и структурах данных.

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

СМО применяются при анализе сервисов, транспорта, компьютерных сетей и вычислительных систем. Везде сравнивают ограниченные ресурсы с потоком запросов. Имитационное моделирование помогает проверить решение до изменения реальной системы.

Что запомнить

• СМО состоит из входящего потока заявок и одного или нескольких каналов обслуживания.
• Если свободных каналов нет, заявка ждёт или получает отказ — это определяется правилами системы.
• Время поступления заявки и время её обслуживания — разные характеристики.
• Состояние системы меняется при поступлении заявки и при завершении обслуживания.
• Имитационная модель воспроизводит работу системы шаг за шагом.
• Случайные результаты надёжнее оценивать по нескольким прогонам.