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, las porciones de tiempo (también conocidas como cuantos de tiempo) [3] se asignan a cada proceso en porciones iguales y en orden circular, manejando todos los procesos sin prioridad (también conocido como ejecutivo cíclico ). La programación round-robin es simple, fácil de implementar y libre de inanición . La programación round-robin se puede aplicar a otros problemas de programación, como la programación de paquetes de datos en redes de computadoras. Es un concepto de sistema operativo .
El nombre del algoritmo proviene del principio round-robin , conocido en otros campos, donde cada persona toma una parte igual de algo por turno.
Para programar procesos de manera justa, un planificador round-robin generalmente emplea el método de compartir el tiempo , asignando a cada trabajo un intervalo de tiempo o quantum [4] (su asignación de tiempo de CPU) e interrumpiendo el trabajo si no se completa para entonces. El trabajo se reanuda la próxima vez que se asigna un intervalo de tiempo a ese proceso. Si el proceso termina o cambia su estado a espera durante su quantum de tiempo atribuido, el planificador selecciona el primer proceso en la cola de listos para ejecutar. En ausencia de tiempo compartido, o si los quanta fueran grandes en relación con los tamaños de los trabajos, un proceso que produzca trabajos grandes sería favorecido sobre otros procesos.
El algoritmo round-robin es un algoritmo preventivo ya que el programador fuerza al proceso a salir de la CPU una vez que expira la cuota de tiempo.
Por ejemplo, si el intervalo de tiempo es de 100 milisegundos y el trabajo 1 tarda un tiempo total de 250 ms en completarse, el programador de turnos rotativos suspenderá el trabajo después de 100 ms y les dará a los demás trabajos su tiempo en la CPU. Una vez que los demás trabajos hayan tenido su parte equitativa (100 ms cada uno), el trabajo 1 obtendrá otra asignación de tiempo de CPU y el ciclo se repetirá. Este proceso continúa hasta que el trabajo finaliza y no necesita más tiempo en la CPU.
Considere la siguiente tabla con el tiempo de llegada y el tiempo de ejecución del proceso con el tiempo cuántico de 100 ms para comprender la programación round-robin:
Otro enfoque consiste en dividir todos los procesos en un número igual de cuantos de tiempo, de modo que el tamaño del cuanto sea proporcional al tamaño del proceso. Por lo tanto, todos los procesos terminan al mismo tiempo.
En la conmutación de paquetes de máximo esfuerzo y otras multiplexaciones estadísticas , la programación por turnos se puede utilizar como alternativa a la cola por orden de llegada .
Un multiplexor, conmutador o enrutador que proporciona programación por turnos tiene una cola separada para cada flujo de datos, donde un flujo de datos puede identificarse por su dirección de origen y destino. El algoritmo permite que cada flujo de datos activo que tenga paquetes de datos en la cola se turne para transferir paquetes en un canal compartido en un orden que se repite periódicamente. La programación conserva el trabajo , lo que significa que si un flujo se queda sin paquetes, el siguiente flujo de datos ocupará su lugar. Por lo tanto, la programación intenta evitar que los recursos del enlace queden sin usar.
La programación por turnos da como resultado una equidad máxima y mínima si los paquetes de datos tienen el mismo tamaño, ya que se le da prioridad de programación al flujo de datos que ha esperado más tiempo. Puede que no sea deseable si el tamaño de los paquetes de datos varía ampliamente de un trabajo a otro. Un usuario que produce paquetes grandes sería favorecido por sobre otros usuarios. En ese caso, sería preferible una cola justa .
Si se ofrece una calidad de servicio garantizada o diferenciada, y no solo una comunicación de máximo esfuerzo, se puede considerar la programación por turnos con déficit (DRR), la programación por turnos ponderada (WRR) o la cola justa ponderada (WFQ).
En 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 a canales de paso de tokens , como Token Ring , o mediante sondeo o reserva de recursos desde una estación de control central.
En una red de radio por paquetes inalámbrica centralizada, donde muchas estaciones comparten un canal de frecuencia, un algoritmo de programación en una estación base central puede reservar intervalos de tiempo para las estaciones móviles en forma de turnos rotativos y proporcionar equidad. Sin embargo, si se utiliza la adaptación de enlace , se necesitará mucho más tiempo para transmitir una cierta cantidad de datos a usuarios "costosos" que a otros, ya que las condiciones del canal difieren. Sería más eficiente esperar con la transmisión hasta que se mejoren las condiciones del canal, o al menos dar prioridad de programación a los usuarios menos costosos. La programación por turnos rotativos no utiliza esto. Se puede lograr un mayor rendimiento y una mayor eficiencia del espectro del sistema mediante una programación dependiente del canal, por ejemplo, un algoritmo proporcionalmente justo o una programación de máximo rendimiento . Obsérvese que esta última se caracteriza por una inanición de la programación indeseable . Este tipo de programación es uno de los algoritmos más básicos para los sistemas operativos en computadoras que se pueden implementar a través de una estructura de datos de cola circular.
5.3.4 Programación por turnos