Очередь с одним сервером

Простейшая система с очередью изображена на рис. 9.20. Центральным элементом системы является сервер, обеспечивающий некоторый сервис элементам очереди. Элементы поступают в систему для обслуживания из некоторого множества элементов. Если сервер не занят, поступивший элемент обслуживается немедленно; в противном случае он попадает в линию ожидания.² Когда сервер завершает обслуживание элемента, он покидает систему. При наличии элементов в очереди один из них немедленно поступает в сервер для обслуживания. Сервером в этой модели может быть нечто, выполняющее некоторые действия над множеством элементов (например, процессор, обслуживающий процессы, линия передач, обеспечивающая передачу пакетов данных, или устройство ввода-вывода, обеспечивающее чтение или запись по запросу).

² В ряде источников линия ожидания известна как очередь, однако достаточно распространено применение термина "очередь" ко всей системе в целом. Мы используем термин "очередь" для обозначения линии ожидания, если не оговорено иное.

В табл. 9.10 приведены основные параметры, связанные с очередями. Элементы поступают в систему с некоторой скоростью λ. В любой момент времени в очереди ожидает обслуживания некоторое количество элементов (может быть нулевым); среднее количество элементов в очереди — w, а среднее время ожидания обслуживания — Т_s. Эта величина усредняется по всем входящим в систему элементам, в том числе обслуживаемым немедленно, без ожидания. Сервер обслуживает элементы со средним временем обслуживания T_s, которое представляет собой интервал между диспетчеризацией элемента и его выходом из системы. Загруженность, ρ, представляет собой отношение времени, в течение которого сервер занят, к общему времени. И, наконец, два параметра описывают систему в целом. Это — среднее количество элементов r, находящихся в системе, включая обслуживающиеся и ожидающие (если таковые имеются), и Т_r — среднее время, затраченное ими на прохождение системы (мы будем говорить о нем как о времени нахождения в системе).³

Таблица 9.10. Параметры системы с очередью

Если предположить, что емкость очереди не ограничена, то системой не будет потерян ни один элемент; будет только отложено обслуживание элементов. При таком условии скорость поступления элементов в систему будет равна скорости их выхода из системы. При увеличении потока элементов в системе возрастает загруженность сервера, и при ρ = 1 достигается насыщение. Таким образом, теоретическая максимальная скорость поступления равна

Однако при приближении к насыщению очередь становится очень большой (и растет неограниченно при ρ = 1). Практические требования, такие, как требования ко времени отклика или ограничения на размер буферов, обычно ограничивают скорость поступления в систему с одним сервером 70-90% от теоретиче­ского максимума.

³ В ряде литературных источников этот термин применяется к среднему време­ни ожидания в очереди до момента обслуживания.

Обычно делаются следующие предположения.

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

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

• Стратегия диспетчеризации. Когда сервер освобождается, а очередь — не пуста, принимается решение о том, какой элемент из очереди будет передан серверу для обслуживания. Простейшим подходом является стратегия "первым вошел — первым вышел". При использовании термина очередь подразумевается именно такая стратегия. Другая возможность — стратегия "последним вошел — первым вышел". На практике можно встретить стратегии, основанные на времени обслуживания. Например, маршрутизатор может обрабатывать сначала как короткие пакеты (для генерации большего количества пакетов), так и длинные (для минимизации времени обработки по отношению ко времени передачи). К сожалению, очень сложно аналитически смоделировать стратегию, основанную на времени обслуживания.