Políticas del SO: lectura, ubicación y reemplazo

💡 En simple

El escritorio (la RAM) está lleno y necesitas un libro nuevo: ¿cuál devuelves a la estantería?

• Lo ideal sería devolver el que vas a tardar más en volver a usar. Ese es el algoritmo óptimo (OPT), pero exige adivinar el futuro.
• Como no se puede, se aproxima mirando el pasado: devolver el que llevas más tiempo sin tocar (LRU).
• Otra opción es una versión barata de LRU que solo recuerda si lo tocaste «hace poco» (Clock).
• La opción ingenua es devolver el que llegó primero (FIFO), aunque lo estés usando todo el tiempo.

🎯 Al terminar podrás

1. Simular FIFO, LRU, OPT y Clock sobre una cadena de referencias y contar los fallos, declarando la convención.
2. Aplicar el Clock mejorado (bits u y m) y decir en qué pasada aparece la víctima.
3. Mostrar la anomalía de Belady con FIFO y justificar por qué LRU y OPT no la tienen.
4. Elegir una política para un escenario y defenderla con su costo de implementación.

Antes necesitas: Page fault y bits P, u y m de la PTE · Localidad

• Simulador predice el estado antes de pulsar el paso siguiente
• Laboratorio sube la escalera: resuelto → completa → solo → variante
• Debate elige una alternativa para el escenario y defiéndela
• Examen cronométrate y no abras la solución hasta terminar

Stallings organiza el software de memoria virtual en seis decisiones de diseño. Esta página cubre las tres primeras; las otras tres están en conjunto residente, limpieza y carga.

Política	Pregunta	Opciones
Fetch (lectura)	¿cuándo traigo una página?	por demanda · prepaging
Placement (ubicación)	¿dónde la pongo?	con paginación da igual; importa en segmentación pura (best/first/next-fit)
Reemplazo	¿a quién expulso?	OPT · LRU · FIFO · Clock (+ page buffering)
Conjunto residente	¿cuántos frames le doy a cada proceso, y de quién expulso?	fija/variable × local/global
Limpieza	¿cuándo escribo al disco las páginas modificadas?	por demanda · precleaning
Control de carga	¿cuántos procesos tengo en memoria?	nivel de multiprogramación, suspender procesos

Fetch: ¿cuándo traer una página?

• Paginación por demanda: se trae la página solo cuando se referencia. Al inicio hay muchos fallos y, gracias a la localidad, después se estabiliza.
• Prepaging: se traen más páginas que la pedida, aprovechando que en el disco suelen estar contiguas y que leer varias de una vez es más barato que una por una. Es eficaz si esas páginas se terminan usando; si no, es desperdicio. Se usa, por ejemplo, al arrancar un proceso o al traerlo de vuelta desde swap.

Ojo: prepaging no es lo mismo que swapping (sacar o meter un proceso entero).

Placement: ¿dónde ponerla?

Con paginación (y con segmentación paginada) la ubicación es irrelevante: el hardware traduce cualquier frame igual de rápido. Importa con segmentación pura (best-fit, first-fit, next-fit; ver particiones) y en multiprocesadores NUMA, donde conviene poner la página cerca del procesador que la usa.

Reemplazo: ¿a quién expulsar?

El objetivo es expulsar la página con menos probabilidad de usarse pronto. Por la localidad, el pasado reciente predice bien el futuro cercano.

Bloqueo de frames (frame locking): algunos frames no pueden ser víctimas:

• el kernel y sus estructuras de control,
• los buffers de E/S que un dispositivo está usando (por DMA),
• otras áreas críticas en tiempo.

Se marcan con un bit de bloqueo en la tabla de frames o en la PTE.

Cómo leerlo: un fallo de página es cualquier referencia a una página que no está en RAM. Si queda un marco libre (típico al principio), se carga ahí y no corre ningún algoritmo. Solo cuando la memoria está llena hay que elegir una página víctima, que puede ser del mismo proceso o de otro (reemplazo local o global). Sacar un proceso entero es otra cosa: swapping.

🔮 Predice antes de seguir

Antes de ver la tabla: con 3 marcos y la cadena 1 2 3 1 4, ¿cuántos fallos da FIFO y cuántos LRU? ¿Cuál de los dos expulsa al 1, y por qué eso es una mala idea?

Ya tengo mi respuesta: comparar

Los dos dan 4 fallos: los tres de arranque y el del 4. La diferencia está en a quién sacan para meter el 4. FIFO saca al 1, porque llegó primero, aunque se acaba de usar. LRU saca al 2, que es el que lleva más tiempo sin usarse. Si la cadena siguiera con otro 1, FIFO fallaría de nuevo y LRU acertaría.

