Round Robin: equidad en la planificación de la CPU

5 minutos de lectura

Round Robin es un algoritmo de planificación de procesos utilizado en sistemas operativos. Su funcionamiento se basa en que cada proceso en la cola recibe una pequeña unidad de tiempo de CPU, llamada quantum, tras el que se envía al final de la cola de espera. Si un proceso tiene un tiempo de CPU menor que el quantum (interrupción de reloj para poder ejecutarse en períodos regulares de tiempo), puede finalizar su ejecución, liberando la CPU para otros procesos. Si no puede finalizar en ese tiempo, el proceso se coloca al final de la cola de procesos y espera su próxima oportunidad para ejecutar sus operaciones restantes.

Diagrama de flujo del funcionamiento del algoritmo Round Robin:

Este algoritmo me interesó al realizar un programa implementando una estructura de datos llamada “Priority Queue” con listas para un problema de una CPU que necesitaba ejecutar programas según su prioridad, sin embargo, me pareció que no era el adecuado por la prioridad que se manejaba en la cola para ejecutar los programas. Aunque ambos, Round Robin y las colas de prioridades, tienen sus ventajas y desventajas. Round Robin es simple y garantiza un trato equitativo para todos los procesos, pero puede no ser eficiente si los procesos tienen requerimientos de tiempo de CPU muy diferentes.

Por otro lado, las colas de prioridades pueden asegurar que los procesos más "importantes" (según alguna métrica de prioridad) se ejecuten primero. Sin embargo, esto puede llevar al problema llamado “problema de inanición”, donde los procesos con baja prioridad pueden no tener la oportunidad de ejecutarse si siempre hay procesos de alta prioridad en la cola.

Aplicación del algoritmo:

Este algoritmo es utilizado comúnmente en sistemas operativos, especialmente en aquellos que manejan múltiples tareas simultáneamente. También se utiliza en la planificación de procesos en sistemas de tiempo compartido y en sistemas de redes para manejar la equidad en el ancho de banda.

Complejidad del algoritmo:

La complejidad de tiempo del algoritmo Round Robin puede variar dependiendo del número de procesos y del tiempo que se les otorga (el quantum). Es decir que tiene una complejidad en el peor de los casos de O(n) Sin embargo, en la práctica, factores como la elección del quantum pueden influir en el rendimiento del algoritmo.

Consultas:

• ¿Qué es el problema de inanición?
• Algoritmos apropiativos

• Explicación del algoritmo Round Robin
• Aplicación de Round Robin