Hispanopedia Wiki
Articulo de referencia

Algoritmo de almacenamiento en caché LIRS

LIRS ( Low Inter-reference Recency Set ) es un algoritmo de reemplazo de páginas con un rendimiento mejorado en comparación con LRU (Least Recently Used) y muchos otros algoritm...

Hispanopedia WikiContenido en espanolLectura gratuita

LIRS ( Low Inter-reference Recency Set ) es un algoritmo de reemplazo de páginas con un rendimiento mejorado en comparación con LRU (Least Recently Used) y muchos otros algoritmos de reemplazo más nuevos. [1] Esto se logra utilizando la "distancia de reutilización" [2] como métrica de localidad para clasificar dinámicamente las páginas a las que se accede para tomar una decisión de reemplazo.

Resumen

Cuantificación de la localidad

Si bien todos los algoritmos de reemplazo de páginas dependen de la existencia de una localidad de referencia para funcionar, una diferencia importante entre los distintos algoritmos de reemplazo es la forma en que se cuantifica esta localidad. LIRS utiliza la distancia de reutilización de una página, o el número de páginas distintas a las que se ha accedido entre dos referencias consecutivas de la página, para cuantificar la localidad. Específicamente, LIRS utiliza la última y la penúltima referencia (si las hay) para este propósito. Si se accede a una página por primera vez, su distancia de reutilización es infinita. Por el contrario, LRU utiliza la actualidad de una página, que es el número de páginas distintas a las que se ha accedido después de la referencia de la página, para cuantificar la localidad. Para tener en cuenta el historial de acceso actualizado, la implementación de LIRS utiliza en realidad la distancia de reutilización y la actualidad de una página más grandes como métrica para cuantificar su localidad, denotada como RD-R. Suponiendo que la memoria caché tiene una capacidad de C páginas, el algoritmo LIRS clasifica las páginas a las que se ha accedido recientemente según sus valores RD-R y retiene las C páginas mejor clasificadas en la memoria caché.

Los conceptos de distancia de reutilización y actualidad se pueden visualizar como se muestra a continuación, en donde T1 y T2 son los tiempos de referencia anterior y posterior de la página B, respectivamente, y T3 es el tiempo actual. 

. . . B . . . . . . . . . . . B . . . . . .
               ^----Distancia de reutilización---^--Actualidad--^
               T1T2T3

Selección de la víctima sustituta

LIRS organiza los metadatos de las páginas almacenadas en caché y algunas páginas no almacenadas en caché y lleva a cabo sus operaciones de reemplazo descritas a continuación, que también se ilustran con un ejemplo [3] en el gráfico.

Operaciones de sustitución de LIRS
  1. La memoria caché se divide en una partición de baja interreferencia reciente (LIR) y una partición de alta interreferencia reciente (HIR). La partición LIR almacena las páginas mejor clasificadas (páginas LIR) y la partición HIR almacena algunas de las otras páginas (páginas HIR).
  2. La partición LIR contiene la mayor parte del caché y todas las páginas LIR residen en el caché.
  3. Todas las páginas a las que se accedió recientemente se colocan en una cola FIFO llamada pila LIRS (pila S en el gráfico), y todas las páginas HIR residentes también se colocan en otra cola FIFO (pila Q en el gráfico).
  4. La página a la que se accede se mueve a la parte superior de la pila S y se eliminan todas las páginas HIR que se encuentran en la parte inferior de la pila. Por ejemplo, el gráfico (b) se genera después de que se accede a la página B en el gráfico (a).
  5. Cuando se accede a una página HIR en la pila S , se convierte en una página LIR y, en consecuencia, la página LIR que se encuentra actualmente en la parte inferior de la pila S se convierte en una página HIR y se mueve a la parte superior de la pila Q. Por ejemplo, el gráfico (c) se produce después de que se accede a la página E en el gráfico (a).
  6. Cuando se produce un error y se debe reemplazar una página residente, se selecciona como víctima para el reemplazo la página HIR residente en la parte inferior de la pila Q. Por ejemplo, los gráficos (d) y (e) se generan después de acceder a las páginas D y C en el gráfico (a), respectivamente.

Despliegue

