Stallings cap. 9 · Planificación en monoprocesador

💡 En simple

Stallings divide la planificación en tres niveles de tiempo. El de largo plazo decide quién entra al sistema (como el portero de una discoteca), el de mediano plazo decide quién se queda en memoria y quién se va a swap (como mandar a alguien a esperar afuera un rato) y el de corto plazo decide quién usa la CPU ahora (quién baila). El capítulo es casi entero sobre el de corto plazo: qué criterios hay y cómo se comporta cada algoritmo con el mismo ejemplo de 5 procesos.

Qué entra del cap. 9

La hoja del Lab 4 recomienda el capítulo 9 para las 3 teóricas (5 pts), que «podrán incluir preguntas de desarrollo». Las secciones son 9.1 (tipos), 9.2 (algoritmos, comparación y fair-share) y 9.3 (UNIX tradicional). Las fórmulas de colas de §9.2 son para entender la idea: no hace falta memorizarlas.

🎯 Al terminar podrás

1. Diferenciar la planificación de largo, mediano y corto plazo, y decir cuándo actúa cada una.
2. Clasificar los criterios en orientados al usuario o al sistema, y relacionados o no con el rendimiento.
3. Definir FCFS, RR, VRR, SPN, SRT, HRRN y feedback con su función de selección y su modo de decisión.
4. Responder de memoria las Review Questions 9.1–9.11 y resolver los problemas tipo 9.1, 9.2 y 9.16.

Antes necesitas: Algoritmos a mano

• Feynman explícalo en voz alta sin mirar y compara con la lista
• Examen cronométrate y no abras la solución hasta terminar

Cómo leer el capítulo sin que se te olvide

1. Antes de cada sección, lee solo su título y escribe una pregunta que creas que responde (por ejemplo, «¿por qué FCFS perjudica a los IO-bound?»).
2. Lee la sección buscando esa respuesta.
3. Cierra la página y escribe la idea central en dos líneas.
4. Al final, responde las Review Questions sin mirar y recién después abre cada respuesta.

9.1 Tipos de planificación

Tipo	Decide	Frecuencia	Efecto
Largo plazo	si se admite un nuevo proceso	baja	controla el grado de multiprogramación
Mediano plazo	si un proceso pasa a estar (parcial o totalmente) en memoria; es parte del swapping	media	también controla la multiprogramación
Corto plazo (dispatcher)	qué proceso listo se ejecuta	muy alta	rendimiento visible para el usuario
E/S	qué petición atiende un dispositivo		se ve en el cap. 11

El de largo plazo decide cuándo admitir (si hay más procesos, a cada uno le toca menos CPU; se invoca cuando un trabajo termina o cuando la CPU está ociosa demasiado tiempo) y a quién (FCFS, o por prioridad, duración esperada o requisitos de E/S, buscando una mezcla de procesos CPU-bound e IO-bound). En sistemas interactivos se admite a todos los usuarios autorizados hasta la saturación.

El de corto plazo se invoca ante cualquier evento que pueda bloquear al proceso actual o permitir expropiarlo: interrupciones de reloj, interrupciones de E/S, llamadas al sistema y señales (por ejemplo, de semáforos).

Cómo leerlo: sigue a un proceso de izquierda a derecha. El largo plazo lo deja entrar a la cola de listos; el corto plazo lo pasa a la CPU; de ahí sale porque termina, porque lo expropian (vuelve a listos) o porque espera una E/S (va a bloqueados). El mediano plazo, abajo, puede mandarlo a disco y traerlo de vuelta.

9.2 Criterios

Dos ejes: usuario o sistema y rendimiento o no.

En simple, con un restaurante:

• Response time: desde que pides hasta que llega el primer plato. Es lo que siente un usuario interactivo: que algo empiece a pasar.
• Turnaround: desde que entras hasta que te vas. Importa en un trabajo batch, donde solo cuenta el resultado final.
• Throughput: cuántas mesas atiende el local por hora. Mira al sistema, no a un cliente.
• Fairness: que ninguna mesa se quede sin atender (sin starvation).

	Relacionado con el rendimiento	Otros
Usuario	turnaround (envío → fin; útil para batch), response time (envío → inicio de la respuesta; el crítico en interactivos), deadlines	predictability: el mismo trabajo tarda y cuesta lo mismo sin importar la carga
Sistema	throughput (procesos por unidad de tiempo), utilización del procesador	fairness (sin starvation), respetar prioridades, balancear recursos

