Planificación de la CPU — teoría con FCFS, SJF, SRTF y Round Robin dibujados en diagramas de Gantt (y el parcial en que olvidé restar la llegada)
La noche antes del segundo parcial de IC2 me puse a repasar planificación con lo que tenía abierto en el portátil: OneDrive subiendo la copia de la práctica, gcc compilando, el campus virtual en el navegador y Spotify de fondo. Me inventé las llegadas y las ráfagas, dibujé el Gantt de SRTF y me quedó precioso. Luego calculé las esperas como fin − ráfaga, me salió una media de 6,5 ms y me fui a dormir tranquilo. Al día siguiente, en el examen, hice exactamente lo mismo. La media buena era 5 ms: se me había olvidado restar la llegada. El dibujo estaba bien; las cuentas, no.
De ese error sale este artículo. En el tema anterior viste que los procesos preparados esperan en una cola mientras uno solo ocupa la CPU. Hoy toca la pregunta obvia: ¿quién decide a quién le toca, y con qué criterio? Vamos a ver las métricas con las que se mide un planificador, los cuatro algoritmos que caen en el examen (FCFS, SJF, SRTF y Round Robin) dibujados paso a paso con los mismos cuatro procesos, y el resto de métodos que entran en el test: prioridades, lotería, multicolas y multiprocesadores. Cuando acabes, en los ejercicios de planificación de la CPU tienes cinco Gantt para resolver con las casillas que se corrigen solas.
Tabla de Contenidos
Qué es planificar la CPU
Tu portátil tiene más procesos que núcleos. Con un núcleo, solo uno puede ejecutar instrucciones en cada instante; los demás esperan en la cola de preparados (sus PCB, en realidad). Cada vez que la CPU queda libre, alguien tiene que elegir el siguiente.
Planificar es decidir a qué proceso (o hilo) se le da acceso a un recurso, y en este tema el recurso es la CPU. El planificador del procesador (el planificador a corto plazo del tema anterior) decide qué proceso ocupa el procesador cuando queda libre y, si el algoritmo lo permite, en qué momento debe abandonarlo el que está dentro. El algoritmo que usa para decidirlo es la política de planificación.
Fíjate en el dibujo: con un núcleo, gcc, spotify, campus y onedrive se turnan en trozos tan pequeños que parece que van a la vez. Eso es concurrencia: varias tareas avanzan intercaladas en el tiempo. Con dos núcleos, dos de ellas se ejecutan de verdad a la vez: eso es paralelismo. Este tema trata del caso de un núcleo, que es donde la decisión importa más.
Para estudiar los algoritmos se simplifica el problema: un programa por usuario, un hilo por programa y programas independientes entre sí. No es realista, pero sin esas suposiciones no se podría comparar nada con lápiz y papel.
Ráfagas de CPU y de E/S
Un proceso no pide la CPU de una vez para todo su trabajo. Calcula un rato, pide algo al disco o a la red y se bloquea, vuelve a calcular… La vida activa de un proceso es una sucesión de ráfagas de CPU y de ráfagas de E/S.
Arriba tienes un proceso que alterna ráfagas de CPU de 3, 4, 2 y 5 ms con esperas de E/S. Abajo, la forma típica de la distribución: la mayoría de las ráfagas de CPU son cortas, de menos de 8 ms, y hay unas pocas muy largas (las de los procesos de cálculo). Por eso cada decisión del planificador no reparte «un programa», sino la siguiente ráfaga de CPU. Y por eso, con tiempo compartido, a veces un proceso tiene que dejar la CPU antes de acabar su ráfaga.
¿Qué querría un proceso si pudiera elegir? Que cuando necesite la CPU le atiendan enseguida, que una vez dentro le dejen terminar su ráfaga y acabar cuanto antes. Lo malo es que los cuatro procesos de tu portátil quieren lo mismo a la vez.
Las métricas: cómo se mide un planificador
Para decir que un algoritmo es «mejor» hay que medir algo. Estas son las definiciones que caen en el examen:
- Tiempo de espera: tiempo total que un proceso permanece en la cola de preparados (sumando todas las veces que vuelve a ella).
- Tiempo de retorno: tiempo desde que el proceso llega (nace) hasta que termina.
- Tiempo de respuesta: tiempo que tarda una ráfaga de CPU desde que llega a la cola de preparados hasta que empieza a ejecutarse.
- Utilización de CPU: porcentaje del tiempo en que la CPU hace trabajo productivo.
Y la relación que lo ata todo: tiempo de retorno = tiempo de espera + tiempo de CPU. Con números del Gantt se calculan así:
| Métrica | Fórmula | Se lee en el Gantt… |
|---|---|---|
| Retorno | fin − llegada | desde la flecha de llegada hasta el último bloque |
| Espera | retorno − ráfaga | todo lo rayado: el tiempo en la cola |
| Respuesta | primera entrada − llegada | solo hasta el primer bloque |
Fíjate en gcc con Round Robin (lo verás entero más abajo): llega en t = 1, entra por primera vez en t = 3, sale, vuelve a la cola y termina en t = 15. Su respuesta es 3 − 1 = 2 ms, su retorno 15 − 1 = 14 ms y su espera 14 − 4 = 10 ms. Comprobado a mano por los trozos rayados: (3 − 1) + (14 − 6) = 2 + 8 = 10. Las dos cuentas coinciden, como tiene que ser.
Calcular la espera como fin − ráfaga. Solo vale si el proceso llegó en t = 0. Si llegó más tarde, primero resta la llegada: retorno = fin − llegada, y después espera = retorno − ráfaga. Ese fue mi error del parcial.
¿Qué se intenta optimizar? Depende del sistema, y no hay una política óptima para todos los criterios, así que siempre hay un compromiso:
| Tipo de sistema | Lo que busca el planificador |
|---|---|
| Por lotes | Sacar el máximo rendimiento a la CPU (utilización) |
| Interactivo | Tiempos de respuesta cortos para el usuario |
| Tiempo real | Cumplir los plazos de ejecución establecidos |
Además de las medias, a veces importan los valores extremos (que nadie espere más de X) o la varianza (que el sistema sea predecible).
Expulsivos y no expulsivos
Antes de ver algoritmos, la clasificación que más se pregunta:
- No expulsivos: el proceso que está en la CPU la abandona solo cuando él lo solicita (termina su ráfaga o se bloquea pidiendo E/S). Riesgo: que un proceso acapare la CPU de forma injusta. Así funcionaban Windows 3.11 o las primeras versiones de iOS.
- Expulsivos: el planificador puede desalojar al proceso que está en la CPU. Para implementar tiempo compartido y tiempo real hace falta planificación expulsiva: es lo que usan Unix, Windows o macOS.
El dibujo lo resume en cuatro situaciones. Las dos de arriba (termina la ráfaga, se bloquea por E/S) pasan en todos los algoritmos. Las dos de abajo (llega alguien mejor, se agota el cuanto) solo existen en los expulsivos, y la del cuanto necesita el temporizador que viste en el tema del hardware: sin su interrupción, el SO no se enteraría de que el tiempo se ha acabado.
Decir que el tiempo compartido necesita planificación no expulsiva. Es al revés: si el SO no puede sacar a nadie, un proceso que calcula sin parar deja colgados a todos los interactivos.
El ejemplo: la noche antes de entregar
Todos los algoritmos los vamos a probar con los mismos cuatro procesos, con tiempos en milisegundos:
| Proceso | Qué es | Llegada | Ráfaga de CPU |
|---|---|---|---|
| onedrive | la copia de la práctica a la nube | 0 | 8 |
| gcc | compilando la práctica | 1 | 4 |
| campus | el navegador con el campus virtual | 2 | 9 |
| spotify | la música de fondo | 3 | 2 |
En total piden 8 + 4 + 9 + 2 = 23 ms de CPU. Con un núcleo, el último en terminar lo hará en t = 23 sea cual sea el algoritmo; lo que cambia es quién espera y cuánto.
FCFS: primero en llegar, primero en ser servido
FCFS (First-Come, First-Served) es la política más simple: la cola de preparados es una FIFO ordenada por llegada, y el que entra en la CPU se queda hasta que termina su ráfaga. Es no expulsivo.
Cómo leer este dibujo (y los siguientes): la barra de arriba es el Gantt de la CPU; debajo, cada proceso tiene su «calle», con un triángulo donde llega, lo rayado mientras espera en la cola y los bloques de color cuando está en la CPU. A la derecha, su espera y su retorno.
Comprobación a mano: onedrive llega en 0 y sale en 8 (espera 0). gcc llega en 1 y entra en 8: espera 7, retorno 12 − 1 = 11. campus llega en 2 y entra en 12: espera 10, retorno 19. spotify llega en 3, entra en 21: espera 18, retorno 20. Media de espera: (0 + 7 + 10 + 18) / 4 = 35 / 4 = 8,75 ms.
Fíjate en spotify: pide 2 ms y espera 18. Ese es el gran defecto de FCFS, el efecto convoy: los procesos cortos se atascan detrás de los largos, como coches detrás de un camión en una carretera de un carril.
El dibujo lo enseña con los cuatro llegando a la vez en t = 0. Si el largo va delante, la espera media es (0 + 8 + 12 + 21) / 4 = 10,25 ms; si van primero los cortos, (0 + 2 + 6 + 14) / 4 = 5,5 ms. Mismo trabajo, casi la mitad de espera. Por eso se dice que FCFS es muy sensible al orden de llegada.
| FCFS | |
|---|---|
| Ventajas | Simple de implementar: basta una cola FIFO |
| Inconvenientes | Muy sensible al orden de llegada; efecto convoy; perjudica a los procesos intensivos en E/S (sus ráfagas cortas esperan detrás de las largas) |
SJF: primero el más corto
¿Y si en vez de atender por orden de llegada atendemos primero al que menos va a tardar? Eso es SJF (Shortest Job First): cuando la CPU queda libre, entra el proceso con la ráfaga de CPU más breve de los que están en la cola. Si empatan, el que llegó antes. En su versión básica es no expulsivo: el que entra no sale hasta acabar.
Paso a paso: en t = 0 solo está onedrive, así que entra, y como SJF no expulsa, se queda hasta t = 8 aunque lleguen otros más cortos. En t = 8 esperan gcc (4), campus (9) y spotify (2): entra spotify, el más corto, aunque fue el último en llegar. En t = 10 quedan gcc (4) y campus (9): entra gcc. En t = 14, campus.
Esperas: onedrive 0, spotify 8 − 3 = 5, gcc 10 − 1 = 9 y campus 14 − 2 = 12. Media: (0 + 5 + 9 + 12) / 4 = 26 / 4 = 6,5 ms, mejor que los 8,75 de FCFS.
En SJF no expulsivo, la pregunta «¿quién es el más corto?» solo se hace cuando la CPU queda libre. Nunca mientras alguien está ejecutando.
| SJF | |
|---|---|
| Ventaja | Minimiza el tiempo medio de espera (es el óptimo en esa métrica) |
| Inconveniente | Riesgo de inanición de los procesos con ráfagas largas si no paran de llegar cortos |
| Problema práctico | No se sabe cuánto durará la próxima ráfaga: hay que estimarla |
Si todos los procesos duran lo mismo, SJF y FCFS hacen exactamente lo mismo. La diferencia aparece cuando las duraciones son distintas: con SJF los cortos ya no se atascan detrás de los largos. La otra cara: si tienes la compra del mes en el súper y todos los que llevan solo pan pasan delante, tú no sales nunca.
Estimar la próxima ráfaga
Un SO real no conoce la próxima ráfaga, así que tendría que estimarla. Una forma posible es la media exponencial de las ráfagas anteriores:
τ(n+1) = α · t(n) + (1 − α) · τ(n), con 0 < α < 1
donde t(n) es lo que duró la ráfaga actual y τ(n) era la estimación anterior. Con α = 0,5, si se estimaban 10 ms y la ráfaga duró 6, la nueva estimación es 0,5 · 6 + 0,5 · 10 = 3 + 5 = 8 ms: a medio camino entre lo que se esperaba y lo que pasó.
SJF no se usa en la práctica, ni siquiera con estimaciones. Hay algoritmos con mejor equilibrio entre rendimiento y tiempo de respuesta. Se estudia porque marca el mínimo de espera media con el que comparar a los demás.
SRTF: el SJF que sí expulsa
La versión expulsiva de SJF se llama SRTF (Shortest Remaining Time First): cada vez que llega un proceso, se compara su ráfaga con lo que le QUEDA al que está en la CPU. Si el recién llegado es más corto, expulsa al de dentro, que vuelve a la cola con su tiempo restante.
Esta es la traza completa. Apunta en cada evento lo que le queda a cada uno:
| t | Qué pasa | Restantes en ese instante | Decisión |
|---|---|---|---|
| 0 | llega onedrive (8) | onedrive 8 | entra onedrive |
| 1 | llega gcc (4) | onedrive 7, gcc 4 | 4 < 7: gcc expulsa a onedrive |
| 2 | llega campus (9) | gcc 3, onedrive 7, campus 9 | 9 > 3: sigue gcc |
| 3 | llega spotify (2) | gcc 2, spotify 2, … | 2 = 2: no expulsa, sigue gcc |
| 5 | termina gcc | spotify 2, onedrive 7, campus 9 | entra spotify |
| 7 | termina spotify | onedrive 7, campus 9 | entra onedrive |
| 14 | termina onedrive | campus 9 | entra campus hasta 23 |
La fila de t = 3 es la trampa: a gcc le quedan 2 ms y spotify trae 2 ms. Para expulsar, el nuevo tiene que ser estrictamente más corto; con un empate no compensa pagar un cambio de contexto. (Si en el examen usas otro criterio, escríbelo en una línea).
Ahora las cuentas, restando la llegada (mi error del parcial): onedrive termina en 14, retorno 14 − 0 = 14, espera 14 − 8 = 6. gcc: retorno 5 − 1 = 4, espera 4 − 4 = 0. campus: retorno 23 − 2 = 21, espera 21 − 9 = 12. spotify: retorno 7 − 3 = 4, espera 4 − 2 = 2. Media de espera: (6 + 0 + 12 + 2) / 4 = 20 / 4 = 5 ms. Y si hubieras hecho fin − ráfaga: (6 + 1 + 14 + 5) / 4 = 6,5 ms. Exactamente lo que me pasó a mí.
Comparar la ráfaga del que llega con la ráfaga total del que está dentro. Hay que compararla con lo que le queda: en t = 1, gcc (4) no se compara con los 8 de onedrive, sino con sus 7 restantes.
SRTF baja todavía más la espera media (5 ms frente a los 6,5 de SJF) porque los cortos ya no esperan detrás de un largo que entró antes. Pero hereda el problema de SJF, agravado: un proceso largo puede ser expulsado una y otra vez y sufrir inanición.
Round Robin: turnos con cuanto
Round Robin (RR) es como FCFS, pero cada proceso dispone de un cuanto de tiempo Q en la CPU. Si pasa Q y el proceso sigue ejecutando, el planificador lo desaloja y lo pone al final de la cola de preparados, que funciona como una FIFO circular. Es expulsivo y es el algoritmo típico del tiempo compartido. En la práctica, Q suele estar entre 1 y 200 ms.
Con Q = 3: onedrive entra en t = 0 y en t = 3 agota su cuanto. Justo en ese instante llega spotify. ¿Quién va antes en la cola? El criterio habitual es poner primero al recién llegado y después al que vuelve de agotar su cuanto. La cola queda así en cada decisión:
Lee el dibujo de arriba abajo. En t = 3 entra gcc (el primero de la cola) y onedrive queda al final, detrás de spotify. En t = 6 gcc agota su cuanto (le queda 1) y se pone a la cola. En t = 9 entra spotify, que termina en t = 11 sin agotar el cuanto (solo necesitaba 2). Y así hasta que campus termina en t = 23.
Cuentas: onedrive termina en 20 (espera 20 − 8 = 12), gcc en 15 (retorno 14, espera 10), campus en 23 (retorno 21, espera 12) y spotify en 11 (retorno 8, espera 6). Espera media: (12 + 10 + 12 + 6) / 4 = 10 ms, la peor de los cuatro. Pero mira la respuesta: onedrive entra en 0, gcc en 3 − 1 = 2, campus en 6 − 2 = 4 y spotify en 9 − 3 = 6. Media (0 + 2 + 4 + 6) / 4 = 3 ms, la mejor. Eso es lo que compra Round Robin: que todos empiecen pronto.
Una garantía que se pregunta mucho: si hay N procesos en la cola, el tiempo de respuesta de un proceso es como mucho Q · (N − 1). Aquí, 3 · (4 − 1) = 9 ms: nadie espera más de 9 ms para entrar por primera vez.
En un empate entre un proceso que llega y otro que agota su cuanto, meter primero al que sale. El criterio habitual es el contrario (el recién llegado delante). Lo importante en el examen es escribir qué criterio sigues.
Cómo influye el cuanto
Q no es un detalle: decide cómo se comporta el algoritmo entero.
- Q muy grande (mayor que las ráfagas): todos terminan antes de agotar el cuanto y Round Robin se comporta como FCFS.
- Q muy pequeño: la CPU se reparte de forma muy uniforme, como si cada uno de los N procesos tuviera un procesador N veces más lento (procesador compartido)…
- …pero si Q es demasiado pequeño, hay muchísimos cambios de contexto y el rendimiento cae. Q debería ser mucho mayor que lo que dura un cambio de contexto.
El dibujo sale del segundo simulador de «Compruébalo con Python» (más abajo), con los mismos cuatro procesos y suponiendo que cada cambio de contexto cuesta 0,5 ms. Con Q = 1 la respuesta media es de 0,75 ms, pero hay 20 cambios y solo el 69,7 % de la CPU hace trabajo útil. Con Q = 9 (mayor que la ráfaga más larga) sale exactamente lo de FCFS: espera media 8,75 ms. Y fíjate en la línea de la espera: sube y baja. Un Q más pequeño no siempre es mejor.
Se puede hacer Q variable, según la carga o la prioridad del proceso. Linux (con su planificador CFS) da a cada proceso que entra un cuanto que depende de cuánto ha esperado y de cuántos procesos hay en el sistema.
Los cuatro, frente a frente
Con los mismos procesos, cada algoritmo gana en algo distinto:
| Algoritmo | ¿Expulsivo? | A quién elige | Espera media | Respuesta media | Su problema |
|---|---|---|---|---|---|
| FCFS | No | El primero en llegar | 8,75 | 8,75 | Efecto convoy |
| SJF | No | La ráfaga más corta | 6,5 | 6,5 | Inanición de largos; hay que estimar |
| SRTF | Sí | El menor tiempo restante | 5 | 3,5 | Inanición; más cambios |
| Round Robin | Sí | El siguiente de la FIFO, con cuanto Q | 10 | 3 | Elegir bien Q |
¿Cuándo usar cada uno?
| Si lo que importa es… | Mejor… | Porque… |
|---|---|---|
| La sencillez (lotes sin prisa) | FCFS | Basta una cola FIFO |
| La espera media mínima (en teoría) | SJF / SRTF | Atienden antes a los cortos |
| Que el usuario note respuesta rápida | Round Robin | Nadie espera más de Q · (N − 1) |
| Que no haya inanición | FCFS o Round Robin | Respetan el orden de la cola |
Lo resume bien la cola del súper: FCFS es malo para los que llevan poco (si te toca detrás de cinco carros llenos…) y SJF es malo para los que llevan mucho (si llevas la compra del mes y todos los del pan pasan delante).
Planificación por prioridades
Cada proceso tiene una prioridad y entra en la CPU el de mayor prioridad. Puede ser expulsiva o no (en la expulsiva, si llega uno más prioritario, desaloja al de dentro). Las prioridades pueden ser internas (las calcula el SO, por ejemplo según el uso de memoria o de E/S) o externas (las pone el usuario). SJF es un caso particular: la prioridad es la duración estimada de la ráfaga.
El riesgo es el de siempre: inanición de los procesos con menos prioridad. Si no paran de llegar gcc, spotify y campus con más prioridad, la copia de onedrive no entra nunca. La solución es el envejecimiento (aging): aumentar progresivamente la prioridad de los procesos que esperan, hasta que el olvidado se vuelve el más prioritario y entra. (Los números del dibujo son ilustrativos).
Lotería
Un enfoque curioso: a cada proceso se le dan tickets y, en cada rodaja de tiempo, se sortea un ticket ganador. A la larga, el tiempo de CPU es proporcional al número de tickets de cada proceso.
| Proceso | Tickets | CPU a la larga |
|---|---|---|
| gcc | 3 | 3 / 4 = 75 % |
| onedrive | 1 | 1 / 4 = 25 % |
¿Cuántos tickets dar? Para parecerse a SRTF, más tickets a los trabajos cortos y menos a los largos. Para que nadie se quede sin CPU, todos reciben al menos uno (así no hay inanición). Y si entran o salen procesos, los tickets se vuelven a repartir de forma proporcional.
Multicolas
En lugar de una cola de preparados, varias colas, cada una gestionada con una política distinta. Por ejemplo, los procesos interactivos en una cola con Round Robin y los procesos por lotes en otra con FCFS. Las colas se reparten la CPU por prioridad absoluta (no se atiende una cola hasta que las de arriba están vacías) o con un porcentaje de tiempo para cada una.
El dibujo sigue el ejemplo clásico de cuatro colas de más a menos prioridad: procesos del sistema (FCFS), interactivos (RR), interactivos de estudiantes (RR) y por lotes (FCFS). La flecha discontinua es la realimentación: en las multicolas con realimentación, un proceso puede moverse de una cola a otra, por ejemplo si cambia su comportamiento o, como en el UNIX clásico, si lleva mucho tiempo esperando (sube a una cola más prioritaria, que es otra forma de evitar la inanición).
Planificación en multiprocesadores
Con varios procesadores aparecen problemas nuevos:
- Procesamiento asimétrico: un procesador se encarga de planificar el trabajo de los demás. Es una técnica en desuso.
- Procesamiento simétrico (SMP): cada procesador hace su propia planificación. Puede haber una cola de preparados única en memoria compartida o una cola por procesador.
Y dos políticas que tiran en sentidos opuestos:
- Afinidad al procesador: mantener al proceso siempre en el mismo procesador, para que aproveche los datos que ya tiene en la caché de esa CPU.
- Equilibrado de carga: evitar que haya procesadores muy ocupados mientras otros están ociosos. Con migración comandada (push), una tarea supervisora comprueba la carga y traslada procesos; con migración solicitada (pull), un procesador ocioso «roba» procesos a otro más cargado.
Decir que en el procesamiento simétrico «todos los procesadores planifican a todos». No: cada uno planifica lo suyo. El que planifica a los demás es el asimétrico.
Errores típicos
Olvidar restar la llegada. Retorno = fin − llegada; espera = retorno − ráfaga. Con llegadas distintas de 0, fin − ráfaga da un número que parece razonable y está mal.
En SJF no expulsivo, sacar de la CPU al que está dentro porque ha llegado uno más corto. Eso solo lo hace SRTF.
En Round Robin, devolver al expulsado al principio de la cola. Va al final, y conserva lo que le queda (no vuelve a empezar su ráfaga).
Decir que SJF minimiza el tiempo de respuesta medio. Lo que minimiza es el tiempo de espera medio. En respuesta gana Round Robin.
Con dos de las tres magnitudes (retorno, espera, ráfaga) sacas la tercera. Si las tres cuadran (retorno = espera + ráfaga), tus cuentas están bien.
Compruébalo con Python
Los Gantt de este artículo no están hechos a mano: salen de un simulador de 40 líneas que puedes ejecutar tú. No necesitas nada instalado más allá de Python 3 (o pégalo en pythontutor.com eligiendo Python 3 para ver la cola y el diccionario resto cambiar milisegundo a milisegundo).
# La noche antes de entregar: cuatro procesos piden la CPU (tiempos en ms)
PROCESOS = [('onedrive', 0, 8), ('gcc', 1, 4), ('campus', 2, 9), ('spotify', 3, 2)]
Q = 3 # cuanto de Round Robin
def planifica(alg):
llega = {n: l for n, l, r in PROCESOS}
resto = {n: r for n, l, r in PROCESOS} # lo que le QUEDA a cada uno
cola, gantt, actual, usado, t = [], [], None, 0, 0
while any(resto.values()):
cola += [n for n, l, r in PROCESOS if l == t] # los que llegan, al final
if alg == 'RR' and actual and usado == Q: # agotó el cuanto: detrás
cola.append(actual); actual = None # de los recién llegados
if alg == 'SRTF' and actual and cola and min(resto[n] for n in cola) < resto[actual]:
cola.append(actual); actual = None # llega uno más corto: expulsión
if actual is None: # CPU libre: ¿a quién le toca?
if alg in ('SJF', 'SRTF'): # el más corto (empate: el que llegó antes)
actual = min(cola, key=lambda n: (resto[n], llega[n]))
else: # FCFS y RR: el primero de la cola
actual = cola[0]
cola.remove(actual); usado = 0
if gantt and gantt[-1][0] == actual:
gantt[-1][2] = t + 1 # sigue el mismo: se alarga el bloque
else:
gantt.append([actual, t, t + 1]) # cambio de contexto: bloque nuevo
resto[actual] -= 1; usado += 1; t += 1
if resto[actual] == 0:
actual = None # termina y libera la CPU
return gantt
print('proceso llegada ráfaga fin retorno espera respuesta')
for alg in ('FCFS', 'SJF', 'SRTF', 'RR'):
gantt = planifica(alg)
print(f'== {alg}' + (f' (Q = {Q})' if alg == 'RR' else '') + ': ' + ' '.join(f'{n}[{a}-{b}]' for n, a, b in gantt))
medias = [0, 0, 0]
for n, l, r in PROCESOS:
fin = max(b for m, a, b in gantt if m == n) # último instante en CPU
primera = min(a for m, a, b in gantt if m == n) # primera vez que entra
retorno, espera, respuesta = fin - l, fin - l - r, primera - l
medias = [x + y / len(PROCESOS) for x, y in zip(medias, (retorno, espera, respuesta))]
print(f'{n:<9}{l:>8}{r:>8}{fin:>5}{retorno:>11}{espera:>8}{respuesta:>11}')
print(f'{"media":<9}{"":>21}{medias[0]:>11.2f}{medias[1]:>8.2f}{medias[2]:>11.2f}')
La idea es simular la CPU milisegundo a milisegundo: en cada t se meten en la cola los que llegan, se decide si alguien sale (cuanto agotado o expulsión), se elige quién entra si la CPU está libre y se ejecuta 1 ms. Esta es su salida real:
proceso llegada ráfaga fin retorno espera respuesta == FCFS: onedrive[0-8] gcc[8-12] campus[12-21] spotify[21-23] onedrive 0 8 8 8 0 0 gcc 1 4 12 11 7 7 campus 2 9 21 19 10 10 spotify 3 2 23 20 18 18 media 14.50 8.75 8.75 == SJF: onedrive[0-8] spotify[8-10] gcc[10-14] campus[14-23] onedrive 0 8 8 8 0 0 gcc 1 4 14 13 9 9 campus 2 9 23 21 12 12 spotify 3 2 10 7 5 5 media 12.25 6.50 6.50 == SRTF: onedrive[0-1] gcc[1-5] spotify[5-7] onedrive[7-14] campus[14-23] onedrive 0 8 14 14 6 0 gcc 1 4 5 4 0 0 campus 2 9 23 21 12 12 spotify 3 2 7 4 2 2 media 10.75 5.00 3.50 == RR (Q = 3): onedrive[0-3] gcc[3-6] campus[6-9] spotify[9-11] onedrive[11-14] gcc[14-15] campus[15-18] onedrive[18-20] campus[20-23] onedrive 0 8 20 20 12 0 gcc 1 4 15 14 10 2 campus 2 9 23 21 12 4 spotify 3 2 11 8 6 6 media 15.75 10.00 3.00
Las cuatro tablas son las de los dibujos: mismos fines, mismas esperas y mismas medias (8,75, 6,5, 5 y 10 ms de espera). El corazón del simulador son estas líneas:
cola += [n for n, l, r in PROCESOS if l == t] # los que llegan, al final
if alg == 'RR' and actual and usado == Q: # agotó el cuanto: detrás
cola.append(actual); actual = None # de los recién llegados
if alg == 'SRTF' and actual and cola and min(resto[n] for n in cola) < resto[actual]:
cola.append(actual); actual = None # llega uno más corto: expulsión
if actual is None: # CPU libre: ¿a quién le toca?
if alg in ('SJF', 'SRTF'): # el más corto (empate: el que llegó antes)
actual = min(cola, key=lambda n: (resto[n], llega[n]))
else: # FCFS y RR: el primero de la cola
actual = cola[0]
cola.remove(actual); usado = 0
El orden de los if es el criterio de desempate. Primero entran en la cola los que llegan en t (línea de cola +=) y después se pone a la cola el que agota su cuanto: por eso, en t = 3, spotify queda delante de onedrive. En SRTF, el < estricto es la regla de «solo expulsa si es más corto»: en t = 3, como 2 no es menor que 2, gcc sigue dentro. Y la clave (resto[n], llega[n]) del min dice «el que menos le quede y, si empatan, el que llegó antes».
Cosas que observar:
- En la línea de SRTF, onedrive aparece dos veces (
onedrive[0-1]yonedrive[7-14]): es la expulsión de t = 1. Su respuesta es 0 aunque su espera sea 6. - En la tabla de RR, la columna de respuesta (0, 2, 4, 6) es la mejor de todas, aunque la de espera sea la peor.
- En FCFS y SJF, respuesta y espera coinciden siempre: como no expulsan, un proceso solo espera una vez, antes de entrar.
- En las cuatro tablas, el último proceso termina en t = 23 (8 + 4 + 9 + 2): el trabajo total no cambia, solo cambia quién espera.
- Pon
Q = 9y comprueba que la línea de RR sale idéntica a la de FCFS.
El segundo simulador responde a la pregunta del cuanto: repite Round Robin con varios valores de Q y cuenta los cambios de contexto, suponiendo que cada uno cuesta 0,5 ms.
# ¿Qué cuanto elegir? Round Robin con los mismos cuatro procesos y varios Q
PROCESOS = [('onedrive', 0, 8), ('gcc', 1, 4), ('campus', 2, 9), ('spotify', 3, 2)]
CAMBIO = 0.5 # lo que cuesta cada cambio de contexto (ms): guardar un PCB y cargar otro
def round_robin(Q):
resto = {n: r for n, l, r in PROCESOS}
cola, gantt, actual, usado, t = [], [], None, 0, 0
while any(resto.values()):
cola += [n for n, l, r in PROCESOS if l == t] # los que llegan, al final
if actual and usado == Q: # cuanto agotado: al final,
cola.append(actual); actual = None # detrás de los recién llegados
if actual is None:
actual = cola.pop(0); usado = 0 # FIFO circular
if gantt and gantt[-1][0] == actual:
gantt[-1][2] = t + 1
else:
gantt.append([actual, t, t + 1])
resto[actual] -= 1; usado += 1; t += 1
if resto[actual] == 0:
actual = None
return gantt
print(' Q espera media retorno medio respuesta media cambios CPU útil')
for Q in (1, 2, 3, 4, 6, 9):
gantt = round_robin(Q)
espera = retorno = respuesta = 0
for n, l, r in PROCESOS:
fin = max(b for m, a, b in gantt if m == n)
retorno += (fin - l) / len(PROCESOS)
espera += (fin - l - r) / len(PROCESOS)
respuesta += (min(a for m, a, b in gantt if m == n) - l) / len(PROCESOS)
cambios = len(gantt) - 1 # cada bloque nuevo = un cambio
cpu = gantt[-1][2] # ms de trabajo útil (23)
util = 100 * cpu / (cpu + cambios * CAMBIO) # % que no se pierde en cambios
print(f'{Q:>3}{espera:>14.2f}{retorno:>16.2f}{respuesta:>17.2f}{cambios:>10}{util:>10.1f} %')
Su salida, que es la que dibuja la gráfica del cuanto:
Q espera media retorno medio respuesta media cambios CPU útil 1 9.25 15.00 0.75 20 69.7 % 2 9.00 14.75 2.00 10 82.1 % 3 10.00 15.75 3.00 8 85.2 % 4 8.50 14.25 4.50 5 90.2 % 6 10.50 16.25 6.50 5 90.2 % 9 8.75 14.50 8.75 3 93.9 %
- La respuesta media crece con Q (0,75 → 8,75 ms): con cuantos pequeños todos entran enseguida.
- Los cambios de contexto caen de 20 a 3, y la CPU útil sube del 69,7 % al 93,9 %: con Q = 1 se tira casi un tercio de la CPU en guardar y cargar PCB.
- Con Q = 9, espera y retorno medios (8,75 y 14,5) son los de FCFS: el cuanto ya no expulsa a nadie.
- La espera media no baja de forma regular (9,25, 9, 10, 8,5, 10,5, 8,75): depende de en qué momento coinciden los cuantos con las llegadas. No existe un «Q mágico» para todo.
Y si quieres probar tus propios procesos sin escribir código, el simulador de planificación de CPU del Laboratorio dibuja el Gantt de FCFS, SJF, SRTF y Round Robin paso a paso y te da los tiempos medios.
Resumen
| Concepto | Lo que tienes que recordar |
|---|---|
| Planificador | Decide qué proceso preparado entra en la CPU y, si es expulsivo, cuándo sale el de dentro |
| Ráfagas | La vida de un proceso alterna CPU y E/S; la mayoría de ráfagas de CPU duran menos de 8 ms |
| Métricas | Retorno = fin − llegada = espera + CPU; respuesta = primera entrada − llegada |
| No expulsivo / expulsivo | El proceso suelta la CPU él solo / el SO puede sacarlo (necesario en tiempo compartido y real) |
| FCFS | FIFO, no expulsivo, sencillo; efecto convoy y muy sensible al orden |
| SJF / SRTF | El más corto / el de menor tiempo restante; mínima espera media; inanición |
| Round Robin | FIFO circular con cuanto Q; respuesta ≤ Q · (N − 1); Q grande = FCFS, Q pequeño = muchos cambios |
| Prioridades | Entra el más prioritario; inanición → envejecimiento |
| Lotería | CPU proporcional a los tickets; todos al menos uno |
| Multicolas | Una política por cola; con realimentación, los procesos cambian de cola |
| Multiprocesador | Asimétrico (en desuso) o simétrico; afinidad frente a equilibrado (push / pull) |
Tres ideas para llevarte:
- Todo sale del Gantt. Dibuja primero, apunta los fines y después resta: retorno = fin − llegada, espera = retorno − ráfaga. Y nunca te olvides de la llegada.
- No hay algoritmo perfecto. SJF y SRTF ganan en espera media, Round Robin en respuesta, FCFS en sencillez. Cada sistema elige qué métrica sacrificar.
- Los empates se deciden con un criterio, y se escribe. SRTF solo expulsa si el nuevo es estrictamente más corto; en Round Robin, el recién llegado va antes que el que agota su cuanto.
Ahora te toca a ti. Primero, en la práctica guiada de planificación de la CPU resolvemos juntos, paso a paso, problemas de examen con su Gantt y sus cuentas; después, en los ejercicios de planificación de la CPU tienes un test con todos los formatos del examen, cinco Gantt con casillas que se corrigen solas (FCFS, SJF, SRTF y Round Robin con dos cuantos) y las preguntas de desarrollo. Y en el siguiente tema veremos qué pasa cuando estos procesos que se turnan la CPU comparten datos: la concurrencia y las secciones críticas.
Siguiente paso: prácticaPlanificación de la CPU — práctica con problemas guiados paso a paso: FCFS frente a SJF, una expulsión en SRTF, la cola de Round Robin y un ejercicio con el formato del examen (y el cuanto que le regalé a quien no tocaba)¿Te ha servido este artículo? Así puedes apoyar SergioLearns →
Simulacro del examen práctico de IC2 — diagrama de flujo, fork e hilos en C (y las capturas que no pueden faltar)