Cache-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.

Ursprünglich galt der Cache als ein Zwischenpuffer zwischen CPU und Hauptspeicher. Da deren Taktfrequenzen immer mehr voneinander abwichen, wurde es nötig einen Puffer (Cache) einzuführen. Man erkannte aber früh, dass man mit dem Cache einen beträchtlichen Teil der Bandbreite des Speicher-Bus sparen kann.

Dazu werden die Daten nicht direkt in den Speicher geschrieben sondern in den Cache. Die Methode nennt sich Rückschreibetechnik (engl. write-back,copy-back oder store-in). Wird ein Block im Cache überschrieben, findet allerdings auch ein Schreiben in den Hauptspeicher statt. Wird ein Block im Cache verfehlt (write-miss), wird er zuerst in den Cache kopiert. Dann wird entweder nur in den Cache geschrieben (write-allocate) oder direkt in den übergeordneten Hauptspeicher (no-write-allocate).

Diese Methode wird in der Regel in Rechnerarchitekturen mit einem Prozessor eingesetzt. Allerdings kann es hier zu Inkonsistenzen bei I/O-Operationen kommen.

Multiprozessorsysteme[Bearbeiten]

Verschiedene Cache-Algorithmen

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, sorgt ein Cache-Algorithmus für Cache-Kohärenz.

Durchschreibetechnik (write-through, write-thru)[Bearbeiten]

Es wird am Cache vorbei in den Hauptspeicher geschrieben. Die Cacheline verliert dabei ihre Gültigkeit. Daher folgt beim nächsten Lesen aus der Cacheline ein cache-miss.

Rückschreibetechnik (write-back)[Bearbeiten]

Die Daten werden in den Cache zurückgeschrieben und das Dirty-Bit (= Daten im Hauptspeicher und Cache sind inkonsistent) wird gesetzt. Der Abgleich mit dem Hauptspeicher kann durch ein FLUSH ausgelöst werden. Außerdem werden die Daten in den Hauptspeicher zurückgeschrieben, wenn die Cacheline für andere Daten verwendet werden soll.

Diese Technik ist zwar aufwändiger, allerdings auch schneller als write through.

Write-allocate[Bearbeiten]

Tritt beim Schreiben ein cache-miss auf, so kommt write-allocate zum Zug. Dabei werden die Daten direkt an den Hauptspeicher durchgeschrieben. Der Cache-Controller sorgt anschließend dafür, dass die eben geschriebenen Daten in den Cache nachgeladen werden.