Ejercicios resueltos: Page Replacement

💡 En simple

Para este tipo de pregunta, dibuja una tabla: una columna por referencia y una fila por frame. En cada columna escribe qué hay en memoria después de ese acceso y marca con F los fallos. La regla de cada algoritmo solo importa cuando la memoria está llena y hay que elegir a quién sacar. Practica en el simulador y después compara tu tabla con la solución.

🎯 Al terminar podrás

1. Simular FIFO, OPT, LRU y Clock en una tabla referencia × frames y contar los fallos sin errores de convención.
2. Mostrar la anomalía de Belady con números.
3. Calcular el tamaño de una tabla de páginas a partir del espacio virtual, el tamaño de página y el tamaño de la PTE.
4. Diseñar una PTE para Clock y simularlo dejando el puntero y los bits de uso explícitos.

Antes necesitas: Reemplazo (con escalera de práctica) · Paginación

• Examen cronométrate y no abras la solución hasta terminar
• Simulador predice el estado antes de pulsar el paso siguiente

Modo examen

Estas son hojas de análisis como las del LC3 (3 pts cada pregunta). Hazlas cronometradas (unos 12 minutos por pregunta), en papel y sin abrir la solución hasta terminar. Al corregir, clasifica cada error: ¿conceptual (no sabías la regla), procedimental (sabías la regla pero te saltaste un paso) o de interpretación (leíste mal el enunciado)? Repasa según el tipo: si es conceptual, vuelve a la página del tema; si es procedimental, a la escalera de práctica.

Convenciones usadas (decláralas en el examen)

• Los frames empiezan vacíos, y los primeros fallos (que solo llenan frames) sí se cuentan.
• Clock (como Stallings): al cargar una página su bit de uso queda en 1 y el puntero avanza al siguiente frame. Un acierto pone el bit en 1 sin mover el puntero.
• OPT: si hay empate (varias páginas que no se vuelven a usar), se saca la del frame de menor número. El empate no cambia la cantidad de fallos.

Pregunta 1 · FIFO, OPT, LRU y Clock con 3 frames

Referencias: A B D C B E D B D B A C B C A C.

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	A	B	D	C	B	E	D	B	D	B	A	C	B	C	A	C
f0	A	A	A	C	C	C	C	C	D	D	D	D	B	B	B	B
f1	·	B	B	B	B	E	E	E	E	E	A	A	A	A	A	A
f2	·	·	D	D	D	D	D	B	B	B	B	C	C	C	C	C
fallo	F	F	F	F		F		F	F		F	F	F

Paso 16: C ya está en el frame 2: acierto.

Fallos10

Aciertos6

Tasa de fallos63 %

Fallos según el número de frames

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

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

Solución: FIFO = 10, OPT = 7, LRU = 8, Clock = 9 fallos

FIFO (10 fallos)

Verde: la página que entra en ese fallo. El punto verde marca el bit de uso en 1, si la traza lo tiene. Total: 10 fallos.

OPT (7 fallos)

Verde: la página que entra en ese fallo. El punto verde marca el bit de uso en 1, si la traza lo tiene. Total: 7 fallos.

Por ejemplo, en la cuarta referencia (C), el futuro es B E D B D B A…: A es la que se usa más tarde, así que sale A.

LRU (8 fallos)

Verde: la página que entra en ese fallo. El punto verde marca el bit de uso en 1, si la traza lo tiene. Total: 8 fallos.

Clock (9 fallos). El punto verde en la esquina de cada casilla es el bit de uso en 1.

Verde: la página que entra en ese fallo. El punto verde marca el bit de uso en 1, si la traza lo tiene. Total: 9 fallos.

Por ejemplo, en la cuarta referencia (C) los tres tienen u = 1. El puntero da una vuelta completa poniéndolos en 0, vuelve al frame 0 y reemplaza a A. Es el caso en que Clock se comporta como FIFO.

Comparación: OPT (7) < LRU (8) < Clock (9) < FIFO (10). Es el orden esperable: Clock aproxima a LRU con un solo bit.

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

Variante de P1: la misma cadena con 4 frames (y con 2)

Antes de simular, predice: ¿todos los algoritmos bajan de fallos con 4 frames? Después compruébalo en el simulador cambiando el número de frames.

Comparar (verificado con un script)

Frames	FIFO	LRU	OPT	Clock
2	13	12	9	13
3	10	8	7	9
4	7	7	6	8

Con esta cadena todos mejoran al agregar frames: aquí no aparece la anomalía de Belady. Que pueda aparecer con FIFO no significa que aparezca siempre: P2 es una cadena construida justamente para provocarla.

Pregunta 2 · FIFO con 3 y 4 frames

Referencias: A B C D A B E A B C D E.

Solución: 9 fallos con 3 frames y 10 con 4 (anomalía de Belady)

3 frames: 9 fallos

