Memoria virtual — práctica con problemas guiados paso a paso: FIFO con su cola, LRU frente al óptimo, lo que cuesta un fallo y un ejercicio con el formato del examen (y la víctima de LRU que elegí mirando el futuro)
En el examen de prueba de IC2 me tocó un reemplazo de páginas con LRU. Iba rápido, rellenando la rejilla, hasta que en un fallo dudé a quién sacar. Miré la cadena, vi que la página 5 no volvía a aparecer en un buen rato y la eché. Me salieron 6 fallos y me quedé encantado. Al corregir: 8. Había hecho el óptimo, no LRU. LRU no mira lo que viene: mira lo que ya pasó y saca a la que lleva más tiempo sin usarse. Desde entonces, cuando dudo, me digo en voz baja: «FIFO mira la llegada, LRU el último uso, el óptimo el próximo uso».
Esta es la práctica guiada de memoria virtual. En la teoría de memoria virtual viste la paginación por demanda, el fallo de página, los algoritmos de reemplazo, la anomalía de Belady y el conjunto de trabajo, con gcc y sus tres marcos. Aquí resolvemos cuatro problemas paso a paso: FIFO con su cola, LRU y óptimo con la misma cadena, el tiempo efectivo de acceso con fallos y un ejercicio con el formato del examen. Después, en los ejercicios de memoria virtual, te toca a ti.
Tabla de Contenidos
Antes de empezar
Conviene tener claro:
- Qué es un fallo de página y que los tres primeros fallos con tres marcos vacíos son obligatorios (no hay a quién sacar).
- Qué mira cada algoritmo para elegir la víctima: FIFO, la que entró antes; LRU, la que lleva más tiempo sin usarse; óptimo, la que se va a usar más tarde (o nunca).
- La fórmula del tiempo efectivo de acceso: .
- Qué es la anomalía de Belady y que solo la sufre FIFO.
Si alguno te suena dudoso, repasa la teoría antes de seguir.
En papel, dibuja una rejilla con una columna por referencia y una fila por marco, y una fila extra abajo para marcar F (fallo) o un punto (acierto). Cada página nueva ocupa el marco de su víctima: no muevas las demás.
Cómo se resuelve un problema de reemplazo
Los cuatro problemas siguen el mismo método de cuatro pasos:
- Apunta la cadena de referencias, el número de marcos y el algoritmo.
- Para cada referencia, pregúntate primero si está en memoria. Si está, acierto (y en LRU, apunta que se acaba de usar). Si no, fallo.
- En cada fallo con los marcos llenos, elige la víctima con el criterio del algoritmo y escríbela debajo de la columna.
- Cuenta y comprueba: fallos + aciertos = longitud de la cadena; los primeros fallos obligatorios son tantos como marcos; el óptimo no puede dar más fallos que LRU ni que FIFO.
Problema 1: FIFO con su cola
Enunciado. Un proceso tiene 3 marcos y genera la cadena de referencias 1, 4, 5, 3, 1, 4, 2, 1, 4, 5, 1, 4. Aplica FIFO, indica las víctimas y cuenta los fallos.
La idea
FIFO se comporta como una cola: cuando hay que sacar a alguien, sale el que entró antes, aunque se haya usado hace un momento. Un acierto no cambia nada en la cola. Para no equivocarte, lleva la cola de llegada escrita al lado de la rejilla.
Paso a paso
| Pide | ¿Está? | Cola de llegada (la primera sale) | Víctima |
|---|---|---|---|
| 1 | no | 1 | — (obligatorio) |
| 4 | no | 1, 4 | — (obligatorio) |
| 5 | no | 1, 4, 5 | — (obligatorio) |
| 3 | no | 4, 5, 3 | 1 |
| 1 | no | 5, 3, 1 | 4 |
| 4 | no | 3, 1, 4 | 5 |
| 2 | no | 1, 4, 2 | 3 |
| 1 | sí | 1, 4, 2 | — |
| 4 | sí | 1, 4, 2 | — |
| 5 | no | 4, 2, 5 | 1 |
| 1 | no | 2, 5, 1 | 4 |
| 4 | no | 5, 1, 4 | 2 |
10 fallos y 2 aciertos. Víctimas: 1, 4, 5, 3, 1, 4 y 2.
Comprobación
- 10 + 2 = 12 referencias.
- Los tres primeros fallos son obligatorios: los tres marcos empiezan vacíos.
- En la referencia 5 de la cadena (el 1), FIFO saca al 4, que se había pedido hacía muy poco: es justo lo que hace mal FIFO, y por eso da tantos fallos.
Preguntas que te puedes hacer
¿Por qué un acierto no cambia la cola de FIFO? Porque FIFO solo mira cuándo entró cada página. Que se use otra vez no la «rejuvenece»; eso es lo que hace LRU.
¿Con 4 marcos habría menos fallos? Con esta cadena, sí: 8. Pero con FIFO no está garantizado: hay cadenas en las que más marcos dan más fallos. Es la anomalía de Belady.
¿Por qué los fallos obligatorios cuentan como fallos? Porque la página no estaba en memoria y hubo que traerla del disco. Que no haya víctima no lo hace gratis.
Mover la página acertada al final de la cola en FIFO. Eso es LRU. En FIFO, los aciertos no tocan la cola.
Pruébalo tú
- Repite FIFO con 4 marcos y comprueba que salen 8 fallos.
- ¿Qué referencia de la cadena tendrías que cambiar para que FIFO acertara una vez más?
Problema 2: LRU frente al óptimo
Enunciado. Con la misma cadena y 3 marcos, aplica LRU y el algoritmo óptimo. Compara los fallos de los tres algoritmos.
La idea
Los dos miran algo distinto en cada fallo: LRU mira hacia atrás (¿a cuál le hace más tiempo que no pido?) y el óptimo mira hacia delante (¿a cuál voy a pedir más tarde, o nunca?). Con la cadena escrita delante, en LRU se busca hacia la izquierda desde la referencia actual y en el óptimo, hacia la derecha.
Paso a paso
LRU. Llevamos las páginas en memoria ordenadas de la menos a la más reciente (la primera es la víctima):
| Pide | ¿Está? | Orden de uso (primera = víctima) | Víctima |
|---|---|---|---|
| 1, 4, 5 | no | 1, 4, 5 | — (obligatorios) |
| 3 | no | 4, 5, 3 | 1 |
| 1 | no | 5, 3, 1 | 4 |
| 4 | no | 3, 1, 4 | 5 |
| 2 | no | 1, 4, 2 | 3 |
| 1 | sí | 4, 2, 1 | — |
| 4 | sí | 2, 1, 4 | — |
| 5 | no | 1, 4, 5 | 2 |
| 1 | sí | 4, 5, 1 | — |
| 4 | sí | 5, 1, 4 | — |
8 fallos. La diferencia con FIFO está en la referencia 10 (el 5): LRU saca al 2, que lleva tiempo sin usarse, mientras que FIFO sacaba al 1, que se acababa de usar.
Óptimo. En cada fallo con los marcos llenos, miramos la cadena que queda desde ese punto y sacamos a la página que se vuelve a pedir más tarde (o nunca):
| Fallo en | Marcos | Lo que queda de cadena | Próximo uso | Víctima |
|---|---|---|---|---|
| el 3 (ref. 4) | 1, 4, 5 | 1, 4, 2, 1, 4, 5, 1, 4 | 1 enseguida, 4 después, 5 mucho más tarde | 5 |
| el 2 (ref. 7) | 1, 4, 3 | 1, 4, 5, 1, 4 | 1 y 4 enseguida, el 3 nunca | 3 |
| el 5 (ref. 10) | 1, 4, 2 | 1, 4 | 1 y 4 enseguida, el 2 nunca | 2 |
Entre medias, todo son aciertos: las referencias 5 y 6 (1 y 4), 8 y 9 (1 y 4) y 11 y 12 (1 y 4). 6 fallos: 3 obligatorios y solo 3 de reemplazo.
| Algoritmo | Fallos | Aciertos | Víctimas |
|---|---|---|---|
| FIFO | 10 | 2 | 1, 4, 5, 3, 1, 4, 2 |
| LRU | 8 | 4 | 1, 4, 5, 3, 2 |
| Óptimo | 6 | 6 | 5, 3, 2 |
Comprobación
- 6 ≤ 8 ≤ 10: el óptimo es el mínimo posible con 3 marcos; si otro algoritmo te diera menos, el óptimo estaría mal.
- En los tres hay 3 fallos obligatorios.
- Cada víctima del óptimo es una página que se pide más tarde que las otras dos (o nunca): compruébalo columna a columna en la rejilla.
Preguntas que te puedes hacer
¿Y si dos páginas no vuelven a pedirse nunca? Da igual cuál salga para el número de fallos; para que la rejilla sea única, se desempata con FIFO (sale la que entró antes). Escríbelo si te pasa en el examen.
Si el óptimo es el mejor, ¿por qué no se usa? Porque necesita conocer el futuro. Sirve de referencia para medir lo cerca que se queda un algoritmo real.
¿Por qué LRU se parece al óptimo? Por la localidad: lo que no se ha usado hace mucho, probablemente tarde en volver a usarse. Es mirar el pasado como predicción del futuro.
¿Cómo se lleva LRU en la práctica? Con contadores o con una pila de páginas, cosa cara. Por eso los sistemas usan aproximaciones con el bit de referencia (el reloj, NRU, aging).
En LRU, elegir la víctima mirando hacia delante en la cadena. Eso es el óptimo. LRU mira solo hacia atrás.
Pruébalo tú
- Aplica LRU con 4 marcos. ¿Mejora como FIFO?
- Cambia la última referencia (el 4) por un 3. ¿Cambia algún fallo del óptimo?
Problema 3: lo que cuesta un fallo de página
Enunciado. La memoria tarda 100 ns y servir un fallo de página, 8 ms. a) Calcula el tiempo efectivo de acceso con una probabilidad de fallo y . b) ¿Qué máxima permite que el tiempo efectivo no pase de 110 ns (un 10 % más lento)?
La idea
Es la misma media ponderada de la TLB, pero con números muy desiguales: un fallo cuesta 8 ms = 8 000 000 ns, ochenta mil veces un acceso. Hay que pasar todo a la misma unidad antes de multiplicar.
Paso a paso
a)
b) Se despeja :
Un fallo cada 800 000 accesos, como mucho.
Comprobación
- Con sale 100 ns y con , 8 ms: los dos resultados están entre esos extremos.
- parece pequeña, pero el TEA se multiplica por 81. Si te sale un número «razonable» con esa , revisa las unidades.
Preguntas que te puedes hacer
¿Por qué un fallo tarda milisegundos? Porque hay que leer la página del disco (y, si la víctima está modificada, escribirla antes). La CPU y la RAM trabajan en nanosegundos; el disco, en milisegundos.
¿Cambia algo si la mitad de las víctimas están sucias? Sí: esas cuestan dos operaciones de disco (escribir la víctima y leer la nueva), así que el servicio medio del fallo sube y el TEA también. Por eso existe el bit M.
¿Cómo se consigue una tan pequeña? Con la localidad: los programas trabajan en cada momento con pocas páginas (su conjunto de trabajo), y si caben en sus marcos casi no hay fallos.
Mezclar milisegundos y nanosegundos en la fórmula (poner 8 en lugar de 8 000 000). Pasa siempre todo a la misma unidad antes de multiplicar.
Pruébalo tú
- Calcula el TEA con .
- Repite el apartado b) para no pasar de 200 ns.
Problema 4: un ejercicio con el formato del examen
En la parte escrita y en los cálculos del test de IC2 cae casi seguro un reemplazo de páginas: una cadena, un número de marcos y uno o varios algoritmos, con los fallos y la tasa de fallos. Se valora la rejilla completa y las víctimas. Este ejercicio es original y está escrito con ese formato.
Ejercicio. Con 3 marcos inicialmente vacíos y la cadena 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3: a) aplica FIFO y LRU y dibuja la rejilla; b) indica en cada uno el número de fallos y la tasa de fallos; c) ¿cuál se comporta mejor con esta cadena y por qué?
| Algoritmo | Fallos | Tasa de fallos |
|---|---|---|
| FIFO | ___ | ___ |
| LRU | ___ | ___ |
La idea
Dos rejillas con la misma cadena: haz una entera antes de empezar la otra. La diferencia entre FIFO y LRU aparecerá cuando una página que se acaba de usar sea la más antigua en llegar.
Paso a paso
FIFO (cola de llegada, la primera sale):
| Pide | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ¿Fallo? | F | F | F | F | · | F | F | F | F | F | F | · |
| Víctima | 7 | 0 | 1 | 2 | 3 | 0 | 4 |
LRU (sale la que lleva más tiempo sin usarse):
| Pide | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ¿Fallo? | F | F | F | F | · | F | · | F | F | F | F | · |
| Víctima | 7 | 1 | 2 | 3 | 0 | 4 |
| Algoritmo | Fallos | Tasa de fallos |
|---|---|---|
| FIFO | 10 | 10 / 12 = 83,3 % |
| LRU | 9 | 9 / 12 = 75 % |
c) LRU es mejor con esta cadena. La diferencia está en la referencia 6 (el 3): FIFO saca al 0, que entró el primero de los que quedan pero se acababa de usar; LRU saca al 1, que llevaba más tiempo sin usarse. Por eso en la referencia 7 (otra vez el 0) LRU acierta y FIFO falla.
Comprobación y cómo se corrige
- Fallos + aciertos = 12 en las dos rejillas (10 + 2 y 9 + 3).
- Cada víctima de FIFO es la primera de la cola de llegada en ese momento; cada víctima de LRU, la que se usó hace más tiempo. Compruébalo en dos o tres columnas al azar.
Se valora la rejilla completa (con el contenido de los marcos, no solo las F), las víctimas, la tasa de fallos como fracción y el porqué del apartado c), que tiene que señalar la referencia en la que los algoritmos se separan.
Dar solo el número de fallos sin la rejilla. Si un fallo está mal, sin rejilla no hay nada que puntuar.
Pruébalo tú
- Aplica el óptimo a la misma cadena. ¿Cuántos fallos da?
- ¿Cuántos fallos da FIFO con 4 marcos? ¿Hay anomalía de Belady?
Errores típicos en esta práctica
- Mover la página acertada en FIFO: los aciertos no cambian la cola de llegada.
- Mirar hacia delante en LRU: eso es el óptimo; LRU mira el pasado.
- Decidir el óptimo fuera de orden: cada víctima se elige en su fallo, con la cadena que queda desde ahí.
- Olvidar los fallos obligatorios de los primeros marcos vacíos.
- Mezclar unidades en el tiempo efectivo de acceso.
- Dar el resultado sin rejilla, o sin comprobar fallos + aciertos.
Compruébalo con Python
Este programa aplica FIFO, LRU y el óptimo a las cadenas del Problema 1, 2 y 4, escribe la traza de FIFO y LRU y calcula el tiempo efectivo de acceso. Hazlo primero a mano.
# Memoria virtual de papel: FIFO, LRU y óptimo con traza de marcos, y tiempo efectivo de acceso.
def reemplazo(cad, nmarcos, alg):
marcos, fallos, filas = [], 0, []
for i, p in enumerate(cad):
if p in marcos:
filas.append((p, list(marcos), "acierto", ""));
if alg == "LRU": marcos.remove(p); marcos.append(p) # LRU: pasa a ser el más reciente
continue
fallos += 1; vict = ""
if len(marcos) == nmarcos:
if alg == "OPT": # el que se va a usar más tarde (o nunca)
fut = cad[i + 1:]
vict = max(marcos, key=lambda m: fut.index(m) if m in fut else len(fut) + 1)
else: vict = marcos[0] # FIFO: el más antiguo; LRU: el menos reciente
marcos.remove(vict)
marcos.append(p); filas.append((p, list(marcos), "fallo", vict))
return fallos, filas
cad = [1, 4, 5, 3, 1, 4, 2, 1, 4, 5, 1, 4]
for alg in ("FIFO", "LRU", "OPT"):
f, filas = reemplazo(cad, 3, alg)
print(f"{alg}: {f} fallos, {len(cad) - f} aciertos; víctimas:", " ".join(str(v) for _, _, e, v in filas if v != ""))
if alg in ("FIFO", "LRU"):
for p, m, e, v in filas: print(f" pide {p}: marcos {m} {e}{' (sale ' + str(v) + ')' if v != '' else ''}")
ex = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3]
for alg in ("FIFO", "LRU"):
f, _ = reemplazo(ex, 3, alg); print(f"examen {alg}: {f} fallos, tasa {f}/{len(ex)} = {f / len(ex):.2%}")
for m in (3, 4):
print(f"FIFO con {m} marcos:", reemplazo(cad, m, "FIFO")[0], "fallos")
acc, serv = 100, 8_000_000 # ns: acceso a memoria y servicio del fallo (8 ms)
for p in (0.001, 0.00001):
print(f"TEA p={p}: {(1 - p) * acc + p * serv:.1f} ns")
print("p máxima para no pasar de 110 ns:", (110 - acc) / (serv - acc))
Salida (ejecutado una vez):
FIFO: 10 fallos, 2 aciertos; víctimas: 1 4 5 3 1 4 2 pide 1: marcos [1] fallo pide 4: marcos [1, 4] fallo pide 5: marcos [1, 4, 5] fallo pide 3: marcos [4, 5, 3] fallo (sale 1) pide 1: marcos [5, 3, 1] fallo (sale 4) pide 4: marcos [3, 1, 4] fallo (sale 5) pide 2: marcos [1, 4, 2] fallo (sale 3) pide 1: marcos [1, 4, 2] acierto pide 4: marcos [1, 4, 2] acierto pide 5: marcos [4, 2, 5] fallo (sale 1) pide 1: marcos [2, 5, 1] fallo (sale 4) pide 4: marcos [5, 1, 4] fallo (sale 2) LRU: 8 fallos, 4 aciertos; víctimas: 1 4 5 3 2 pide 1: marcos [1] fallo pide 4: marcos [1, 4] fallo pide 5: marcos [1, 4, 5] fallo pide 3: marcos [4, 5, 3] fallo (sale 1) pide 1: marcos [5, 3, 1] fallo (sale 4) pide 4: marcos [3, 1, 4] fallo (sale 5) pide 2: marcos [1, 4, 2] fallo (sale 3) pide 1: marcos [1, 4, 2] acierto pide 4: marcos [4, 2, 1] acierto pide 5: marcos [1, 4, 5] fallo (sale 2) pide 1: marcos [1, 4, 5] acierto pide 4: marcos [4, 5, 1] acierto OPT: 6 fallos, 6 aciertos; víctimas: 5 3 2 examen FIFO: 10 fallos, tasa 10/12 = 83.33% examen LRU: 9 fallos, tasa 9/12 = 75.00% FIFO con 3 marcos: 10 fallos FIFO con 4 marcos: 8 fallos TEA p=0.001: 8099.9 ns TEA p=1e-05: 180.0 ns p máxima para no pasar de 110 ns: 1.250015625195315e-06
Cosas que observar:
- En LRU, un acierto hace
marcos.remove(p); marcos.append(p): la página pasa a ser la más reciente. En FIFO los aciertos no tocan la lista: esa es toda la diferencia entre los dos. - El óptimo elige con
fut.index(m), el próximo uso; si una página no vuelve a aparecer, recibe un valor mayor que cualquier índice y sale la primera. - La traza de LRU escribe los marcos de la menos a la más reciente, por eso el orden cambia también en los aciertos.
- La p máxima, 1,25 · 10⁻⁶, sale despejando la misma fórmula del TEA.
Para probar con tus propias cadenas, tienes el simulador de reemplazo de páginas del Laboratorio, con FIFO, LRU y el óptimo.
Resumen
- FIFO mira la llegada, LRU el último uso y el óptimo el próximo uso.
- Los primeros fallos con los marcos vacíos son obligatorios y cuentan.
- El óptimo siempre da el mínimo de fallos; entre FIFO y LRU suele ganar LRU, pero no siempre.
- TEA = (1 − p) · acceso + p · servicio, con todo en la misma unidad; p tiene que ser diminuta.
- Con FIFO, más marcos pueden dar más fallos (Belady); con LRU y el óptimo, no.
- En el examen, rejilla completa, víctimas y tasa de fallos como fracción.
Checklist: ¿lo has practicado?
- ¿Has hecho los cuatro problemas en papel antes de leer el paso a paso?
- ¿Sabes qué mira cada algoritmo para elegir la víctima?
- ¿Puedes hacer la rejilla de LRU sin confundirte con el óptimo?
- ¿Sabes calcular el TEA y despejar la p máxima?
- ¿Has comprobado los problemas con el programa de Python o con el simulador?
- ¿Has intentado los «Pruébalo tú» sin mirar la teoría?
Si has respondido que sí a casi todo, estás listo para los ejercicios de memoria virtual, con un test de todo el tema, trazas y cálculos con casillas que se corrigen solas. ¡Nos vemos allí!
Siguiente paso: ejerciciosMemoria virtual — ejercicios tipo examen con fallos de página, trazas de FIFO, LRU y óptimo y conjuntos de trabajo (y los tres fallos que no conté en el simulacro)¿Te ha servido este artículo? Así puedes apoyar SergioLearns →
