Teoría de scheduling (clase sem. 12)

💡 En simple

La CPU es una sola ventanilla y hay muchos procesos en la cola. Cada cierto tiempo pasa algo (suena el reloj, termina una lectura de disco, un proceso pide algo al SO) y el scheduler decide quién usa la ventanilla. El dispatcher es quien hace el cambio físico: guarda el estado del que sale y carga el del que entra. Esa decisión se mide con varios relojes: cuánto esperó cada uno, cuánto tardó en terminar, cuánto tardó en recibir la primera respuesta y cuántos terminaron por hora. Ningún algoritmo gana en todos.

🎯 Al terminar podrás

1. Decir en qué 4 momentos decide el scheduler y cuáles corresponden a un scheduler no expropiativo.
2. Definir y calcular turnaround, waiting y response time, y decir cuáles se maximizan y cuáles se minimizan.
3. Explicar el convoy effect, la starvation y el aging con un ejemplo.
4. Estimar la próxima ráfaga con el promedio exponencial.
5. Distinguir interrupción y trap, y explicar por qué Linux divide el manejo de interrupciones en top half y bottom half.

Antes necesitas: Estados de un proceso y PCB · Interrupciones (hardware)

• Visual mira el diagrama o la tabla y explica qué cambia en cada paso
• Socrático responde la pregunta guía antes de seguir leyendo
• Feynman explícalo en voz alta sin mirar y compara con la lista

1. Cómo se cambia de proceso

Las diapositivas empiezan recordando cómo el SO recupera la CPU:

	Interrupción	Trap
Origen	un evento externo al proceso que corre	un error o excepción dentro del proceso que corre
Ejemplos	reloj (fin del time slice), E/S terminada, fallo de memoria	división por cero, instrucción inválida, syscall
Qué hace el SO	atiende y, si corresponde, llama al scheduler	decide si es fatal (el proceso pasa a Exit) o lo atiende

Cómo leerlo: las dos flechas terminan en el mismo lugar (el SO en modo kernel); la diferencia es de dónde salen. La interrupción viene de un dispositivo o del reloj, sin relación con la instrucción que corría. El trap lo dispara esa misma instrucción.

El time slice es el tiempo máximo que un proceso puede correr antes de ser interrumpido por el reloj. Sin interrupción de reloj no hay expropiación: un proceso con un bucle infinito nunca soltaría la CPU.

Manejo de una interrupción: se guarda el PC, se deshabilitan las interrupciones, se pasa a modo kernel, se saltan al handler por el vector de interrupciones, se guardan los registros, se atiende, se restauran los registros y el PC, y se vuelve a modo usuario. Todo eso usa la pila de kernel del hilo, no la pila de usuario.

Cómo leerlo: la fila de arriba ocurre sola, en el hardware, en cuanto llega la interrupción. La de abajo es código del SO. El paso verde es donde puede cambiar quién corre: si el scheduler elige otro proceso, el paso 7 restaura los registros de ese otro.

yield en hilos de kernel y de usuario: con hilos de kernel, ceder la CPU es una syscall (un trap, caro). Con hilos de usuario es una llamada a una función de biblioteca (barato), pero si un hilo de usuario hace una E/S bloqueante, el kernel bloquea todo el proceso, porque no sabe que tiene varios hilos.

Interrupciones anidadas y la solución de Linux

Anidar es dejar que una interrupción nueva interrumpa al handler de otra que todavía no terminó. Así un evento urgente no espera, pero cada nivel guarda su estado encima del anterior:

Cómo leerlo: arriba, la cronología: B llega mientras corre el handler de A, así que A queda en pausa hasta que B termina. A la derecha, la pila de kernel: cada interrupción anidada apila otro juego de registros.

Permitir que una interrupción interrumpa a otra mejora la respuesta, pero obliga a que el código del handler sea reentrante, hace más probable un desborde de pila y complica la depuración. Linux lo resuelve partiendo el trabajo en dos:

