04. Planificación de CPU

Abrir las diapositivas de apoyo: Planificación de CPU (pantalla completa)

El bloque anterior ha distinguido los procesos listos de los bloqueados. El planificador solo puede asignar CPU a quienes están preparados. Resolveremos modelos simplificados para entender las decisiones, sin suponer que un SO actual use exclusivamente uno de estos algoritmos para todas sus tareas.

4.1. Planificador a corto plazo

El planificador a corto plazo decide cuál de los procesos listos obtiene la CPU a continuación. Los algoritmos que veremos usan una simplificación útil para aprender:

Una única unidad de ejecución: solo un proceso ejecuta en cada instante del modelo.
Todos los tiempos están expresados en unidades enteras.
No hay coste de cambio de contexto, salvo que se indique.
La llegada de un proceso a la cola de preparados se anota como llegada.
No hay bloqueos de E/S: cada proceso solo necesita recibir tiempo de CPU hasta completar el trabajo indicado.

La ráfaga de CPU es la cantidad de tiempo de ejecución que necesita un proceso antes de terminar o de bloquearse, por ejemplo, para esperar una operación de E/S. En nuestros ejercicios no hay esos bloqueos: la columna ráfaga de CPU indica cuánto tiempo de CPU necesita el proceso para terminar. No incluye el tiempo que pasa esperando su turno.

Por ejemplo, una ráfaga de 5 significa que el proceso necesita cinco unidades de uso de CPU. Puede recibirlas seguidas o repartidas en varios turnos: con Round Robin y quantum 2, podría ejecutar 2 + 2 + 1. Si además pasa cuatro unidades esperando, habrá permanecido nueve unidades en el sistema: cinco ejecutando y cuatro esperando. Su ráfaga sigue siendo cinco.

Para cada proceso calcularemos estas métricas:

Métrica	Cálculo	Significado
Instante de finalización	Instante en que termina.	Cuándo acaba el proceso.
Tiempo de retorno	`finalización - llegada`	Tiempo total dentro del sistema.
Tiempo de espera	`retorno - ráfaga`	Tiempo que pasó listo sin usar CPU.
Tiempo de respuesta	Primer uso de CPU `- llegada`	Espera hasta recibir CPU por primera vez.

4.2. Algoritmo FCFS/FIFO

FCFS (First Come, First Served), también llamado FIFO (First In, First Out), ejecuta los procesos por orden de llegada. Una vez que un proceso empieza, no se interrumpe hasta terminar su ráfaga: es un algoritmo no expropiativo.

Ejemplo resuelto 1: FCFS

Proceso	Llegada	Ráfaga de CPU
P1	0	5
P2	1	3
P3	2	1
P4	3	2

P1 llega primero y ejecuta de 0 a 5. Mientras tanto llegan P2, P3 y P4, que esperan por orden de llegada. Después se ejecutan P2, P3 y P4.

Cronograma FCFS: P1 ejecuta de 0 a 5; P2 espera de 1 a 5 y ejecuta de 5 a 8; P3 espera de 2 a 8 y ejecuta de 8 a 9; P4 espera de 3 a 9 y ejecuta de 9 a 11.

Las barras claras muestran la espera desde la llegada; las oscuras, el uso de CPU. Su anchura es proporcional al tiempo y las etiquetas indican la duración de cada tramo.

Proceso	Finalización	Retorno	Espera
P1	5	5 - 0 = 5	5 - 5 = 0
P2	8	8 - 1 = 7	7 - 3 = 4
P3	9	9 - 2 = 7	7 - 1 = 6
P4	11	11 - 3 = 8	8 - 2 = 6
Media		6,75	4,00

FCFS es sencillo y previsible, pero puede provocar el efecto convoy: un proceso largo al principio obliga a esperar a muchos procesos cortos que llegan detrás.

4.2.1. Practica FCFS

RA2.b.

Proceso	Llegada	Ráfaga de CPU
P1	0	6
P2	1	3
P3	2	1
P4	4	2

