Planificación de la CPU — ejercicios tipo examen con test, cinco diagramas de Gantt que se corrigen solos y preguntas de desarrollo (y la llegada que ya no se me olvida restar)

Respuesta: Cuál de los procesos preparados entra en la CPU cuando esta queda libre (y, si es expulsivo, cuándo debe salir el que está dentro)

El planificador a corto plazo mira la cola de preparados y decide quién usa la CPU. Lo hace muchísimas veces por segundo, por eso tiene que ser rápido.

• V — Mientras está activo, un proceso alterna ráfagas de CPU con ráfagas de E/S.
• F — La mayoría de las ráfagas de CPU duran más de 100 ms.
• V — Un proceso intensivo en E/S (como un reproductor de música) suele tener ráfagas de CPU cortas.
• F — El planificador reparte la CPU por programas completos, no por ráfagas.

La vida activa de un proceso es una sucesión de ráfagas: calcula un rato (CPU), espera al disco o a la red (E/S), vuelve a calcular…

Las ráfagas de CPU típicas son cortas, de menos de 8 ms: hay muchas cortas y pocas largas. Cada decisión del planificador reparte la siguiente ráfaga, no el programa entero.

• Tiempo de espera → Suma de todos los ratos que el proceso pasa en la cola de preparados
• Tiempo de retorno → Desde que el proceso llega hasta que termina
• Tiempo de respuesta → Desde que llega a la cola hasta que entra en la CPU por primera vez
• Utilización de CPU → Porcentaje del tiempo en que la CPU hace trabajo útil

La que sobra es la definición del cambio de contexto, que no es una métrica de un proceso sino un coste del sistema. Recuerda: retorno = espera + tiempo de CPU.

Respuesta: 7

Retorno = espera + CPU, así que espera = retorno − ráfaga = 12 − 5 = 7 ms.

Respuesta: 5 ms

El tiempo de respuesta solo mira la primera vez que entra en la CPU: 9 − 4 = 5 ms. Lo que pase después (salir y volver) ya cuenta para el retorno y la espera, no para la respuesta.

• Por lotes → Sacar el máximo rendimiento a la CPU
• Interactivo → Que el usuario vea respuestas rápidas
• Tiempo real → Cumplir siempre los plazos marcados

Cada sistema persigue un objetivo distinto y no hay una política óptima para todos los criterios: hay que llegar a un compromiso.

Respuesta: En un algoritmo no expulsivo, el proceso solo deja la CPU cuando termina su ráfaga o se bloquea · Los sistemas de tiempo compartido necesitan planificación expulsiva

En los no expulsivos el proceso puede acaparar la CPU. Los expulsivos (SRTF, Round Robin, prioridades expulsivas) permiten al SO desalojarlo, y por eso son la base del tiempo compartido y del tiempo real.

En FCFS la cola de preparados es una FIFO ordenada por el instante de llegada. Si un proceso muy largo va delante, los cortos se quedan atascados detrás: es el efecto convoy.

FCFS atiende por orden de llegada (FIFO). Su gran problema es el efecto convoy: como un camión lento en una carretera de un carril.

Respuesta: 7,33 ms

Gantt: A de 0 a 10, B de 10 a 12, C de 12 a 15. Esperas: A = 0, B = 10, C = 12. Media = (0 + 10 + 12) / 3 = 7,33 ms.

Con los cortos delante (B, C, A) las esperas serían 0, 2 y 5: media 2,33 ms. Mismo trabajo, un tercio de espera: así de sensible es FCFS al orden.

Respuesta: Es muy sensible al orden en que llegan los procesos · Perjudica a los procesos intensivos en E/S · Es sencillo de implementar

FCFS es simple, pero un proceso de cálculo largo delante hace esperar a todos los interactivos y de E/S (efecto convoy).

Respuesta: Cuando la CPU queda libre, se elige el de ráfaga más corta entre los que están en la cola

SJF (Shortest Job First) no expulsa: el que entra se queda hasta terminar su ráfaga. Solo al quedar libre la CPU se mira quién es el más corto de la cola (si empatan, el que llegó antes).

• V — SJF consigue el menor tiempo medio de espera posible.
• V — Si no paran de llegar procesos cortos, uno largo puede esperar indefinidamente.
• F — Lo que SJF minimiza siempre es el tiempo medio de respuesta.
• F — Los sistemas operativos reales usan SJF puro porque conocen de antemano la duración de cada ráfaga.

SJF minimiza el tiempo medio de espera; su riesgo es la inanición de los procesos largos.

En la práctica no se conoce la siguiente ráfaga: habría que estimarla (por ejemplo, con una media exponencial de las anteriores), y ni así se usa SJF puro.

