Memoria virtual y reemplazo de páginas — teoría con gcc en tres marcos, FIFO, LRU y el óptimo cara a cara (y el portátil que se arrastraba con 40 pestañas)

Semana de entregas. Tenía abiertas 40 pestañas de Chrome (la mitad, documentación de IC2), VS Code compilando la práctica, Spotify y Teams. El portátil tiene 8 GB de RAM y, de repente, todo empezó a ir a tirones: el ratón se congelaba medio segundo, Spotify cortaba la canción y el ventilador sonaba como un secador. Abrí el Monitor de recursos de Windows y vi dos cosas: el disco al 100 % y, en la pestaña Memoria, una columna que no había mirado nunca: errores graves por segundo (hard faults), con números de cuatro cifras. La CPU, en cambio, estaba casi parada. ¿Cómo puede ir todo lento si la CPU no hace nada?

La respuesta es la segunda mitad del Tema 5 de IC2. En el tema anterior, Gestión de memoria, vimos cómo la paginación reparte la RAM en marcos y traduce direcciones. Hoy damos el paso que lo cambia todo: un proceso no tiene que estar entero en la RAM para ejecutarse. Veremos qué pasa cuando pide una página que no está (el fallo de página), cómo decide el SO a quién echar (FIFO, el óptimo, LRU y sus aproximaciones), por qué dar más memoria puede empeorar las cosas (la anomalía de Belady) y qué le pasaba a mi portátil (la hiperpaginación). Todo con un ejemplo que se repite: gcc, con 8 páginas lógicas y solo 3 marcos de RAM. Cuando termines, tienes los ejercicios tipo examen de memoria virtual.

La idea: no hace falta caber entero

Hasta ahora, para ejecutar un proceso había que cargar todas sus páginas. Pero piensa en gcc: tiene código para optimizar, para avisar de errores, para C++, para ensamblador… y en una compilación normal usa una pequeña parte. ¿Para qué ocupar RAM con lo que no se va a usar?

La memoria virtual es la técnica que permite ejecutar un proceso aunque solo una parte de sus páginas esté en la memoria principal; el resto se queda en el almacenamiento secundario, que hace de extensión de la RAM. El SO mueve las páginas entre los dos de forma transparente: el programador no decide nada, escribe su programa como si tuviera toda la memoria del mundo.

Fíjate en el dibujo: en t = 3 gcc solo tiene en RAM las páginas 1, 2 y 3 (en los marcos 5, 9 y 2, los mismos que usaba en el Tema 9). Las otras cinco tienen una i en la tabla de páginas: no están en la RAM, sino en el área de intercambio (swap), una zona del disco que el SO reserva para esto. Las ocho páginas existen siempre en el disco; en la RAM solo hay una copia de las que se están usando.

¿Qué se gana?

• Programas más grandes que la RAM: el espacio lógico de un proceso ya no está limitado por la memoria física.
• Más procesos a la vez: si cada uno ocupa solo lo que usa, caben más (más grado de multiprogramación, y la CPU tiene más donde elegir).
• Arranques más rápidos: no hay que leer el programa entero antes de empezar.
• Menos E/S: lo que nunca se usa nunca se lee.

Paginación por demanda

¿Cómo decide el SO qué páginas cargar? La forma habitual es la más perezosa posible: en la paginación por demanda, una página no se lee del disco hasta que el proceso la referencia por primera vez.

La cadena de referencias de gcc de este artículo usa las páginas 1, 2, 3, 4, 5 y 7. Con carga completa se leerían las 8 páginas al empezar; con paginación por demanda se leen 6, cada una cuando se pide, y la 0 y la 6 no llegan a leerse nunca. Ese ahorro es justo lo que hace que la idea compense.

Para saber si una página está en la RAM, cada entrada de la tabla de páginas tiene, además del número de marco, unos cuantos bits:

Bit	Lo pone…	Para qué sirve
v (validez o presencia)	el SO, al cargar o echar la página	v = está en un marco; i = está en el disco → acceder da fallo de página
R (referencia)	el hardware, en cada acceso	saber qué se ha usado hace poco (aproximaciones de LRU); el SO lo borra periódicamente
M (modificación, «sucio»)	el hardware, en cada escritura	saber si hay que guardar la página en el disco antes de echarla
protección	el SO	qué se permite: leer, escribir, ejecutar

El fallo de página, paso a paso

Un fallo de página es la interrupción (trap) que produce la MMU cuando un proceso referencia una página cuyo bit de validez es i. No es un error del programa: es el aviso de que el SO tiene que traer esa página. Veámoslo con gcc en t = 7, cuando pide la página 4:

