¿Por qué LRU es mejor que FIFO?

Question

Por que es Menos usado recientemente ¿Mejor que FIFO en relación con los archivos de página?

Answer 1

Si quiere decir en términos de descarga de páginas de memoria al disco: si su proceso está accediendo con frecuencia a una página, realmente no desea que se pague al disco, incluso si fue el primero a quien accedió. Por otro lado, si no ha accedido a una página de memoria durante varios días, es poco probable que lo haga en el futuro cercano.

Si eso no es lo que quiere decir, edite su pregunta para dar más detalles.

Answer 2

No hay un algoritmo de caché único que siempre funcionará bien porque eso requiere un conocimiento perfecto del futuro. (Y si sabe dónde obtener eso ...) El dominio de LRU en el diseño de caché VM es el resultado de una larga historia de comportamiento del sistema de medición. Dadas las cargas de trabajo reales, LRU funciona bastante bien una fracción muy grande del tiempo. Sin embargo, no es muy difícil construir una cadena de referencia para la cual FIFO tendría un rendimiento superior sobre LRU.

Considere un barrido lineal a través de un espacio de dirección grande mucho más grande que la memoria real amacatoria disponible. LRU se basa en la suposición de que "lo que ha tocado recientemente es probable que vuelva a tocar", pero el barrido lineal viola por completo esa suposición. Esta es la razón por la cual algunos sistemas operativos permiten a los programas asesorar al núcleo sobre su comportamiento de referencia: un ejemplo es la recolección de basura "Marca y barrido" tipificada por los intérpretes clásicos de LISP. (Y un gran impulsor para trabajar en GC más modernos como "Generacional".)

Otro ejemplo es la tabla de símbolos en un cierto procesador macro antiguo (Stage2). Se busca el árbol binario desde la raíz de cada símbolo, y la evaluación de la cadena se está realizando en una pila. Resultó que reductora Los marcos de página disponibles "cableando" la página raíz del árbol de símbolos y la página inferior de la pila hicieron una gran mejora en la tasa de falla de la página. El caché era pequeño y se agitaba violentamente, siempre empujando las dos páginas con mayor frecuencia referenciadas porque el caché era más pequeño que la distancia entre referencia a esas páginas. Entonces un pequeña El caché funcionó mejor, pero solo porque esos dos marcos de página robados del caché se usaron sabiamente.

La red de todo esto es que LRU es la respuesta estándar porque generalmente es bastante buena para cargas de trabajo reales en sistemas que no están sobrecargados horriblemente (VM muchas veces la memoria real disponible), y eso es compatible con años de mediciones cuidadosas. Sin embargo, ciertamente puede encontrar casos en los que el comportamiento alternativo sea superior. Esta es la razón por medición Los sistemas reales son importantes.

Answer 3

Trate a la RAM como un caché. Para ser un caché efectivo, debe mantener los elementos con mayor probabilidad de ser solicitados en la memoria.

LRU mantiene las cosas que se usaron más recientemente en la memoria. FIFO mantiene las cosas que se agregaron más recientemente. LRU es, en general, más eficiente, porque generalmente hay elementos de memoria que se agregan una vez y nunca se usan nuevamente, y hay elementos que se agregan y se usan con frecuencia. Es mucho más probable que LRU mantenga los elementos de uso frecuente en la memoria.

Answer 4

Dependiendo de los patrones de acceso, FIFO a veces puede vencer a LRU. Un Caché de reemplazo adaptativo es híbrido que adapta su estrategia basada en patrones de uso reales.

Answer 5

De acuerdo a localidad temporal de referencia, es más probable que la memoria se haya accedido recientemente pronto.