Reemplazo de páginas: FIFO, LRU y la política óptima

La memoria dispone de unos pocos marcos. Cada uno aloja una página, y el programa solicita las páginas en el orden de la cadena de referencias. Si la página ya está en un marco, hay un acierto; si falta, hay un fallo. Cuando todos los marcos están ocupados, hay que retirar una página. FIFO retira la que lleva más tiempo cargada; LRU, la que lleva más tiempo sin usarse; OPT, la que tardará más en volver a necesitarse.

Ejemplo resuelto — Reemplazo de páginas: FIFO, LRU y la política óptima

Referencias	12
FIFO fallos con 3 marcos: referencias − aciertos	9
LRU fallos con 3 marcos: referencias − aciertos	10
OPT fallos con 3 marcos: referencias − aciertos	7

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — Reemplazo de páginas: FIFO, LRU y la política óptima

La memoria se divide en marcos de igual tamaño, y los datos de un programa, en páginas de ese mismo tamaño. Así, cualquier página cabe en cualquier marco. La cadena de referencias es la secuencia de páginas a las que accede un programa. Una referencia a una página que no está en memoria produce un fallo de página: la página se carga y, si no queda ningún marco libre, una política de reemplazo elige qué página retirar. Para una cadena dada, una política presenta la anomalía de Bélády si produce más fallos con F + 1 marcos que con F.

Qué significa cada símbolo

F: número de marcos
n: número de páginas del bucle (problema resuelto)
r: número de veces que se repite el bucle

Supone: Se usa paginación por demanda: una página solo se carga cuando se solicita. La memoria empieza vacía, así que la primera referencia a cada página produce un fallo con cualquier política. Si varias páginas no vuelven a necesitarse, esta versión de OPT retira la de menor número. Cada referencia corresponde a una página; no se distingue entre lecturas y escrituras, y retirar una página no tiene coste. LRU exacto necesita registrar cuándo se produce cada acceso a memoria, algo demasiado costoso. Por eso, los núcleos de los sistemas operativos usan aproximaciones con un bit de referencia por página; el algoritmo del reloj es la más conocida.

Un marco más, un fallo más 🖖

Pulsa FIFO, 3 marcos y luego FIFO, 4 marcos. La cadena es 1 2 3 4 1 2 5 1 2 3 4 5. Con más memoria hay más fallos: 10 frente a 9. Avanza en ambos casos hasta el paso 7, cuando llega la página 5. Con 3 marcos, las páginas 1 y 2 ya se habían retirado y vuelto a cargar, así que son las más recientes y FIFO retira la 4. Con 4 marcos, las páginas 1 y 2 no han salido de la memoria. La página 1 es, por tanto, la que lleva más tiempo cargada, y FIFO la retira justo un paso antes de que el programa la solicite. Bélády, Nelson y Shedler describieron este efecto en 1969. Es poco frecuente: probamos FIFO con todas las cadenas de referencias de longitud inferior a doce, con cualquier número de páginas, y no apareció en ninguna. De las 4.213.597 cadenas de longitud doce (contando como una sola las que solo difieren en los nombres de las páginas), ocurre en ocho. Todas empiezan por 1 2 3 4 1 2 5 1 y todas producen un único fallo adicional al pasar de 3 marcos a 4. Esta es la única de las ocho que usa cinco páginas.

Con LRU y OPT, más memoria nunca implica más fallos 🖖

Pulsa LRU, 4 marcos: la misma cadena produce 8 fallos, frente a 10 con 3 marcos. Con F marcos, LRU conserva las F páginas usadas más recientemente; con F + 1, conserva esas mismas páginas y una más. En cada paso, todas las páginas de la memoria menor están también en la mayor. Una referencia que es un acierto con 3 marcos lo será con 4. FIFO conserva las páginas cargadas más recientemente, y al cambiar el número de marcos cambia el historial de cargas: tras el paso 7, los 3 marcos contienen 1, 2 y 5, mientras que los 4 contienen 2, 3, 4 y 5. OPT cumple la misma propiedad de inclusión que LRU. Las políticas que la cumplen se llaman algoritmos de pila. En la tabla situada bajo los resultados, que cuenta los fallos para cada número de marcos, sus valores nunca aumentan al añadir marcos. Los de FIFO sí pueden aumentar; la celda donde ocurre aparece marcada.