1. Referencia: gcc ejecuta una instrucción que toca la página 4.
2. Trap: la MMU mira la tabla, ve una i y salta al núcleo del SO (lo que vimos en el Tema 5, interrupciones).
3. Buscar: el SO comprueba que la dirección es legal (si no lo fuera, el proceso moriría con un segmentation fault) y localiza la página en el área de intercambio.
4. Leer: pide al disco que copie la página en un marco libre. Mientras tanto, gcc pasa a bloqueado y la CPU atiende a otro proceso.
5. Actualizar: pone en la entrada el número de marco (el 9) y el bit a v.
6. Repetir: gcc vuelve a listo y, cuando le toca, repite la instrucción que falló, que ahora sí encuentra la página.

Cuando no queda ningún marco libre

El paso 4 da por hecho que hay un marco libre. En t = 7 gcc ya tiene sus 3 marcos ocupados (con 1, 5 y 2), así que antes de leer hay que echar a alguien: elegir una página víctima. Quién sea la víctima lo decide el algoritmo de reemplazo (lo vemos en la sección siguiente). Lo que importa ahora es cuánto cuesta echarla:

Si la víctima tiene M = 0 (limpia), su copia del disco es idéntica y basta con pisarla: una sola operación de disco, la lectura de la página nueva. Si tiene M = 1 (sucia), primero hay que escribirla en el disco y después leer la nueva: dos operaciones. Los pasos completos quedan así: fallo → no hay marcos libres → elegir víctima → si M = 1, escribirla → marcarla como i en su tabla → leer la nueva → actualizar su entrada → repetir la instrucción.

Por eso los SO hacen precleaning (prelimpieza): cuando están ociosos, escriben en el disco las páginas sucias y les ponen M = 0, para que la próxima víctima tenga más probabilidades de estar limpia.

Cuánto cuesta un fallo: el tiempo efectivo de acceso

Un acceso a RAM tarda unos 100 ns; atender un fallo de página, unos 8 ms (8.000.000 ns), porque hay que ir al disco. Si p es la probabilidad de que un acceso provoque un fallo, el tiempo efectivo de acceso es:

TEA = (1 − p) · tiempo de acceso a memoria + p · tiempo de servicio del fallo

Hagamos las cuentas con un fallo cada 1.000 accesos (p = 0,001): TEA = 0,999 · 100 + 0,001 · 8.000.000 = 99,9 + 8.000 = 8.099,9 ns. La memoria parece 81 veces más lenta (8.099,9 / 100 ≈ 81). Con un fallo por millón: 99,9999 + 8 ≈ 108 ns, un 8 % más lento.

Esto explica la mitad de lo que le pasaba a mi portátil: miles de fallos por segundo, cada uno esperando milisegundos al disco. La otra mitad (por qué había tantos) llega al final.

Algoritmos de reemplazo de páginas

Cuando hay que elegir víctima, ¿a quién se echa? La meta es producir el menor número de fallos de página posible. Para comparar algoritmos se usa una cadena de referencias: la lista de páginas que pide el proceso, en orden. La de gcc en este artículo es esta:

Los tres algoritmos clásicos reciben exactamente la misma cadena y los mismos 3 marcos (al principio, vacíos). Hay algo que ninguno puede evitar: la primera vez que se pide cada página, falla. Son los fallos obligatorios, y aquí hay 6, uno por página distinta (1, 2, 3, 5, 4 y 7). Todo lo que pase de 6 es culpa del algoritmo.

FIFO: el primero que entra, el primero que sale

FIFO echa la página que lleva más tiempo cargada en memoria. Basta con una cola: las páginas entran por el final y la víctima sale por el principio.

Lee la traza columna a columna. En las celdas coral entra una página (fallo); en las verdes, la página pedida ya estaba (acierto); en la fila «fuera», la víctima. Los tres primeros fallos llenan los marcos (el 1 de t = 2 acierta). En t = 4 llega la 5 y FIFO echa la 1 porque entró la primera, en t = 0, aunque gcc la había usado en t = 2. Resultado: en t = 5 gcc vuelve a pedir la 1 y falla otra vez. Lo mismo en t = 8: echa la 1, que se usó en t = 5, y en t = 9 vuelve a fallar con ella. Total: 11 fallos de 15 referencias.

t	ref	marcos después	¿fallo?	sale	por qué esa
3	3	1 2 3	sí	—	quedaba un marco libre
4	5	5 2 3	sí	1	la 1 entró en t = 0, la más antigua
5	1	5 1 3	sí	2	la 2 entró en t = 1
6	2	5 1 2	sí	3	la 3 entró en t = 3
7	4	4 1 2	sí	5	la 5 entró en t = 4