Aplica FCFS sin interrumpir la ráfaga de ningún proceso. Si dos procesos llegan a la vez, desempata por el orden de la tabla. Usa una única unidad de ejecución, sin bloqueos de E/S ni coste de cambio de contexto; los tiempos se expresan en unidades enteras.

Dibuja un cronograma con una fila por proceso y distingue la espera de la ejecución. Completa la tabla y calcula las medias de retorno, espera y respuesta.

Proceso	Primer inicio	Finalización
P1
P2
P3
P4
Media	—	—

Explica por qué P3 debe esperar aunque su ráfaga sea la más corta.

Comprueba que cada proceso recibe exactamente su ráfaga, que ninguna espera es negativa y que el tiempo total de CPU ocupado es 12 unidades.

4.3. Algoritmo SJF/SRTF

SJF (Shortest Job First) selecciona, entre los procesos listos, el que tiene la menor ráfaga de CPU y lo deja terminar: aquí estudiaremos su versión no expropiativa. Su versión expropiativa es SRTF (Shortest Remaining Time First): si llega un proceso cuya ráfaga restante es menor que la del proceso actual, lo sustituye.

SJF necesita conocer o estimar la duración de la ráfaga. En la práctica no se conoce con certeza, pero el sistema puede estimarla a partir del comportamiento anterior.

Ejemplo resuelto: SJF no expropiativo

Proceso	Llegada	Ráfaga de CPU
P1	0	5
P2	1	3
P3	2	1
P4	3	2

En el instante 0 solo está P1; SJF lo deja terminar en 5 aunque lleguen procesos cortos. Entonces elige P3, después P4 y por último P2.

P1 llega en 0 y ejecuta de 0 a 5; espera total: 0. P2 llega en 1 y ejecuta de 8 a 11; espera total: 7. P3 llega en 2 y ejecuta de 5 a 6; espera total: 3. P4 llega en 3 y ejecuta de 6 a 8; espera total: 3.

Las barras claras muestran la espera y las oscuras, la ejecución. Tras P1, SJF elige P3, después P4 y finalmente P2, según la ráfaga más corta entre los procesos listos.

Proceso	Finalización	Retorno	Espera
P1	5	5	0
P2	11	10	7
P3	6	4	3
P4	8	5	3
Media		6,00	3,25

Este ejemplo muestra la diferencia con SRTF: llegar con una ráfaga corta no interrumpe al proceso que ya ejecuta en SJF no expropiativo.

4.3.1. Practica SJF no expropiativo

RA2.b.

Proceso	Llegada	Ráfaga de CPU
P1	0	6
P2	1	3
P3	2	1
P4	4	2

Aplica SJF no expropiativo. Compara las ráfagas solo entre procesos que ya han llegado. Desempata por llegada y después por el orden de la tabla. Usa una única unidad de ejecución, sin bloqueos de E/S ni coste de cambio de contexto; los tiempos se expresan en unidades enteras.

Dibuja un cronograma con una fila por proceso y distingue la espera de la ejecución. Completa la tabla y calcula las medias de retorno, espera y respuesta.

Proceso	Primer inicio	Finalización
P1
P2
P3
P4
Media	—	—

Indica qué procesos están listos cuando termina P1 y justifica cuál ejecuta a continuación.

Comprueba que cada proceso recibe exactamente su ráfaga, que ninguna espera es negativa y que el tiempo total de CPU ocupado es 12 unidades.

Ejemplo resuelto 2: SRTF

SRTF significa Shortest Remaining Time First: primero el proceso con menor tiempo restante de CPU. Es la variante expropiativa de SJF: el planificador puede interrumpir al proceso que está ejecutando y asignar la CPU a otro. El proceso interrumpido vuelve a la cola de preparados y conserva el trabajo ya realizado; cuando reciba CPU de nuevo, continuará con el tiempo que le quede pendiente.

En SRTF, esa interrupción ocurre si llega un proceso que necesita menos tiempo de CPU que el que le queda al proceso actual. En cambio, SJF no expropiativo deja terminar la ráfaga del proceso elegido, aunque mientras tanto llegue otro más corto. Usamos los mismos procesos del ejemplo resuelto de SJF, recogidos de nuevo en esta tabla.

