Vorgehensweise bei einer anderen Aufgabe (Assoziativ-Cache)

Question

>Wenn z.B. zwischendurch wieder die Daten von der Adresse aufgerufen wurden, die in der ersten Zeile steht, so ist ab diesem Zeitpunkt die 2. Zeile die "least-recently-used" Zeile.

Dazu habe ich noch eine Frage, und zwar habe ich vor kurzem eine Aufgabe gesehen, die sah so aus: Folgende Adressen werden aufgerufen, benutzt wird ein 4-zeiliger Assoziativ-Cache, welcher Daten an die erste freie Stelle schreibt bzw falls notwendig nach dem Least-Recently-Used-Prinzip alte Daten aus dem Cache löscht:

101, 102, 103, 106, 105, 106, 105, 102

Bis zur 4. Zahl komme ich noch ohne Schwierigkeiten, danach bin ich mir aber unsicher, wie ich verfahren soll. Die fünfte Zahl ist 105, und ich hätte die 101 in der 0-Zeile (da deren Benutzung am weitesten zurückliegt) gelöscht und 105 reingeschrieben

Zeilennummer

0: 101 (1) 105 (5)

1: 102 (2)

2: 103 (3)

3: 106 (4)

Und jetzt rufe ich die 106 (6) auf. Tue ich die dann in die am längsten nicht benutzte Zeile 1 rein oder muss ich wegen der 106 auf die 3-Zeile gehen? Danach kommt nochmal 105, schreibe ich die dann in die 0-Zeile, weil dort auch die 105 steht? Dann bleibt noch die 102 übrig, und die kommt in die 1-Zeile rein? Ich habe anfangs gedacht, dass ich die Tabelle nacheinander von oben wieder aufgefüllt wird, weil die Zeilen in der Reihenfolge zum ersten Mal benutzt wurden und dadurch das Verwendungsmuster sozusagen erhalten bleibt. Dummerweise hat dann mein Ergebnis nicht mit der Musterlösung übereingestimmt, weswegen ich hier an dieser Stelle lieber nochmal nachfrage, wie das mit dem Verfahren genau geht :)

Answer 1

> Bis zur 4. Zahl komme ich noch ohne Schwierigkeiten, danach bin ich mir aber unsicher, wie ich verfahren soll. Die fünfte Zahl ist 105, und ich hätte die 101 in der 0-Zeile (da deren Benutzung am weitesten zurückliegt) gelöscht und 105 reingeschrieben.

Stimmt.

> Und jetzt rufe ich die 106 (6) auf. Tue ich die dann in die am längsten nicht benutzte Zeile 1 rein oder muss ich wegen der 106 auf die 3-Zeile gehen?

Wenn die Daten von Adresse 106 schon im Cache stehen, dann muss man sie nicht nochmal reinschreiben. Also bliebe es bei 106 in der 3. Zeile, nur dass sich der Zeitpunkt der letzten Benutzung ändert.

> Danach kommt nochmal 105, schreibe ich die dann in die 0-Zeile, weil dort auch die 105 steht?

Genauso wie oben. Und ebenso für 102. Überschreiben müssen wir also nur, wenn ein neues Datum in den Cache geschrieben werden soll.


Viele Grüße

Lukas König