Conjunto residente, working set, limpieza y control de carga

💡 En simple

La página anterior respondía a quién expulsar. Esta responde tres preguntas de reparto:

• ¿Cuánto espacio le doy a cada proceso? Si le das muy poco a alguien, pasa el día yendo a la estantería (muchos fallos). Si le das mucho, caben menos procesos.
• Cuando hay que expulsar, ¿le quito a cualquiera o solo al que pidió?
• ¿Cuántos procesos dejo en la sala? Si entran demasiados, nadie avanza: todos están esperando libros. Eso es el thrashing.

El working set es la idea que une todo: el conjunto de páginas que un proceso está usando ahora. Si cada proceso tiene su working set en RAM, todo va bien.

🎯 Al terminar podrás

1. Clasificar una política como fija o variable y local o global, y explicar por qué fija + global es imposible.
2. Calcular el working set W(t, Δ) de una cadena para un Δ dado y su tamaño promedio.
3. Describir cómo PFF y VSWS aproximan el working set, y cuál es el punto débil de PFF.
4. Diagnosticar thrashing a partir de síntomas y proponer qué hacer (y qué no sirve).

Antes necesitas: Reemplazo de páginas · Localidad

• Laboratorio sube la escalera: resuelto → completa → solo → variante
• Debate elige una alternativa para el escenario y defiéndela
• Detective escribe tu hipótesis del bug antes de abrir el diagnóstico

Tamaño del conjunto residente

Con menos frames por proceso caben más procesos en RAM, así que hay más probabilidad de tener alguno listo. Pero si un proceso tiene muy pocos frames, la tasa de fallos se dispara. Pasado cierto punto, darle más frames casi no mejora nada, por la localidad.

Cómo leerlo: a la izquierda, con muy pocos marcos, el proceso no alcanza a tener su zona de trabajo y falla todo el tiempo. Cuando los marcos cubren su working set, la curva se aplana: dar más ya casi no baja los fallos. Por eso conviene darle a cada proceso lo justo para su working set y usar el resto para otros.

Asignación	Idea	Problema
Fija	número fijo de frames por proceso, decidido al crearlo (según el tipo de proceso o lo que pida)	si es poco hay muchos fallos; si es mucho, caben pocos procesos
Variable	el número de frames cambia durante la vida del proceso	hay que medir el comportamiento: overhead del SO

Alcance del reemplazo: local o global

💡 En simple: ¿le quito a quién pidió o a cualquiera?

Tu escritorio está lleno y necesitas un libro más.

• Local: devuelves uno de tu propio escritorio. Tu espacio no cambia.
• Global: devuelves uno de cualquier escritorio, incluso el de un compañero. Tú creces y él se achica.

Global es más simple y flexible, pero puede perjudicar a un compañero que necesitaba ese libro.

• Local: la víctima sale del mismo proceso que causó el fallo.
• Global: la víctima puede ser cualquier página no bloqueada de la memoria.

Cómo leerlo: arriba, la RAM antes del fallo (3 marcos de A, 5 de B); abajo, después. Con reemplazo local, A se reemplaza a sí mismo y los tamaños no cambian. Con global, A le quita un marco a B: A crece y B se achica. Ejemplo propio.

	Reemplazo local	Reemplazo global
Asignación fija	el número de frames no cambia y la víctima sale de las páginas del propio proceso	imposible: si se le quita una página a otro, el tamaño ya no sería fijo
Asignación variable	se reevalúa cada cierto tiempo cuántos frames darle; la víctima sale de los propios	la más fácil y la más usada (por ejemplo, en muchos UNIX): el proceso que falla crece, otro pierde un frame

Variable + global es simple, pero no tiene forma de saber a quién le conviene quitarle un frame: puede quitárselo a un proceso que lo necesitaba. Se compensa con page buffering: la página quitada queda un tiempo en una lista y se recupera barato.

Variable + local necesita una estrategia para decidir cuántos frames dar. Ahí entra el working set.

🔮 Debate: elige y defiende

En la misma máquina corren un reproductor de audio (pocas páginas, siempre las mismas, no puede cortarse) y una compilación enorme que no para de pedir memoria. ¿Usarías reemplazo local o global? ¿Qué cambia si solo corre la compilación?

Ya tengo mi respuesta: comparar

• Con los dos procesos: local (con asignación variable), porque con reemplazo global la compilación, que falla mucho, le iría quitando frames al reproductor hasta cortarlo. Local aísla a los procesos: los fallos de uno no castigan a otro.
• Solo la compilación: global es más simple y aprovecha toda la RAM libre sin tener que medir el working set. Por eso es la opción más usada en los UNIX.
• Criterio: global maximiza el uso de la memoria; local da previsibilidad. Ninguno gana siempre.

