Más memoria de la que hay

Memoria virtual

Los procesos piden cada vez más memoria, y muchas veces piden más de la que usarán. Si el sistema trabajara solo con la RAM, pronto no podría cargar más procesos. La memoria virtual intercambia páginas entre la RAM y el disco para que los procesos usen más memoria de la que realmente hay, cuidando el balance entre usabilidad y rendimiento: el disco es muchísimo más lento que la RAM.

• Intercambio (swap): grabar en disco memoria que estaba en RAM, y viceversa.
• Fallo de página: el proceso accede a una página que no está en RAM y hay que traerla del disco.
• Hiperpaginación: exceso de fallos de página. Su consecuencia es el desperdicio (thrashing): la CPU pasa más tiempo decidiendo qué intercambiar y esperando al disco que ejecutando procesos.
• Localidad temporal: lo que se usó hace poco probablemente se vuelva a usar pronto. Localidad espacial: lo que está cerca de lo que se usó probablemente se use también.

Qué pasa en un fallo de página

Es la misma paginación de siempre, con una bandera más en cada entrada de la tabla: si la página está en memoria o en disco. Si está en memoria, el acceso sigue normal. Si no, la MMU genera una interrupción de fallo de página y el sistema:

1. busca un marco libre y trae ahí la página desde el disco;
2. si no hay marcos libres, elige una página víctima según su política de reemplazo y la baja al disco;
3. actualiza la tabla de páginas: la página ya está en memoria, en tal marco;
4. reintenta el acceso, que ahora sí se resuelve normalmente.

Las estrategias de la memoria virtual

• Reposición: qué página de la RAM bajar al disco cuando hace falta lugar.
• Búsqueda: cuándo subir páginas del disco a la RAM.
• Alcance: entre qué páginas se elige la víctima.

Estrategias de reposición

Todas persiguen el principio de optimización: reemplazar la página que no se va a usar durante más tiempo. Ese algoritmo, el óptimo, tiene la menor cantidad de fallos posible, pero exige conocer el futuro: sirve como meta y como referencia.

• Al azar: ningún sistema la usa; es una referencia para comparar, y evita mal la hiperpaginación.
• FIFO o PEPS (primero en entrar, primero en salir): sale la que lleva más tiempo en memoria. Es fácil y rápida de decidir, pero saca también páginas que se usan todo el tiempo. Además sufre la anomalía de Belady: con ciertas secuencias, darle más marcos a un proceso produce más fallos. Con la secuencia A B C D A B E A B C D E, tres marcos dan 9 fallos y cuatro marcos, 10.
• Segunda oportunidad: una lista circular con un apuntador y el bit de referencia (R) que el hardware enciende cada vez que se usa una página. Si la página que toca sacar tiene R = 1, se le apaga el bit y se pasa a la siguiente; sale la primera con R = 0. Es tan simple como FIFO y no expulsa las páginas que se están usando. ampliación Aun así, sigue basada en el orden de llegada y puede mostrar la anomalía: con la secuencia anterior también da 9 y 10 fallos. Los algoritmos que nunca la sufren son el óptimo y LRU.
• Menos recientemente usada (LRU): el hardware pone una marca de tiempo en cada acceso y sale la página con la marca más vieja. Aprovecha la localidad temporal, pero decidir exige revisar todas las páginas o mantener una lista ordenada en segundo plano. Para que una página usada una sola vez no se quede mucho tiempo, se le aplica un envejecimiento con desplazamientos de bits.
• Menos frecuentemente usada (LFU): cada página lleva un contador de accesos y sale la de menor contador. Para evitar la "memoria eterna" de páginas muy usadas al principio, se envejece el contador: restándole uno periódicamente (así lo hace Linux) o desplazándolo e insertando el bit R a la izquierda.
• No usada recientemente (NRU): usa los bits R (se lee) y M (se modifica), con R reiniciado periódicamente. Forman cuatro clases (MR = 00, 01, 10, 11) y sale la primera página de la clase más baja. En promedio basta revisar una cuarta parte de las páginas.

Estrategias de búsqueda

• Por demanda: se trae una página cada vez que hay un fallo. Es la más simple, pero no aprovecha la localidad, y leer página por página rara vez coincide con el tamaño de bloque óptimo del disco: la cantidad que se lee en el mismo tiempo que un solo byte (por ejemplo, si leer 1 byte o 32 KB tarda lo mismo y 33 KB tarda el doble, el bloque óptimo es de 32 KB).
• Anticipada: se suben las páginas que el proceso muy probablemente usará: su conjunto de trabajo, las páginas que usó en un período reciente (las que tienen R = 1). Al suspender un proceso se guarda su conjunto de trabajo y se bajan sus páginas; al despertarlo, se suben de nuevo.

Estrategias de alcance

• Local: cada proceso tiene sus marcos y la víctima sale de los suyos. Solo se busca en una tabla, pero un proceso que necesita mucha memoria entra en hiperpaginación. Los marcos se reparten de forma uniforme (m/n por proceso) o proporcional al tamaño de cada ejecutable.
• Global: la víctima puede ser de cualquier proceso. La hiperpaginación de uno puede contagiar a los demás.

Control de la hiperpaginación

• Por conjunto de trabajo: la demanda es la suma de los conjuntos de trabajo de todos los procesos. Si supera los marcos disponibles, habrá hiperpaginación: se suspende un proceso y sus marcos se reparten entre los demás.
• Por frecuencia de fallos: se fijan un límite inferior y uno superior para la tasa de fallos. Si un proceso falla menos que el inferior, le sobran marcos y se le quita uno; si falla más que el superior, le faltan y recibe uno, a costa del que menos falla. Si no hay marcos, se suspende.

Antes de leer la respuesta