algoritmo de caché

En computación, los algoritmos de caché (referidos también como algoritmos de reemplazo o políticas de reemplazo) son programas que optimizan la gestión de la información en la memoria caché del ordenador. Cuando el caché está lleno, el algoritmo elige qué elementos elimina para liberar espacio y poder añadir nuevos elementos. El tiempo medio de acceso en memoria es​ donde: = tiempo medio de acceso al elemento = probabilidad de fallo = 1 - (probabilidad de acierto) = tiempo para hacer un acceso a memoria cuando ha habido un fallo (o, con caché multinivel, tiempo medio entre accesos al elemento en memoria para el siguiente nivel de caché)= latencia: tiempo para acceder al elemento en caché cuando ha habido un acierto = efectos secundarios, como colas mantenidas por los multiprocesadores Hay dos cifras principales al evaluar un caché:latencia y tasa de aciertos.Hay también otros factores secundarios que afectan a la prestación del caché.​ La tasa de aciertos en el caché describe cuántas veces que se busca un elemento este está en el caché. La latencia del caché describe lo que tarda en devolver un elemento solicitado (implica que ha habido un acierto). Las estrategia de reemplazo más rápidas llevan en cuenta los elementos menos usados para reducir la cantidad de tiempo utilizado en actualizarlos. Cada estrategia de reemplazo supone un compromiso entre la tasa de aciertos y la latencia. Medidas de la tasa de acierto se hacen empíricamente mediante aplicaciones de estrés. La tasa de acierto varía ampliamente de una aplicación a otra. En particular, las aplicaciones de streaming de video y audio generalmente tienen una tasa de acierto cercana a cero, dado que cada bit del stream se lee la primera vez -una omisión obligada- y luego no es leído o escrito nunca más. Incluso peor, muchos algoritmos de caché -especialmente LRU- permiten que estos datos de streaming entren en el caché, sacando fuera otros datos que sí se usarán pronto (contaminación del caché).​