LIRS se ha implementado en MySQL desde la versión 5.1, [4] y otra referencia por enlace. También se adopta en la plataforma de cuadrícula de datos Infinispan . [5] Una aproximación de LIRS, CLOCK-Pro, [6] se adopta en NetBSD . [7] LIRS se adopta en Apache Jackrabbit, un repositorio de contenido. Se desarrolla un caché LIRS en memoria en el sistema de virtualización de datos Red Hat JBoss. LIRS se utiliza en el motor de base de datos H2, que se denomina caché resistente al escaneo. Además, LIRS se utiliza en Apache Impala, un procesamiento de datos con Hadoop.

Véase también

Referencias

  1. ^ Jiang, Song; Zhang, Xiaodong (junio de 2002). "LIRS: una política eficiente de reemplazo de conjuntos de interreferencias de baja actualidad para mejorar el rendimiento de la caché de búfer". Revisión de evaluación del rendimiento de ACM SIGMETRICS . 30 (1): 31–42. doi :10.1145/511399.511340.
  2. ^ Mattson, RL; Gecsei, J.; Slutz, DR; Traiger, IL (1970). "Técnicas de evaluación para jerarquías de almacenamiento". IBM Systems Journal . 9 (2): 78–117. doi :10.1147/sj.92.0078.
  3. ^ Song Jiang; Xiaodong Zhang (2005). "Hacer que LRU sea compatible con cargas de trabajo de localidad débil: un nuevo algoritmo de reemplazo para mejorar el rendimiento de la caché de búfer". IEEE Transactions on Computers . 54 (8): 939–952. doi :10.1109/TC.2005.130. S2CID  11539061.
  4. ^ svn commit - mysqldoc@docsrva: r6768 - tronco/ndbapi
  5. ^ Desalojo de Infinispan, actualizaciones por lotes y LIRS
  6. ^ Song Jiang, Feng Chen y Xiaodong Zhang, "CLOCK-Pro: una mejora efectiva del reemplazo de CLOCK", en Actas de la Conferencia Técnica Anual de USENIX de 2005 (USENIX'05), Anaheim, CA, abril de 2005.
  7. ^ Referencia cruzada del kernel de FreeBSD/Linux sys/uvm/uvm_pdpolicy_clockpro.c
  • Hacia una VM O(1) por Rik van Riel sobre el posible uso de LIRS para equilibrar la memoria caché y la memoria del programa en Linux.
  • Un informe sobre la implementación del reemplazo de la página CLOCK-Pro.
  • Proyectos de reemplazo de páginas avanzados establecidos por el equipo de desarrollo de administración de memoria de Linux.
  • Parche CLOCK-Pro desarrollado por Rik van Riel.
  • Parche CLOCK-Pro desarrollado por Peter Zijlstra.
  • CLOCK-Pro se menciona como ejemplo en la sección de Linux y Academia en el libro Arquitectura profesional del kernel de Linux de Wolfgan Mauerer.
  • Un artículo que detalla las diferencias de rendimiento de LIRS y otros algoritmos “El impacto en el rendimiento de la precarga del kernel en los algoritmos de reemplazo de caché de búfer” por Ali R. Butt, Chris Gniady e Y. Charlie Hu.
Retrieved from "https://en.wikipedia.org/w/index.php?title=LIRS_caching_algorithm&oldid=1238769707"
Lecturas relacionadas
6 articulos
{\estilo de visualización h\leq k}Algoritmo de reemplazo de páginaEn un sistema operativo de computadora que utiliza paginación para la administración de memoria virtual , los algoritmos de reemplazo de páginas de...{\displaystyle T=m\times T_{m}+T_{h}+E}Políticas de reemplazo de cachéEn informática , las políticas de reemplazo de caché (también conocidas como algoritmos de reemplazo de caché o algoritmos de caché ) son instrucci...Localidad de referenciaLocalidad de referenciaEn informática , la localidad de referencia , también conocida como principio de localidad , [1] es la tendencia de un procesador a acceder al mism...FIFO (informática y electrónica)FIFO (informática y electrónica)En informática y en teoría de sistemas , el principio "primero en entrar, primero en salir " (el primero en entrar es el primero en salir), acrónim...MySQLMySQLMySQL ( / ˌ m aɪ ˌ ɛ s ˌ k juː ˈ ɛ l / ) [5] es un sistema de gestión de bases de datos relacionales (RDBMS) de código abierto . [5] [6] Su nombre ...InfinispanInfinispan es una caché distribuida [ 1 ] y una base de datos NoSQL en memoria de clave-valor desarrollada por Red Hat . Las aplicaciones Java pued...