Cache-Algorithmus

Vorlage:Hinweisbaustein 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 {{#invoke:Vorlage:lang|flat}} (dt. Schreibregel) und {{#invoke:Vorlage:lang|flat}} (dt. Ersetzungsregel). Der Begriff Cache-Algorithmus wird im Englischen aber in der Regel nur auf {{#invoke:Vorlage:lang|flat}} bezogen.

Bei der Betrachtung der Algorithmen unterscheidet man zudem zwischen {{#invoke:Vorlage:lang|flat}} (angeforderte Daten liegen im Cache) und {{#invoke:Vorlage:lang|flat}} (angeforderte Daten liegen nicht im Cache). Entsprechend heißen diese Situationen beim Lesen/Schreiben {{#invoke:Vorlage:lang|flat}} und {{#invoke:Vorlage:lang|flat}}.

Cache write policy

Datei:Cache Fill.svg

Verschiedene cache placement policies (hier nicht beschrieben)

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 ({{#invoke:Vorlage:lang|flat}})

Bei {{#invoke:Vorlage:lang|flat}} ist normalerweise sichergestellt, dass die Daten im Cache und im dahinterliegenden Speicher (im Folgenden Hauptspeicher) gleich sind. Das wird dadurch erreicht, dass bei einem {{#invoke:Vorlage:lang|flat}} die Daten sowohl in den Cache als auch in den Hauptspeicher geladen werden. Bei einem Write Miss hängt es von der {{#invoke:Vorlage:lang|flat}} ab, ob die Daten neben dem Hauptspeicher auch in den Cache geladen werden.

Rückschreibetechnik ({{#invoke:Vorlage:lang|flat}})

Bei {{#invoke:Vorlage:lang|flat}} wird nicht direkt in den Hauptspeicher geschrieben, sondern dies geschieht erst, wenn der entsprechende Cache-Block ersetzt werden muss. Dies ist bei einem {{#invoke:Vorlage:lang|flat}} oder bei einem {{#invoke:Vorlage:lang|flat}} mit {{#invoke:Vorlage:lang|flat}} (siehe {{#invoke:Vorlage:lang|flat}}) 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.

{{#invoke:Vorlage:lang|flat}} ist zwar technisch anspruchsvoller, allerdings auch schneller als {{#invoke:Vorlage:lang|flat}}.

Tritt ein {{#invoke:Vorlage:lang|flat}} auf, so kommt eine {{#invoke:Vorlage:lang|flat}} zum Einsatz.

Hier gelangen die zu schreibenden Daten direkt in den Cache. Sie werden aber auch in den Hauptspeicher geschrieben. Je nach Schreibtechnik ({{#invoke:Vorlage:lang|flat}}, {{#invoke:Vorlage:lang|flat}}) geschieht dies sofort oder bei Verdrängung der Cacheline.

{{#invoke:Vorlage:lang|flat}} ({{#invoke:Vorlage:lang|flat}})

Die Daten werden nur in den Hauptspeicher geschrieben, ohne eine Cacheline zu belegen.

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 {{#invoke:Vorlage:lang|flat}} – auch Cache-Algorithmus genannt – entscheiden, welche Cache-Blöcke verworfen werden und welche nicht.

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.