El problema de FIFO está a la vista: no mira si una página se usa, solo cuándo entró. Una página muy usada, como la 1 de gcc (el bucle principal, por ejemplo), sale igual que una que no se vuelve a tocar.

El algoritmo óptimo (OPT o MIN)

¿Cuál sería la mejor decisión posible? Echar la página que más tarde se va a necesitar. El algoritmo óptimo reemplaza la página que más tiempo va a tardar en volver a ser referenciada (o que no se va a referenciar nunca más).

En t = 4 llega la 5 con 1, 2 y 3 en memoria. Mirando hacia delante, la 1 vuelve en t = 5, la 2 en t = 6 y la 3 en t = 12: sale la 3. Gracias a eso, en t = 5 y t = 6 acierta donde FIFO fallaba. Total: 7 fallos, solo uno más que los obligatorios. Está demostrado que ningún algoritmo puede dar menos fallos con la misma cadena y los mismos marcos.

¿Y por qué no lo usa todo el mundo? Porque necesita conocer el futuro: el SO no sabe qué páginas pedirá gcc dentro de un rato. El óptimo es imposible de implementar en un SO real; sirve como vara de medir: un algoritmo es mejor cuanto más se acerca a él.

LRU: el que lleva más tiempo sin usarse

Si no podemos ver el futuro, usemos el pasado reciente como predicción. LRU (Least Recently Used) echa la página que hace más tiempo que no se usa. La idea se apoya en la localidad, que veremos más abajo: lo que se ha usado hace poco probablemente se volverá a usar pronto.

En t = 4 llega la 5. Los últimos usos son: la 1 en t = 2, la 2 en t = 1 y la 3 en t = 3. Sale la 2, y la 1 se queda; por eso en t = 5 LRU acierta con la 1 donde FIFO fallaba. Total: 9 fallos, entre FIFO (11) y el óptimo (7).

Pero LRU tiene un problema práctico: hay que saber en cada acceso qué página se ha usado, y eso son millones de veces por segundo. Hay dos formas de implementarlo exacto:

• Contador: cada entrada guarda el instante de su último uso (el hardware copia un reloj en cada acceso) y la víctima es la de valor más pequeño. Hay que buscar en todas las entradas.
• Pila: cada vez que se usa una página, se saca de donde esté y se pone en la cima; la víctima es la del fondo. Mover la página en cada acceso es caro.

Las dos piden hardware especial o son lentísimas por software. Por eso, en la práctica, se usan aproximaciones de LRU con el bit R (más abajo).

Qué mira cada uno

En t = 7 los tres algoritmos tienen en memoria las mismas páginas (1, 2 y 5, aunque en distintos marcos) y llega la 4. Cada uno hace una pregunta distinta:

FIFO y LRU coinciden aquí en echar la 5, pero por motivos distintos: para FIFO es la que entró antes (t = 4); para LRU, la que lleva más tiempo sin usarse (también t = 4, porque desde que entró no se ha vuelto a pedir). El óptimo echa la 2: ni la 2 ni la 5 vuelven a aparecer, así que da igual cuál de las dos (en el simulador se queda con la primera según el orden de los marcos).

Algoritmo	Víctima	Fallos (gcc, 3 marcos)	¿Implementable?	Belady
FIFO	la que entró antes	11	sí, muy barato (una cola)	puede sufrirla
Óptimo	la que más tarde se usará	7	no: necesita el futuro	no
LRU	la que lleva más tiempo sin usarse	9	caro (contador o pila en cada acceso)	no

La anomalía de Belady

Lo lógico sería pensar que, con más marcos, siempre hay menos fallos (o los mismos). Con FIFO, no siempre. La anomalía de Belady es que, al aumentar el número de marcos, aumente el número de fallos de página. Mira esta cadena con FIFO:

Con 3 marcos, 9 fallos; con 4 marcos, 10. ¿Qué ha pasado? Con 4 marcos las páginas 3 y 1 aciertan en t = 4 y t = 5, así que FIFO no las saca y, cuando llega la 5, echa a la 3, que es justo la que se pide después; a partir de ahí encadena un fallo tras otro. Con 3 marcos el orden de salidas es otro y acierta en t = 7 y t = 8.

¿Por qué LRU y el óptimo no la sufren? Porque son algoritmos de pila: el conjunto de páginas que tienen en memoria con n marcos está siempre contenido en el que tendrían con n + 1. Con un marco más tienen todo lo de antes y una más, así que no pueden fallar más. FIFO no cumple esa propiedad.

Aproximaciones de LRU

