Saltar al contenido
Codifíca.me | Desarrollo web | Programación

Memorias caché y algoritmos de reemplazo

8 junio, 2012

Memorias caché

Como hemos visto en otro artículo la memoria caché se utiliza para guardar bloques de datos que se prevé que vayan a ser reutilizados en la ejecución de un programa.

procesador, cpu, jerárquia de memorias

La memoria cache se encuentra localizada entre el procesador y la memoria principal, así que técnicamente es más rápido un acceso a la memoria caché que un acceso a la memoria principal.

Las distintas memorias tienen una distribución jerárquica dependiendo de la cercanía y rapidez con las que el procesador obtiene los datos, y entre ellas se establece una comunicación directa entre la superior y la inferior, es decir, si el procesador quiere obtener un dato de la memoria principal, el dato será trasladado primeramente de la memoria principal a la memoria cache y después de la memoria cache al procesador.

Dado que la velocidad de acceso a una memoria es inversamente proporcional al tamaño de la misma, las memorias cache que tienden a ser muy rápidas no pueden ser muy grandes. Por ello, la memoria cache se llenará con mucha facilidad y tendrá que ir renovando el contenido rápidamente.

Para asignar los bloques de datos que tiene que tener una memoria cache se han diseñado varios tipos de políticas de asignación y varios algoritmos de reemplazo para intercambiar bloques de datos.

Políticas de asignación de memorias

Política de asignación directa:

Cada bloque de datos de la memoria principal se encuentra alojado en una sola línea de la memoria cache.

Política de asignación completamente asociativa

Cada bloque de datos de la memoria principal se puede encontrar en cualquier línea de la memoria cache.

Política de asignación por conjuntos

Cada bloque de datos de la memoria principal se puede encontrar dividido entre distintas líneas de la memoria caché.

Algoritmos de reemplazo de la memoria caché

Los algoritmos de reemplazo son los encargados de seleccionar que línea de la memoria cache se va a reemplazar cuando la memoria caché está llena y tenemos que asignar una línea de la memoria principal en la memoria caché.

Cada vez que el procesador accede a la memoria cache para buscar un dato y este no se encuentra en la memoria caché, se produce lo que se denomina fallo en la memoria cache, entonces ocurre que tenemos que ir a buscar ese dato a la memoria principal, obtener la fila en la que se encuentra y llevar este bloque de datos a la memoria caché
La memoria caché directa es la única que no utiliza ningún algoritmo de reemplazo, puesto que cada bloque ocupará una sola línea, y la asignación es directa.

Los ejemplos que vienen a continuación son para memorias caché completamente asociativas.

Los algoritmos de reemplazo más utilizados en las memorias caché son los siguientes:

FIFO:

Este algoritmo es el clásico, “first in, first out”, primero en entrar será el primero en salir.
La utilización de este algoritmo no es muy eficiente, ya que una línea que lleve mucho tiempo en la memoria cache no tiene porque no utilizarse más que una que acabe de entrar.
Utilizando FIFO se irán reemplazando las líneas de la memoria cache que lleven más tiempo por las nuevas.

LFU:

Con este algoritmo se irán reemplazando las líneas que se hayan utilizado menos veces por las nuevas.

LRU:

Este algoritmo reemplaza las líneas que hace más tiempo que no se utilizan por las líneas nuevas que necesita el procesador.