Los cuatro algoritmos básicos

💡 En simple: un ejemplo de cinco referencias

3 marcos y las referencias 1 2 3 1 4. Las tres primeras llenan los marcos; el 1 acierta. Cuando llega el 4, hay que sacar a alguien:

• FIFO saca la que llegó primero: la 1… ¡aunque la acabas de usar!
• LRU saca la que lleva más tiempo sin usarse: la 2 (el 1 se usó recién y el 3 después del 2).
• OPT mira el futuro: saca la que se vuelva a usar más tarde, o nunca. Si después vienen «1 3», sacaría la 2.

Por eso FIFO suele ser malo: no le importa si la página se está usando, solo cuándo llegó.

Algoritmo	Expulsa…	Costo	Comentario
OPT (óptimo, Belady)	la página cuya próxima referencia está más lejos en el futuro	imposible de implementar	sirve de referencia para medir a los demás: produce el mínimo de fallos
LRU	la página no referenciada hace más tiempo	caro: hay que registrar cada acceso (marca de tiempo o pila)	casi tan bueno como OPT; la mejor aproximación práctica
FIFO	la página que lleva más tiempo en memoria	trivial: un buffer circular	malo: expulsa páginas muy usadas solo por ser «viejas»; sufre la anomalía de Belady
Clock (segunda oportunidad)	la primera página con bit de uso = 0 que encuentra el puntero	barato: un bit por frame	aproxima LRU

Cómo funciona Clock (Stallings fig. 8.15):

1. Los frames candidatos forman un círculo, con un puntero y un bit de uso u por frame.
2. Al cargar una página o al referenciarla, u = 1.
3. En un fallo, el puntero avanza:
   • si encuentra u = 1, lo pone en 0 (la página «gasta su segunda oportunidad») y sigue;
   • si encuentra u = 0, reemplaza esa página, pone su u = 1 y deja el puntero en el siguiente frame.
4. Si todos tenían u = 1, el puntero da la vuelta completa, apaga todos los bits y reemplaza la página donde empezó. En ese caso Clock degenera en FIFO.

Cómo leerlo: a la izquierda, el estado cuando llega la página 4 y no está. El puntero empieza en la pág. 8 y avanza en sentido horario: a las que tienen u = 1 les apaga el bit y sigue; en la primera con u = 0 (la pág. 2) se detiene y la reemplaza. A la derecha, el resultado: en amarillo, los bits que cambiaron; en verde, la página nueva. Ejemplo propio.

Acierto contra fallo: quién sube y quién baja el bit. Es la duda más común con Clock:

• Acierto (la página ya está en RAM): el hardware pone su u en 1. Si ya era 1, queda en 1. El puntero no se mueve y ningún otro bit cambia.
• Fallo (la página no está): recién ahí se mueve el puntero. Baja a 0 solo los bits de las páginas por las que pasa, hasta encontrar la víctima. Las que quedan más adelante conservan su u.

El bit de uso es una segunda oportunidad: un acierto se la devuelve a la página; el paso del puntero en un fallo se la quita.

Cómo leerlo: los dos lados parten del mismo estado. A la izquierda llega B, que ya está: solo su bit pasa a 1 y el puntero sigue apuntando a C. A la derecha llega X, que no está: el puntero apaga el bit de C, encuentra a D con u = 0 y la reemplaza.

Reemplazo de páginas paso a paso

Escribe la cadena de referencias, elige cuántos frames hay y el algoritmo. «F» marca un fallo de página; en Clock, el * es el bit de uso y ▸ es la posición del puntero.

Ejercicio P1 (3 frames)Belady (P2)Ejercicio P4 (Clock, 4 frames)Stallings fig. 8.14Hoja sem 11 · ej 1Ej 2 (RR + FIFO)Ej 3 (prioridad + LRU)

ReferenciasFrames: 3

FIFOOPTLRUClock

⟲ Inicio◀ PasoPaso ▶Todo ⏭

ref	2	3	2	1	5	2	4	5	3	2	5	2
f0	2	2	2	2	2	2	2	2	3	3	3	3
f1	·	3	3	3	5	5	5	5	5	5	5	5
f2	·	·	·	1	1	1	4	4	4	2	2	2
fallo	F	F		F	F		F		F	F

Paso 12: 2 ya está en el frame 2: acierto.

Fallos7

Aciertos5

Tasa de fallos58 %

Fallos según el número de frames