Los criterios compiten: un buen response time exige cambiar de proceso a menudo, y eso suma overhead y baja el throughput.

Prioridades

Hay varias colas de listos, RQ0, RQ1, …, en orden descendente de prioridad, y se elige de la más alta que no esté vacía. Convención del libro: como en UNIX, un valor menor es una prioridad mayor (Windows usa la convención opuesta). El problema es la starvation de los de baja prioridad; la solución es que la prioridad cambie con la edad o la historia del proceso.

Cómo leerlo: cada cola es un nivel de prioridad. El dispatcher no mira el orden de llegada global: baja por las colas hasta encontrar una con alguien, y toma al primero de esa cola.

Ojo con la convención

Stallings: valor menor = más prioridad. La hoja de ejercicios del lab y el framework: valor mayor = más prioridad. Si una teórica pregunta por el libro, responde con la convención del libro y dilo.

Las políticas (tabla 9.3)

Cada política se describe con dos cosas:

• La función de selección: la regla que elige al siguiente entre los listos. Usa tres números de cada proceso: w, el tiempo que lleva esperando; e, el tiempo que lleva ejecutado; y s, su tiempo de servicio total (incluye e).
• El modo de decisión: no expropiativo (el proceso corre hasta terminar o bloquearse) o expropiativo (el SO puede sacarlo a la mitad).

El ejemplo del libro (tabla 9.4), que se usa para todas las políticas:

Proceso	A	B	C	D	E
Llega en	0	2	4	6	8
Servicio (s)	3	6	4	5	2

Los Gantt de abajo los recalculé con un simulador propio y coinciden con la figura 9.5 y la tabla 9.5 del libro. Para leerlos: cada casilla es una unidad de tiempo y la letra es el proceso que usa la CPU en ella. Las rayas de arriba marcan cuándo llega cada uno, y entre paréntesis va su servicio.

FCFS: la fila del banco

En simple: atiende en orden de llegada y no interrumpe a nadie. Si delante tuyo hay alguien con un trámite de una hora, esperas una hora aunque lo tuyo sea un minuto.

• Regla: max[w], no expropiativo.
• Problema 1, los cortos sufren: rinde mucho mejor con procesos largos que con cortos. En el ejemplo W, X, Y, Z del libro, Y dura 1 unidad y aun así tiene Tr/Ts = 100.
• Problema 2, favorece a los CPU-bound: mientras uno de ellos usa la CPU, los IO-bound esperan en la cola y los dispositivos de E/S quedan ociosos.
• Solo no conviene, pero combinado con prioridades (una cola FCFS por nivel) sí se usa.

Cómo leerlo: cada proceso corre de un tirón, en orden de llegada. E solo necesita 2 unidades, pero llega en 8 y espera hasta 18: Tr = 12, seis veces su servicio.

Round Robin: el turno de micrófono

En simple: cada uno habla como máximo q unidades; si no terminó, vuelve al final de la fila. Nadie monopoliza el micrófono.

• Regla: FCFS más una interrupción de reloj periódica que expropia (time slicing).
• El tamaño de q es la decisión clave:
  • q muy corto: muchos cambios de proceso y mucho overhead.
  • q más grande que el proceso más largo: nadie es expropiado y se degenera en FCFS.
  • La guía del libro: q un poco mayor que una interacción típica, para que una petición corta termine en un solo turno.
• Convención del libro para empates: si en el mismo instante llega un proceso nuevo y otro es expropiado, el nuevo va primero en la cola.
• Debilidad: un IO-bound usa un pedacito de su quantum, se bloquea y vuelve al final de la cola. Un CPU-bound usa su quantum entero cada vez. Resultado: el CPU-bound se lleva más CPU de la que le toca. Para eso existe VRR.

Cómo leerlo: arriba, la interacción cabe en un quantum y la respuesta llega en s. Abajo, el quantum la corta en dos y, entre medio, corren todos los demás: la respuesta tarda mucho más que s.

Cómo leerlo: con q = 1 los procesos se intercalan unidad por unidad. En t = 2 llega B y, por la convención de empates, pasa delante de A, que vuelve a correr en t = 3. Con q = 4, B corre 4 seguidas, va al final y retoma en t = 15.

VRR: la fila preferencial