Casi todos los procesadores ponen a 1 el bit R cuando se accede a una página, y el SO puede ponerlo a 0 cuando quiera. Con ese bit tan barato se construyen algoritmos que se parecen a LRU sin pagar su precio.

Segunda oportunidad (algoritmo del reloj)

La segunda oportunidad es FIFO más el bit R: antes de echar una página, se mira su bit de referencia; si vale 1, se le pone a 0 y se le da otra oportunidad. La versión del reloj organiza los marcos en una lista circular con una aguja:

La aguja apunta a la página 1, que tiene R = 1: se le pone R = 0 y la aguja avanza. La página 4 tiene R = 0: es la víctima. La 1 se ha librado, pero ahora tiene R = 0; si nadie la usa antes de la próxima vuelta, caerá. Si todas tuvieran R = 1, la aguja daría la vuelta entera poniéndolas a 0 y acabaría echando la primera: en el peor caso se comporta como FIFO.

NRU: no usada recientemente

NRU (Not Recently Used) clasifica las páginas en cuatro clases según los bits R y M, y elige la víctima al azar dentro de la clase no vacía más baja.

La clase 0 (R = 0, M = 0) es la víctima perfecta: no se ha usado hace poco y no hay que escribirla. Fíjate en el orden de las clases 1 y 2: NRU prefiere echar una página sucia sin usar (clase 1) antes que una limpia usada (clase 2). Escribir cuesta, pero echar algo que se está usando cuesta más, porque volverá a fallar enseguida. ¿Y cómo puede haber páginas con M = 1 y R = 0? Porque el SO borra R periódicamente, pero no M (si borrara M, perdería la información de que hay que escribirla).

NFU, LFU y aging

Estos tres usan contadores en lugar de un solo bit:

• NFU (Not Frequently Used): a intervalos regulares (cada tic del reloj), el SO suma el bit R de cada página a su contador y borra R. La víctima es la de contador más bajo. Problema: nunca olvida; una página muy usada al principio conserva un contador alto aunque ya no se use.
• LFU (Least Frequently Used): cada página guarda un contador del número de referencias, y se echa la de menor contador. Mismo problema: lo antiguo pesa tanto como lo reciente.
• Aging (envejecimiento): arregla el olvido de NFU. Cada tic, el registro de cada página se desplaza un bit a la derecha y el bit R entra por la izquierda. Así el bit de la izquierda es el tic más reciente y los antiguos se van perdiendo por la derecha.

He dividido las referencias de gcc de t = 0 a t = 11 en cuatro tics de tres referencias y he seguido a las tres páginas que LRU tiene en memoria en t = 11: la 1, la 4 y la 7. Al final, la 1 vale 1011 (11) y la 4 y la 7, 1100 (12). La víctima es la de menor valor, la 1: exactamente la que echa LRU en t = 12. Lo que aging no puede hacer es distinguir la 4 de la 7, que empatan: LRU sabe que la 4 se usó en t = 10 y la 7 en t = 11, pero aging solo sabe que las dos se usaron en el último tic. Es una aproximación.

WSClock

WSClock combina el reloj con el conjunto de trabajo (lo vemos ahora mismo): la aguja recorre una lista circular y, para cada página, usa el bit R, el instante de su último uso (U) y una ventana de tiempo (Δ). Si la página tiene R = 1, se le pone a 0 y se apunta el instante actual como U; si tiene R = 0 y lleva más de Δ sin usarse, es candidata a víctima (y si está sucia, se programa su escritura y se sigue buscando una limpia).

Algoritmo	Qué guarda por página	A quién echa
Segunda oportunidad / reloj	bit R	la primera con R = 0 que encuentra la aguja
NRU	bits R y M	al azar, de la clase no vacía más baja
NFU	contador que suma R cada tic	la de contador más bajo
LFU	contador de referencias	la de contador más bajo
Aging	registro desplazado con R por la izquierda	la de valor más bajo
WSClock	bit R, último uso U (y ventana Δ)	una con R = 0 y reloj − U > Δ (mejor si está limpia)

Localidad y conjunto de trabajo

¿Por qué funciona todo esto? Porque los procesos no saltan al azar por sus páginas. La localidad es la tendencia de un proceso a concentrar sus accesos, durante un tiempo, en unas pocas zonas de código y datos. Un bucle repite las mismas instrucciones; una función usa sus variables locales; un recorrido de un array avanza por páginas contiguas.

Míralo en gcc: de t = 0 a t = 6 se mueve por las páginas 1, 2, 3 y 5; de t = 7 a t = 14, por la 1, la 3, la 4 y la 7. Cada tramo es una localidad. Si el proceso tiene en RAM toda su localidad actual, apenas falla; cuando cambia de localidad, falla unas cuantas veces hasta cargar la nueva.

