Обобщенное совместное использование процессора ( GPS ) - идеальный алгоритм планирования для планировщиков процессов и сетевых планировщиков . Это связано с принципом справедливой организации очередей, который группирует пакеты по классам и распределяет между ними служебную емкость. GPS разделяет эту емкость в соответствии с некоторыми фиксированными весами . [1]
При планировании процессов GPS - это «идеализированный алгоритм планирования, который обеспечивает идеальную справедливость. Все практические планировщики аппроксимируют GPS и используют его в качестве ориентира для измерения справедливости». [2]
Обобщенное совместное использование процессора предполагает, что трафик является непостоянным ( бесконечно малые размеры пакетов) и может быть произвольно разделен. Существует несколько дисциплин обслуживания, которые достаточно внимательно отслеживают производительность GPS, например, взвешенная справедливая организация очереди (WFQ) [3], также известная как разделение обобщенного процессора между пакетами (PGPS).
Обоснование
В сети, такой как Интернет, разные типы приложений требуют разного уровня производительности. Например, электронная почта - это действительно приложение для хранения и пересылки , а видеоконференцсвязь - нет, поскольку для этого требуется низкая задержка . Когда пакеты помещаются в очередь на одном конце перегруженного канала, узел обычно имеет некоторую свободу в выборе порядка, в котором он должен отправлять поставленные в очередь пакеты. Один из примеров упорядочения - это просто « первым пришел - первым обслужен» , который отлично работает, если размеры очередей малы, но может привести к проблемам, если есть пакеты, чувствительные к задержке, которые блокируются пакетами из импульсных приложений с более высокой пропускной способностью.
Подробности
В GPS планировщик обработки потоки (также называемые "классами" или "сеансами") настроены с одним весом для каждого потока. Затем GPS гарантирует, что с учетом одного потока, и некоторый временной интервал такой, что поток постоянно задерживается на этом интервале ( т.е. очередь никогда не бывает пустой), то для любого другого потока, имеет место соотношение
где обозначает количество битов потока сделал вывод на интервале .
Тогда можно доказать, что каждый поток получит хотя бы ставку
где скорость сервера. [1]
Это минимальная ставка. Если некоторый поток не использует свою полосу пропускания в течение некоторого периода, эта оставшаяся пропускная способность совместно используется активными потоками с учетом их соответствующих весов. Например, рассмотрим GPS-сервер с. Первый поток получит как минимум половину мощности, а два других - только 1/4 . Тем не менее, если на каком-то временном интервале, активны только второй и третий потоки, каждый из них получит половину мощности.
Реализации, параметризация и справедливость
В GPS и во всех протоколах, основанных на GPS, выбор веса оставлен на усмотрение администратора сети.
Обобщенное совместное использование процессора предполагает, что трафик является непостоянным, т. Е. Бесконечно делимым, так что всякий раз, когда тип приложения имеет пакеты в очереди, он будет получать точно часть сервера, заданную формулой выше. Однако трафик не является плавным и состоит из пакетов, возможно, переменного размера. Следовательно, GPS - это в основном теоретическая идея, и было разработано несколько алгоритмов планирования, чтобы приблизиться к этому идеалу GPS: PGPS, также известная как взвешенная справедливая организация очереди , является наиболее известной реализацией GPS, но у нее есть некоторые недостатки, и было предложено несколько других реализаций. , как круговой алгоритм дефицита или WF2Q. [4]
GPS считается справедливым идеалом, и все его приближения «используют его как ориентир для измерения справедливости». [2] Тем не менее, существует несколько мер справедливости .
GPS нечувствителен к размерам пакетов, поскольку предполагает подвижную модель.
Смотрите также
Рекомендации
- ^ а б Парех, А. К.; Галлагер, Р.Г. (1993). «Обобщенный подход с совместным использованием процессора для управления потоком в сетях с интегрированными услугами: случай с одним узлом» (PDF) . Транзакции IEEE / ACM в сети . 1 (3): 344. DOI : 10,1109 / 90,234856 .
- ^ а б Li, T .; Baumberger, D .; Хан, С. (2009). «Эффективное и масштабируемое многопроцессорное справедливое планирование с использованием распределенного взвешенного циклического перебора» (PDF) . Уведомления ACM SIGPLAN . 44 (4): 65. CiteSeerX 10.1.1.567.2170 . DOI : 10.1145 / 1594835.1504188 .
- ^ Демерс, А .; Кешав, С .; Шенкер, С. (1989). «Анализ и моделирование алгоритма справедливой организации очередей». Обзор компьютерных коммуникаций ACM SIGCOMM . 19 (4): 1. DOI : 10,1145 / 75247,75248 .
- ^ Беннетт, JCR; Хуэй Чжан (1996). «WF / sup 2 / Q: Справедливая организация очередей со справедливым взвешиванием в худшем случае». Труды IEEE INFOCOM '96. Конференция по компьютерным коммуникациям . 1 . п. 120. DOI : 10,1109 / INFCOM.1996.497885 . ISBN 978-0-8186-7293-4.