Parte	Interrupciones	Qué hace
Top half	deshabilitadas	lo mínimo y urgente; marca que hay trabajo pendiente
Bottom half: softirqs y tasklets	habilitadas	trabajo de duración media que no duerme; se revisa al volver del top half o en los hilos ksoftirqd
Bottom half: work queues	habilitadas	trabajo lento o que puede dormir, en hilos de kernel

En simple: es como la recepción de un restaurante. La recepcionista (top half) solo anota el pedido y avisa; no puede dejar sonar el teléfono mucho tiempo. El cocinero (softirq o tasklet) lo prepara después, y mientras cocina el teléfono puede volver a sonar y se atiende. Si el plato necesita un insumo que hay que esperar, lo hace alguien que puede quedarse esperando (work queue).

¿Por qué el softirq no puede dormir y la work queue sí? Dormir es pasar a waiting y que el scheduler elija a otro, y eso solo se puede hacer con un hilo que después se despierte. El softirq corre «prestado» encima de lo que estaba en la CPU, sin hilo propio. La work queue corre en un hilo de kernel, así que puede bloquearse como cualquier hilo.

Cómo leerlo: la fila de abajo dice si las interrupciones están habilitadas. Solo se apagan durante los top halves, que son muy cortos. Por eso la interrupción 2, que llega en medio del softirq, se atiende enseguida. El trabajo que tiene que esperar algo se va a una work queue, que puede dormir.

Además, las excepciones en el kernel se anidan como mucho a dos niveles: una excepción y un page fault provocado por su propio handler (por ejemplo, al leer una página de usuario que estaba en swap).

🔮 Predice antes de seguir

Una tarea del kernel toma el runq_lock (un spinlock) para agregar un proceso a la cola de listos. En ese momento llega una interrupción de reloj en el mismo núcleo y el scheduler intenta tomar el mismo lock. ¿Qué pasa?

Ya tengo mi respuesta: comparar

Deadlock en un solo núcleo. El handler gira esperando el lock, pero el dueño del lock es el código que el propio handler interrumpió: nunca volverá a correr hasta que el handler termine. Es el «deadlock de un hilo» que ya viste en el LC3. Por eso, en el kernel, un spinlock que también se usa desde interrupciones se toma deshabilitando las interrupciones locales (spin_lock_irqsave). Sin soporte multinúcleo, un spinlock de Linux se reduce justamente a eso: guardar el estado de interrupciones y deshabilitarlas.

Cómo leerlo: en (a), la tarea tiene el lock y el handler lo pide en el mismo núcleo: el handler gira para siempre y la tarea nunca vuelve a correr para soltarlo. En (b), la tarea apaga las interrupciones antes de tomar el lock: el reloj queda pendiente y se atiende recién cuando el lock está libre.

Del Big Kernel Lock al bloqueo fino. Cuando Linux agregó soporte multinúcleo (1996), usó un único lock que se tomaba al entrar al kernel: era simple y el código de usuario seguía siendo paralelo, pero solo un núcleo podía estar dentro del kernel a la vez. Con los años se reemplazó por locks de grano fino.

2. ¿A quién elegir? IO-bound y CPU-bound

• IO-bound: pasa casi todo el tiempo esperando E/S. Sus ráfagas de CPU son cortas.
• CPU-bound: calcula mucho y hace poca E/S. Sus ráfagas son largas.
• Un proceso puede cambiar de comportamiento, y el scheduler debe notarlo.

En general conviene favorecer a los IO-bound: usan la CPU un instante, lanzan su próxima E/S y así el disco o la red trabajan en paralelo con la CPU. La ejecución de un proceso es un ciclo: ráfaga de CPU, ráfaga de E/S, ráfaga de CPU… El histograma de ráfagas tiene muchísimas ráfagas cortas y pocas largas, y eso es lo que justifica favorecer a los procesos de ráfaga corta.