Working set

💡 En simple: lo que tienes sobre la mesa

El working set son las páginas que el proceso usó en los últimos Δ accesos: lo que tiene «sobre la mesa» ahora.

Ejemplo trivial: referencias A B A C D.

• Con Δ = 2 (los 2 últimos accesos: C D) → W = {C, D}.
• Con Δ = 4 (los 4 últimos: B A C D) → W = {A, B, C, D}.

La regla: un proceso solo se ejecuta si su working set cabe completo en la RAM. Si no cabe, va a pasar el tiempo trayendo páginas.

Definición (Denning): $W(t, \Delta)$ es el conjunto de páginas referenciadas en las últimas Δ referencias (unidades de tiempo virtual), mirando hacia atrás desde el instante t.

Propiedades:

• $W(t, \Delta + 1) \supseteq W(t, \Delta)$: una ventana más grande nunca tiene menos páginas.
• $1 \le |W(t,\Delta)| \le \min(\Delta, N)$, donde N es el número de páginas del proceso.
• Su tamaño sube durante las transiciones entre fases de localidad (las páginas viejas siguen en la ventana mientras llegan las nuevas) y baja cuando el proceso se estabiliza.

Ejemplo de Stallings (fig. 8.19). Cadena 24 15 18 23 24 17 18 24 18 17 17 15 24 17 24 18. Working set después de cada referencia, para cuatro tamaños de ventana (calculado):

ref	Δ = 2	Δ = 3	Δ = 4	Δ = 5
24	24	24	24	24
15	24 15	24 15	24 15	24 15
18	15 18	24 15 18	24 15 18	24 15 18
23	18 23	15 18 23	24 15 18 23	24 15 18 23
24	23 24	18 23 24	15 18 23 24	24 15 18 23
17	24 17	23 24 17	18 23 24 17	15 18 23 24 17
18	17 18	24 17 18	23 24 17 18	18 23 24 17
24	18 24	17 18 24	24 17 18	23 24 17 18
18	24 18	18 24	17 18 24	24 17 18
17	18 17	24 18 17	18 24 17	17 18 24
17	17	18 17	24 18 17	18 24 17
15	17 15	17 15	18 17 15	24 18 17 15
24	15 24	17 15 24	17 15 24	18 17 15 24
17	24 17	15 24 17	17 15 24	17 15 24
24	17 24	24 17	15 24 17	17 15 24
18	24 18	17 24 18	24 17 18	15 24 17 18

Tamaño promedio: 1.88 · 2.56 · 3.06 · 3.38. Con Δ más grande, el working set crece, pero cada vez menos.

Cómo leerlo: cada barra es el tamaño promedio del working set para una ventana Δ. Los números verdes son lo que se gana al agrandar Δ en 1: cada vez menos. Es la misma forma de la curva «marcos vs fallos»: pasado el working set, más memoria aporta poco.

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

Complétalo: working set con Δ = 3 para la cadena 1 2 1 3 2 4 4 1

t	1	2	3	4	5	6	7	8
ref	1	2	1	3	2	4	4	1
W(t, 3)	1	1 2	1 2	1 2 3	?	?	?	?

Recuerda: se miran las últimas 3 referencias (incluida la actual) y se quitan los repetidos.

Comparar

t	5	6	7	8
últimas 3	1 3 2	3 2 4	2 4 4	4 4 1
W(t, 3)	1 2 3	2 3 4	2 4	1 4

Tamaños: 1, 2, 2, 3, 3, 3, 2, 2, así que el promedio es 18 / 8 = 2.25. Fíjate en t = 7: la referencia repetida (4 4) achica el working set.

Cómo leerlo: la ventana es un recuadro de Δ casillas que termina en la referencia actual. W son las páginas distintas dentro del recuadro. En t = 7 hay tres referencias pero solo dos páginas distintas; por eso W tiene tamaño 2.

Peldaño 3 · Solosin ayuda; luego compara

Solo: la misma cadena con Δ = 2

Calcula W(t, 2) para cada t y su tamaño promedio. Después verifica la propiedad W(t, 2) ⊆ W(t, 3) en todos los instantes.

Comparar

W(t, 2): 1 · 12 · 12 · 13 · 23 · 24 · 4 · 14. Tamaños: 1, 2, 2, 2, 2, 2, 1, 2, así que el promedio es 14 / 8 = 1.75. En cada t, el conjunto está contenido en el de Δ = 3: una ventana más chica nunca tiene más páginas.

La estrategia del working set:

