Hispanopedia Wiki
Articulo de referencia

Menos utilizado

El método de reemplazo de caché ( LFU , por sus siglas en inglés ) se utiliza para administrar la memoria de un ordenador. Este método consiste en que el sistema registra la can...

Hispanopedia WikiContenido en espanolLectura gratuita

El método de reemplazo de caché ( LFU , por sus siglas en inglés ) se utiliza para administrar la memoria de un ordenador. Este método consiste en que el sistema registra la cantidad de veces que se accede a un bloque de memoria. Cuando la caché está llena y necesita más espacio, el sistema elimina el elemento con la menor frecuencia de acceso.

LFU a veces se combina con un algoritmo de uso menos reciente y se denomina LRFU. [ 1 ]

Implementación

El método más sencillo para emplear un algoritmo LFU consiste en asignar un contador a cada bloque que se carga en la caché. Cada vez que se hace referencia a ese bloque, el contador se incrementa en uno. Cuando la caché alcanza su capacidad máxima y hay un nuevo bloque esperando a ser insertado, el sistema busca el bloque con el contador más bajo y lo elimina de la caché. En caso de empate (es decir, dos o más claves con la misma frecuencia), se invalida la clave menos utilizada . [ 2 ]

  • LFU ideal: hay un contador para cada artículo del catálogo.
  • LFU práctico: existe un contador para los elementos almacenados en la caché. El contador se pierde si el elemento se elimina.

Problemas

Aunque el método LFU pueda parecer un enfoque intuitivo para la gestión de memoria, no está exento de fallos. Consideremos un elemento en memoria al que se accede repetidamente durante un breve periodo de tiempo y al que no se vuelve a acceder durante un periodo prolongado. Debido a la rapidez con la que se accedió a él, su contador ha aumentado drásticamente, aunque no se vuelva a utilizar durante un tiempo considerable. Esto deja otros bloques que, en realidad, podrían utilizarse con mayor frecuencia, susceptibles de ser eliminados simplemente porque se accedió a ellos mediante un método diferente. [ 3 ]

Además, los elementos nuevos que acaban de entrar en la caché están sujetos a ser eliminados muy pronto, ya que comienzan con un contador bajo, aunque posteriormente se utilicen con mucha frecuencia. Debido a problemas importantes como estos, un sistema LFU explícito es bastante infrecuente; en su lugar, existen sistemas híbridos que utilizan conceptos de LFU. [ 4 ]

Véase también

Referencias

  1. ↑ Donghee Lee; Jongmoo Choi; Jong-Hun Kim; SH Noh; Sang Lyul Min; Yookun Cho; Chong Sang Kim (diciembre de 2001). "LRFU: un espectro de políticas que engloba las políticas menos usadas recientemente y menos usadas frecuentemente". IEEE Transactions on Computers . 50 (12): 1352– 1361. Bibcode : 2001ITCmp..50.1352L . doi : 10.1109/TC.2001.970573 . S2CID 2636466 . 
  2. ↑ Silvano Maffeis (diciembre de 1993). "Algoritmos de gestión de caché para sistemas de archivos flexibles" . ACM SIGMETRICS Performance Evaluation Review . 21 (2): 16– 25. CiteSeerX 10.1.1.48.8399 . doi : 10.1145/174215.174219 . S2CID 7624318 .  
  3. ↑ William Stallings (2012). Sistemas operativos: Principios internos y de diseño (7.ª ed.). 
  4. ↑ BT Zivkoz; AJ Smith (1997). "Almacenamiento en caché en disco en grandes bases de datos y sistemas de tiempo compartido". Actas del Quinto Simposio Internacional sobre Modelado, Análisis y Simulación de Sistemas Informáticos y de Telecomunicaciones . doi : 10.1109/MASCOT.1997.567612 .
  • Un algoritmo O(1) para implementar el esquema de desalojo de caché LFU , 16 de agosto de 2010, por Ketan Shah, Anirban Mitra y Dhruv Matani.