Proceso	Llegada	Ráfaga
P1	0	5
P2	1	3
P3	2	1
P4	3	2

En t=0, solo existe P1: ejecuta durante una unidad. Le quedan 4.
En t=1, llega P2 con ráfaga 3. Como 3 < 4, P2 sustituye a P1.
En t=2, llega P3 con ráfaga 1. Como 1 < 2 que le queda a P2, P3 ejecuta y termina.
En t=3, llega P4. P2 y P4 tienen ambos 2 unidades restantes; mantenemos el que ya estaba listo antes, P2.
Al terminar P2, se ejecuta P4 y finalmente P1.

P1 llega en 0 y ejecuta de 0 a 1, de 7 a 11; espera total: 6. P2 llega en 1 y ejecuta de 1 a 2, de 3 a 5; espera total: 1. P3 llega en 2 y ejecuta de 2 a 3; espera total: 0. P4 llega en 3 y ejecuta de 5 a 7; espera total: 2.

Las barras claras incluyen también la espera después de una interrupción. P1 ejecuta una unidad, espera seis y completa sus cuatro unidades restantes al final.

Proceso	Finalización	Retorno	Espera
P1	11	11 - 0 = 11	11 - 5 = 6
P2	5	5 - 1 = 4	4 - 3 = 1
P3	3	3 - 2 = 1	1 - 1 = 0
P4	7	7 - 3 = 4	4 - 2 = 2
Media		5,00	2,25

SRTF mejora la espera media en este caso porque termina antes los trabajos cortos. Sin embargo, si siguen llegando procesos breves, uno largo puede retrasarse mucho: este riesgo se denomina inanición.

4.3.2. Practica SRTF

RA2.b.

Proceso	Llegada	Ráfaga de CPU
P1	0	6
P2	1	3
P3	2	1
P4	4	2

Aplica SRTF: revisa el tiempo restante en cada llegada y al terminar un proceso. En un empate conserva al que está ejecutando; si la CPU queda libre, desempata por llegada y después por el orden de la tabla. Usa una única unidad de ejecución, sin bloqueos de E/S ni coste de cambio de contexto; los tiempos se expresan en unidades enteras.

Dibuja un cronograma con una fila por proceso y distingue la espera de la ejecución. Completa la tabla y calcula las medias de retorno, espera y respuesta.

Proceso	Primer inicio	Finalización
P1
P2
P3
P4
Media	—	—

Explica las decisiones de los instantes 1, 2 y 4. Distingue la primera respuesta de P1 de su espera total.

Comprueba que cada proceso recibe exactamente su ráfaga, que ninguna espera es negativa y que el tiempo total de CPU ocupado es 12 unidades.

4.4. Algoritmo Round Robin

Round Robin reparte la CPU en turnos de duración máxima fija, llamada quantum. Cuando el quantum termina, el proceso vuelve al final de la cola de preparados si todavía necesita CPU. Es un algoritmo expropiativo y adecuado para sistemas interactivos, porque evita que un proceso largo monopolice la CPU.

Ejemplo resuelto 3: Round Robin con quantum 2

Para aislar el funcionamiento de la cola, suponemos que todos los procesos llegan en t=0.

Proceso	Ráfaga
P1	5
P2	3
P3	1

P1 usa dos unidades y le quedan 3: vuelve al final de la cola.
P2 usa dos unidades y le queda 1: vuelve al final.
P3 necesita solo una unidad y termina.
P1 usa otras dos unidades y le queda 1.
P2 termina en su siguiente turno y P1 termina al final.

P1 llega en 0 y ejecuta de 0 a 2, de 5 a 7, de 8 a 9; espera total: 4. P2 llega en 0 y ejecuta de 2 a 4, de 7 a 8; espera total: 5. P3 llega en 0 y ejecuta de 4 a 5; espera total: 4.

Cada barra oscura representa un turno de CPU de hasta dos unidades. Las barras claras muestran cómo cada proceso espera entre sus turnos; el último turno puede ser más corto que el quantum.

