Cache-Algorithmus
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
(dt. Schreibregel) und
(dt. Ersetzungsregel). Der Begriff Cache-Algorithmus wird im Englischen aber in der Regel nur auf
bezogen. Bei der Betrachtung der Algorithmen unterscheidet man zudem zwischen
(angeforderte Daten liegen im Cache) und
(angeforderte Daten liegen nicht im Cache). Entsprechend heißen diese Situationen beim Lesen/Schreiben
und
.
Cache write policy
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)
Bei
ist normalerweise sichergestellt, dass die Daten im Cache und im dahinterliegenden Speicher (im Folgenden Hauptspeicher) gleich sind. Das wird dadurch erreicht, dass bei einem
die Daten sowohl in den Cache, als auch in den Hauptspeicher geladen werden. Bei einem Write Miss hängt es von der
ab, ob die Daten neben dem Hauptspeicher auch in den Cache geladen werden.
Rückschreibetechnik (write-back)
Bei
wird nicht direkt in den Hauptspeicher geschrieben, sondern dies geschieht erst, wenn der entsprechende Cache-Block ersetzt werden muss. Dies ist bei einem
oder bei einem
mit
(siehe
) 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.
ist zwar technisch anspruchsvoller, allerdings auch schneller als
.
Write-miss policy
Tritt ein
auf, so kommt eine
zum Einsatz.
Write allocate
Hier gelangen die zu schreibenden Daten direkt in den Cache. Sie werden aber auch in den Hauptspeicher geschrieben. Je nach Schreibtechnik (
,
) geschieht dies sofort oder bei Verdrängung der Cacheline.
No-write allocate (write around)
Die Daten werden nur in den Hauptspeicher geschrieben, ohne eine Cacheline zu belegen.
Cache replacement policy
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
– auch Cache-Algorithmus genannt – entscheiden, welche Cache-Blöcke verworfen werden und welche nicht. Ein Beispiel für eine
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
(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 (
, 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
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.
