Compartición generalizada del procesador

El algoritmo de compartición generalizada de procesadores ( GPS ) es un algoritmo de planificación ideal para planificadores de procesos y planificadores de red . Está relacionado con el principio de cola justa , que agrupa los paquetes en clases y comparte la capacidad de servicio entre ellos. GPS comparte esta capacidad según ciertos pesos fijos . ^{[ 1 ]}

En la planificación de procesos, GPS es "un algoritmo de planificación idealizado que logra una equidad perfecta. Todos los planificadores prácticos se aproximan a GPS y lo utilizan como referencia para medir la equidad". ^{[ 2 ]}

El uso compartido generalizado del procesador asume que el tráfico es fluido ( tamaños de paquete infinitesimales ) y puede dividirse arbitrariamente. Existen varias disciplinas de servicio que monitorean el rendimiento del GPS con bastante precisión, como la cola justa ponderada (WFQ), ^{[ 3 ]} también conocida como uso compartido generalizado del procesador paquete por paquete (PGPS).

En una red como internet, los distintos tipos de aplicaciones requieren diferentes niveles de rendimiento. Por ejemplo, el correo electrónico es una aplicación de almacenamiento y reenvío , pero la videoconferencia no lo es, ya que requiere baja latencia . Cuando los paquetes se acumulan en un extremo de un enlace congestionado, el nodo suele tener cierta libertad para decidir el orden en que debe enviarlos. Un ejemplo de ordenación es simplemente el primero en llegar, el primero en ser atendido , que funciona bien si el tamaño de las colas es pequeño, pero puede generar problemas si los paquetes sensibles a la latencia se ven bloqueados por paquetes de aplicaciones con mayor ancho de banda y picos de tráfico.

En GPS, un planificador maneja${\displaystyle N}$Los flujos (también llamados "clases" o "sesiones") se configuran con un peso.${\displaystyle w_{i}}$para cada flujo. Luego, el GPS garantiza que, considerando un flujo${\displaystyle i}$y algún intervalo de tiempo${\displaystyle (s,t]}$de tal manera que el flujo${\displaystyle i}$está continuamente acumulado en este intervalo ( es decir, la cola nunca está vacía), entonces, para cualquier otro flujo${\displaystyle j}$Se cumple la siguiente relación.

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

dónde${\displaystyle O_{k}(s,t)}$indica la cantidad de bits del flujo${\displaystyle k}$produjo salida a intervalos${\displaystyle (s,t]}$.

Entonces, se puede demostrar que cada flujo${\displaystyle i}$recibirá al menos una tasa

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

dónde${\displaystyle R}$es la tasa del servidor. ^{[ 1 ]}

Esta es una tasa mínima. Si algún flujo no utiliza su ancho de banda durante algún período, esta capacidad restante se comparte entre los flujos activos con respecto a sus respectivos pesos. Por ejemplo, considere un servidor GPS con${\displaystyle w_{1}=2,w_{2}=w_{3}=1}$. El primer flujo recibirá al menos la mitad de la capacidad, mientras que los otros dos solo obtienen 1/4 . Sin embargo, si en algún intervalo de tiempo${\displaystyle (s,t]}$, solo el segundo y el tercer flujo están activos, recibirán cada uno la mitad de la capacidad.

En el GPS, y en todos los protocolos inspirados en el GPS, la elección de los pesos queda a criterio del administrador de la red.

El uso compartido generalizado del procesador (GPS) asume que el tráfico es fluido, es decir, infinitamente divisible, de modo que cuando un tipo de aplicación tiene paquetes en la cola, recibirá exactamente la fracción del servidor dada por la fórmula anterior. Sin embargo, el tráfico no es fluido y se compone de paquetes, posiblemente de tamaños variables. Por lo tanto, el GPS es principalmente una idea teórica, y se han desarrollado varios algoritmos de planificación para aproximarse a este ideal: PGPS, también conocido como cola justa ponderada , es la implementación más conocida del GPS, pero tiene algunos inconvenientes, y se han propuesto otras implementaciones, como Deficit round robin o WF2Q. ^{[ 4 ]}

El GPS se considera un ideal justo, y todas sus aproximaciones "lo utilizan como referencia para medir la justicia". ^{[ 2 ]} Sin embargo, existen varias medidas de justicia .

El GPS es insensible al tamaño de los paquetes, ya que se basa en un modelo fluido.

• Planificador de red
• Filas justas
• Compartición del procesador
• colas justas ponderadas
• Round robin de déficit
• Round robin ponderado
• multiplexación estadística
• Medida de equidad