algoritmo	1 fr	2 fr	3 fr	4 fr	5 fr	6 fr	7 fr
FIFO	12	10	9	6	5	5	5
OPT	12	7	6	5	5	5	5
LRU	12	10	7	6	5	5	5
Clock	12	10	8	6	5	5	5

Con esta cadena ningún algoritmo empeora al agregar frames.

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

Resuelto: la cadena de Stallings (fig. 8.14)

Cadena 2 3 2 1 5 2 4 5 3 2 5 2 con 3 marcos. En el simulador de arriba elige el preset «Stallings» y avanza paso a paso. Antes de cada paso, di qué página sale y por qué. El resultado está justo debajo: OPT 6, LRU 7, Clock 8 y FIFO 9, contando los fallos de arranque.

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

Complétalo: LRU con 3 marcos y la cadena 1 2 3 2 4 1 3 2 4 1

Las cinco primeras columnas ya están resueltas. Completa las otras cinco: escribe qué hay en los marcos y marca cada fallo con ✗.

Ref.	1	2	3	2	4	1	3	2	4	1
Marcos	1	1 2	1 2 3	1 2 3	4 2 3	?	?	?	?	?
¿Fallo?	✗	✗	✗	✓	✗ (sale 1)	?	?	?	?	?

Comparar con la solución (9 fallos)

Ref.	1	3	2	4	1
Marcos	4 2 1	4 3 1	2 3 1	2 3 4	2 1 4
Sale	3	2	4	1	3

En cada fallo sale la página cuyo último uso es el más antiguo. Por ejemplo, cuando llega el 1 (posición 6), el último uso del 4 fue en la posición 5, el del 2 en la 4 y el del 3 en la 3. Por eso sale el 3. En total son 9 fallos: solo acierta el segundo 2.

Peldaño 3 · Solosin ayuda; luego compara

Solo: la misma cadena con FIFO, OPT y Clock

Usa la misma cadena y 3 marcos. Cuenta los fallos de FIFO, de OPT y de Clock. En Clock, u = 1 al cargar una página y, después de reemplazar, el puntero pasa al marco siguiente.

Comparar (verificado con un script)

• FIFO = 6: 1 · 12 · 123 · ✓ · 423 · 413 · ✓ · 412 · ✓ · ✓.
• OPT = 5: cuando llega el 4 sale el 2, porque de 1, 2 y 3 es el que se vuelve a usar más tarde (posición 8). Cuando llega el 2 sale el 3, que ya no se vuelve a usar.
• Clock = 6: coincide paso a paso con FIFO. En cada fallo todos los u están en 1, así que el puntero da la vuelta completa y reemplaza en orden de llegada.

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

Variante: ¿LRU siempre le gana a FIFO?

Con esta misma cadena, LRU da 9 fallos y FIFO 6. Antes de abrir la respuesta, explica cómo puede pasar.

Por qué aquí pierde LRU

La cadena repite un ciclo de 4 páginas (… 4 1 3 2 4 1), pero solo hay 3 marcos. En ese caso LRU siempre saca justo la página que se va a pedir a continuación: si el ciclo es más largo que la memoria, la que lleva más tiempo sin usarse es precisamente la próxima. Es el peor caso de LRU, el mismo de la segunda pasada sobre un arreglo grande.

Lección: que «LRU es casi tan bueno como OPT» es cierto en promedio y con buena localidad, no para cualquier cadena. En el examen, simula siempre y no supongas de antemano qué algoritmo saldrá mejor.

Ejemplo de Stallings (fig. 8.14). Cadena 2 3 2 1 5 2 4 5 3 2 5 2 con 3 frames. Contando también los 3 fallos iniciales: OPT 6, LRU 7, Clock 8, FIFO 9. Stallings cuenta solo los fallos después de llenar los frames: 3, 4, 5 y 6. Revisa en el examen cuál de las dos convenciones piden.

Clock con bit de modificado (Clock mejorado)

💡 En simple: tarjeta amarilla y segunda oportunidad

Clock es como un árbitro que recorre las páginas en círculo:

• si la página fue usada hace poco (u = 1), le muestra una tarjeta amarilla (u = 0) y la deja seguir;
• si ya tenía tarjeta amarilla (u = 0), la expulsa.

El Clock mejorado además prefiere expulsar páginas que no se modificaron (m = 0), porque echarlas no cuesta escribir nada en el disco.

Si además se considera el bit M, expulsar una página sin modificar es más barato, porque no hay que escribirla al disco. Hay cuatro clases:

Clase	u	m	Significado	Preferencia
1	0	0	ni usada recientemente ni modificada	mejor víctima
2	0	1	no usada recientemente, pero modificada (hay que escribirla)	2.ª
3	1	0	usada recientemente, sin modificar	3.ª
4	1	1	usada y modificada	última