Cómo leerlo: arriba, la vida de cada proceso como alternancia de ráfagas de CPU y de espera de E/S. Abajo, la forma típica del histograma de duraciones de ráfagas de CPU: la mayoría son cortas (verde). Es una forma cualitativa, no datos medidos.

Convoy effect, starvation y aging

• Convoy effect: en FCFS, un proceso CPU-bound largo delante de varios IO-bound los hace esperar a todos, como un camión lento en una carretera de un carril con autos detrás. Mientras tanto, el disco y la red quedan ociosos, porque los IO-bound no pueden lanzar su próxima E/S.
• Starvation (inanición): un proceso listo que nunca llega a correr porque siempre hay otro preferido. Por ejemplo, uno de baja prioridad cuando no paran de llegar procesos de prioridad alta.
• Aging (envejecimiento): subir poco a poco la prioridad de quien lleva mucho esperando. Tarde o temprano pasa a ser el más prioritario y corre. Es la solución clásica a la starvation.

Cómo leerlo: la misma carga en dos órdenes. En (a), el CPU-bound va primero y los tres IO-bound esperan detrás, con el disco en rojo (ocioso). En (b), los IO-bound usan la CPU un instante cada uno y sus lecturas de disco se superponen con el cálculo largo de P1.

3. Cuándo decide el scheduler

El short-term scheduler elige entre los procesos de la cola de listos. Puede decidir cuando un proceso:

1. pasa de running a waiting (pide E/S, hace wait);
2. pasa de running a ready (interrupción de reloj);
3. pasa de waiting a ready (termina su E/S);
4. termina.

Cómo leerlo: los números son los cuatro momentos de la lista. En ① y ④ la CPU queda libre sola y alguien tiene que elegir, así que decide cualquier scheduler. En ② y ③ el proceso que corre podría seguir: decidir ahí es expropiar.

Si solo decide en 1 y 4, el scheduling es no expropiativo (nonpreemptive): el proceso suelta la CPU por su cuenta. Si decide también en 2 y 3, es expropiativo (preemptive), y aparecen problemas nuevos: datos compartidos que quedan a medio actualizar, expropiación en modo kernel e interrupciones durante operaciones críticas del SO.

El dispatcher entrega la CPU al proceso elegido: cambia el contexto, pasa a modo usuario y salta a la instrucción donde el programa se había quedado. La dispatch latency es el tiempo que tarda en detener uno y arrancar otro.

Cómo leerlo: durante la dispatch latency no corre ningún proceso de usuario: es tiempo de CPU gastado solo en cambiar. Por eso un quantum demasiado chico es malo: se pagaría este costo muy seguido.

Hilos: cuando el SO soporta hilos, se planifican hilos, no procesos. Si una biblioteca planifica hilos de usuario sobre LWPs, la competencia es dentro del proceso (PCS, process-contention scope); si el kernel planifica hilos de kernel en las CPUs, la competencia es entre todos los hilos del sistema (SCS, system-contention scope).

4. Criterios: qué se mide

Criterio	Definición	Se busca
Utilización de CPU	porcentaje del tiempo en que la CPU está ocupada	máx
Throughput	procesos terminados por unidad de tiempo	máx
Turnaround	desde que llega hasta que termina	mín
Waiting time	tiempo total en la cola de listos	mín
Response time	desde que llega hasta su primera respuesta (primera vez que corre)	mín

Las fórmulas que pide la hoja de ejercicios:

turnaround = completion - arrival
waiting    = turnaround - burst
response   = first_run  - arrival

Peldaño 1 · Resueltolee cada paso y su porqué

Resuelto: las tres métricas de un proceso

P3 llega en t = 4 con ráfaga 2. En SJF no expropiativo (la hoja, ej. 7) corre de 7 a 9.