En simple: a quien tuvo que salir a buscar un papel (una E/S) no lo mandas al final de la fila: entra por una fila preferencial y termina lo que le quedaba de su turno.

• Regla: RR más una cola auxiliar FCFS para los procesos que vuelven de una E/S.
• La auxiliar tiene preferencia sobre la principal.
• Quien sale de la auxiliar corre solo lo que le quedaba de su quantum, no uno nuevo.
• Efecto: el libro muestra que es más justo con los IO-bound que RR.

Cómo leerlo: hay dos caminos de vuelta a la CPU. Quien agotó su quantum vuelve a la cola principal; quien se bloqueó por E/S vuelve por la cola auxiliar verde, que se atiende primero.

SPN: el cajero de «pocos artículos»

En simple: cuando la caja se libera, pasa el que lleva menos artículos. Mientras alguien está pagando, nadie lo interrumpe.

• Regla: min[s], no expropiativo.
• Ventaja: mejora mucho el tiempo de respuesta promedio.
• Problema 1: hay que estimar s, porque nadie sabe de antemano cuánto va a durar un proceso. Más abajo se ve cómo.
• Problema 2: aumenta la variabilidad de los tiempos, es decir, baja la predictibilidad.
• Problema 3: los largos pueden sufrir starvation si siguen llegando cortos.

Cómo leerlo: en t = 9, cuando termina B, están listos C (4), D (5) y E (2). Gana E, el más corto, aunque llegó último. Compárala con FCFS: E pasa de Tr = 12 a Tr = 3.

SRT: SPN que sí interrumpe

En simple: igual que SPN, pero si llega alguien con menos trabajo pendiente que el que está en caja, se le cede el lugar en ese momento.

• Regla: min[s − e], expropiativo solo al llegar un proceso.
• No penaliza a los cortos como FCFS ni genera interrupciones de reloj como RR.
• Debe registrar cuánto lleva ejecutado cada proceso (e), y también necesita estimar s.
• Da mejor turnaround que SPN: en el ejemplo, 7.2 contra 7.6.

Cómo leerlo: en t = 4 llega C (4) y B ya solo lleva 1 de 6: le quedan 5 > 4, así que C lo expropia. En t = 8 termina C y, entre B (le quedan 5), D (5) y E (2), gana E. B recién retoma en t = 10.

HRRN: el que más «se merece» el turno

En simple: el turno se lo gana quien tiene la espera más desproporcionada respecto de lo que pide. Un trámite corto que espera mucho sube rápido; uno largo también sube si espera lo suficiente.

• Regla: max[R], con R = (w + s) / s. No expropiativo.
• Recién llegado: w = 0, así que R = 1.
• Con el tiempo: w crece y R crece. Para el mismo w, el corto (s chico) sube más rápido.
• Sin starvation: un largo que espera suficiente termina teniendo el R más alto y gana.

Cómo leerlo: en t = 13 quedan D (llegó en 6, s = 5) y E (llegó en 8, s = 2). R(D) = (7 + 5)/5 = 2.4 y R(E) = (5 + 2)/2 = 3.5, así que gana E. En t = 9 había ganado C: R(C) = (5 + 4)/4 = 2.25 contra R(D) = (3 + 5)/5 = 1.6 y R(E) = (1 + 2)/2 = 1.5.

Feedback: aprender de la historia

En simple: como no sabes cuánto va a durar cada uno, castigas a quien ya lleva mucho corriendo. Todos empiezan arriba; el que agota su turno baja un escalón. Los cortos terminan antes de bajar mucho.

• Regla: colas RQ0, RQ1, … de prioridad decreciente. Un proceso nuevo entra a RQ0; cada vez que es expropiado baja una cola. En la última cola se usa RR.
• No necesita estimar s: usa solo lo que ya ejecutó.
• Variante q = 2ⁱ: en RQi el quantum es 2ⁱ, para que los largos no se estiren tanto.
• Puede haber starvation de los largos. Se corrige promoviendo a quien espera mucho.
• Convención del libro: si no hay nadie más listo, el proceso no baja de cola (fig. 9.5).

Cómo leerlo: la flecha roja es la expropiación: el proceso vuelve una cola más abajo. Un IO-bound se bloquea antes de agotar el quantum, así que no baja y se queda en las colas de arriba.