Verde: la página que entra en ese fallo. El punto verde marca el bit de uso en 1, si la traza lo tiene. Total: 9 fallos.

4 frames: 10 fallos

Verde: la página que entra en ese fallo. El punto verde marca el bit de uso en 1, si la traza lo tiene. Total: 10 fallos.

Comparación: con más memoria hay más fallos. Es la anomalía de Belady (es la cadena clásica de su artículo de 1969).

Con 4 frames, FIFO mantiene A y B «viejas» hasta que justo se necesitan. Con 3, el orden de expulsión coincide mejor con el uso. FIFO no es un algoritmo de pila: el contenido con 3 frames no está incluido en el de 4.

Con la misma cadena: LRU 10 → 8 y OPT 7 → 6 (no tienen la anomalía); Clock 9 → 10 (también la tiene). Compruébalo en el simulador con «Belady (P2)»: la tabla inferior marca en rojo los saltos.

Pregunta 3 · Memoria virtual de 6 GB, páginas de 8 kB y PTE de 6 B

Solución: 786 432 páginas; tabla de 4.5 MiB

• Páginas virtuales:

$$\frac{6\ \text{GB}}{8\ \text{kB}} = \frac{6 \cdot 2^{30}}{2^{13}} = 6 \cdot 2^{17} = 3 \cdot 2^{18} = \mathbf{786\,432}$$

• Tamaño de la tabla: una PTE por página virtual.

$$786\,432 \times 6\ \text{B} = 4\,718\,592\ \text{B} = \mathbf{4.5\ MiB}$$

Es decir, $4\,718\,592 / 8192 = 576$ páginas de 8 kB solo para la tabla de un proceso.

Ojo: 6 GB no es potencia de 2. Se necesitan $\lceil \log_2(6 \cdot 2^{30}) \rceil = 33$ bits de dirección virtual, que direccionan 8 GB. Si el enunciado tomara la tabla «completa» para 33 bits, serían $2^{20}$ entradas × 6 B = 6 MiB. Declara cuál usas. La pregunta dice «memoria virtual de 6 GB», así que lo natural es 786 432 páginas.

Pregunta 4 · PTE para Clock (10-10-12) y simulación con 4 frames

Formato de la PTE

• Dirección virtual: 10 | 10 | 12. Offset de 12 bits, así que la página es de 4 KB. 10 bits por nivel dan 1024 entradas por tabla, y con PTE de 4 B cada tabla ocupa 4 KB: una página.
• Dirección física de 32 bits: el número de frame tiene 32 − 12 = 20 bits.
• La PTE de 32 bits tiene 20 bits de frame más 12 bits de control:

Los números de arriba son las posiciones de bit. El frame ocupa los 20 bits altos y los bits de control, los de abajo.

• V (válido/presente): la página está en RAM.
• U (uso/referenciado): imprescindible para Clock. Lo pone en 1 el hardware al acceder y lo apaga el puntero del reloj.
• M (modificado/dirty): no es necesario para Clock básico, pero sí para Clock mejorado y para saber si hay que escribir la víctima.
• W/X (o R/W/X): protección.
• Los bits libres pueden usarse para usuario/supervisor, caché deshabilitada, etc.

Simulación Clock con 4 frames: A B C A C D B D A E B F

Verde: la página que entra en ese fallo. El punto verde marca el bit de uso en 1, si la traza lo tiene. Total: 6 fallos.

Los dos momentos clave:

• E (10.ª referencia): los 4 frames tienen u = 1 y el puntero está en f0. Da una vuelta poniendo todo en 0 y reemplaza A por E en f0. El puntero queda en f1.
• B (11.ª): acierto, así que u(B) = 1.
• F (12.ª): el puntero está en f1. B tiene u = 1: se pone en 0 y avanza. C tiene u = 0: se reemplaza C por F. El puntero queda en f3.

Respuesta:

Frame	Página	Bit de uso
f0	E	1
f1	B	0
f2	F	1
f3	D	0

El puntero queda en el frame 3 (D) y hubo 6 fallos. Se puede comprobar con el preset «Ejercicio P4» del simulador.

Si tu profesor usa otra convención (por ejemplo, u = 0 al cargar), el contenido final puede cambiar. Escribe la convención en tu respuesta.

⚠️ Errores que cuestan puntos

• No escribir la convención de Clock (u al cargar, a dónde queda el puntero).Escríbela al inicio de la respuesta. Con u = 0 al cargar, el contenido final puede cambiar.
• En OPT, sacar la página que se usó hace más tiempo.Eso es LRU. OPT mira hacia adelante: saca la que se vuelve a usar más tarde, o nunca.
• Calcular el tamaño de la tabla con el número de frames.Entradas = páginas virtuales. Tamaño = entradas × bytes por PTE.

📈 ¿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_9/11-OSL-Ejercicios_Page_Replacement.pdf · Soluciones propias verificadas con dos simuladores independientes (el de esta web y un script en Python)