2 Wege SetAssoziativeZwischenSpeicher?: Da es hier immer einen aktuelleren Eintrag gibt, genügt ein Bit. Ist es gesetzt, ist der erste eintrag neuer, ist es gelösch, ist der zweite Eintrag neuer. Zugriff setzt bzw. löscht dieses Bit automatisch. Aufgrund der enormen Komplexität des LRU-Algorithmus für 2-Wege Zwischenspeicher spare ich mir jetzt eine ausführlichere Betrachtung ;-)

Vorteil: Dies lässt sich verdammt einfach implementieren, und kostet nur 1 zusätzliches Bit. Nachteile: Funktioniert nur für 2 Elemente

4 Wege SetAssoziativeZwischenSpeicher?: Hier benutzt man drei Bits. Das eine gibt an, ob der älteste Eintrag einer von 0 und 1 ist, oder einer von 2 und 3. Das zweite Bit gibt an, ob Eintrag 0 oder 1 älter ist, das dritte gibt an, ob Eintrag 2 oder 3 älter ist. Beim Ersetzen wird entsprechend der älteste Eintrag wie folgt gefunden:

Eintrag=B0?(B2?3:2):(B1?1:0)

Bei einem Zugriff auf einen Eintrag wird das Bit 1 bzw. 2 so gesetzt, daß es auf den anderen Eintrag zeigt, und Bit 0 wird so gesetzt, daß es auf die andere Eintragsgruppe zeigt.

Fehler: Wenn Eintrag 3 am ältesten ist, 2 am zweitältesten, und 1 am drittältesten, werden die Einträge in der falschen Reihenfolge erneuert, nämlich 3,1,2,0. (es gibt 3 äquivalente Fälle, bei denen das gleiche geschieht.) Vorteil: Dies lässt sich verhältnismäßig einfach implementieren, und kostet nur 3 Bits pro 4 zu verwaltende Einträge. Nachteile: Funktioniert nur für 4 Elemente

FixMe: Gibt es hierfür einen Namen: Es wird eine Listenstruktur wie struct eintrag { int neuer,älder,benutzt; } Eintrag[{NUM ENTRIES}?]; angelegt, und derart initialisiert, daß Eintrag[i].älder=i-1 und Eintrag[i].neuer=i+1 und Eintrag[i].benutzt=0 ist. (Eintrag[0].älter=-1 und Eintrag[{NUM ENTRIES}?].neuer=-1, weiterhin gibt es die Werte ältester=0 und neuster={NUM ENTRIES}?-1).

Bei einem Zugriff auf ein Element wird es aus der doppelt verketteten liste entfernt, und an das Ende der neuesten Elemente angehängt. Wird ein neuer (freier) Eintrag gebraucht, wird er von der anderen Seite genommen ggf. geleert (und auch nach vorne geschoben).

Vorteil: Ist absolut genau, ist verhältnismäßig einfach zu implementieren, verliert nicht an Geschwindigkeit, wenn mehr Einträge hinzu kommen. Nachteil: Kostet viel Speicher, eignet sich daher nur, wenn man große Datenmengen pro Eintrag hat, da sonst der Speicher Overhead zu groß wird, braucht einige zusätzliche Speicherzugriffe (es müssen die Einträge für drei Eintrag-Strukturen geändert werden).

ToDo: Schilderung weiterer Verfahren und ihre Vor- und Nachteile.