Cómo leerlo: en las dos filas, A corre 2 unidades seguidas al principio porque está solo y no baja. Con q = 2ⁱ, los procesos que ya bajaron reciben turnos más largos: B corre 3 unidades seguidas al final (t = 14 a 17).

Estimar la ráfaga

Promedio simple: $S_{n+1} = \frac{1}{n}\sum_{i=1}^{n} T_i$. Promedio exponencial: $S_{n+1} = \alpha T_n + (1-\alpha) S_n$. Con α = 0.8 casi todo el peso está en las 4 últimas observaciones; con α = 0.2 se reparte en unas 8. Un α alto reacciona rápido a los cambios, pero se vuelve «nervioso» ante picos breves.

Por qué funciona: la estimación nueva es una mezcla entre lo que acaba de pasar (Tₙ) y lo que creías antes (Sₙ). α dice cuánto le crees a lo último.

Ejemplo propio con α = 0.5 y una estimación inicial S₁ = 10, para ráfagas reales de 6, 4 y 13:

• S₂ = 0.5 · 6 + 0.5 · 10 = 8;
• S₃ = 0.5 · 4 + 0.5 · 8 = 6;
• S₄ = 0.5 · 13 + 0.5 · 6 = 9.5. La estimación sube, pero no salta hasta 13 de golpe.

Cómo leerlo: al desarrollar la fórmula, la ráfaga de hace k pasos pesa α(1 − α)ᵏ. Con α = 0.8 el peso cae casi a cero después de 3 o 4 ráfagas; con α = 0.2 baja despacio y hasta la octava todavía cuenta.

Comparación de rendimiento

Primero, todas las políticas juntas con el ejemplo del libro:

Cómo leerlo: la columna de la derecha es el turnaround medio de la tabla 9.5. Las que favorecen a los cortos (SRT 7.2 y SPN 7.6) ganan; las que reparten la CPU sin mirar duraciones (RR y FB) pierden en promedio, pero ninguna deja a un proceso esperando mucho tiempo sin correr.

Ojo: con 5 procesos el resultado depende mucho del ejemplo. Por eso el libro también compara con teoría de colas y con simulación de miles de procesos:

• Teoría de colas: para cualquier disciplina que elija sin mirar el tiempo de servicio, $T_r/T_s = 1/(1-\rho)$, donde ρ es la utilización. Una prioridad que no depende de la duración da el mismo turnaround promedio que FCFS, con o sin expropiación.
• Prioridad según la duración (dos clases): el promedio global mejora poco, pero los cortos mejoran mucho (más todavía con expropiación) y los largos empeoran.
• Simulación (50 000 procesos, ρ = 0.8): FCFS es muy desfavorable con los cortos (un tercio de los procesos tiene Tr/Ts > 10); RR con q = 1 da Tr/Ts ≈ 5 para casi todos; SPN es mejor que RR salvo para los más cortos; SRT es mejor que SPN salvo para el 7 % más largo; HRRN queda entre FCFS y SPN; FB funciona muy bien con los cortos.

Cómo leerlo: Tr/Ts es cuántas veces más tarda un proceso respecto de su servicio puro. Mientras la CPU está poco ocupada casi no hay cola; pasado ρ ≈ 0.8, cada poco de carga extra dispara la espera. Con ρ = 0.8, el promedio ya es 5 veces el servicio, que es justo el valor de RR en la simulación.

Fair-share scheduling (FSS)

En simple: primero se reparte la CPU entre grupos (por ejemplo, usuarios) y después, dentro de cada grupo, entre sus procesos. Un usuario que lanza 10 procesos no se queda con 10 veces más CPU que otro con uno solo.

Planifica por grupos de procesos (un usuario o un departamento), no por proceso suelto. Cada grupo tiene un peso $W_k$ y la prioridad del proceso j del grupo k es:

$$P_j(i) = Base_j + \frac{CPU_j(i)}{2} + \frac{GCPU_k(i)}{4 \times W_k}$$

donde $CPU_j(i) = CPU_j(i-1)/2$ y $GCPU_k(i) = GCPU_k(i-1)/2$ (un valor menor es más prioridad). En la fig. 9.16, A está en un grupo y B y C en otro, ambos con peso 0.5: el orden resulta A, B, A, C, A, B…, y A recibe el 50 %, igual que B y C juntos.