• turnaround = 9 − 4 = 5
• waiting = 5 − 2 = 3 (estuvo listo de 4 a 7)
• response = 7 − 4 = 3

En un algoritmo no expropiativo, waiting = response, porque cuando un proceso empieza ya no vuelve a esperar. En RR o SRTF difieren: un proceso puede empezar pronto (response chico) y después esperar mucho entre turnos (waiting grande).

Peldaño 3 · Solosin ayuda; luego compara

Solo: RR con q = 3 y los mismos procesos

Con P1 (0, 7), P2 (2, 3), P3 (4, 2) y P4 (5, 4), Round Robin con quantum 3 da este Gantt: P1 0–3 · P2 3–6 · P1 6–9 · P3 9–11 · P4 11–14 · P1 14–15 · P4 15–16. Calcula turnaround, waiting y response de P4.

Comparar

• turnaround = 16 − 5 = 11
• waiting = 11 − 4 = 7
• response = 11 − 5 = 6

Waiting (7) es mayor que response (6) porque P4 esperó 6 hasta su primer turno y 1 más entre su primer y su segundo turno (14–15, mientras corría P1).

Cómo leerlo: arriba, el Gantt completo. Abajo, la vida de P4: rayado es «listo pero esperando», verde es «corriendo». Response mide hasta el primer verde; waiting suma todo lo rayado; turnaround va de la llegada al final.

5. Predecir la próxima ráfaga

SJF necesita conocer la próxima ráfaga, que no se sabe. Se estima con un promedio exponencial:

$$\tau_{n+1} = \alpha\, t_n + (1-\alpha)\,\tau_n, \qquad 0 \le \alpha \le 1$$

donde $t_n$ es la última ráfaga real y $\tau_n$ la estimación anterior.

• $\alpha = 0$: $\tau_{n+1} = \tau_n$. La historia reciente no cuenta.
• $\alpha = 1$: $\tau_{n+1} = t_n$. Solo cuenta la última ráfaga.
• Al expandir, cada término pesa $(1-\alpha)^j$: cuanto más vieja la ráfaga, menos pesa.

Peldaño 2 · Complétalofaltan pasos clave: llénalos tú

Complétalo: α = 0.5, τ₀ = 10 y ráfagas reales 6, 4, 6, 4, 13, 13, 13

n	ráfaga real $t_n$	estimación siguiente $\tau_{n+1} = 0.5\,t_n + 0.5\,\tau_n$
0	6	0.5·6 + 0.5·10 = 8
1	4	0.5·4 + 0.5·8 = 6
2	6	?
3	4	?
4	13	?
5	13	?
6	13	?

Comparar (verificado con un script)

Cómo leerlo: las barras son las ráfagas reales y la línea verde, la estimación que hace SJF antes de cada una. Cuando las ráfagas saltan de 4 a 13, la línea sube por pasos y siempre va un poco atrás.

6, 5, 9, 11, 12. La estimación sigue a la ráfaga real con retraso: cuando el proceso pasa de ráfagas de 4–6 a ráfagas de 13, la estimación sube 9 → 11 → 12, acercándose a 13 sin alcanzarla. Este es el problema 9.4 de Stallings.

6. Cómo se evalúa un algoritmo

Método	Idea	Ventaja	Desventaja
Modelo determinista	se toma una carga fija y se calcula cada métrica a mano	simple y rápido	el resultado vale solo para esa carga
Modelos de colas	análisis estadístico (llegadas de Poisson, servicio exponencial)	resultados generales	supuestos idealizados
Simulación	un programa genera o reproduce cargas	flexible	cuesta escribirlo; vale para lo que simulaste
Implementación real	se programa en el SO y se mide	lo más realista	difícil y arriesgado: un bug en el kernel

El ejemplo determinista de las diapositivas, con 5 procesos que llegan en 0 y ráfagas 10, 29, 3, 7 y 12, da una espera promedio de 28 con FCFS, 13 con SJF y 23 con RR (q = 10). Lo comprobé con el simulador de la página siguiente.

