Come viene sostituito il blocco della cache nella cache completamente associativa?

Nelle cache associative impostate e completamente associative, vengono usate varie politiche di sostituzione per questo scopo. Alcune di esse sono FIFO, LRU, P-LRU, ecc.

La più popolare è la strategia LRU (least recently used). In questo schema, vengono impiegati dei contatori pari al numero di linee di cache (uno per ogni linea di cache). Alla linea di cache meno usata viene dato il conteggio di '0′ e a quella usata più recentemente viene dato il conteggio di 'n-1', dove n è il numero di linee di cache.

Ogni volta che un blocco è richiesto e se non è presente nella cache, il blocco viene letto dal dramma e viene sostituito con l'ultima linea di cache usata (conteggio di '0′).

Così si vede chiaramente che ad ogni accesso, tutti i contatori cambiano il loro valore (se l'ultimo usato non viene nuovamente consultato). E quindi il consumo di energia è abbastanza alto. Inoltre sarà richiesto un totale di nlog(n) flip flop che aumenta il consumo di spazio.

Per evitare questi problemi, viene spesso impiegata una strategia diversa (pseudo LRU). Questa strategia usa alberi binari invece di contatori.