Cómo leerlo: cada casilla es la prioridad del proceso al empezar ese segundo; corre el valor menor (▶). Cuando corre B, sube también la prioridad de C, porque comparten el uso del grupo (GCPU). Por eso A corre uno de cada dos segundos. Valores recalculados con la fórmula; coinciden con la fig. 9.16.

9.3 UNIX tradicional

Feedback multinivel con RR en cada cola y expropiación cada 1 segundo. La prioridad se recalcula cada segundo:

$$CPU_j(i) = \frac{CPU_j(i-1)}{2}, \qquad P_j(i) = Base_j + \frac{CPU_j(i)}{2} + nice_j$$

El reloj interrumpe 60 veces por segundo e incrementa el contador del proceso que corre. Las bandas de prioridad base son, de mayor a menor: swapper, control de dispositivos de bloque, manipulación de archivos, control de dispositivos de caracteres y procesos de usuario. El uso reciente de CPU penaliza a los CPU-bound y favorece a los IO-bound.

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

Complétalo: la fig. 9.17 (A, B y C con base 60, sin nice)

En el segundo 0 corre A, y su contador llega a 60. Al recalcular: $CPU_A = 60/2 = 30$ y $P_A = 60 + 30/2 = 75$. B y C siguen con prioridad 60. ¿Quién corre en el segundo 1? ¿Y cuánto valen las prioridades al final del segundo 1?

Comparar

Corre B (60 < 75; empata con C y gana el primero). Al final del segundo 1: $CPU_A = 30/2 = 15$ → $P_A = 60 + 7 = 67$ (división entera); $CPU_B = 60/2 = 30$ → $P_B = 75$; $P_C = 60$. En el segundo 2 corre C. El patrón es A, B, C, A, B, C…: con procesos CPU-bound iguales, el decaimiento reparte la CPU como un RR.

Cómo leerlo: el que corre en un segundo suma 60 a su contador, que al recalcular se divide entre 2; su prioridad sube (empeora) y le cede el turno al siguiente. Al segundo siguiente su contador se vuelve a dividir entre 2 y su prioridad mejora. Valores de la fig. 9.17, recalculados con la fórmula.

Review Questions 9.1–9.11

9.1 Describe brevemente los tres tipos de planificación del procesador.

Largo plazo: decide si se agrega un nuevo proceso al conjunto de procesos activos (controla el grado de multiprogramación). Mediano plazo: decide si un proceso pasa a estar parcial o totalmente en memoria principal; es parte del swapping. Corto plazo: decide cuál de los procesos listos ejecuta el procesador; es el dispatcher y el que más seguido corre.

9.2 ¿Cuál es normalmente el requisito de rendimiento crítico en un SO interactivo?

El response time, o tiempo de respuesta.

9.3 ¿Cuál es la diferencia entre turnaround time y response time?

Turnaround es el intervalo entre el envío de un proceso y su fin: incluye la ejecución y todas las esperas, y es la medida adecuada para batch. Response time es el intervalo entre el envío de una petición y el inicio de la respuesta: el proceso puede empezar a responder mientras sigue trabajando, así que refleja mejor lo que percibe el usuario interactivo.

9.4 En planificación de procesos, ¿un valor de prioridad bajo representa una prioridad baja o alta?

Depende del sistema. En UNIX y en muchos otros, y en la convención del libro, un valor bajo es prioridad alta. Algunos, como Windows, usan lo contrario. (En el lab, el número mayor es más prioridad: decláralo siempre.)

9.5 ¿Cuál es la diferencia entre planificación expropiativa y no expropiativa?

No expropiativa: el proceso en ejecución sigue hasta que termina o se bloquea (E/S o servicio del SO). Expropiativa: el SO puede interrumpirlo y pasarlo a listo, al llegar un proceso nuevo, cuando una interrupción desbloquea a otro o periódicamente por reloj. La expropiativa tiene más overhead, pero evita que un proceso monopolice la CPU.

9.6 Define brevemente FCFS.

Cuando el proceso actual deja de ejecutar, se elige el que lleva más tiempo en la cola de listos (max[w]). No es expropiativo.

9.7 Define brevemente Round Robin.

Se genera una interrupción de reloj periódica. En cada una, el proceso que corre vuelve a la cola de listos y se elige el siguiente en orden FCFS. Cada proceso recibe una porción de tiempo (time slicing).

9.8 Define brevemente SPN (shortest process next).

Política no expropiativa que elige el proceso con el menor tiempo de procesamiento esperado. Los procesos cortos se adelantan a los largos.