1. Monitorea el working set de cada proceso.
2. Quítale periódicamente las páginas que salieron del working set (reemplazo tipo LRU).
3. Un proceso solo se ejecuta si su working set cabe completo en RAM.

Problemas prácticos: el pasado no siempre predice el futuro, porque cambia la localidad; medir el working set exacto es caro (habría que registrar cada referencia), y el Δ óptimo es desconocido y varía. Por eso se usan aproximaciones.

Aproximaciones: PFF y VSWS

• PFF (Page Fault Frequency): cada página tiene un bit de uso. En cada fallo, el SO mira el tiempo virtual desde el fallo anterior:

  • si es menor que un umbral F (fallos muy seguidos), agrega la página al conjunto residente: el proceso crece;
  • si no, descarta todas las páginas con bit de uso 0 y pone los demás bits en 0: el proceso se encoge.

  El punto débil: durante una transición de localidad, las páginas viejas no alcanzan a salir y el conjunto residente se infla.

• VSWS (Variable-Interval Sampled Working Set): evalúa el working set en instantes de muestreo con tres parámetros:

  • M: intervalo mínimo;
  • L: intervalo máximo;
  • Q: número de fallos permitidos entre muestras.

  El intervalo termina al llegar a L, o al llegar a Q fallos si ya pasó M. Así reacciona rápido en las transiciones sin muestrear de más en las fases estables.

Política de limpieza

💡 En simple: lavar los platos

Las páginas modificadas son platos sucios: antes de reutilizarlos hay que lavarlos (escribirlos al disco).

• Por demanda: lavas el plato justo cuando lo necesitas. El que espera la comida espera también el lavado (dos E/S).
• Precleaning: lavas todo de antemano, en tandas. Pero quizá ensucies otra vez un plato que ya lavaste (E/S desperdiciada).

El punto medio es el page buffering: lavar en tandas solo lo que ya está apartado para salir.

¿Cuándo se escribe al disco una página modificada?

Política	Cuándo	Problema
Por demanda	solo cuando la página es elegida como víctima	el proceso que falló espera dos E/S: escribir la víctima y leer la nueva
Precleaning	antes de que haga falta, en lotes	se escriben páginas que quizá se vuelvan a modificar antes de ser expulsadas: E/S desperdiciada

Mejor solución: page buffering. Las páginas reemplazadas van a dos listas, modificadas y no modificadas. Las modificadas se escriben en lotes y pasan a la lista de no modificadas. De ahí se pueden recuperar si se vuelven a referenciar, o se reutilizan sus frames si se pierden.

Es el mismo esquema de page buffering, visto desde la limpieza: las páginas sucias se escriben en lote (arriba a la derecha) y recién después se reutiliza su frame.

Control de carga y thrashing

💡 En simple: demasiada gente en la cocina

Con pocos cocineros, la cocina está ociosa. Al agregar más, se produce más… hasta que son tantos que no caben, se estorban y pasan el tiempo pidiéndose los utensilios. La producción se desploma.

Eso es el thrashing: demasiados procesos, cada uno con muy pocos marcos, y la CPU casi solo espera al disco. La solución es sacar a algunos (suspender procesos) hasta que los demás tengan espacio suficiente.

El nivel de multiprogramación es el número de procesos residentes en RAM.

• Muy pocos: a menudo todos están bloqueados, así que la CPU queda ociosa.
• Demasiados: cada uno tiene un conjunto residente insuficiente y la tasa de fallos se dispara. Es el thrashing, que Stallings muestra en la fig. 8.21:
  • el uso del procesador sube al agregar procesos,
  • llega a un máximo,
  • y cae en picada: la CPU pasa el tiempo esperando al disco de paginación.

Cómo leerlo: al agregar procesos, la CPU se ocupa más porque casi siempre hay alguno listo. Pasado el máximo, cada proceso tiene muy pocos marcos y vive fallando (zona roja): la CPU se queda esperando al disco. La solución no es agregar procesos sino sacar algunos, para volver a la izquierda del máximo.

Criterios para elegir el nivel:

• Working set: solo se ejecuta un proceso si su working set está residente. Eso regula la carga de forma implícita.
• Criterio L = S (Denning): ajustar la carga para que el tiempo medio entre fallos (L) sea igual al tiempo medio de atender un fallo (S). Así se maximiza el uso del procesador.
• Criterio del 50 %: mantener la utilización del dispositivo de paginación cerca del 50 %.
• Adaptar Clock: si el puntero da vueltas muy rápido, hay escasez de memoria; si gira lento, sobra memoria y caben más procesos.