Para medir la localidad se usa el conjunto de trabajo: el conjunto de trabajo WS(t, Δ) son las páginas distintas que el proceso ha referenciado en las últimas Δ referencias (la ventana).

Con Δ = 4, en t = 9 la ventana tiene las referencias de t = 6 a t = 9 (2, 4, 7 y 1): WS = {1, 2, 4, 7} y |WS| = 4. En t = 13 la ventana es 4, 7, 3, 7: la 7 se repite y solo cuenta una vez, así que WS = {3, 4, 7} y |WS| = 3. La ventana es delicada: si Δ es muy pequeña, no abarca la localidad entera; si es muy grande, mezcla varias localidades.

Los SO reales no guardan la ventana entera. Usan un reloj virtual del proceso y, por página, el instante de su último uso U. La regla del examen es: una página está en el conjunto de trabajo si reloj − U ≤ Δ. Por ejemplo, con reloj = 50 y Δ = 8, una página con U = 45 está dentro (50 − 45 = 5 ≤ 8) y una con U = 40, fuera (10 > 8).

Y ahora lo importante: el tamaño del conjunto de trabajo de gcc llega a 4 en varios momentos (t = 4, 6, 7, 8, 9 y 12), pero gcc solo tiene 3 marcos. En esos momentos su localidad no cabe y tiene que echar páginas que va a pedir enseguida. ¿Recuerdas los fallos de FIFO y LRU entre t = 4 y t = 9? Ahí están.

Hiperpaginación

Ahora multiplica eso por todos los procesos. La hiperpaginación (thrashing) es la situación en la que los procesos no tienen marcos suficientes para su conjunto de trabajo y se producen fallos de página encadenados: el sistema pasa más tiempo paginando que ejecutando.

El círculo vicioso funciona así: un proceso falla y echa una página de otro; ese otro falla al poco y echa una del primero; los dos se bloquean esperando al disco; la CPU se queda sin trabajo y el uso de la CPU baja. Un planificador ingenuo ve la CPU ociosa y admite más procesos, que necesitan más marcos… y la caída se acelera. Es la curva de la izquierda del dibujo.

La forma de verlo con números es sumar los conjuntos de trabajo de todos: D = Σ |WSᵢ|. Si D es mayor que el número de marcos disponibles, la hiperpaginación es segura. En el simulador, en t = 3, gcc necesita 3 marcos, spotify 3, el campus 4 y onedrive 2: D = 3 + 3 + 4 + 2 = 12, y solo hay 10 marcos libres. No caben. Si el SO suspende onedrive (lo que en el Tema 6 llamábamos planificación a medio plazo), D = 10 y caben justos.

Eso era mi portátil: 40 pestañas, VS Code, Spotify y Teams con conjuntos de trabajo que sumaban más que mis 8 GB. El disco al 100 %, miles de errores graves (fallos de página) por segundo y la CPU esperando.

¿Cómo lo evita el SO?

• Modelo del conjunto de trabajo: dar a cada proceso al menos |WS| marcos y, si D no cabe, suspender procesos hasta que quepa.
• Frecuencia de fallos de página (PFF): vigilar cuántos fallos tiene cada proceso.

Con PFF se fija una banda: si la tasa de fallos de un proceso supera el límite superior, le faltan marcos y se le dan más; si baja del límite inferior, le sobran y se le quitan. Si hay que dar marcos y no quedan libres, se suspende algún proceso.

También influye cómo está escrito el programa. Lo que rompe la localidad aumenta los fallos:

• Estructuras enlazadas (listas, árboles) cuyos nodos están repartidos por muchas páginas.
• Lenguajes interpretados con comprobación de tipos en tiempo de ejecución, que ejecutan mucho código del intérprete por cada línea.
• Funciones muy grandes, que ocupan muchas páginas.
• Recorrer un array por columnas cuando está guardado por filas.

En cambio, la pila, los arrays recorridos en orden y el código compacto de un lenguaje compilado tienen muy buena localidad.

Errores típicos

Compruébalo con Python

Vamos a comprobar las tres trazas con un simulador. Tiene los datos fijos (la cadena de gcc y 3 marcos), no pide nada por teclado y se ha ejecutado una sola vez; la salida que verás es la de esa ejecución.

# FIFO, LRU y óptimo con la misma cadena de referencias de gcc y 3 marcos
CADENA = [1, 2, 1, 3, 5, 1, 2, 4, 7, 1, 4, 7, 3, 7, 4]   # páginas que pide gcc, en orden
N_MARCOS = 3                                            # marcos que el SO le deja a gcc