9.9 Define brevemente SRT (shortest remaining time).

Versión expropiativa de SPN: siempre se elige el proceso con menor tiempo restante esperado. Cuando llega uno con menos tiempo restante que el actual, lo expropia.

9.10 Define brevemente HRRN (highest response ratio next).

Cuando el proceso actual termina o se bloquea, se elige el listo con mayor R = (w + s)/s (w = espera, s = servicio esperado). Favorece a los cortos, pero la espera hace crecer R, así que los largos no sufren starvation.

9.11 Define brevemente feedback scheduling.

Expropiativa por quantum y con prioridades dinámicas. Un proceso entra a RQ0 y, cada vez que es expropiado, baja a la cola siguiente. En cada cola, FCFS, y en la última, RR. Así se favorece a los cortos sin conocer sus duraciones, penalizando a los que llevan más tiempo ejecutando.

Problemas resueltos (soluciones propias, verificadas)

Peldaño 3 · Solosin ayuda; luego compara

Problema 9.16: cinco trabajos que llegan juntos

Duraciones A = 15, B = 9, C = 3, D = 6, E = 12 minutos; prioridades 6, 3, 7, 9, 4 (valor menor = más prioridad). Turnaround de cada uno y promedio para: (a) RR con q = 1, (b) prioridad, (c) FCFS en orden A–E y (d) SJF.

Comparar

	A	B	C	D	E	Promedio
(a) RR q = 1	45	35	13	26	42	32.2
(b) Prioridad: B, E, A, C, D	36	9	39	45	21	30.0
(c) FCFS	15	24	27	33	45	28.8
(d) SJF: C, D, B, E, A	45	18	3	9	30	21.0

Cómo se llega a RR: en cada vuelta corren todos los que quedan, 1 minuto cada uno. C termina en la 3.ª vuelta (t = 13); D en la 6.ª (t = 26); B en la 9.ª (t = 35); E en la 12.ª (t = 42) y A al final (t = 45). SJF da el menor promedio, como predice el problema 9.3.

Peldaño 3 · Solosin ayuda; luego compara

Problema 9.1: SRT, prioridad no expropiativa y RR (q = 30 ms)

P1 (50 ms, prioridad 4, llega en 0), P2 (20, 1, llega en 20), P3 (100, 3, llega en 40), P4 (40, 2, llega en 60). Valor menor = más prioridad. Espera promedio de cada política.

Comparar (unidad de 10 ms, como el ejemplo del libro)

Política	Gantt (×10 ms)	Esperas P1/P2/P3/P4 (ms)	Promedio
FCFS	P1 0–5 · P2 5–7 · P3 7–17 · P4 17–21	0 / 30 / 30 / 110	42.5 ms
SRT	P1 0–2 · P2 2–4 · P1 4–7 · P4 7–11 · P3 11–21	20 / 0 / 70 / 10	25 ms
Prioridad no exp.	P1 0–5 · P2 5–7 · P4 7–11 · P3 11–21	0 / 30 / 70 / 10	27.5 ms
RR q = 30 ms	P1 0–3 · P2 3–5 · P1 5–7 · P3 7–10 · P4 10–13 · P3 13–16 · P4 16–17 · P3 17–21	20 / 10 / 70 / 70	42.5 ms

En SRT, P2 expropia a P1 en t = 20 ms (20 < 30 restantes). En prioridad, P1 no es expropiado aunque P2 llegue con prioridad 1, porque es no expropiativa.

Peldaño 4 · Variantecambia una condición: ¿sigue valiendo lo anterior?

Problema 9.2: la tabla 9.5 con otro conjunto

A (llega 0, servicio 3), B (1, 5), C (3, 2), D (9, 5), E (12, 5). Calcula el instante de fin y el turnaround promedio de cada política.

Comparar (verificado con el simulador; RR y FB con la convención del libro)

Política	Fin A, B, C, D, E	Tr promedio	Tr/Ts promedio
FCFS	3, 8, 10, 15, 20	6.2	1.74
RR q = 1	6, 11, 8, 18, 20	7.6	1.98
RR q = 4	3, 10, 9, 19, 20	7.2	1.88
SPN	3, 10, 5, 15, 20	5.6	1.32
SRT	3, 10, 5, 15, 20	5.6	1.32
HRRN	3, 8, 10, 15, 20	6.2	1.74
FB q = 1	7, 16, 6, 19, 20	8.6	2.09
FB q = 2i	4, 10, 8, 18, 20	7.0	1.81