Respuesta: SRTF

SRTF, Shortest Remaining Time First: el que está en la CPU es desalojado si llega uno cuya ráfaga es más corta que lo que le queda al de dentro.

Respuesta: gcc sigue: solo se expulsa si lo que llega es estrictamente más corto

En SRTF se compara la ráfaga del que llega con el tiempo restante del que ejecuta. Con 4 = 4 no hay expulsión (si en un examen te encuentras otro criterio, indícalo en una línea).

Respuesta: 8

τ(n+1) = 0,5 · 6 + 0,5 · 10 = 3 + 5 = 8 ms. Con α = 0,5 la estimación nueva queda a medio camino entre lo que pasó y lo que se esperaba.

Respuesta: Es un algoritmo expulsivo · La cola de preparados funciona como una FIFO circular · Si un proceso agota su cuanto sin terminar, vuelve al final de la cola

Round Robin es FCFS con un cuanto Q: nadie puede quedarse más de Q seguidos si hay otros esperando. Es el algoritmo típico del tiempo compartido.

Respuesta: 100

Antes que él pueden pasar los otros N − 1 = 5, cada uno como mucho un cuanto: Q · (N − 1) = 20 · 5 = 100 ms.

• Q mayor que todas las ráfagas → Round Robin se comporta igual que FCFS
• Q demasiado pequeño → Muchos cambios de contexto y menos CPU útil
• Q algo mayor que la ráfaga típica → Casi todos terminan en un solo cuanto: buen compromiso

Q tiene que ser mucho mayor que lo que cuesta un cambio de contexto. Con Q enorme no se expulsa a nadie (FCFS); con Q diminuto la CPU se pasa el día cambiando de proceso.

Respuesta: B, C, D, A

Los que llegan se ponen al final de la cola y, en un empate de instante, se suele colocar primero al recién llegado y después al expulsado. Escribe siempre en una línea el criterio que sigues.

Orden correcto:

1. Colocar los bloques en el eje de tiempo según el algoritmo
2. Anotar el instante de fin de cada proceso
3. Calcular el retorno: fin − llegada
4. Calcular la espera: retorno − ráfaga
5. Sumar y dividir entre el número de procesos para las medias

Primero el dibujo y después las cuentas. Todo sale del Gantt: el fin se lee en él, y retorno y espera son restas.

Respuesta: Entra en la CPU el proceso preparado de mayor prioridad · Puede ser expulsiva o no expulsiva · SJF es un caso particular: la prioridad es la duración estimada de la ráfaga

Las prioridades pueden ser internas (las calcula el SO) o externas (las pone el usuario). Su riesgo es la inanición de los de baja prioridad.

Si siempre llegan procesos más prioritarios, uno de baja prioridad puede sufrir inanición. La solución es el envejecimiento, que aumenta poco a poco la prioridad de los que llevan tiempo esperando.

El envejecimiento (aging) hace que esperar tenga premio: tarde o temprano el proceso olvidado se vuelve el más prioritario.

Respuesta: El 75 %

En cada rodaja se sortea un ticket ganador: el tiempo de CPU es proporcional al número de tickets. gcc tiene 3 de 4 → 75 %.

• V — Todos los procesos reciben al menos un ticket, para que ninguno se quede sin CPU.
• F — Para imitar a SRTF, se dan más tickets a los trabajos largos.
• V — Si entran o salen procesos, los tickets se vuelven a repartir de forma proporcional.

Para parecerse a SRTF se dan más tickets a los cortos. Con al menos un ticket cada uno, nadie sufre inanición.

En las multicolas hay varias colas de preparados, cada una con su propia política: por ejemplo, Round Robin para los procesos interactivos y FCFS para los procesos por lotes. Con realimentación, un proceso puede pasar de una cola a otra.

Las colas se reparten la CPU por prioridad absoluta o con un porcentaje de tiempo para cada una. La realimentación permite subir de cola a un proceso que lleva mucho esperando o bajarlo si cambia su comportamiento.

Respuesta: En el procesamiento asimétrico, un procesador planifica el trabajo de los demás · En el simétrico puede haber una cola única compartida o una cola por procesador · La afinidad intenta que un proceso repita procesador para aprovechar su caché

Simétrico (SMP) = cada procesador hace su propia planificación. El equilibrado de carga mueve procesos para que ninguna CPU esté saturada ni parada.

• Migración push → Una tarea supervisora revisa la carga y traslada procesos
• Migración pull → Un procesador ocioso se lleva procesos de otro más cargado
• Afinidad al procesador → Mantener al proceso en la misma CPU por su caché
• Procesamiento asimétrico → Una CPU planifica a todas las demás

