Cache: mechanizmy zastępowania danych

Wiemy już, że nie wszystko z pamięci głównej zmieści się jednocześnie w pamięci cache, trzeba więc na jakiś zasadach wyrzucać stare dane z cache, aby zrobić miejsce na nowe. Można to zrobić na kilka sposobów:

MIN - czyli próbujemy przewidzieć, co nie będzie nam najdłużej potrzebne. Stosuje się do tego różne dziwne mechanizmy analizujące kod programu (zwłaszcza, jeśli kod programu też leży w cache) sprawdzające, do jakich miejsc w pamięci będziemy się w najbliższym czasie odwoływać. Oczywiście, można łatwo zmylić takie algorytmy poprzez np. rozgałęzienia w programie.

LRU - czego najdłużej nie używaliśmy. Dość oczywiste, problem polega jednak na tym, że jeśli używamy w kółko np. 10 danych, a w cache jest miejsce na 9, to po pewnym czasie cały czas będziemy mieli chybienia.

FIFO - Co pierwsze zostało załadowane, to pierwsze zostanie usunięte. Problem pojawia się, jeśli np. dużo operujemy na jednej danej z pamięci, a potem obrabiamy inne, korzystając z informacji z tej jednej. Wtedy po chwili zostanie ona wywalona z cache i będzie trzeba ponownie po nią sięgać do pamięci.

Random - jak sama nazwa wskazuje. Wbrew pozorom, nie jest to metoda najgorsza! Tego nie było na wykładzie, ale warto zauważyć, że nie wymaga przechowywania jakichkolwiek informacji o tym, kiedy linia została wrzucona do cache bądź kiedy była ostatnio używana, oraz nie wymaga żadnego systemu przewidującego!

Na slajdzie Cache - nominacje, Rada Wyspy (2) można zerknąć sobie, jak dane zostają wrzucane do cache i jak z niej wylatują. Po chwili przyglądania się i analizowania rysunków nabierają one sensu.

Na dole slajdów są zdjęcia z różnych reality show dlatego, że te mechanizmy kojarzą się dr. Mazurkiewiczowi z różnego rodzaju metodami eliminacji uczestników w owych programach.

Mamy rozwiązane odczytywanie z pamięci za pośrednictwem cache, ale co z zapisywaniem? Oczywiście, sam procesor nie pisze bezpośrednio do pamięci, ale do cache, a następnie cache synchronizuje się z pamięcią główną. Może to robić na trzy sposoby:

• Zawsze, gdy coś jest zapisane do cache, to jest zapisywane również do pamięci głównej. Plus jest taki, że dane na pewno nie zginą, bo są w obu miejscach jednocześnie. Minusem jest powolność.
• Gdy linia jest usuwana z cache, to jest zapisywana w pamięci głównej.
• Gdy linia jest usuwana z cache, to jest zapisywana w pamięci głównej pod warunkiem, że została zmodyfikowana podczas pobytu w cache. To jest przemyślane - ponieważ jeśli nie została zmodyfikowana, to nadpisywalibyśmy w pamięci głównej te same dane na te same dane.