⚠️ Errores que cuestan puntos

• Llamar «response time» al tiempo hasta que el proceso termina.Eso es turnaround. Response es hasta la primera vez que corre.
• Calcular waiting como «inicio − llegada» en RR o SRTF.Ese es el response. Waiting suma todos los ratos en la cola de listos: turnaround − ráfaga.
• Decir que un scheduler que decide cuando el proceso termina o se bloquea es expropiativo.Los casos 1 y 4 son los del no expropiativo. Expropiar es quitarle la CPU a un proceso que quería seguir (casos 2 y 3).
• Confundir scheduler y dispatcher.El scheduler decide a quién; el dispatcher ejecuta el cambio de contexto.
• Decir que con α = 1 se usa todo el historial.Con α = 1 solo cuenta la última ráfaga; con α = 0, solo la estimación inicial.

Autoevaluación

0/7 correctas · 0 respondidas Reiniciar

1. Un scheduler que solo decide cuando el proceso se bloquea o termina es…

a) expropiativob) no expropiativoc) de tiempo reald) Round Robin

2. ¿Qué métrica se MAXIMIZA?

a) turnaroundb) waiting timec) throughputd) response time

3. Response time es el tiempo desde la llegada hasta…

a) que terminab) que corre por primera vezc) su última E/Sd) que sale de la cola de bloqueados

4. El convoy effect aparece típicamente en…

a) RR con q chicob) FCFS con un proceso largo delante de varios cortosc) SRTFd) MLFQ

5. La solución clásica a la starvation en prioridades es…

a) agingb) aumentar el quantumc) FCFSd) deshabilitar interrupciones

6. En Linux, el top half de una interrupción corre…

a) con interrupciones habilitadas y puede dormirb) con interrupciones deshabilitadas y debe ser rápidoc) en una work queued) en modo usuario

7. Con α = 0 en el promedio exponencial…

a) solo cuenta la última ráfagab) la estimación nunca cambiac) todas pesan iguald) SJF se vuelve FCFS

🗣️ Explícalo tú (Feynman)

Explica con el ejemplo de un editor de texto y un render de video por qué un buen scheduler de propósito general favorece a los procesos IO-bound, y qué riesgo trae hacerlo.

Dilo en voz alta o escríbelo en 4–5 líneas, sin mirar la página. Después revisa qué te faltó.

Tu explicación debería mencionar…

• El editor pasa casi todo el tiempo esperando una tecla: sus ráfagas de CPU son cortísimas. El render usa la CPU sin parar.
• Si el editor espera detrás del render, cada tecla tarda en aparecer: el response time es malo aunque el throughput sea bueno.
• Darle prioridad al editor casi no le quita CPU al render (usa muy poco) y mantiene ocupados a la vez la CPU y los dispositivos.
• El riesgo es la starvation del proceso CPU-bound si siempre hay alguien más prioritario; se corrige con aging.

Error típico al explicarlo: decir que el editor «es más importante». El criterio no es la importancia, sino que sus ráfagas son cortas.

📈 ¿Qué tan bien lo dominas?

Elige pensando en lo que hiciste, no en lo que leíste. Para marcar 3 tienes que haber resuelto un ejercicio nuevo sin pistas y haberlo justificado. Si solo lo leíste y sientes que «ya entendí», todavía es un 1.

0No lo reconozco o lo confundo con otro tema1Lo entiendo leyendo, pero no lo aplico solo2Resuelvo ejercicios parecidos a los vistos, con alguna pista3Resuelvo uno nuevo sin ayuda y justifico cada paso4Lo transfiero: comparo alternativas y veo casos límite

Fuente ·sem_12/Sema12_11-OST-Scheduling.pdf (diap. 4–45) · Ejercicios y la tabla α = 0.5: propios, verificados con un script