1. Qué es Round Robin
Round Robin es el algoritmo de planificación que reparte la CPU en turnos de igual duración (quantum) entre todos los procesos listos. Cada proceso recibe un quantum de tiempo; si no termina en ese tiempo, se le quita la CPU y se le envía al final de la cola. El siguiente proceso recibe su quantum, y así sucesivamente.
Round Robin es la solución al problema de la equidad: en lugar de favorecer a los procesos cortos (SJF) o a los importantes (prioridades), da a todos la misma oportunidad. Es el algoritmo más usado en sistemas de tiempo compartido (time-sharing), donde varios usuarios comparten la máquina y cada uno espera una respuesta rápida.
Round Robin es inherentemente apropiativo: el temporizador del sistema interrumpe al proceso cuando se le acaba el quantum. No necesita conocer las ráfagas de CPU, lo que lo hace aplicable en la práctica (a diferencia de SJF).
A diferencia de SJF, Round Robin no necesita saber cuánto va a durar un proceso. Solo necesita un quantum y una cola. Esto lo hace aplicable en sistemas reales, donde las ráfagas no se conocen de antemano.
2. El quantum
El quantum (o time slice) es la duración máxima que un proceso puede ejecutarse antes de ser interrumpido. Es el parámetro central de Round Robin: determina el equilibrio entre respuesta y overhead.
El quantum típico en los sistemas operativos modernos es de 1 a 10 milisegundos. En Linux (CFS), no hay un quantum fijo: el tiempo de ejecución se calcula dinámicamente según el número de procesos y la latencia objetivo.
El quantum afecta a dos cosas:
- Tiempo de respuesta: un quantum más corto significa que los procesos reciben la CPU más frecuentemente, mejorando la respuesta.
- Overhead: un quantum más corto significa más cambios de contexto, lo que consume más tiempo de CPU.
El quantum ideal es lo suficientemente corto para que la respuesta sea buena, pero lo suficientemente largo para que el overhead sea aceptable. El tema 21 profundiza en cómo elegir el quantum.
3. Cómo funciona
Round Robin funciona con una cola circular de procesos listos:
- Llega un proceso. Se añade al final de la cola de listos. llegada
- La CPU queda libre. Se toma el proceso del principio de la cola. desencolar
- El proceso se ejecuta. Recibe un quantum de tiempo. Si termina antes del quantum, sale del sistema. Si no termina, se interrumpe y se envía al final de la cola. ejecutar
- Se repite. El siguiente proceso recibe su quantum. bucle
La regla clave es que un proceso que no termina en su quantum se envía al final de la cola, no se descarta. Así, todos los procesos reciben turnos periódicos.
El temporizador del sistema interrumpe al proceso cuando se le acaba el quantum. Esta interrupción es la que hace que Round Robin sea apropiativo: el planificador no espera a que el proceso termine o se bloquee.
4. La cola circular
La estructura de datos de Round Robin es una cola circular: los procesos circulan por la cola, recibiendo un quantum cada vez que les toca. Cuando un proceso termina, se elimina de la cola. Cuando un proceso se bloquea en E/S, sale de la cola temporalmente y vuelve al final cuando termina la E/S.
5. Un ejemplo desarrollado
Tres procesos, todos llegando en 0, con ráfagas 8, 4 y 2, y un quantum de 3:
| Proceso | Llegada | Ráfaga |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 0 | 4 |
| P3 | 0 | 2 |
Simulación paso a paso (quantum = 3):
- t = 0: Cola: [P1, P2, P3]. Se ejecuta P1 durante 3. P1 no termina (le quedan 5). Se envía al final. Cola: [P2, P3, P1]. quantum
- t = 3: Se ejecuta P2 durante 3. P2 no termina (le queda 1). Se envía al final. Cola: [P3, P1, P2]. quantum
- t = 6: Se ejecuta P3 durante 2. P3 termina (ráfaga 2 ≤ quantum 3). Sale del sistema. Cola: [P1, P2]. terminación
- t = 8: Se ejecuta P1 durante 3. P1 no termina (le quedan 2). Se envía al final. Cola: [P2, P1]. quantum
- t = 11: Se ejecuta P2 durante 1. P2 termina. Sale del sistema. Cola: [P1]. terminación
- t = 12: Se ejecuta P1 durante 2. P1 termina. Cola: []. terminación
El Gantt resultante es:
Las métricas (leyendo el Gantt: S es el borde izquierdo del primer bloque, F es el borde derecho del último bloque):
| Proceso | Llegada | Ráfaga | Primer bloque | Último bloque | Respuesta | Espera | Retorno |
|---|---|---|---|---|---|---|---|
| P1 | 0 | 8 | 0-3 | 12-14 | 0 | 6 | 14 |
| P2 | 0 | 4 | 3-6 | 11-12 | 3 | 8 | 12 |
| P3 | 0 | 2 | 6-8 | 6-8 | 6 | 6 | 8 |
| Promedio | 3,00 | 6,67 | 11,33 |
Compara con FCFS para el mismo conjunto: respuesta promedio 0 + 8 + 10 = 6,00; espera 0 + 8 + 10 = 6,00; retorno 8 + 12 + 14 = 11,33. Round Robin tiene mejor respuesta (3,00 vs 6,00) pero peor espera (6,67 vs 6,00). El retorno es similar.
6. Propiedades de Round Robin
| Propiedad | ¿La cumple? | Comentario |
|---|---|---|
| Equidad | Sí | Todos los procesos reciben el mismo quantum. |
| Buen tiempo de respuesta | Sí | Ningún proceso espera más de (n−1)·q para recibir la CPU. |
| Ausencia de inanición | Sí | Todo proceso recibe turnos periódicos. |
| Minimiza espera promedio | No | SJF es mejor. |
| Minimiza retorno promedio | No | SJF es mejor. |
| Simplicidad | Sí | Una cola circular y un temporizador. |
| Overhead | Depende de q | Más cambios de contexto cuanto menor sea q. |
| Necesita conocer ráfagas | No | Funciona sin conocer las duraciones. |
Round Robin es el único algoritmo clásico que combina equidad, buena respuesta y ausencia de inanición sin necesitar conocer las ráfagas. Su única debilidad es que no minimiza el tiempo de espera ni el de retorno.
7. Ventajas
- Equidad: todos los procesos reciben el mismo quantum.
- Buena respuesta: ningún proceso espera más de (n−1)·q para recibir la CPU.
- Sin inanición: todos los procesos reciben turnos periódicos.
- No necesita conocer las ráfagas: aplicable en la práctica.
- Simplicidad: una cola circular y un temporizador.
- Bueno para interactividad: los procesos cortos responden rápido.
8. Desventajas
- No minimiza el tiempo de espera: SJF es mejor.
- No minimiza el tiempo de retorno: SJF es mejor.
- Overhead de cambios de contexto: cada quantum implica un cambio de contexto.
- Sensible al quantum: un quantum mal elegido degrada el rendimiento.
- Procesos largos sufren: un proceso largo se ejecuta en muchos turnos, con espera entre ellos.
Round Robin sacrifica el tiempo de espera y el de retorno a cambio de equidad y buena respuesta. Es un compromiso consciente, no un defecto.
9. Round Robin vs FCFS vs SJF
| Aspecto | FCFS | SJF | Round Robin |
|---|---|---|---|
| Criterio | Orden de llegada | Ráfaga más corta | Turnos iguales |
| Necesita ráfagas | No | Sí | No |
| Equidad | Parcial | No | Sí |
| Tiempo de respuesta | Malo | Bueno (cortos) | Bueno |
| Tiempo de espera | No óptimo | Óptimo | No óptimo |
| Inanición | No | Sí | No |
| Overhead | Bajo | Bajo | Depende de q |
| Uso real | Componente | Con predicción | Base de sistemas reales |
10. Simulador interactivo
Este simulador ejecuta Round Robin con un quantum ajustable. Cambia el quantum y observa cómo cambian el Gantt y las métricas:
Simulador · Round Robin
| Proceso | Llegada | Ráfaga | Inicio | Fin | Respuesta | Espera | Retorno |
|---|---|---|---|---|---|---|---|
11. Resumen
- Round Robin reparte la CPU en turnos de igual duración (quantum) entre todos los procesos listos.
- Usa una cola circular: los procesos que no terminan en su quantum vuelven al final.
- Es inherentemente apropiativo: el temporizador interrumpe al proceso.
- No necesita conocer las ráfagas de CPU.
- Ningún proceso espera más de (n−1)·q para recibir la CPU.
- Es equitativo: todos reciben el mismo quantum.
- No minimiza el tiempo de espera ni el de retorno (SJF es mejor).
- El quantum determina el equilibrio entre respuesta y overhead.
- Es la base de los planificadores modernos (Linux CFS/EEVDF).
12. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. ¿Qué es el quantum?
La duración máxima que un proceso puede ejecutarse antes de ser interrumpido en Round Robin.
2. ¿Qué estructura de datos usa Round Robin?
Una cola circular. Los procesos que no terminan en su quantum vuelven al final.
3. ¿Round Robin es apropiativo?
Sí. El temporizador del sistema interrumpe al proceso cuando se le acaba el quantum.
4. ¿Necesita Round Robin conocer las ráfagas?
No. Funciona sin conocer las duraciones de los procesos.
5. ¿Cuánto espera un proceso para recibir la CPU en el peor caso?
(n−1)·q, donde n es el número de procesos y q el quantum.
6. ¿Minimiza Round Robin el tiempo de espera promedio?
No. SJF es mejor. Round Robin sacrifica la espera a cambio de equidad y respuesta.
7. ¿Qué ocurre si un proceso termina antes de su quantum?
El proceso sale del sistema y la CPU se da al siguiente proceso inmediatamente.
8. ¿Qué ocurre si un proceso se bloquea en E/S durante su quantum?
El proceso sale de la cola temporalmente y vuelve al final cuando termina la E/S.
9. ¿Round Robin sufre inanición?
No. Todos los procesos reciben turnos periódicos.
10. ¿Cuál es el trade-off principal de Round Robin?
Un quantum corto mejora la respuesta pero aumenta el overhead de cambios de contexto.
Para practicar
- Calcula las métricas para P1(0,8), P2(0,4), P3(0,2) con quantum 4 y compara con quantum 2.
- Dibuja el Gantt de Round Robin para el ejemplo del tema con quantum 2.
- Explica por qué un quantum muy grande se acerca a FCFS.
- Explica por qué un quantum muy pequeño se acerca a un procesador compartido (processor sharing).
- Calcula el overhead de cambios de contexto para n procesos con quantum q.
- Modifica el simulador para añadir llegadas distintas y observa el efecto.