Обобщенное совместное использование процессора

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

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

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

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

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

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

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

Тогда можно доказать, что каждый поток получит по крайней мере ставку${\displaystyle я}$

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

где - скорость сервера. ^[1]${\displaystyle R}$

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

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

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

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

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

• Сетевой планировщик
• Справедливая очередь
• Совместное использование процессора
• Взвешенная справедливая организация очереди
• Дефицитный циклический робин
• Круговой турнир с весовым коэффициентом
• Статистическое мультиплексирование
• Мера справедливости