Push = empujar (alguien reparte); pull = tirar (el ocioso se lo lleva). La afinidad tira en contra del equilibrado: mover un proceso equilibra la carga pero le hace perder la caché.

Respuesta: Concurrencia, pero no paralelismo

Concurrencia: varias tareas avanzan intercalándose en el tiempo. Paralelismo: se ejecutan simultáneamente en núcleos distintos. Con un núcleo, el planificador decide el turno.

Como todos llegan en t = 0, el retorno coincide con el fin: 6, 9 y 10 (media 25 / 3 = 8,33 ms). Las esperas son 0, 6 y 9: media 15 / 3 = 5 ms.

Si fueran en orden SJF (P3, P2, P1), las esperas serían 0, 1 y 4: media 1,67 ms. Por eso SJF minimiza la espera media.

Respuesta: SJF · SRTF · Prioridades sin envejecimiento

La inanición aparece cuando la regla de elección puede saltarse a alguien siempre. FCFS y Round Robin respetan el orden de la cola, así que todos acaban entrando.

Paso 1, el Gantt. En FCFS se atiende por orden de llegada y nadie expulsa: P1 de 0 a 5, P2 de 5 a 8, P3 de 8 a 15 y P4 de 15 a 17.

Paso 2, retorno = fin − llegada: P1 = 5 − 0 = 5, P2 = 8 − 1 = 7, P3 = 15 − 2 = 13, P4 = 17 − 4 = 13. Media = 38 / 4 = 9,5 ms.

Paso 3, espera = retorno − ráfaga: P1 = 5 − 5 = 0, P2 = 7 − 3 = 4, P3 = 13 − 7 = 6, P4 = 13 − 2 = 11. Media = 21 / 4 = 5,25 ms.

Fíjate en P4: con solo 2 ms de trabajo espera 11, porque llegó detrás de P3 (7 ms). Es el efecto convoy.

t = 0: solo está P1. Entra y, como SJF no expulsa, se queda hasta t = 6 aunque lleguen otros.

t = 6: en la cola esperan P2 (5), P3 (2) y P4 (3). Entra el más corto, P3, hasta t = 8.

t = 8: quedan P2 (5) y P4 (3): entra P4 hasta t = 11. t = 11: solo queda P2, hasta t = 16.

Retornos: 6 − 0 = 6, 16 − 2 = 14, 8 − 3 = 5 y 11 − 5 = 6 (media 31 / 4 = 7,75 ms). Esperas: 0, 14 − 5 = 9, 5 − 2 = 3 y 6 − 3 = 3 (media 15 / 4 = 3,75 ms).

En cada llegada se compara la ráfaga del nuevo con lo que le queda al que está en la CPU.

t = 2: llega P2 (5). A P1 le quedan 6 − 2 = 4. Como 5 > 4, no expulsa. t = 3: llega P3 (2). A P1 le quedan 3. Como 2 < 3, P3 expulsa a P1.

t = 5: P3 termina y llega P4 (3). Restantes: P1 = 3, P2 = 5, P4 = 3. Empate entre P1 y P4: entra el que llegó antes, P1, hasta t = 8. Después P4 (8-11) y P2 (11-16).

Retornos: 8, 14, 2 y 6 (media 30 / 4 = 7,5 ms). Esperas: 8 − 6 = 2, 14 − 5 = 9, 2 − 2 = 0 y 6 − 3 = 3 (media 14 / 4 = 3,5 ms). Respuestas (primera entrada − llegada): 0, 11 − 2 = 9, 3 − 3 = 0 y 8 − 5 = 3 (media 12 / 4 = 3 ms).

Con los mismos datos, SRTF (3,5 ms de espera media) mejora a SJF (3,75 ms).

Lleva la cola apuntada en cada cambio:

t = 2: P1 agota su cuanto y llega P3 → cola [P2, P3, P1]. Entra P2. t = 4: P2 agota su cuanto y llega P4 → cola [P3, P1, P4, P2]. Entra P3.

t = 6: P3 agota → [P1, P4, P2, P3]. Entra P1 (6-8; le queda 1). t = 8: entra P4 (8-10, termina). t = 10: P2 (10-11, termina). t = 11: P3 (11-13, termina). t = 13: P1 (13-14, termina).

Retornos: 14, 10, 11 y 6 (media 41 / 4 = 10,25 ms). Esperas: 14 − 5 = 9, 10 − 3 = 7, 11 − 4 = 7 y 6 − 2 = 4 (media 27 / 4 = 6,75 ms). Respuestas: 0, 2 − 1 = 1, 4 − 2 = 2 y 8 − 4 = 4 (media 7 / 4 = 1,75 ms).

t = 0-4: P1 usa su cuanto entero (le queda 1). En t = 4 llega P4 a la vez que P1 agota: cola [P2, P3, P4, P1].