Aquí SRT coincide con SPN: ninguna llegada encuentra en ejecución a un proceso con más tiempo restante que el recién llegado. HRRN coincide con FCFS: en t = 8 el único listo es C. En FB, si no hay nadie más listo, el proceso no baja de cola (es lo que hace Stallings en la fig. 9.5).

🔮 Pregunta de desarrollo

«¿Qué tipo de proceso favorece un scheduler de colas multinivel con realimentación: uno CPU-bound o uno IO-bound? Explica.» (problema 9.14). Responde en 4 líneas antes de abrir.

Ya tengo mi respuesta: comparar

Favorece a los IO-bound. Un proceso IO-bound usa la CPU poco tiempo y se bloquea antes de agotar su quantum, así que no es expropiado y no baja de cola: se mantiene en las colas de mayor prioridad. Un CPU-bound agota su quantum una y otra vez y va bajando a colas de menor prioridad. Así, sin conocer las duraciones, el scheduler aprende de la historia de cada proceso.

⚠️ Errores que cuestan puntos

• Decir que el scheduler de mediano plazo elige quién usa la CPU.Decide quién está en memoria (swapping). La CPU la asigna el de corto plazo.
• Definir response time como el tiempo hasta que el proceso termina.Es hasta que la respuesta empieza. Hasta el fin es el turnaround.
• Afirmar que RR es siempre mejor que FCFS.RR trata peor a los IO-bound (motivo de VRR) y con q grande es igual a FCFS. Con q chico, el overhead baja el throughput.
• Decir que HRRN puede causar starvation.La espera hace crecer R hasta que el proceso es elegido.
• Decir que la prioridad mejora el turnaround promedio frente a FCFS.Si la prioridad no depende de la duración, el promedio es el mismo (teoría de colas).

Autoevaluación

0/7 correctas · 0 respondidas Reiniciar

1. ¿Qué scheduler controla el grado de multiprogramación al admitir nuevos procesos?

a) corto plazob) mediano plazoc) largo plazod) de E/S

2. Según Stallings, el requisito crítico en un sistema interactivo es…

a) throughputb) response timec) utilizaciónd) predictability

3. En VRR, los procesos que vuelven de una E/S…

a) van al final de la cola principalb) van a una cola auxiliar con preferencia y usan lo que les quedaba de quantumc) reciben un quantum dobled) bajan de prioridad

4. La función de selección de SRT es…

a) max[w]b) min[s]c) min[s − e]d) max[(w + s)/s]

5. En UNIX tradicional, la prioridad de un proceso…

a) es fijab) empeora con el uso reciente de CPU, que decae a la mitad cada segundoc) solo depende del niced) mejora cuanto más CPU usa

6. En fair-share, si dos grupos tienen peso 0.5 y uno tiene 1 proceso y el otro 2…

a) cada proceso recibe 1/3b) el proceso solo recibe 50 % y los otros dos 25 % cada unoc) el grupo grande recibe 2/3d) depende del nice

7. ¿Cuál de estas políticas NO necesita estimar el tiempo de servicio?

a) SPNb) SRTc) HRRNd) Feedback

🗣️ Explícalo tú (Feynman)

Explica, como en una pregunta de desarrollo, por qué feedback penaliza «el tiempo ya ejecutado» en vez del «tiempo que falta», y qué problema introduce.

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…

• SPN, SRT y HRRN necesitan estimar el tiempo de servicio, que a menudo no se conoce.
• Feedback usa algo que sí se conoce: cuánto lleva ejecutando. Cada expropiación lo baja de cola.
• Los cortos terminan en las colas altas y los largos se hunden, así que se favorece a los cortos sin estimar nada.
• Problema: los largos pueden sufrir starvation si llegan cortos sin parar. Se mitiga con q = 2ⁱ y promoviendo a quien espera mucho.

Error típico al explicarlo: decir que feedback «conoce» qué procesos son cortos. No lo sabe: lo deduce de su historia.

📈 ¿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 ·Stallings, Operating Systems 9e, cap. 9 (§9.1–9.3, tablas 9.1–9.6, fig. 9.16–9.17, Review Questions y problemas) · Respuestas y problemas: soluciones propias, verificadas con un script