Algoritmo de caché para niños

En el mundo de la computación, los algoritmos de caché son como los organizadores de una mochila muy especial en tu ordenador, llamada memoria caché. Esta mochila es súper rápida y guarda la información que tu computadora usa más a menudo.

Imagina que tu mochila (el caché) tiene un espacio limitado. Cuando está llena y necesitas guardar algo nuevo, los algoritmos de caché son las reglas que deciden qué cosas viejas sacar para hacer espacio. Su objetivo es que tu computadora funcione lo más rápido posible.

Hay dos cosas muy importantes para saber si un caché funciona bien:

• Tasa de aciertos: Esto mide cuántas veces la información que tu computadora busca ya está en el caché. ¡Cuanto más alta, mejor! Significa que la computadora encuentra lo que necesita rápidamente.
• Latencia: Es el tiempo que tarda el caché en darte la información que pediste, si es que ya la tenía guardada. Cuanto más baja sea la latencia, más rápido es el caché.

Cada algoritmo de caché busca un equilibrio entre tener muchos aciertos y ser muy rápido. A veces, para ser más rápido, se sacrifica un poco la tasa de aciertos, y viceversa.

Algunas aplicaciones, como las que transmiten videos o música en vivo (streaming), no se benefician mucho del caché. Esto es porque cada parte del video o la música se usa una sola vez y luego se descarta. Si el caché guarda estos datos, puede ocupar espacio que sería útil para otra información.

Tipos de algoritmos de caché

Existen diferentes estrategias o "reglas" que los algoritmos de caché usan para decidir qué información guardar y cuál eliminar. Aquí te explicamos algunas de las más conocidas:

Algoritmo de Bélády: El ideal imposible

El algoritmo de Bélády es un concepto teórico. Imagina que pudiera saber exactamente qué información vas a necesitar en el futuro y cuándo. Así, podría descartar justo lo que no usarás por más tiempo. ¡Sería perfecto! Pero como nadie puede predecir el futuro, este algoritmo no se puede usar en la vida real. Sin embargo, sirve como un modelo para comparar qué tan buenos son los algoritmos que sí podemos usar.

Menos usado recientemente (LRU)

El algoritmo Least Recently Used (LRU), que significa "menos usado recientemente", es muy popular. Su regla es simple: si el caché está lleno, elimina la información que no se ha usado en más tiempo. Es como si tu mochila sacara el libro que dejaste de leer hace semanas para meter uno nuevo. Para que funcione bien, el sistema tiene que recordar cuándo se usó cada cosa, lo cual puede ser un poco complicado.

Usado más recientemente (MRU)

El algoritmo Most Recently Used (MRU), o "usado más recientemente", hace lo contrario que LRU. Cuando necesita espacio, descarta la información que acabas de usar. Parece extraño, ¿verdad? Pero hay situaciones donde esto es muy útil. Por ejemplo, si estás revisando una lista muy larga de archivos una y otra vez, MRU es mejor porque mantiene los archivos más antiguos que aún no has vuelto a ver.

Pseudo-LRU (PLRU)

El Pseudo-LRU (PLRU) es una versión simplificada de LRU que se usa mucho en los cerebros de las computadoras (las CPU). Como implementar LRU de forma perfecta puede ser muy costoso y lento para las CPU más rápidas, PLRU usa una técnica más sencilla que casi siempre logra descartar algo que no se ha usado mucho. Es un buen equilibrio entre eficiencia y velocidad.

Reemplazo aleatorio (RR)

El algoritmo de Random Replacement (RR), o "reemplazo aleatorio", es el más sencillo de todos. Cuando el caché necesita espacio, simplemente elige al azar qué información eliminar. No necesita recordar nada sobre el uso de los datos, lo que lo hace muy rápido y fácil de implementar. Por eso, se ha usado en algunos procesadores de teléfonos y tabletas (como los ARM).

LRU segmentado (SLRU)

El Segmented LRU (SLRU) es un poco más complejo. Divide el caché en dos partes: un segmento de "supervisión" y un segmento "protegido". La información nueva entra en el segmento de supervisión. Si algo en el segmento de supervisión se usa varias veces, se mueve al segmento protegido, que guarda las cosas más importantes. Si el segmento protegido se llena, la información menos usada de ahí vuelve al segmento de supervisión, dándole una última oportunidad antes de ser eliminada.

Asociación de ida y vuelta (2-way set associative)

Este método se usa en los cachés de alta velocidad de las CPU. En lugar de tener que buscar en todo el caché, cada nueva pieza de información solo puede ir a una de dos posibles ubicaciones predefinidas. El algoritmo solo necesita un pequeño indicador para saber cuál de esas dos ubicaciones se usó menos recientemente, lo que lo hace muy rápido.

Mapeo directo de caché

El Direct-mapped cache es aún más rápido y se usa en las CPU más veloces. Aquí, cada pieza de información tiene un único lugar específico donde puede guardarse en el caché. Si ese lugar ya está ocupado, la información que estaba ahí se elimina sin preguntar. Es como tener un casillero asignado para cada cosa.

Menos frecuentemente usados (LFU)

El algoritmo Least Frequently Used (LFU), o "menos frecuentemente usados", cuenta cuántas veces se ha solicitado cada pieza de información. Cuando necesita espacio, elimina la que se ha usado menos veces en total.

Caché de reemplazo adaptativo (ARC)

El Adaptive Replacement Cache (ARC) es un algoritmo inteligente que combina las ideas de LRU y LFU. Se ajusta automáticamente para decidir cuál de las dos estrategias es mejor en cada momento, dependiendo de cómo se estén usando los datos. Esto le permite adaptarse a diferentes situaciones y mejorar el rendimiento.

CLOCK con reemplazo adaptativo (CAR)

El CLOCK with Adaptive Replacement (CAR) es similar a ARC, pero usa otra técnica llamada CLOCK. También se ajusta solo y no necesita que le digas cómo funcionar, ofreciendo un rendimiento muy bueno.

Algoritmo de caché multi-cola (MQ)

El algoritmo Multi Queue (MQ) es otra estrategia avanzada que organiza la información en varias "colas" para gestionar mejor el caché.

Otros aspectos importantes

Además de las reglas de reemplazo, hay otros factores que los algoritmos de caché pueden considerar:

• Costo de los elementos: Algunos datos son más difíciles o lentos de obtener que otros. Un algoritmo podría preferir mantener en el caché la información que cuesta más conseguir.
• Tamaño de los elementos: Si los datos tienen diferentes tamaños, a veces es mejor eliminar un elemento grande para hacer espacio, en lugar de varios pequeños.
• Expiración de elementos: Algunos datos en el caché tienen una "fecha de caducidad" (como las noticias o la información de una página web). El sistema puede eliminar automáticamente los datos que ya no son válidos.

Cómo la información de la memoria principal puede guardarse en diferentes lugares del caché.

Véase también

En inglés: Cache replacement policies Facts for Kids

• Caché (informática)
• Algoritmos de reemplazo de páginas