Programación por turnos rotativos

Round-robin ( RR ) es uno de los algoritmos empleados por los planificadores de procesos y redes en informática . ^{[ 1 ] [ 2 ]} Como se usa generalmente el término, se asignan segmentos de tiempo (también conocidos como cuantos de tiempo) ^{[ 3 ]} a cada proceso en porciones iguales y en orden circular, manejando todos los procesos sin prioridad (también conocido como ejecutivo cíclico ). La planificación Round-robin es simple, fácil de implementar y no tiene problemas de inanición . La planificación Round-robin se puede aplicar a otros problemas de planificación, como la planificación de paquetes de datos en redes informáticas. Es un concepto de sistema operativo .

El nombre del algoritmo proviene del principio de turno rotatorio, conocido en otros campos, en el que cada persona toma una parte igual de algo por turno.

Para programar procesos de manera equitativa, un planificador round-robin generalmente emplea tiempo compartido , asignando a cada tarea una ranura de tiempo o cuanto ^{[ 4 ]} (su asignación de tiempo de CPU), e interrumpiendo la tarea si no se completa para entonces. La tarea se reanuda la próxima vez que se le asigne una ranura de tiempo a ese proceso. Si el proceso termina o cambia su estado a espera durante su cuanto de tiempo asignado, el planificador selecciona el primer proceso en la cola de listos para ejecutarlo. En ausencia de tiempo compartido, o si los cuantos fueran grandes en relación con el tamaño de las tareas, un proceso que produjera tareas grandes sería favorecido sobre otros procesos.

El algoritmo Round-robin es un algoritmo preventivo, ya que el planificador fuerza la salida del proceso de la CPU una vez que expira la cuota de tiempo.

Por ejemplo, si el intervalo de tiempo es de 100 milisegundos y la tarea 1 tarda 250 ms en completarse, el planificador round-robin suspenderá la tarea después de 100 ms y asignará su tiempo de CPU a las demás tareas. Una vez que las demás tareas hayan tenido su parte equitativa (100 ms cada una), la tarea 1 recibirá otra asignación de tiempo de CPU y el ciclo se repetirá. Este proceso continúa hasta que la tarea finaliza y ya no necesita más tiempo de CPU.

• Trabajo1 = Tiempo total para completar 250 ms (cuántico 100 ms) .

1. Primera asignación = 100 ms.
2. Segunda asignación = 100 ms.
3. La tercera asignación dura 100 ms, pero el trabajo 1 finaliza automáticamente después de 50 ms.
4. Tiempo total de CPU del trabajo 1 = 250 ms

Considere la siguiente tabla con el tiempo de llegada y el tiempo de ejecución del proceso con un tiempo cuántico de 100 ms para comprender la planificación round-robin:

Otro enfoque consiste en dividir todos los procesos en un número igual de cuantos de tiempo, de manera que el tamaño del cuanto sea proporcional al tamaño del proceso. Por lo tanto, todos los procesos finalizan al mismo tiempo.

En la conmutación de paquetes de mejor esfuerzo y otras técnicas de multiplexación estadística , la planificación round-robin puede utilizarse como alternativa a la cola de primero en llegar, primero en ser atendido .

Un multiplexor, conmutador o enrutador que implementa la programación round-robin dispone de una cola independiente para cada flujo de datos, donde cada flujo se identifica por su dirección de origen y destino. El algoritmo permite que cada flujo de datos activo con paquetes en la cola se turne para transferirlos a través de un canal compartido, en un orden que se repite periódicamente. Esta programación conserva la carga de trabajo , lo que significa que si un flujo se queda sin paquetes, el siguiente lo reemplazará. Por lo tanto, la programación busca evitar que los recursos del enlace queden sin utilizar.

La planificación round-robin garantiza la equidad máxima-mínima si los paquetes de datos tienen el mismo tamaño, ya que se prioriza el flujo de datos que lleva más tiempo esperando. Esto puede no ser conveniente si el tamaño de los paquetes de datos varía considerablemente entre las distintas tareas. Un usuario que genere paquetes grandes tendría prioridad sobre otros usuarios. En ese caso, sería preferible una cola equitativa .

Si se ofrece una calidad de servicio garantizada o diferenciada, y no solo una comunicación de mejor esfuerzo, se puede considerar la programación de turno rotatorio con déficit (DRR), la programación de turno rotatorio ponderado (WRR) o la cola justa ponderada (WFQ).

En las redes de acceso múltiple , donde varios terminales están conectados a un medio físico compartido, la programación round-robin puede proporcionarse mediante esquemas de acceso al canal de paso de testigo, como Token Ring , o mediante sondeo o reserva de recursos desde una estación de control central.

En una red de radio de paquetes inalámbrica centralizada, donde muchas estaciones comparten un canal de frecuencia, un algoritmo de planificación en una estación base central puede reservar ranuras de tiempo para las estaciones móviles de forma rotativa y garantizar la equidad. Sin embargo, si se utiliza la adaptación de enlace , la transmisión de una determinada cantidad de datos a usuarios con mayor consumo de datos llevará mucho más tiempo que a otros, ya que las condiciones del canal difieren. Sería más eficiente esperar con la transmisión hasta que mejoren las condiciones del canal, o al menos dar prioridad de planificación a los usuarios con menor consumo de datos. La planificación rotativa no aprovecha esta característica. Se puede lograr un mayor rendimiento y una mayor eficiencia del espectro del sistema mediante una planificación dependiente del canal, por ejemplo, un algoritmo proporcionalmente justo o una planificación de máximo rendimiento . Cabe destacar que esta última se caracteriza por una inanición de planificación indeseable . Este tipo de planificación es uno de los algoritmos más básicos de los sistemas operativos en computadoras, que se puede implementar mediante una estructura de datos de cola circular.

• Cola multinivel
• SCHED_RR

• Algoritmo de planificación de CPU Round Robin optimizado
• Planificación Round Robin en C++
• Planificación Round Robin en C