P2 (4-7) termina antes de agotar el cuanto, P3 (7-11) usa justo 4 y termina, P4 (11-13) termina y P1 (13-14) remata su último milisegundo.

Retornos: 14, 6, 9 y 9 (media 38 / 4 = 9,5 ms). Esperas: 9, 3, 5 y 7 (media 24 / 4 = 6 ms). Respuestas: 0, 3, 5 y 7 (media 15 / 4 = 3,75 ms).

Compara con Q = 2: con el cuanto más grande hay menos cambios (4 frente a 7) y mejor espera media (6 frente a 6,75), pero la respuesta media empeora (3,75 frente a 1,75).

Respuesta modelo:

En la planificación no expulsiva, el proceso que está en la CPU solo la abandona cuando él mismo lo pide: al terminar su ráfaga de CPU o al bloquearse esperando una E/S. El planificador únicamente decide cuando la CPU queda libre. Son no expulsivos FCFS y SJF. Su riesgo es el acaparamiento: un proceso con una ráfaga muy larga hace esperar a todos los demás.

En la planificación expulsiva, el sistema operativo puede desalojar al proceso que está ejecutando, por ejemplo cuando llega otro con una ráfaga más corta (SRTF) o de mayor prioridad, o cuando se agota su cuanto (Round Robin), algo que detecta gracias a la interrupción del temporizador. El tiempo compartido necesita expulsión porque tiene que garantizar a cada usuario respuestas rápidas aunque haya procesos que calculen sin parar; el tiempo real la necesita para atender a tiempo las tareas con plazo.

Respuesta modelo:

FCFS atiende a los procesos por orden de llegada con una cola FIFO y no expulsa. Es el más sencillo, pero es muy sensible al orden: si un proceso largo va delante, los cortos esperan mucho detrás de él (efecto convoy), lo que perjudica a los procesos intensivos en E/S.

SJF elige, cuando la CPU queda libre, el proceso con la ráfaga de CPU más corta. Minimiza el tiempo medio de espera, pero puede provocar la inanición de los procesos largos si no paran de llegar cortos, y además exige conocer la siguiente ráfaga, que en la práctica solo se puede estimar. Su versión expulsiva es SRTF.

Round Robin es un FCFS expulsivo: cada proceso usa la CPU como mucho un cuanto Q y, si no termina, vuelve al final de la cola. Reparte la CPU de forma equitativa y da buenos tiempos de respuesta, por lo que es el típico de los sistemas interactivos; su problema es elegir bien Q, porque con un Q muy grande se comporta como FCFS y con uno muy pequeño se pierde mucho tiempo en cambios de contexto.

Respuesta modelo:

En Round Robin cada proceso puede usar la CPU como mucho durante un cuanto Q seguido; si no termina, vuelve al final de la cola de preparados. Con N procesos en la cola, un proceso espera como mucho Q · (N − 1) hasta volver a entrar, así que Q marca directamente el tiempo de respuesta.

Si Q es muy grande, mayor que las ráfagas de CPU, los procesos terminan su ráfaga antes de agotar el cuanto y el algoritmo se comporta igual que FCFS, con sus problemas de efecto convoy. Si Q es muy pequeño, la CPU se reparte de forma muy uniforme, como si cada proceso tuviera un procesador N veces más lento, pero aumentan los cambios de contexto y se pierde tiempo de CPU guardando y cargando PCB. Por eso Q debe ser bastante mayor que lo que cuesta un cambio de contexto y, a ser posible, algo mayor que la ráfaga típica; en la práctica suele estar entre 1 y 200 ms, y sistemas como Linux lo ajustan según la carga.

Respuesta modelo:

En la planificación por prioridades cada proceso tiene una prioridad, que puede asignar el sistema operativo (interna) o el usuario (externa), y entra en la CPU el proceso preparado de mayor prioridad. Puede ser expulsiva, si un proceso más prioritario que llega desaloja al que está ejecutando, o no expulsiva. SJF es un caso particular en el que la prioridad es la duración estimada de la ráfaga.

Su problema es la inanición: si siempre hay procesos más prioritarios, uno de baja prioridad puede esperar indefinidamente. La solución clásica es el envejecimiento (aging), que aumenta poco a poco la prioridad de los procesos que llevan tiempo esperando hasta que acaban entrando. Las multicolas organizan los preparados en varias colas con políticas distintas (por ejemplo, Round Robin para interactivos y FCFS para lotes) que se reparten la CPU por prioridad o por porcentaje de tiempo; con realimentación, un proceso puede cambiar de cola, de modo que el que lleva mucho tiempo esperando sube a una cola más prioritaria.