def victima(alg, marcos, t, cadena, llegada, uso):
    if alg == 'FIFO':          # la que lleva más tiempo en memoria (entró antes)
        return min(marcos, key=lambda p: llegada[p])
    if alg == 'LRU':           # la que hace más tiempo que nadie la usa
        return min(marcos, key=lambda p: uso[p])
    futuro = cadena[t + 1:]    # óptimo: la que más tarde se vuelve a pedir (o nunca)
    return max(marcos, key=lambda p: futuro.index(p) if p in futuro else len(futuro))

def simula(alg, n_marcos, cadena, traza=True):
    marcos = [None] * n_marcos    # cada posición es un marco físico fijo
    llegada, uso, fallos = {}, {}, 0
    for t, p in enumerate(cadena):
        fuera, acierto = None, p in marcos
        if acierto:               # acierto: solo se apunta el último uso (para LRU)
            uso[p] = t
        else:
            fallos += 1
            if None in marcos:    # aún hay un marco libre: no hace falta víctima
                i = marcos.index(None)
            else:
                fuera = victima(alg, marcos, t, cadena, llegada, uso)
                i = marcos.index(fuera)   # la nueva ocupa el marco de la víctima
            marcos[i] = p
            llegada[p] = uso[p] = t
        if traza:
            fila = ' '.join('-' if m is None else str(m) for m in marcos)
            res = 'acierto' if acierto else 'FALLO  '
            fin = f'fuera: {fuera}' if fuera is not None else ''
            print(f'{t:>2}  {p:>3}  [{fila}]  {res}  {fin}'.rstrip())
    return fallos

for alg in ('FIFO', 'LRU', 'OPT'):
    print(f'== {alg} con {N_MARCOS} marcos ==')
    print(f"{'t':>2}  {'ref':>3}  {'marcos':<7}  {'acceso':<7}  víctima")
    f = simula(alg, N_MARCOS, CADENA)
    print(f'{alg}: {f} fallos de página en {len(CADENA)} referencias\n')

Lo interesante está en victima, que es donde cada algoritmo decide. Vamos a verla de cerca:

def victima(alg, marcos, t, cadena, llegada, uso):
    if alg == 'FIFO':          # la que lleva más tiempo en memoria (entró antes)
        return min(marcos, key=lambda p: llegada[p])
    if alg == 'LRU':           # la que hace más tiempo que nadie la usa
        return min(marcos, key=lambda p: uso[p])
    futuro = cadena[t + 1:]    # óptimo: la que más tarde se vuelve a pedir (o nunca)
    return max(marcos, key=lambda p: futuro.index(p) if p in futuro else len(futuro))

Los tres casos usan la misma idea, buscar el mínimo o el máximo de algo:

• FIFO: min sobre llegada, el instante en que entró cada página. La más pequeña es la más antigua.
• LRU: min sobre uso, el instante del último acceso. Por eso simula actualiza uso[p] también en los aciertos, y llegada[p] solo cuando la página entra.
• Óptimo: max sobre la posición de la próxima aparición en futuro. Si una página no vuelve a aparecer, le damos len(futuro), un valor mayor que cualquier posición, para que sea la favorita. Si hay empate, max se queda con la primera en el orden de los marcos.

Otro detalle: marcos es una lista con una posición por marco físico y la página nueva ocupa el hueco de la víctima (marcos.index(fuera)). Así la traza se lee como las tablas de los dibujos: cada columna de [ ] es siempre el mismo marco. Esta es la salida real:

== FIFO con 3 marcos ==
 t  ref  marcos   acceso   víctima
 0    1  [1 - -]  FALLO
 1    2  [1 2 -]  FALLO
 2    1  [1 2 -]  acierto
 3    3  [1 2 3]  FALLO
 4    5  [5 2 3]  FALLO    fuera: 1
 5    1  [5 1 3]  FALLO    fuera: 2
 6    2  [5 1 2]  FALLO    fuera: 3
 7    4  [4 1 2]  FALLO    fuera: 5
 8    7  [4 7 2]  FALLO    fuera: 1
 9    1  [4 7 1]  FALLO    fuera: 2
10    4  [4 7 1]  acierto
11    7  [4 7 1]  acierto
12    3  [3 7 1]  FALLO    fuera: 4
13    7  [3 7 1]  acierto
14    4  [3 4 1]  FALLO    fuera: 7
FIFO: 11 fallos de página en 15 referencias

