Impacto de los Fallos en Cache y Estrategias de Reemplazo

¿Qué ocurre cuando hay un fallo a cache? Considere las estrategias aleatoria, LRU y FIFO. ¿Qué pasa si es conjunto asociativo, totalmente asociativo o transformación directa?

R.- Cuando ocurre un fallo en el acceso a cache, se debe realizar una búsqueda de datos o de la instrucción requerida en la memoria principal y luego trasladar eso a cache. Si ocurre que el cache está lleno, debemos reemplazar un bloque de la cache por el bloque donde se encuentra la información. Esto se realiza con estrategias de reemplazo:

Estrategias de Reemplazo

• Aleatoria: Un bloque de memoria es elegido aleatoriamente entre los bloques que forman el conjunto donde se ha producido el fallo de acceso a la cache, generando un reparto uniforme.
• FIFO: Los bloques dentro del conjunto están ordenados de acuerdo a la secuencia en que son cargados. Cuando se debe cargar un bloque, se elimina de la memoria cache el que fue cargado en primer lugar y los bloques siguientes son removidos en el mismo orden.
• LRU: Es el más usado, tiene la ventaja de que luego de cada referencia se actualiza una lista que indica cuán reciente fue la última referencia a un bloque determinado. Si se produce un fallo, se reemplaza ese bloque con la referencia más lejana.

Tipos de Transformación

• Transformación directa: Consiste en que a cada posición de memoria principal le corresponde un solo bloque en el cache. Debido a esto, no sirven las estrategias de reemplazo, ya que solo puede llevar la información deseada a un bloque específico de la cache. El bloque está disponible antes de terminar la comparación.
• Transformación asociativa: En este caso, las direcciones de memoria pueden ocupar cualquier posición de bloque dentro del cache. Es más complejo de hacer físicamente, pero evita en gran medida el swapping. Aquí, las estrategias de reemplazo deben trabajar con toda la cache, debido a que cualquier posición de la memoria principal puede ser llamada a cualquier bloque del cache. Se compara el tag con todos los tags de los bloques de cache.
• Transformación asociativa por conjunto: A cada posición de la memoria principal le corresponde una posición determinada en un conjunto de bloques, que puede ser ubicada en distintos bloques del cache.

Preguntas Frecuentes

• ¿Dónde colocar un bloque en el nivel superior? Colocando un bloque superior como page frame.
• ¿Cómo encontrar un bloque en el nivel superior? Encontrando una posición en una tabla de página.
• ¿Cuál bloque sería reemplazado en un fallo? Usando algoritmos del menos usado recientemente (LRU).
• ¿Qué sucede al escribir? Es necesario realizar un write back.