Proceso	Finalización	Retorno	Espera
P1	9	9	9 - 5 = 4
P2	8	8	8 - 3 = 5
P3	5	5	5 - 1 = 4
Media		7,33	4,33

Round Robin ofrece una respuesta inicial equilibrada: todos los procesos reciben CPU pronto. Su resultado depende mucho del quantum:

Con un quantum muy grande, se comporta de forma parecida a FCFS.
Con un quantum pequeño, los procesos pueden recibir antes su primera atención, pero pueden aumentar los cambios de contexto. El efecto depende de la carga y del tamaño de las ráfagas.

4.4.1. Practica Round Robin

RA2.b.

Proceso	Llegada	Ráfaga de CPU
P1	0	4
P2	0	3
P3	0	2

Aplica Round Robin con quantum 2. Todos llegan en 0 y la cola inicial es P1, P2, P3. Cuando se agota el turno, reencola el proceso al final solo si le queda CPU pendiente. Usa una única unidad de ejecución, sin bloqueos de E/S ni coste de cambio de contexto; los tiempos se expresan en unidades enteras.

Dibuja un cronograma con una fila por proceso y distingue la espera de la ejecución. Completa la tabla y calcula las medias de retorno, espera y respuesta.

Proceso	Primer inicio	Finalización
P1
P2
P3
Media	—	—

Anota la cola, de primero a último, justo después de finalizar el turno de los instantes 2, 4 y 6. Explica por qué P3 no vuelve a la cola.

Comprueba que cada proceso recibe exactamente su ráfaga, que ninguna espera es negativa y que el tiempo total de CPU ocupado es 9 unidades.

4.6. Planificación por prioridades

Cada proceso recibe un nivel de prioridad. El planificador selecciona el más prioritario de la cola de listos. Debe indicarse si un número pequeño o grande significa mayor prioridad y si el algoritmo permite expropiación. En el modelo no expropiativo, el proceso elegido conserva CPU hasta terminar su ráfaga; en el expropiativo, una llegada de mayor prioridad puede interrumpirlo.

Una prioridad fija puede retrasar indefinidamente trabajos poco prioritarios. El envejecimiento aumenta progresivamente la prioridad de quienes llevan mucho tiempo esperando para reducir ese riesgo. Prioridad no equivale a duración: un trabajo largo puede ser urgente.

Ejemplo resuelto: prioridades no expropiativas

Proceso	Ráfaga de CPU	Prioridad
A	4	2
B	2	1
C	3	3

Los tiempos se expresan en unidades. Un número menor indica mayor prioridad.

A llega en 0 y ejecuta de 2 a 6; espera total: 2. B llega en 0 y ejecuta de 0 a 2; espera total: 0. C llega en 0 y ejecuta de 6 a 9; espera total: 6.

Las barras claras muestran la espera y las oscuras, la ejecución. B usa la CPU primero por tener prioridad 1; después ejecutan A y C, sin interrupciones.

B no se elige por ser corto, sino por prioridad. Las esperas son A=2, B=0 y C=6; la espera media es 8/3 ≈ 2,67. Los retornos son A=6, B=2 y C=9; media 17/3 ≈ 5,67.

4.6.1. Practica prioridades no expropiativas

RA2.b.

Proceso	Ráfaga de CPU	Prioridad
A	3	2
B	5	1
C	2	3

Aplica prioridades no expropiativas. Un número menor indica mayor prioridad. Todos llegan en 0; en caso de empate, usa el orden de la tabla. Usa una única unidad de ejecución, sin bloqueos de E/S ni coste de cambio de contexto; los tiempos se expresan en unidades enteras.

Dibuja un cronograma con una fila por proceso y distingue la espera de la ejecución. Completa la tabla y calcula las medias de retorno, espera y respuesta.

Proceso	Primer inicio	Finalización
A
B
C
Media	—	—

Justifica por qué B ejecuta primero aunque su ráfaga sea la más larga y explica qué cambiaría si usaras SJF no expropiativo.

Comprueba que cada proceso recibe exactamente su ráfaga, que ninguna espera es negativa y que el tiempo total de CPU ocupado es 10 unidades.

4.7. Comparación de algoritmos de planificación

