Cache-Algorithmus

Grundidee und zentrale Begriffe

Ein Cache-Algorithmus steuert einen Cache, um Speicherzugriffe zwischen CPU und Arbeitsspeicher zu optimieren und Inkonsistenzprobleme zu verhindern. Caches werden außerdem in Software eingesetzt; die beschriebenen Cache-Algorithmen gelten dort entsprechend.

Man unterscheidet zwei Aufgabenbereiche: Die cache write policy (Schreibregel) legt fest, wie Schreibvorgänge zwischen Cache und Hauptspeicher ausgeführt werden. Die cache replacement policy (Ersetzungsregel) entscheidet, welche Daten aus dem Cache entfernt werden. Im Englischen bezeichnet „Cache-Algorithmus“ meist nur die replacement policy.

Ein Cache Hit liegt vor, wenn die angeforderten Daten im Cache vorhanden sind. Bei einem Cache Miss fehlen sie dort. Beim Lesen spricht man entsprechend von Read Hit und Read Miss, beim Schreiben von Write Hit und Write Miss. Ein Cache-Block, auch Cacheline genannt, ist die kleinste Verwaltungseinheit des Caches.

Schreibregeln für Cache und Hauptspeicher

Die folgenden Schreibverfahren werden in der Regel in Rechnerarchitekturen mit einem Prozessor eingesetzt. Bei I/O-Operationen kann es jedoch zu Inkonsistenzen kommen.

Bei der Durchschreibetechnik (write-through) bleiben die Daten im Cache und im dahinterliegenden Hauptspeicher normalerweise gleich. Bei einem Write Hit werden die Daten deshalb sowohl in den Cache als auch in den Hauptspeicher geschrieben. Bei einem Write Miss hängt es von der Write-miss policy ab, ob die Daten zusätzlich zum Hauptspeicher auch in den Cache geladen werden.

Bei der Rückschreibetechnik (write-back) wird zunächst nicht direkt in den Hauptspeicher geschrieben. Die Übertragung erfolgt erst, wenn der betreffende Cache-Block ersetzt werden muss. Dies kann bei einem Read Miss oder bei einem Write Miss mit write allocate geschehen. Ein Dirty-Bit zeigt an, dass die Daten im Hauptspeicher und im Cache inkonsistent sind; ist es gesetzt, stehen die aktuellen Daten noch nicht im Hauptspeicher.

Zum Abgleich werden die mit Dirty-Bit markierten Cachelines einzeln in den Hauptspeicher geschrieben. Alternativ kann ein FLUSH ausgeführt werden, bei dem der gesamte Cache in den Hauptspeicher geschrieben wird. Write-back ist technisch anspruchsvoller, aber schneller als write-through.

Verhalten bei einem Write Miss

Bei einem Write Miss wird eine Write-miss policy angewendet. Sie bestimmt, ob die zu schreibenden Daten eine Cacheline belegen.

Bei Write allocate gelangen die zu schreibenden Daten direkt in den Cache. Sie werden außerdem in den Hauptspeicher geschrieben. Abhängig von der verwendeten Schreibtechnik geschieht dies bei write-through sofort, bei write-back dagegen erst bei der Verdrängung der Cacheline.

Bei No-write allocate, auch write around genannt, werden die Daten ausschließlich in den Hauptspeicher geschrieben. Sie belegen keine Cacheline.

Ersetzungsregel und Multiprozessorsysteme

Beim Lesen und Schreiben muss häufig eine Cacheline ersetzt werden, weil der Cache voll ist. Die Cache replacement policy, die ebenfalls Cache-Algorithmus genannt wird, entscheidet dann, welche Cache-Blöcke verworfen und welche beibehalten werden.

In Multiprozessorsystemen besitzt üblicherweise jeder Prozessor einen eigenen Cache und greift darüber auf einen zentralen gemeinsamen Speicher zu. Dadurch können die Inhalte der einzelnen Caches untereinander sowie gegenüber dem Hauptspeicher voneinander abweichen. Ein Cache-Algorithmus muss deshalb für Cache-Kohärenz sorgen, also Inkonsistenzen zwischen den Caches und dem Hauptspeicher verhindern.