Универсальное совместное использование процессоров

Универсальное совместное использование процессоров ( GPS ) является идеальным алгоритмом планирования для планировщиков процессов и сетевых планировщиков . Это связано с принципом справедливой организации очередей , который группирует пакеты по классам и разделяет между ними пропускную способность службы. GPS разделяет эту емкость в соответствии с некоторыми фиксированными весами . ^[1]

При планировании процессов GPS представляет собой «идеализированный алгоритм планирования, который обеспечивает идеальную справедливость. Все практические планировщики аппроксимируют GPS и используют его в качестве эталона для измерения справедливости». ^[2]

Обобщенное совместное использование процессоров предполагает, что трафик является непостоянным ( бесконечно малые размеры пакетов) и может быть произвольно разделен. Существует несколько дисциплин обслуживания, которые довольно точно отслеживают производительность GPS, например, взвешенная справедливая организация очередей (WFQ), ^[3] также известное как попакетное совместное использование процессора (PGPS).

Обоснование

В такой сети, как Интернет, разные типы приложений требуют разного уровня производительности. Например, электронная почта действительно является для хранения и пересылки приложением , а видеоконференции — нет, поскольку для нее требуется низкая задержка . Когда пакеты ставятся в очередь на одном конце перегруженного канала, узел обычно имеет некоторую свободу в выборе порядка, в котором ему следует отправлять пакеты в очереди. Одним из примеров упорядочения является принцип «первым пришел — первым обслужен» , который отлично работает, если размеры очередей невелики, но может привести к проблемам, если чувствительные к задержке пакеты блокируются пакетами из пакетных приложений с более высокой пропускной способностью.

Подробности

В GPS планировщик обрабатывает $N$ потоки (также называемые «классами» или «сеансами») настроены с одним весом $w_{i}$ для каждого потока. Тогда GPS гарантирует, что, учитывая один поток $i$ , и некоторый интервал времени $(s,t]$ такой, что поток $i$ постоянно задерживается на этом интервале ( т.е. очередь никогда не пуста), то для любого другого потока $j$ , имеет место следующее соотношение

w_{j}O_{i}(s,t)\geq w_{i}O_{j}(s,t)

где $O_{k}(s,t)$ обозначает количество бит потока $k$ сделал вывод по интервалу $(s,t]$ .

Тогда можно доказать, что каждый поток $i$ получит как минимум ставку

R_{i}={\frac {w_{i}}{\sum _{j=1}^{N}w_{j}}}R

где $R$ это скорость сервера. ^[1]

Это минимальная ставка. Если какой-то поток не использует свою пропускную способность в течение некоторого периода, эта оставшаяся пропускная способность распределяется между активными потоками с учетом их соответствующих весов. Например, рассмотрим GPS-сервер с $w_{1}=2,w_{2}=w_{3}=1$ . Первый поток получит не менее половины мощности, тогда как два других — только $1/4$ . Тем не менее, если на некотором интервале времени $(s,t]$ , активны только второй и третий потоки, каждый получит по половине мощности.

Реализации, параметризация и справедливость

В GPS и всех протоколах, основанных на GPS, выбор весов остается за администратором сети.

Обобщенное совместное использование процессора предполагает, что трафик является непостоянным, т. е. бесконечно делимым, так что всякий раз, когда у типа приложения есть пакеты в очереди, оно получит ровно ту часть сервера, которая задана формулой выше. Однако трафик непостоянен и состоит из пакетов, возможно, разного размера. Таким образом, GPS является в основном теоретической идеей, и для приближения к этому идеалу GPS было разработано несколько алгоритмов планирования: PGPS, также известная как взвешенная справедливая организация очередей , является наиболее известной реализацией GPS, но у нее есть некоторые недостатки, и было предложено несколько других реализаций. , как циклический алгоритм дефицита или WF2Q. ^[4]

GPS считается справедливым идеалом, и все его приближения «используют его как эталон для измерения справедливости». ^[2] несколько мер справедливости Тем не менее, существует .

GPS нечувствителен к размерам пакетов, поскольку предполагает гибкую модель.

См. также

Ссылки

^ Jump up to: ^а ^б Парех, АК; Галлагер, Р.Г. (1993). «Обобщенный подход к совместному использованию процессоров для управления потоками в сетях с интеграцией услуг: случай с одним узлом» (PDF) . Транзакции IEEE/ACM в сети . 1 (3): 344. дои : 10.1109/90.234856 .
^ Jump up to: ^а ^б Ли, Т.; Баумбергер, Д.; Хан, С. (2009). «Эффективное и масштабируемое многопроцессорное справедливое планирование с использованием распределенного взвешенного циклического обслуживания» (PDF) . Уведомления ACM SIGPLAN . 44 (4): 65. CiteSeerX 10.1.1.567.2170 . дои : 10.1145/1594835.1504188 .
^ Демерс, А.; Кешав, С.; Шенкер, С. (1989). «Анализ и моделирование справедливого алгоритма организации очередей» . Обзор компьютерных коммуникаций ACM SIGCOMM . 19 (4): 1. дои : 10.1145/75247.75248 .
^ Беннетт, JCR; Хуэй Чжан (1996). «WF/sup 2/Q: справедливо взвешенная справедливая очередь в наихудшем случае». Труды IEEE INFOCOM '96. Конференция по компьютерным коммуникациям . Том. 1. п. 120. дои : 10.1109/INFCOM.1996.497885 . ISBN 978-0-8186-7293-4 . S2CID 17558577 .

[parekh-1] Jump up to: ^а ^б Парех, АК; Галлагер, Р.Г. (1993). «Обобщенный подход к совместному использованию процессоров для управления потоками в сетях с интеграцией услуг: случай с одним узлом» (PDF) . Транзакции IEEE/ACM в сети . 1 (3): 344. дои : 10.1109/90.234856 .

[doi10.1145/1594835.1504188-2] Jump up to: ^а ^б Ли, Т.; Баумбергер, Д.; Хан, С. (2009). «Эффективное и масштабируемое многопроцессорное справедливое планирование с использованием распределенного взвешенного циклического обслуживания» (PDF) . Уведомления ACM SIGPLAN . 44 (4): 65. CiteSeerX 10.1.1.567.2170 . дои : 10.1145/1594835.1504188 .

[demers-3] Демерс, А.; Кешав, С.; Шенкер, С. (1989). «Анализ и моделирование справедливого алгоритма организации очередей» . Обзор компьютерных коммуникаций ACM SIGCOMM . 19 (4): 1. дои : 10.1145/75247.75248 .

[WF2Q-4] Беннетт, JCR; Хуэй Чжан (1996). «WF/sup 2/Q: справедливо взвешенная справедливая очередь в наихудшем случае». Труды IEEE INFOCOM '96. Конференция по компьютерным коммуникациям . Том. 1. п. 120. дои : 10.1109/INFCOM.1996.497885 . ISBN 978-0-8186-7293-4 . S2CID 17558577 .

[1]

[2]

[3]

[4]