Algoritmo	Tipo	Ventaja principal	Limitación principal	Contexto apropiado
FCFS/FIFO	No expropiativo	Sencillo y previsible.	Efecto convoy; respuesta pobre ante trabajos largos.	Procesos por lotes simples.
SJF/SRTF	SJF no expropiativo; SRTF expropiativo	Reduce la espera media cuando se estiman bien las ráfagas.	Requiere estimaciones; puede causar inanición.	Lotes con trabajos de duración previsible.
Prioridades	Según la variante; aquí no expropiativo	Atiende trabajos con mayor prioridad.	Puede causar inanición sin medidas como envejecimiento.	Cargas con importancia o urgencia diferenciadas.
Round Robin	Expropiativo	Reparte respuesta entre procesos y evita monopolios.	Depende del quantum y puede generar más cambios de contexto.	Sistemas interactivos y uso compartido.

No existe un algoritmo universalmente mejor. Un servidor de cálculo por lotes puede priorizar el rendimiento medio; un escritorio interactivo debe evitar que una aplicación larga deje sin respuesta a las demás; un sistema de tiempo real necesita además cumplir plazos definidos.

4.8. Una misma carga, distintas decisiones

RA2.b.

Reutilizarás este producto en la práctica integrada de funcionamiento del SO, apartado 6.8; no tiene una nota ni una entrega separadas. En 4.8, solo se incorporan FCFS y RR.

Resuelve esta carga con FCFS, SJF no expropiativo, SRTF, Round Robin con quantum 2 y prioridades no expropiativas.

Proceso	Llegada	Ráfaga	Prioridad
A	0	6	3
B	1	2	1
C	2	4	2
D	4	1	1

Reglas comunes: una única unidad de ejecución, sin E/S ni coste de contexto; solo un proceso ejecuta en cada instante. Desempata por llegada y después orden A, B, C, D. En prioridades, menor número significa mayor prioridad. En SRTF conserva al que ejecuta si su tiempo restante empata con una nueva llegada. En RR, las llegadas que coinciden con el fin de quantum se incorporan a la cola antes de reencolar el proceso que agota su turno; las que llegaron durante el turno ya están esperando.

Para cada uno de los cinco algoritmos dibuja Gantt y completa una copia de esta tabla:

Proceso	Primer inicio	Finalización	Retorno	Espera	Respuesta
A
B
C
D
Media

Comprueba que se ejecutan exactamente 13 unidades de CPU y que ninguna espera es negativa. Explica qué decisión favorece a D y por qué una mejora de la media no garantiza mejorar cada proceso. Entrega los diagramas, tablas y comparación razonada.

4.9. El tamaño del turno

RA2.b.

Todos llegan en 0 y se encolan A, B, C. Sus ráfagas son A=5, B=4 y C=2. Resuelve RR con quantum 2 y quantum 4, sin coste de contexto ni E/S. Compara primer inicio, finalización y respuesta de cada proceso. Cuenta cambios de proceso entre intervalos consecutivos, sin contar el arranque inicial ni la salida final.

Completa esta tabla y entrega ambos Gantt:

Proceso	Primer inicio q2	Finalización q2	Respuesta q2	Primer inicio q4	Finalización q4	Respuesta q4
A
B
C

Añade el número de cambios entre procesos para cada quantum. Explica qué quantum reparte antes la primera atención y por qué turnos más cortos pueden aumentar el coste real aunque nuestro cálculo lo omita.

4.10. Elegir una política

RA2.b.

Un equipo comparte CPU entre tareas de cálculo largas y una interfaz que debe responder a pulsaciones. Otro equipo procesa por lotes trabajos cuyas ráfagas se estiman razonablemente. Propón una política para cada escenario entre FCFS, SJF, RR y prioridades, explica una ventaja y un riesgo, y describe cómo el envejecimiento ayuda cuando se usan prioridades. Se aceptan alternativas justificadas; no se pide identificar el planificador real de un producto.

La CPU no puede trabajar con cualquier dato directamente desde el disco. El siguiente bloque estudia cómo el SO organiza el espacio de memoria de cada proceso.