LRU - Aufwändig zu implementieren?

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

LRU - Aufwändig zu implementieren?

Beitrag von Red*Star »

Ich lese immer wieder, LRU als Seitenersetzungsstrategie sei aufwändig zu implementieren.

Finde ich nicht. Die Variante, die wir im Praktikum hatten (mit Countern und wasweißich) war aufwändig, ja. Aber was ist mit folgender, die mir gerade eingefallen ist?

Man speichere zu jeder Seite in einem Array:

S0. valid und isinfile?-bit
S1. physikalische Seitennummer
S2. Adresse auf Festplatte

Man speichere zu jeder Kachel in einem Array:

K0. dirty bit
K1. zwei Pointer auf "folgende" und "vorhergehende" Kachel (was das heißt, siehe unten)
[falls benötigt: K2. Rückreferenz auf momentan in diese Kachel eingelagerte virtuelle Seite]

Die zwei Pointer werden zur Implementierung einer doppelt zyklisch verketteten Liste verwendet, die als maximale Länge (logischerweise) die maximale Anzahl an Kacheln hat.
D.h. man speichere global:

Einen head-pointer hd (zeigt auf Kopf der Liste, das hintere Ende (tail) der Liste ist wegen der doppelt zyklischen Verkettung durch "tl = hd + 1" erreichbar (bzw. je nach Implementierungsvariante auch "tl = hd - 1"))


Zum Algorithmus: Der Tail der Liste sei jeweils die "älteste" (also am längsten nicht benutzte) Seite. D.h. die Liste sieht folgendermaßen aus:

[entry0 = head (most recently used)| entry1 | entry2 | ... | entryn-2| entryn-1 = tail (least recently used)] (tail <-> wieder verlinkt mit head)
  • Solange der physikalische Speicher "ungefüllt" ist, fügt man die neu benutzte Kachel K einfach vorne an die Liste an (läuft auf das Umsetzen von 5 Pointern hinaus: Nachfolger von K: Vorgänger, Vorgänger von K: Nachfolger, K: Nachfolger UND Vorgänger, sowie zusätzlich dem hd-Pointer).
  • Sobald der physikalische Speicher "voll" (sprich jetzt geht die swap-page-Party erst richtig los) ist:
    1. Bei einem Page hit: Löse die betroffene Kachel aus der Liste und setze sie an deren Anfang (Umsetzen von den 5 o.g. Pointern sowie zwei Pointern zusätzlich (neuer Nachfolger und neuer Vorgänger der umgesetzten Kachel), insgesamt also 7 Pointer).
    2. Bei einem Page miss: Wo ist die älteste Kachel? Genau: Am Ende der Liste. -> Anschaulich: Schmeiße also die am weitesten hinten stehende Kachel der Liste (Zugriff über den implizit existenten tl-Pointer) raus und setze die neue Kachel an diese Stelle. Vorher, falls die Kachel dirty war, macht man das übliche, also man sichert sie auf den Hintergrundspeicher zurück. (Konkret: Im Algorithmus würde sich dies bei o.g. Datenstrukturen lediglich auf ein Umsetzen des hd-Pointers beschränken, da ja die älteste Kachel nach vorne kommt!)

Konntet ihr mir 1. folgen und könnt ihr mir 2. bestätigen, dass ich nicht irgendwo einen total dämlichen Fehler gemacht habe, der das Konzept sofort als total nutzlos brandmarkt? ;) Freue mich auf Antworten.
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Re: LRU - Aufwändig zu implementieren?

Beitrag von Christoph B »

(Unter Vorbehalt, dass ich deine Theorie richtig verstanden hab:)
ich schätze mal das problem is, das du dadurch bei JEDEN Speicherzugriff 5 weitere Zugriffe (Wenn auch auf Hauptspeicher) brauchst um das zu implementieren.
Und wenn schon wegen wenigeren Speicherzugriffen im HS TLB entwickelt wurde um das stark zu optimieren.... :D
alternativ könnteste das mit einem extra Cache machen, der hätte dann aber nicht den Platz um was weiß ich wieviele Seitenadressen zu speichern.

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Re: LRU - Aufwändig zu implementieren?

Beitrag von Red*Star »

Hm, das wäre auch meine Theorie, dann würde das aber heißen, dass z.B. das "Excellent, but difficult to implement exactly" auf S. 78 in Foliensatz 6 in Wirklichkeit "Excellent, but produces much memory access overhead" lauten müsste. Denn schwierig/aufwändig finde ich meine Implementierung eigentlich nicht [crossout](z.B. verglichen mit Aging)[/crossout].

edit: (es gibt kein BB-Tag fürs durchstreichen)
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

citta
Mausschubser
Mausschubser
Beiträge: 96
Registriert: 7. Nov 2006 21:52

Re: LRU - Aufwändig zu implementieren?

Beitrag von citta »

Beachte das beim Aging ein Update nach einem Timer-Interrupt stattfindet (Millisekundenbereich) und nicht bei jedem Speicherzugriff (Nanosekundenbereich).

Antworten

Zurück zu „Archiv“