Planificación de procesos para GSI: FCFS, SJF, SRTF y Round Robin con ejemplo resuelto
Este artículo pertenece al Bloque II, tema 2 del temario de las oposiciones GSI: «Conceptos y fundamentos de los sistemas operativos. Características técnicas, funcionales y de administración: Windows, Linux, Unix y otros. Sistemas operativos para dispositivos móviles». Nos centramos en uno de los puntos más preguntados de ese tema: la planificación de procesos, es decir, cómo decide el sistema operativo qué proceso usa la CPU en cada momento.
Al terminar deberías poder clasificar cualquier algoritmo (expropiativo o no), calcular tiempos medios de espera y de retorno sin dudar y reconocer las trampas habituales: inanición, efecto convoy y elección del quantum.
Conceptos previos: estados y planificador
Un proceso pasa por cinco estados clásicos: nuevo, listo, en ejecución, bloqueado (esperando una E/S o un evento) y terminado. El planificador a corto plazo elige qué proceso de la cola de listos pasa a ejecución, y el despachador (dispatcher) realiza el cambio de contexto para cederle la CPU.
La distinción clave para el examen es esta:
- Planificación no expropiativa (cooperativa o non-preemptive): el proceso conserva la CPU hasta que termina o se bloquea voluntariamente.
- Planificación expropiativa (preemptive): el sistema operativo puede quitarle la CPU a un proceso, por ejemplo al agotarse su quantum o al llegar otro más prioritario.
Criterios para medir un algoritmo
- Utilización de CPU: porcentaje de tiempo que la CPU está ocupada.
- Productividad (throughput): procesos completados por unidad de tiempo.
- Tiempo de retorno (turnaround): instante de fin menos instante de llegada.
- Tiempo de espera: tiempo total en la cola de listos. Se obtiene como retorno − ráfaga de CPU.
- Tiempo de respuesta: desde la llegada hasta que el proceso obtiene la CPU por primera vez. Es el criterio que importa en sistemas interactivos.
Los algoritmos clásicos de planificación
FCFS (First Come, First Served)
Atiende por orden de llegada, como una cola FIFO. Es no expropiativo y muy sencillo, pero sufre el efecto convoy: si llega primero un proceso largo, todos los cortos esperan detrás de él y el tiempo medio de espera se dispara.
SJF (Shortest Job First)
Elige el proceso con la ráfaga de CPU más corta. En su versión no expropiativa, una vez que un proceso empieza, termina. Para un conjunto de procesos dado, SJF minimiza el tiempo medio de espera, por eso se cita como algoritmo «óptimo». Sus dos pegas: necesita conocer o estimar la duración de la ráfaga (en la práctica se predice con una media exponencial de las ráfagas anteriores) y puede provocar inanición de los procesos largos.
SRTF (Shortest Remaining Time First)
Es la versión expropiativa de SJF. Cada vez que llega un proceso nuevo se compara su ráfaga con lo que le queda al proceso en ejecución; si es menor, lo expulsa. Mejora aún más el tiempo medio de espera, a costa de más cambios de contexto y el mismo riesgo de inanición.
Planificación por prioridades
Cada proceso tiene una prioridad y se ejecuta primero el más prioritario. Puede ser expropiativa o no. SJF es en realidad un caso particular, donde la prioridad es la inversa de la ráfaga. El problema típico es la inanición, y su solución de libro es el envejecimiento (aging): ir aumentando la prioridad de los procesos que llevan mucho tiempo esperando.
Round Robin (turno rotatorio)
Es FCFS con expropiación por quantum: cada proceso usa la CPU durante un intervalo fijo y, si no ha terminado, vuelve al final de la cola. Es el algoritmo de referencia para tiempo compartido porque ofrece buen tiempo de respuesta. La elección del quantum es la pregunta estrella:
- Quantum muy grande: Round Robin degenera en FCFS.
- Quantum muy pequeño: la CPU pierde mucho tiempo en cambios de contexto.
Colas multinivel y colas multinivel con realimentación
En las colas multinivel los procesos se reparten en varias colas fijas (por ejemplo, interactivos y por lotes), cada una con su algoritmo. En las colas multinivel con realimentación (feedback) un proceso puede cambiar de cola según su comportamiento: si consume todo su quantum baja de nivel, y si espera mucho puede subir, lo que también combate la inanición.
Tabla comparativa
| Algoritmo | ¿Expropiativo? | Criterio de elección | Ventaja | Inconveniente |
|---|---|---|---|---|
| FCFS | No | Orden de llegada | Simple y justo en el orden | Efecto convoy |
| SJF | No | Ráfaga más corta | Mínimo tiempo medio de espera (no expropiativo) | Inanición; hay que estimar ráfagas |
| SRTF | Sí | Menor tiempo restante | Aún mejor tiempo medio de espera | Inanición; más cambios de contexto |
| Prioridades | Ambas versiones | Mayor prioridad | Refleja la importancia de cada proceso | Inanición (se corrige con envejecimiento) |
| Round Robin | Sí (por quantum) | Turno rotatorio | Buen tiempo de respuesta | Sensible al tamaño del quantum |
| Multinivel con realimentación | Sí | Cola según comportamiento | Muy flexible | Compleja de configurar |
Ejemplo resuelto: cuatro procesos, cuatro algoritmos
Este es el tipo de ejercicio que conviene dominar. Tenemos cuatro procesos con su instante de llegada y su ráfaga de CPU (en milisegundos):
| Proceso | Llegada | Ráfaga |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
Los diagramas de Gantt quedan así (el número entre paréntesis es el instante de fin de cada tramo):
- FCFS: P1 (8) → P2 (12) → P3 (21) → P4 (26).
- SJF no expropiativo: en t=0 solo está P1, que se ejecuta entera. Después se elige la ráfaga más corta: P1 (8) → P2 (12) → P4 (17) → P3 (26).
- SRTF: en t=1 llega P2 (4) y a P1 le quedan 7, así que P2 expulsa a P1. P1 (1) → P2 (5) → P4 (10) → P1 (17) → P3 (26).
- Round Robin, quantum = 4 (los procesos que llegan entran en la cola antes que el expulsado): P1 (4) → P2 (8) → P3 (12) → P4 (16) → P1 (20) → P3 (24) → P4 (25) → P3 (26).
Con el instante de fin calculamos retorno (fin − llegada) y espera (retorno − ráfaga):
| Algoritmo | Espera P1 / P2 / P3 / P4 | Espera media | Retorno medio |
|---|---|---|---|
| FCFS | 0 / 7 / 10 / 18 | 8,75 ms | 15,25 ms |
| SJF | 0 / 7 / 15 / 9 | 7,75 ms | 14,25 ms |
| SRTF | 9 / 0 / 15 / 2 | 6,5 ms | 13 ms |
| Round Robin (q=4) | 12 / 3 / 15 / 17 | 11,75 ms | 18,25 ms |
Comprobación rápida: la suma de esperas siempre es igual a la suma de retornos menos la suma de ráfagas (26 ms). En SRTF, por ejemplo, 52 − 26 = 26, que repartido entre 4 da 6,5. Si al hacer un ejercicio no te cuadra, revisa el Gantt.
Fíjate en la lectura: SRTF gana en espera media, pero Round Robin, que sale el peor en este criterio, es el que reparte la CPU con más equidad y da mejor tiempo de respuesta a los procesos interactivos. «Mejor» siempre depende del criterio que pregunten.
¿Y en los sistemas operativos reales?
- Windows usa planificación expropiativa basada en prioridades, con 32 niveles (0 a 31) y quantum de tiempo dentro de cada nivel.
- Linux utilizó durante años el planificador CFS (Completely Fair Scheduler), que reparte la CPU de forma proporcional. Desde la versión 6.6 del núcleo el planificador por defecto para procesos normales es EEVDF (Earliest Eligible Virtual Deadline First). Además, Linux ofrece políticas de tiempo real como SCHED_FIFO y SCHED_RR.
Observa que SCHED_FIFO y SCHED_RR son, en esencia, FCFS y Round Robin aplicados dentro de cada nivel de prioridad de tiempo real: los algoritmos de libro siguen vivos en los sistemas actuales.
Pregunta tipo test de ejemplo
¿Cuál de los siguientes algoritmos de planificación puede provocar inanición de procesos largos si no se aplica ningún mecanismo de envejecimiento?
- a) FCFS.
- b) Round Robin con quantum fijo.
- c) SJF.
- d) Ninguno de los anteriores.
Respuesta correcta: c). En SJF, si siguen llegando procesos cortos, uno largo puede quedarse esperando indefinidamente. En FCFS todo proceso acaba llegando a la cabeza de la cola, y en Round Robin cada proceso recibe su turno en cada vuelta, así que ninguno de los dos produce inanición. El distractor peligroso es la a): FCFS puede dar esperas muy largas (efecto convoy), pero esperar mucho no es lo mismo que no ejecutarse nunca.
Resumen para repasar
- Estados del proceso: nuevo, listo, ejecución, bloqueado y terminado. El planificador elige; el despachador cambia el contexto.
- Retorno = fin − llegada; espera = retorno − ráfaga; respuesta = primera vez en CPU − llegada.
- FCFS y SJF clásico son no expropiativos; SRTF y Round Robin son expropiativos; prioridades admite ambas versiones.
- FCFS → efecto convoy. SJF, SRTF y prioridades → inanición, que se corrige con envejecimiento.
- SJF minimiza el tiempo medio de espera; SRTF es su versión expropiativa.
- Round Robin: quantum grande → FCFS; quantum pequeño → exceso de cambios de contexto.
- Windows: prioridades expropiativas con 32 niveles. Linux: CFS hasta EEVDF (núcleo 6.6), más SCHED_FIFO y SCHED_RR para tiempo real.
Practica la planificación con tests y flashcards
Los ejercicios de Gantt se dominan haciéndolos, no leyéndolos. En PreparaGSI tienes tests con explicación, flashcards con repetición espaciada y audios de todo el temario. Regístrate gratis y empieza hoy a repasar el Bloque II.