# La caché LRU - Sitio: Ikusmira — enciclopedia en castellano de ciencias sociales y humanidades - URL canónica: https://ikusmira.org/p/la-cache-lru/ - Categoría: Informática - Publicado: 2026-09-04 - Autoría: Eneko Sarasola (redacción de Ikusmira) - Política editorial (autoría, revisión, correcciones, financiación): https://ikusmira.org/politica-editorial/ Una **caché** es una memoria pequeña y rápida que guarda copias de lo que se ha usado hace poco, con la apuesta de que volverá a hacer falta. La apuesta se cumple tan a menudo que la informática entera está construida sobre ella: el procesador tiene tres niveles de caché delante de la memoria, el sistema operativo guarda en memoria las páginas del disco, el navegador guarda las imágenes de las webs, y las redes de distribución de contenidos guardan copias de los vídeos cerca de quien los ve. Como la caché es pequeña, tarde o temprano se llena, y entonces hay que decidir qué copia tirar para hacer sitio. Esa decisión es la *política de reemplazo*, y la más usada, la que da título a esta página, es **LRU**: expulsar la que lleva más tiempo sin usarse, *least recently used*. La figura de esta página es una caché de unos pocos huecos frente a una secuencia de trescientos accesos a sesenta elementos. La cinta superior es la secuencia: cada acceso se pinta en verde si el elemento estaba en la caché, un *acierto*, y en rojo si no, un *fallo*. Debajo, los huecos, con el elemento que ocupa cada uno y cuántas veces se ha pedido. El deslizador cambia el tamaño; el selector, la política; y el otro selector, la forma de la secuencia, que es lo que de verdad decide si una caché sirve para algo. La gráfica inferior calcula, para esta misma secuencia, la tasa de aciertos de cada política con cada tamaño de caché. Lo primero que enseña la figura es que ninguna política sirve sin una buena secuencia. Con accesos uniformes —cada elemento igual de probable que cualquier otro— una caché de ocho huecos sobre sesenta elementos acierta alrededor del 13 % de las veces, sea cual sea la política, porque no hay nada que recordar. Con accesos tipo Zipf, en los que unos pocos elementos se piden muchísimo y la mayoría casi nunca, la misma caché acierta más de la mitad de las veces, y una de dieciséis huecos, casi tres de cada cuatro. Lee Breslau y sus colegas mostraron en 1999 que las peticiones a las páginas web siguen una distribución de ese tipo, y eso es lo que hace rentables las cachés de Internet. La propiedad se llama *localidad*: que lo que se acaba de usar tenga más probabilidad de volver a usarse. Peter Denning la formalizó en 1968 con el modelo del conjunto de trabajo, el grupo de páginas que un programa está usando en cada momento, y mostró que ese grupo es pequeño y cambia despacio. Lo segundo es el caso en que LRU se equivoca sistemáticamente, que la figura llama bucle. Si un programa recorre nueve elementos en orden, una y otra vez, con una caché de ocho huecos, LRU expulsa siempre el elemento que va a hacer falta justo a continuación —el que lleva más tiempo sin usarse es, en un bucle, el siguiente de la cola— y no acierta nunca. FIFO, que expulsa el más antiguo, tampoco. La política aleatoria, que no sabe nada, acierta a veces. Y con un hueco más, nueve, todas aciertan siempre. Este comportamiento se ve en los recorridos secuenciales de ficheros grandes y en los escaneos de bases de datos, y es la razón de que las cachés reales lleven protecciones contra los barridos: Nimrod Megiddo y Dharmendra Modha propusieron en 2003 el algoritmo ARC, que reparte la caché entre lo recién llegado y lo que ya ha demostrado repetirse, y ajusta el reparto solo según cuál de las dos mitades habría acertado. Lo tercero es la política contra la que se compara todo, que es imposible. László Bélády demostró en 1966 que la política óptima es expulsar el elemento que tardará más en volver a pedirse, lo que exige conocer el futuro; ninguna caché real puede hacerlo, pero sobre una secuencia ya grabada, como la de la figura, se puede calcular, y la curva negra es esa cota. Mide cuánto de lo que se pierde es culpa de la política y cuánto es inevitable. Daniel Sleator y Robert Tarjan probaron en 1985 el resultado que ancla la teoría: cualquier política que no conozca el futuro puede llegar a fallar *k* veces más que la óptima, siendo *k* el tamaño de la caché, y LRU alcanza exactamente ese límite, lo que significa que ninguna otra política sin información del futuro puede garantizar nada mejor en el peor caso. En el caso medio, con secuencias reales, LRU se queda bastante cerca de la óptima, y por eso es la que se usa. Bélády encontró también algo que se conoce como su anomalía: con FIFO, agrandar la caché puede *reducir* los aciertos para algunas secuencias. LRU no padece eso; Mattson y sus colegas demostraron en 1970 que pertenece a la clase de los algoritmos de pila, en los que el contenido de una caché de tamaño *k* está siempre contenido en el de una de tamaño *k* + 1, de modo que la curva de aciertos según el tamaño solo puede subir, y se puede calcular de una pasada para todos los tamaños a la vez. Es exactamente lo que hace la gráfica inferior de la figura. Que la curva de LRU sea monótona y la de FIFO tenga dientes de vez en cuando es una de las cosas que se ven al ejecutar unas cuantas secuencias, y una de las razones por las que la política que tira lo menos usado recientemente es la que todo el mundo elige sin pensarlo mucho. ## Fuentes - László A. Bélády — *A Study of Replacement Algorithms for a Virtual-Storage Computer*, IBM Systems Journal 5(2) (1966) - Peter J. Denning — *The Working Set Model for Program Behavior*, Communications of the ACM 11(5) (1968) - Richard L. Mattson, Jan Gecsei, Donald R. Slutz e Irving L. Traiger — *Evaluation Techniques for Storage Hierarchies*, IBM Systems Journal 9(2) (1970) - Daniel D. Sleator y Robert E. Tarjan — *Amortized Efficiency of List Update and Paging Rules*, Communications of the ACM 28(2) (1985) - Lee Breslau, Pei Cao, Li Fan, Graham Phillips y Scott Shenker — *Web Caching and Zipf-like Distributions: Evidence and Implications*, Proceedings of IEEE INFOCOM '99 (1999) - Nimrod Megiddo y Dharmendra S. Modha — *ARC: A Self-Tuning, Low Overhead Replacement Cache*, Proceedings of the 2nd USENIX Conference on File and Storage Technologies (FAST) (2003) --- Cómo citar: Sarasola, Josemari (2026). «La caché LRU». Ikusmira. https://ikusmira.org/p/la-cache-lru/ Índice del sitio para modelos: https://ikusmira.org/llms.txt