LRU falla siempre si al bucle le falta un marco 🖖

Pulsa Bucle, LRU: se leen 5 páginas en orden durante 3 vueltas, con 4 marcos. Las 15 referencias producen fallos, porque la página que lleva más tiempo sin usarse es siempre la siguiente que necesita el bucle. Con FIFO ocurre exactamente lo mismo. Pulsa Bucle, OPT y el recuento baja a 7. OPT retira la página que tardará más en volver a necesitarse; en los pasos 5 y 9, es la que acaba de leer. Para saberlo, tiene que consultar el resto de la cadena antes de elegir. Ningún sistema operativo puede hacer eso. OPT sirve como referencia: da el mínimo de fallos que podría conseguir cualquier política para esta cadena. Añade un quinto marco al bucle y las tres políticas producirán 5 fallos, uno por página.

Problema resuelto al detalle

Cuándo LRU falla en todas las referencias 5 pasos
Pulsa Bucle, OPT e indica en qué pasos se producen sus 7 fallos. Después, considera un programa que suma los elementos de un vector que ocupa 100 páginas, repitiendo el recorrido 1.000 veces con 99 marcos. ¿Cuántos fallos produce LRU? ¿Y OPT? ¿Cuántos habría con un marco número 100?

Abre este problema en la herramienta
1. En el ejemplo de la página, las primeras 5 referencias producen fallos: 4 llenan los marcos vacíos y la quinta obliga a retirar una página. Después, los fallos se producen en los pasos 9 y 13, separados por 4 referencias: 5 + 2 = 7.
  
  $5 + 2 = 7 faults: steps 1 - 5, 9, 13$
2. Con n − 1 marcos y un bucle de n páginas, siempre hay exactamente una página del bucle fuera de la memoria. Cuando se produce un fallo, la página que tardará más en volver a necesitarse es la que acabas de leer: le tocará de nuevo dentro de n − 1 referencias. En la última vuelta, algunas páginas ya no volverán a necesitarse y OPT puede retirar una de ellas. Al retirar la página recién leída, las siguientes n − 2 referencias encuentran sus páginas en memoria. Por eso, el siguiente fallo llega n − 1 referencias después.
  
  $n - 1 frames : one fault every n - 1 references$
3. LRU con 99 marcos: cuando la página p produce un fallo, todas las demás páginas están en los marcos. La que lleva más tiempo sin usarse es p + 1, justo la siguiente que solicita el bucle. Las 100 × 1.000 = 100.000 referencias producen fallos, como en el ejemplo de la página, donde fallaron las 15. FIFO retira las mismas páginas.
  
  $LRU : 100 \times 1000 = 100000$
4. OPT: las primeras 99 referencias llenan los marcos. A partir de la referencia 100, hay un fallo cada 99 referencias: en la 100, la 199, la 298, … Son 1 + ⌊(100.000 − 100) / 99⌋ = 1 + 1.009 = 1.010 fallos. En total, 99 + 1.010 = 1.109, que corresponde a n + ⌊n(r − 1)/(n − 1)⌋ con n = 100 y r = 1.000.
  
  $OPT : 99 + (1 + ⌊ \frac{100 000 - 100}{99} ⌋) = 99 + 1010 = 1109 = n + ⌊ \frac{n ( r - 1 )}{n - 1} ⌋$
5. Con un marco número 100 cabe el vector entero: 100 fallos con cualquiera de las tres políticas, uno por página. Tras la primera vuelta no hay ninguno más.
  
  $F = 100 : 100 faults$
Respuesta

LRU: 100.000; OPT: 1.109; con un marco más: 100. LRU alcanza su peor resultado cuando el bucle necesita una página más de las que caben en memoria. Añadir el marco que falta reduce los fallos a la milésima parte.

$LRU 100000, OPT 1109, 100 with one frame more$

Ruta de aprendizaje

Qué operaciones abarata una estructura de datos

Referencias (1)

The first insight's date and attribution: the anomaly, and its formal treatment for FIFO: L. A. Belady, R. A. Nelson and G. S. Shedler, "An anomaly in space-time characteristics of certain programs running in a paging machine," Communications of the ACM 12(6), 349–353, June 1969.

Por el equipo de 42Math · Contrastado con fuentes publicadas. Se agradecen correcciones.