Hi,
zu der
Aufgabe 49 habe ich mir mal das Verfahren aus der Vorlesung als PHP-Skript gebastelt um mir das nochmal zu veranschaulichen. Evtl. hilft es ja jemanden (der grad PHP hat ;).
Jedenfalls ist mir das mit den 6-Bit ja noch klar, aber mit drei? Muss ich mir nochmal durch den Kopf gehen lassen…
und falls man sich das ganze mal auf einem windows-rechner anschauen will:
Die drei Bit Variante ist hier erklärt. Naja jedenfalls gibt es eine Grafik:
LRU IntelLetzlich läuft das über einen Binärbaum…
gruß
ich verstehe das Grundprinzip davon immer noch nicht so ganz. Also generell LRU is klar. Einfach nach dem FiFo prinzip. Aber was hat die Bitmatrix damit zu tun? Warum werden mehrere Bits gesetzt?
Wäre super wenn jemand eine Step-by-Step erklärung parat hätte.
Eigentlich funktioniert LRU nicht nach dem FiFo Prinzip. Es kann nämlich sein, dass eine Seite am längsten in einer Line liegt, aber trotzdem nicht gelöscht wird, da sie nicht die am längsten unbenutzte ist.
Die drei Bit Matrix approximiert dieses Verhalten durch das FiFo Prinzip.
Dies geschieht über folgenden Code(aus der Aufgabe 49)
if (B0 = 0)
if (B1 = 0)
verdränge Element von Speicherplatz 0
else
verdränge Element von Speicherplatz 1
else if (B2 = 0)
verdränge Element von Speicherplatz 2
else
verdränge Element von Speicherplatz 3
Hier fehlt natürlich noch das setzen der jeweiligen Bits, was man sich aber schnell selber überlegen kann. Da das Ganze ja sinniger Weise einen Zyklus ergeben muss.
Dieser code implementiert eine Baumstruktur mit B0 als wurzel, B1 als linken und B2 als rechten Nachfolger.
An B1 und B2 hängen dann jeweils noch zwei Knoten, die einem Sagen welche Line gelöscht werden muss. Ein Bild dieses Baums findet sich im Intel LRU Seite 4.
Ein Beispiel:
In der Matrix steht B0=1, B1=1(spielt hier keine Rolle, da B0=1), B2=1 -> Nach obigem Code wird also Speicherplatz drei verdrängt. Anschließend muss B0=0, B1=0 sein, damit als nächstes Speicherplatz 1 gelöscht wird(B2 spielt hier keine Rolle).
Ach ja den Baum verwendet man, da man so mit zwei Vergleichen die richtige Line finde kann.
gruß
