Faktor zwischen LRU- und optimaler Strategie(Cache)
-
Hallo,
leider wusste ich kein gescheiten Bereich wo ich die Frage stellen kann noch ein schönes Thema dazu, weil sich halt sehr viele offene Fragen zu dem Problem stellen. Folgende Aufgabe soll ich lösen:
Betrachtet werde ein Hauptspeicher mit Platz für x Seiten. Mittels LRU-Strategie werde bestimmt, welche Seite aus dem Hauptspeicher verdrängt wird.
Konstruieren Sie ein Zugriffsmuster, bei dem die LRU-Strategie zu sehr viel mehr Seitenfehlern führt als eine optimale Strategie. Betrachten Sie sehr lange Muster. Wie groß kann der Faktor zwischen LRU- und optimaler Strategie werden? Drücken Sie den Faktor als Funktion der Seitenanzahl x aus. Beweisen Sie, daß die Schranke scharf ist, abgesehen von einem konstanten Faktor, indem Sie eine(fast) optimale Strategie für Ihr gewähltes Muster und die dadurch bedingten Seitenfehler angeben.Zu einen Beispiel wie man etwas kreiiert, sodass die LRU Methode versagt, würde ich eine Schleife vorschlagen. Eine Seite wird am Anfang geladen und eine weitere davon erzeugt, aber diese Seite soll nun am Ende der Schleife zwecks einen Vergleichs noch genutzt werden. Nun wird in der Schleife noch auf viele weitere Seiten zugegriffen, bzw. auf neu erzeugte Seiten zugegriffen und am Ende der Schleife soll nun die zum Anfang geladene Seite zum Vergleich geladen werden. Da aber der letzte Zugriff auf diese Seite schon sehr lange her ist und zwischendurch auch schon Seiten aus dem Cache verdrängt werden mussten, passiert also ein Cache-Miss und die Seite zum vergleichen muss wieder geladen werden. Nun sag ich halt noch, dass die Schleife nicht nur einmal durchlaufen wird, sondern ziemlich oft. Somit liegt eine nicht optimale Variante zum verdrängen von Seiten aus dem Cache vor.
Wenn man dies so sagen, weis ich nun bei der weiteren Frage mit der Funktion nicht mehr weiter??Hoffe einer von euch hat da ein paar Tipps
Vielen Dank
MfG
Storm
-
Das hast Du schon ganz richtig erkannt. Wir nehmen x+1 Seiten und lesen die immer in der selben Reihenfolge von vorne nach hinten. Nach dem ersten Durchlauf hat LRU bei jedem Zugriff nen Cache-Miss. Anzahl der Cache-Misses für LRU pro durchlauf also x+1. Wieviele Cache-Misses hat die optimale Strategie? Wohl gerade mal 2.
Damit ist der Faktor: (x+1)/2
-
Vielen Dank Jester:)
MfG
Storm