Algoritmo (Stallings fig. 8.17):

1. Recorre buscando (u = 0, m = 0) sin tocar los bits. Si encuentra uno, es la víctima.
2. Si no, recorre buscando (u = 0, m = 1) y va poniendo u = 0 en los que pasa.
3. Si tampoco encuentra, todos los u quedaron en 0: repite el paso 1 y, si hace falta, el 2. Seguro encuentra una víctima.

Cómo leerlo: las filas son el bit u y las columnas, el bit m. La mejor víctima está arriba a la izquierda: nadie la usó y no hay que escribirla. El paso 1 solo mira esa casilla; el paso 2, la de al lado. La flecha muestra por qué el algoritmo siempre termina: el paso 2 va apagando u, así que las páginas de abajo «suben» a la fila de arriba.

Lo usaba el Macintosh.

La anomalía de Belady

💡 En simple: más espacio, más fallos (solo con FIFO)

Lo lógico sería que con más marcos haya menos fallos. Con FIFO no siempre: con la cadena A B C D A B E A B C D E hay 9 fallos con 3 marcos y 10 con 4.

Pasa porque FIFO decide por orden de llegada, y ese orden cambia según cuántos marcos haya. LRU y OPT nunca tienen la anomalía: lo que guardan con 3 marcos siempre está incluido en lo que guardan con 4.

Lo esperable es que con más frames haya menos o los mismos fallos. FIFO puede violar esto. Con la cadena del ejercicio P2 (A B C D A B E A B C D E):

Frames	FIFO	Clock	LRU	OPT
3	9	9	10	7
4	10 ⚠	10 ⚠	8	6

Cómo leerlo: en cada algoritmo, la barra izquierda es con 3 marcos y la derecha con 4. Lo normal es que la derecha sea más baja (LRU, OPT). En FIFO y Clock la derecha es más alta: más memoria, más fallos. Esa es la anomalía.

LRU y OPT son algoritmos de pila: el conjunto de páginas con n frames está siempre contenido en el de n + 1 frames, así que agregar memoria nunca empeora. FIFO y Clock no cumplen esa propiedad. En el simulador de arriba, elige «Belady (P2)» y mira la tabla de fallos por número de frames.

¿Por qué LRU no puede tener la anomalía? (argumento corto)

Con LRU, las páginas en memoria con n frames son siempre las n referenciadas más recientemente. Con n + 1 frames son las n + 1 más recientes, que incluyen a las n anteriores. Si una referencia acierta con n frames (está entre las n más recientes), también acierta con n + 1. Por lo tanto, los fallos con n + 1 frames ≤ fallos con n. FIFO no tiene esta propiedad de inclusión, porque el orden de llegada depende de los fallos previos, que son distintos para cada número de frames.

🔮 Debate: elige y defiende

Diseñas el SO de un equipo pequeño con 64 marcos. El hardware no marca el bit u y el disco es lento. ¿Eliges FIFO, LRU o Clock? Defiende tu elección con el costo de implementación y con el número de fallos. Después cambia el escenario: un servidor cuyo hardware sí pone u = 1 en cada acceso.

Ya tengo mi respuesta: comparar

• Sin bit u en hardware: Clock no se puede usar tal cual, y un LRU exacto obligaría a registrar cada acceso por software, lo que es carísimo. La opción realista es FIFO con page buffering (ver abajo): la víctima queda un tiempo en la lista libre y, si se vuelve a pedir pronto, se recupera sin ir al disco. Eso compensa lo malo de FIFO.
• Con bit u en hardware: Clock, o el Clock mejorado si además hay bit m, porque con un disco lento conviene evitar escrituras. Cuesta solo un bit por marco y aproxima bien a LRU.
• Nunca OPT: no se puede implementar, porque exige conocer el futuro. Solo sirve como referencia para medir a los demás.

No hay un ganador universal: la elección depende de qué ofrece el hardware y de cuánto cuesta un fallo.

Page buffering

💡 En simple: la papelera de reciclaje

La página expulsada no se borra de inmediato: va a una papelera de reciclaje (una lista en RAM). Si al rato la vuelves a necesitar, la recuperas de la papelera sin ir al disco. Recién cuando hace falta el espacio de verdad, se vacía la papelera.

Así hasta un algoritmo simple como FIFO se vuelve bastante bueno.

Es una forma de compensar lo malo de FIFO sin pagar lo que cuesta LRU (la usaba VAX/VMS).

