Ein Cache-Algorithmus ist ein Algorithmus zur Steuerung eines Cache, mit dem Speicherzugriffe zwischen einer CPU und dem Arbeitsspeicher optimiert und Inkonsistenzprobleme verhindert werden sollen. Caches im weiteren Sinne werden aber auch in Software verwendet, wo die Cache-Algorithmen entsprechend gelten.
Es wird unterschieden zwischen cache write policy (dt. Schreibregel) und cache replacement policy (dt. Ersetzungsregel). Der Begriff Cache-Algorithmus wird im Englischen aber in der Regel nur auf replacement policy bezogen.
Bei der Betrachtung der Algorithmen unterscheidet man zudem zwischen Cache Hit (angeforderte Daten liegen im Cache) und Cache Miss (angeforderte Daten liegen nicht im Cache). Entsprechend heißen diese Situationen beim Lesen/Schreiben Write Hit/Read Hit und Write Miss/Read Miss.
Cache write policy Bearbeiten
Die folgenden Methoden werden in der Regel in Rechnerarchitekturen mit einem Prozessor eingesetzt. Allerdings kann es hier zu Inkonsistenzen bei I/O-Operationen kommen. Der Cache-Block (auch Cacheline genannt) ist die kleinste Verwaltungseinheit innerhalb des Caches.
Durchschreibetechnik (write-through) Bearbeiten
Bei write-through ist normalerweise sichergestellt, dass die Daten im Cache und im dahinterliegenden Speicher (im Folgenden Hauptspeicher) gleich sind. Das wird dadurch erreicht, dass bei einem Write Hit die Daten sowohl in den Cache, als auch in den Hauptspeicher geladen werden. Bei einem Write Miss hängt es von der Write-miss policy ab, ob die Daten neben dem Hauptspeicher auch in den Cache geladen werden.
Rückschreibetechnik (write-back) Bearbeiten
Bei write-back wird nicht direkt in den Hauptspeicher geschrieben, sondern dies geschieht erst, wenn der entsprechende Cache-Block ersetzt werden muss. Dies ist bei einem Read Miss oder bei einem Write Miss mit write allocate (siehe Write-miss policy) der Fall.
Um zu erfassen, welche Daten mit dem Hauptspeicher übereinstimmen und welche nicht, wird das Dirty-Bit (= Daten im Hauptspeicher und Cache sind inkonsistent) gesetzt. Wenn das Dirty-Bit gesetzt ist, heißt das, dass die Daten noch nicht im Hauptspeicher stehen.
Der Abgleich mit dem Hauptspeicher erfolgt, indem mit dem Dirty-Bit markierte Cachelines individuell in den Hauptspeicher geschrieben werden. Alternativ geschieht dies durch einen FLUSH, bei dem der gesamte Cache in den Hauptspeicher geschrieben wird.
Write-back ist zwar technisch anspruchsvoller, allerdings auch schneller als write through.
Write-miss policy Bearbeiten
Tritt ein Write Miss auf, so kommt eine Write-miss policy zum Einsatz.
Write allocate Bearbeiten
Hier gelangen die zu schreibenden Daten direkt in den Cache. Sie werden aber auch in den Hauptspeicher geschrieben. Je nach Schreibtechnik (write-through, write-back) geschieht dies sofort oder bei Verdrängung der Cacheline.
No-write allocate (write around) Bearbeiten
Die Daten werden nur in den Hauptspeicher geschrieben, ohne eine Cacheline zu belegen.
Cache replacement policy Bearbeiten
Beim Lesen und beim Schreiben kommt es häufig vor, dass ein Cacheline ersetzt werden muss, weil der Cache voll ist. In diesem Fall muss die Cache replacement policy – auch Cache-Algorithmus genannt – entscheiden, welche Cache-Blöcke verworfen werden und welche nicht.
Ein Beispiel für eine replacement policy wäre es, die am längsten nicht genutzten Daten aus dem Cache zu entfernen, wenn Platz für neue Daten benötigt wird, siehe Least recently used (LRU). Eine andere Möglichkeit ist es, nur die am häufigsten gelesenen Daten im Cache zu behalten bzw. die am wenigsten genutzten zu löschen (Least frequently used, LFU). Weiterhin können einfach die ältesten Einträge gelöscht werden (FIFO) oder die Eintrage werden zufällig gelöscht. Andere Strategien sind CLOCK oder Optimal (nach Laszlo Belady).
Multiprozessorsysteme Bearbeiten
Bei Multiprozessorsystemen hat üblicherweise jeder Prozessor seinen eigenen Cache und greift darüber auf einen zentralen, gemeinsamen Speicher zu. Um Probleme durch Inkonsistenzen zwischen den Caches und dem Hauptspeicher zu verhindern, muss dann ein Cache-Algorithmus für Cache-Kohärenz sorgen.