== LRU con 3 marcos ==
 t  ref  marcos   acceso   víctima
 0    1  [1 - -]  FALLO
 1    2  [1 2 -]  FALLO
 2    1  [1 2 -]  acierto
 3    3  [1 2 3]  FALLO
 4    5  [1 5 3]  FALLO    fuera: 2
 5    1  [1 5 3]  acierto
 6    2  [1 5 2]  FALLO    fuera: 3
 7    4  [1 4 2]  FALLO    fuera: 5
 8    7  [7 4 2]  FALLO    fuera: 1
 9    1  [7 4 1]  FALLO    fuera: 2
10    4  [7 4 1]  acierto
11    7  [7 4 1]  acierto
12    3  [7 4 3]  FALLO    fuera: 1
13    7  [7 4 3]  acierto
14    4  [7 4 3]  acierto
LRU: 9 fallos de página en 15 referencias

== OPT con 3 marcos ==
 t  ref  marcos   acceso   víctima
 0    1  [1 - -]  FALLO
 1    2  [1 2 -]  FALLO
 2    1  [1 2 -]  acierto
 3    3  [1 2 3]  FALLO
 4    5  [1 2 5]  FALLO    fuera: 3
 5    1  [1 2 5]  acierto
 6    2  [1 2 5]  acierto
 7    4  [1 4 5]  FALLO    fuera: 2
 8    7  [1 4 7]  FALLO    fuera: 5
 9    1  [1 4 7]  acierto
10    4  [1 4 7]  acierto
11    7  [1 4 7]  acierto
12    3  [3 4 7]  FALLO    fuera: 1
13    7  [3 4 7]  acierto
14    4  [3 4 7]  acierto
OPT: 7 fallos de página en 15 referencias

Qué observar:

1. En FIFO, t = 4 y t = 5: echa la 1 y, justo después, gcc vuelve a pedirla (fuera: 1 y luego FALLO con la 1). Es el defecto de no mirar el uso.
2. En LRU, t = 5: acierto con la 1. LRU la conservó porque se había usado en t = 2, más tarde que la 2.
3. En el óptimo, t = 5 y t = 6: dos aciertos seguidos, porque en t = 4 echó la 3, que no volvía hasta t = 12.
4. Los tres empiezan con los mismos 3 fallos (t = 0, 1 y 3) y el mismo acierto en t = 2: los marcos aún no están llenos y no hay víctima.
5. Los totales, 11, 9 y 7, cuadran con lo que contamos en las trazas: FIFO tiene 4 fallos más que el óptimo y LRU, 2.

El segundo simulador comprueba la anomalía de Belady con FIFO y calcula el conjunto de trabajo de gcc con Δ = 4:

# La anomalía de Belady con FIFO y el conjunto de trabajo de gcc con una ventana Δ
from collections import deque

def fifo(n_marcos, cadena):
    marcos, cola, marcas = set(), deque(), ''   # cola: orden de llegada a memoria
    for p in cadena:
        if p in marcos:
            marcas += '.'                        # acierto
            continue
        marcas += 'F'                            # fallo de página
        if len(marcos) == n_marcos:              # sin marco libre: sale la más antigua
            marcos.discard(cola.popleft())
        marcos.add(p)
        cola.append(p)
    return marcas

BELADY = [3, 1, 4, 2, 3, 1, 5, 3, 1, 4, 2, 5]
for n in (3, 4):
    m = fifo(n, BELADY)
    print(f'FIFO, {n} marcos: {" ".join(m)}  -> {m.count("F")} fallos')

CADENA = [1, 2, 1, 3, 5, 1, 2, 4, 7, 1, 4, 7, 3, 7, 4]   # la de gcc del primer simulador
DELTA = 4                                               # ventana: las últimas 4 referencias
print(f"\n{'t':>2}  {'ref':>3}  {'WS(t, Δ=4)':<12}  |WS|")
tam = []
for t, p in enumerate(CADENA):
    ventana = CADENA[max(0, t - DELTA + 1):t + 1]   # referencias t-Δ+1 … t
    ws = sorted(set(ventana))                       # páginas distintas = conjunto de trabajo
    tam.append(len(ws))
    print(f'{t:>2}  {p:>3}  {str(ws):<12}  {len(ws):>4}')

OTROS = {'spotify': 3, 'campus': 4, 'onedrive': 2}  # |WS| de los demás procesos
LIBRES = 10                                         # marcos que quedan para los cuatro
for t in (3, 9):
    D = tam[t] + sum(OTROS.values())
    print(f't = {t}: D = {tam[t]} + 3 + 4 + 2 = {D} marcos -> ' + ('caben' if D <= LIBRES else 'NO caben: hiperpaginación'))