1. La víctima elegida (por FIFO) no se borra de inmediato. Su PTE se marca como no presente, pero la página queda en RAM en una de dos listas:
   • la lista de páginas libres, si no estaba modificada;
   • la lista de páginas modificadas, si estaba modificada.
2. Si el proceso la vuelve a referenciar pronto, se recupera de la lista sin leer del disco. Es un fallo baratísimo.
3. Las páginas modificadas se escriben al disco en grupos, lo que reduce la E/S.

Cómo leerlo: la víctima no se borra: su PTE pasa a P = 0, pero la página sigue en RAM en una de las dos listas. Las modificadas se limpian en lote y pasan a la de libres. Desde ahí, o el proceso la vuelve a pedir y se recupera sin disco (verde), o nadie la pide y su frame se reutiliza. Desde la lista de modificadas también se puede recuperar.

Las listas funcionan como una caché de páginas. Linux hace algo parecido con su page cache y sus listas activa e inactiva (ver UNIX y Linux).

Reemplazo y caché: en un sistema con caché de datos, Stallings menciona políticas de ubicación según la caché (page coloring), que eligen frames para repartir las páginas entre los conjuntos de la caché y reducir los conflictos.

⚠️ Errores que cuestan puntos

• Contar los fallos sin decir si se incluyen los de arranque.Declara la convención. En la fig. 8.14, Stallings da 3, 4, 5 y 6 sin contar los fallos iniciales, y contándolos son 6, 7, 8 y 9.
• Atribuir la anomalía de Belady a LRU.Solo pueden tenerla FIFO y Clock. LRU y OPT son algoritmos de pila: lo que guardan con n marcos está incluido en lo que guardan con n + 1.
• En Clock, mover el puntero cuando hay un acierto.Un acierto solo pone u = 1. El puntero se mueve únicamente mientras busca una víctima.
• En Clock mejorado, apagar los bits u en la primera pasada.La 1.ª pasada busca (0,0) sin tocar nada. Recién la 2.ª, que busca (0,1), va poniendo u = 0.
• Suponer que LRU siempre le gana a FIFO.Con un ciclo más largo que la memoria, LRU puede perder: 9 fallos contra 6 en el peldaño 4.

Autoevaluación

0/7 correctas · 0 respondidas Reiniciar

1. Con paginación, la política de placement…

a) es crítica (best-fit)b) es irrelevante: cualquier frame sirve igualc) decide la víctimad) decide cuántos frames tiene el proceso

2. ¿Qué algoritmo produce el mínimo de fallos posible?

a) LRUb) FIFOc) OPTd) Clock

3. En Clock, el puntero encuentra un frame con u = 1. ¿Qué hace?

a) Lo reemplazab) Pone u = 0 y avanzac) Lo bloquead) Se detiene

4. ¿Cuál puede presentar la anomalía de Belady?

a) OPTb) LRUc) FIFOd) Ninguno

5. En Clock mejorado, la mejor víctima es…

a) u=1, m=1b) u=0, m=1c) u=0, m=0d) u=1, m=0

6. Page buffering mejora a FIFO porque…

a) usa marcas de tiempob) la víctima queda un tiempo en una lista y se recupera sin E/S si se vuelve a usarc) evita los page faultsd) bloquea los frames del kernel

7. ¿Qué frames NO pueden ser víctimas?

a) Los que tienen M = 1b) Los bloqueados: kernel, buffers de E/S en usoc) Los del proceso actuald) Los de páginas compartidas

🗣️ Explícalo tú (Feynman)

Explícale a alguien de Programación I por qué Clock es «una versión barata de LRU» y en qué caso se comporta igual que FIFO.

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…

• LRU necesita conocer el orden exacto de los usos, es decir, una marca de tiempo por cada acceso. Clock guarda un solo bit: si la página se usó hace poco o no.
• El puntero recorre los marcos en círculo. Si encuentra u = 1, lo apaga (segunda oportunidad) y sigue; si encuentra u = 0, esa página es la víctima.
• Si todas tienen u = 1, el puntero da la vuelta completa apagándolas y saca la primera. Eso es exactamente FIFO.
• Un ejemplo concreto, como la cadena del peldaño 3, donde Clock coincide con FIFO.

Error típico al explicarlo: decir que Clock «recuerda cuál se usó menos veces». No cuenta usos: solo distingue entre usada hace poco y no usada.

📈 ¿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 (Fetch, Placement, Replacement Policy, Page Buffering) · sem_9/11-OSL-Ejercicios_Page_Replacement.pdf (P1, P2) · Simulador propio verificado contra un script independiente