Least-Recently-Used - LRU

Gegeben sei folgende Liste von Cache-Einträgen in einem Cache, dessen Größe 65536 Bytes betrage. Die 6 vorhanden Cache-Einträge füllen den Cache-Speicher fast vollständig aus.

Eintrags-Nr.	Letzte Verwendung	Größe in Bytes	Zugriffe
1	19.01.2001, 7:53 Uhr	10.000	24
2	19.01.2001, 7:47 Uhr	4.000	16
3	19.01.2001, 4:42 Uhr	21.000	28
4	19.01.2001, 7:30 Uhr	8.000	2
5	19.01.2001, 6:02 Uhr	15.000	20
6	19.01.2001, 7:42 Uhr	5.000	10
63.000 (96%)			100

Mit der nächsten Anfrage an das System ist ein neues Datum zu cachen, dessen Größe mit 7.000 Bytes den verfügbaren, freien Speicherplatz überschreitet. Der LRU Algorithmus ermittelt Eintrag 3 zur Löschung und Ersetzung. Damit wird der in der Vergangenheit am häufigsten verwendete und größe Eintrag verdrängt. Steht die Größe in linearer Korrelation mit den Kosten der Eintragserzeugung und/oder handelt es sich nur um eine kurzes Desinteresse an Eintrag 3, so wurde eine Fehlentscheidung getroffen.

Eintrags-Nr.	Letzte Verwendung	Größe in Bytes	Zugriffe
1	19.01.2001, 7:53 Uhr	10.000	24
2	19.01.2001, 7:47 Uhr	4.000	16
7	19.01.2001, 7:59 Uhr	7.000	1
4	19.01.2001, 7:30 Uhr	8.000	2
5	19.01.2001, 6:02 Uhr	15.000	20
6	19.01.2001, 7:42 Uhr	5.000	10
49.000 (65%)			73

Die Ersetzung hat die Ausnutzung des Cache-Speichers von sehr guten 96% auf 65% gesenkt. Handelt es sich beim Speichermedium um Hauptspeicher, so droht bereits nach wenigen Operationen eine hohe Fragmentierung, die zu zusätzlichen CPU Kosten führt. Die folgende Tabelle deutet die Fragmentierung an, nachdem Eintrag 5 aufgrund eines neuen, 17.000 Bytes großen Eintrags verdrängt wurde. Da der neue Eintrag 8 nicht vollständig in die Lücke von 5 paßt, wird 8 gesplittet abgelegt. Fragmentierung ist nicht nur an LRU gebunden.

1 0-10

2 0-4

7 0-7

8.1 0-15

4 0-8

8.2 16-17

-%-

6 0-5