Esta vez FIFO se programa con una deque (cola doble) para el orden de llegada: popleft() saca la más antigua en tiempo constante y el set responde rápido a «¿está ya en memoria?». Para el conjunto de trabajo, la ventana es una porción de la cadena, CADENA[max(0, t - DELTA + 1):t + 1], y set quita las repeticiones (el max evita índices negativos en los primeros instantes). La salida:

FIFO, 3 marcos: F F F F F F F . . F F .  -> 9 fallos
FIFO, 4 marcos: F F F F . . F F F F F F  -> 10 fallos

 t  ref  WS(t, Δ=4)    |WS|
 0    1  [1]              1
 1    2  [1, 2]           2
 2    1  [1, 2]           2
 3    3  [1, 2, 3]        3
 4    5  [1, 2, 3, 5]     4
 5    1  [1, 3, 5]        3
 6    2  [1, 2, 3, 5]     4
 7    4  [1, 2, 4, 5]     4
 8    7  [1, 2, 4, 7]     4
 9    1  [1, 2, 4, 7]     4
10    4  [1, 4, 7]        3
11    7  [1, 4, 7]        3
12    3  [1, 3, 4, 7]     4
13    7  [3, 4, 7]        3
14    4  [3, 4, 7]        3
t = 3: D = 3 + 3 + 4 + 2 = 12 marcos -> NO caben: hiperpaginación
t = 9: D = 4 + 3 + 4 + 2 = 13 marcos -> NO caben: hiperpaginación

Qué observar:

1. Las dos primeras líneas: 9 fallos con 3 marcos y 10 con 4. Es la anomalía de Belady, con datos.
2. Con 4 marcos aciertan t = 4 y t = 5 (. .), pero después vienen seis fallos seguidos: por no sacar antes la 3 y la 1, luego las echa en mal momento.
3. En la tabla, t = 5: la ventana es 1, 3, 5, 1. La 2 (pedida en t = 1) ya ha salido y la 1 se repite, así que |WS| baja de 4 a 3.
4. |WS| llega a 4 en t = 4, 6, 7, 8, 9 y 12, por encima de los 3 marcos de gcc.
5. Las dos últimas líneas: aunque el gcc de t = 3 solo pide 3 marcos, D = 12 supera los 10 libres. Con todos esos procesos dentro, hay hiperpaginación.

Y para probar tus propias cadenas de referencias, el simulador de reemplazo de páginas del Laboratorio hace la traza de FIFO, LRU y el óptimo marco a marco y marca la anomalía de Belady.

Resumen

Concepto	Idea clave
Memoria virtual	el proceso no tiene que estar entero en RAM; el disco (swap) hace de extensión
Paginación por demanda	una página se lee del disco la primera vez que se pide
Fallo de página	trap por bit i: buscar, (víctima), leer, actualizar y repetir la instrucción
Bit M	víctima sucia = 2 E/S; limpia = 1; precleaning
TEA	(1 − p) · acceso + p · servicio del fallo; p tiene que ser diminuta
FIFO / LRU / óptimo	llegada / último uso / próximo uso: 11, 9 y 7 fallos en el ejemplo
Anomalía de Belady	con FIFO, más marcos pueden dar más fallos; LRU y el óptimo no la sufren
Aproximaciones de LRU	reloj, NRU, NFU, LFU, aging y WSClock, con el bit R y contadores
Conjunto de trabajo	páginas distintas de las últimas Δ referencias; dentro si reloj − U ≤ Δ
Hiperpaginación	Σ |WS| > marcos: fallos en cadena; se evita con el modelo del WS, PFF o suspendiendo procesos

Tres ideas para llevarte:

1. La memoria virtual funciona gracias a la localidad: cada proceso solo necesita unas pocas páginas a la vez.
2. Un algoritmo de reemplazo es bueno cuanto más se parece al óptimo; LRU lo intenta mirando el pasado y sus aproximaciones lo hacen barato con el bit R.
3. Si los conjuntos de trabajo no caben en la RAM, ningún algoritmo te salva: hay hiperpaginación y la solución es quitar procesos de en medio.

¿Listo para comprobarlo? Primero, en la práctica guiada de memoria virtual hacemos paso a paso las trazas de FIFO, LRU y óptimo y el tiempo efectivo con fallos de página; después, en los ejercicios tipo examen de memoria virtual tienes un cuestionario con todos los formatos del examen, trazas de FIFO, LRU y óptimo con casillas que se corrigen solas, preguntas de desarrollo y el chuletario. Y después llega el último tema de IC2: los archivos.

Siguiente paso: prácticaMemoria 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)

¿Te ha servido este artículo? Así puedes apoyar SergioLearns →