Si hay que bajar la carga, ¿qué proceso se suspende (se pasa a disco)? Stallings da seis candidatos:

Candidato	Razón
el de menor prioridad	política de planificación
el que más fallos está causando	probablemente no tiene su working set residente; suspenderlo libera un dispositivo saturado
el último activado	es el que menos probablemente tiene su working set completo
el de conjunto residente más pequeño	cuesta poco volverlo a cargar después, aunque perjudica a los procesos de localidad pequeña
el más grande	libera más frames de una vez
el que tiene más tiempo de ejecución restante	aproxima la política de menor tiempo restante

🔍 Detective · pregunta típica de análisis

Síntoma: La CPU está al 10 % y el disco de paginación al 98 %. El administrador agrega más procesos para «aprovechar la CPU ociosa» y todo empeora. ¿Qué pasa y qué harías?

Escribe tu hipótesis (qué variable o qué orden lo causa) antes de abrir.

Pista

Mira la fig. 8.21: ¿qué le pasa al uso de la CPU cuando el nivel de multiprogramación pasa del máximo?

Diagnóstico: causa raíz, cuándo se dispara, corrección y cómo verificarla

Es thrashing. Hay demasiados procesos para la RAM disponible: ninguno tiene su working set residente, así que todos generan fallos continuamente y esperan al disco. Agregar procesos (para «aprovechar la CPU ociosa») lo empeora.

Qué hacer:

• bajar el nivel de multiprogramación, suspendiendo procesos con alguno de los criterios de la tabla;
• agregar RAM;
• o asignar frames según el working set o PFF, para que cada proceso activo tenga lo que necesita.

Lo que no sirve: un disco de paginación un poco más rápido o una CPU más rápida. El cuello de botella es la falta de frames.

⚠️ Errores que cuestan puntos

• Mirar las próximas Δ referencias al calcular el working set.W(t, Δ) mira hacia atrás: las últimas Δ referencias, incluida la de t.
• Decir que fija + global es «poco eficiente».Es imposible: si le quitas una página a otro proceso, su tamaño deja de ser fijo.
• Ante thrashing, proponer una CPU más rápida o más procesos.Hay que bajar el nivel de multiprogramación (suspender procesos) o dar más RAM. El cuello de botella es la falta de frames.
• Confundir precleaning con prepaging.Precleaning escribe páginas modificadas antes de tiempo. Prepaging lee páginas de más.

Autoevaluación

0/7 correctas · 0 respondidas Reiniciar

1. ¿Qué combinación es imposible?

a) Fija + localb) Variable + localc) Fija + globald) Variable + global

2. W(t, Δ) es…

a) las páginas que el proceso usará en las próximas Δ referenciasb) las páginas referenciadas en las últimas Δ referenciasc) el número de frames fijod) las páginas modificadas

3. Si aumenta Δ, el working set…

a) puede achicarseb) se mantiene o crecec) siempre se duplicad) no cambia

4. En PFF, si el tiempo desde el último fallo es menor que F…

a) se descartan las páginas con u = 0b) se agrega la página: el conjunto residente crecec) se suspende el procesod) nada

5. Limpieza por demanda: el proceso que falla espera…

a) una E/Sb) dos E/S: escribir la víctima modificada y leer la nuevac) ninguna E/Sd) a que termine el precleaning

6. Criterio L = S:

a) L tamaño de página = S tamaño de segmentob) tiempo medio entre fallos = tiempo medio de atender un falloc) nivel de multiprogramación = número de CPUsd) uso del disco = 100 %

7. Con thrashing, agregar más procesos…

a) mejora el uso de la CPUb) lo empeorac) no cambia nadad) elimina los fallos

🗣️ Explícalo tú (Feynman)

Explica qué es el working set y por qué la regla «un proceso solo corre si su working set cabe en RAM» evita el thrashing.

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…

• Es el conjunto de páginas usadas en las últimas Δ referencias: una estimación, basada en el pasado, de lo que el proceso necesita ahora.
• Si un proceso corre con menos frames que su working set, falla todo el tiempo.
• Si muchos procesos están así a la vez, la CPU espera al disco: eso es el thrashing.
• La regla limita cuántos procesos entran (control de carga implícito). Un ejemplo con números, como el peldaño 2.
• En la práctica se aproxima con PFF o VSWS, porque medirlo exacto es caro.

Error típico al explicarlo: decir que el working set son «las páginas que el proceso va a usar». Es lo que usó recientemente, y se usa para predecir.

📈 ¿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 9e §8.2 (Resident Set Management, Cleaning Policy, Load Control; figs. 8.19–8.21) · Working set de la fig. 8.19 calculado con un script propio