Algoritmos de sustitución

Como hemos visto, el espacio de ubicación de un bloque en Mc depende de la función de correspondencia. La correspondencia directa reduce el espacio a un marco de bloque, por lo que no queda alternativa de sustitución cuando hay que ubicar un nuevo bloque. En las correspondencias asociativa y asociativa por conjuntos hay que decidir qué bloque sustituir. En la primera la elección se tiene que realizar sobre cualquier bloque presente en Mc, mientras que en la segunda se reduce al conjunto único donde puede ubicarse el nuevo bloque. Las políticas de reemplazamiento más utilizadas son cuatro:

1. Aleatoria: se escoge un bloque al azar

2. LRU(Least Recently Used)

• Se sustituye el bloque que hace más tiempo que no ha sido referenciado
• Algoritmo: se asocian contadores a los marcos de bloque y

Si se referencia MBi

∀ MBk :contador(MBk) ≤ contador(MBi) ==> contador(MBk) := contado(MBk) + 1 contador(MBi) = 0

Cuando se produce un fallo se sustituye el MBi: contador(MBi) = MAXIMO

• Para una memoria asociativa de dos vías basta con añadir un bit de uso a cada marco de bloque. Cuando un marco de bloque es referenciado su bit de uso se pone a 1 y el del marco del mismo conjunto a 0. Cuando hay que sustituir se elige el marco de bloque con bit de uso igual a 0.

3. FIFO (First In First Out)

• Se sustituye aquel bloque que ha estado más tiempo en la caché (independientemente de sus referencias)
• Se puede implementar con una cola

4. LFU(Least Frequently Used)

• Se sustituye aquel bloque que ha experimentado menos referencias
• Se puede implementar asociando un contador a cada marco de bloque

Fuente: Estructura de Computadores, Facultad de Informática, UCM