Algorytm pamięci podręcznej
Algorytm pamięci podręcznej to algorytm używany do zarządzania pamięcią podręczną lub grupą danych. Kiedy bufor jest pełny, decyduje, który element powinien zostać usunięty z bufora. Słowo wskaźnik trafień opisuje, jak często żądanie może być obsługiwane z pamięci podręcznej. Termin latencja opisuje jak długo można uzyskać zbuforowaną pozycję. Alorytmy buforowania są kompromisem pomiędzy wskaźnikiem trafień a opóźnieniem.
- Najbardziej efektywnym algorytmem buforowania byłoby zawsze odrzucanie informacji, które nie będą potrzebne przez najdłuższy czas w przyszłości. Ten optymalny wynik jest określany jako optymalny algorytm Belady'ego lub algorytm jasnowidzenia. Ponieważ na ogół niemożliwe jest przewidzenie, jak daleko w przyszłości będą potrzebne informacje, nie jest to możliwe do zrealizowania w praktyce. Praktyczne minimum można obliczyć dopiero po przeprowadzeniu eksperymentów, a skuteczność faktycznie wybranego algorytmu buforowego można porównać z optymalnym minimum.
- LRU (Least Recently Used): najpierw usuwa najmniej ostatnio używane elementy. Ten algorytm wymaga śledzenia tego, co zostało użyte, kiedy. Jest to kosztowne, jeśli chcemy mieć pewność, że algorytm zawsze wyrzuca ostatnio używany element. Ogólne implementacje tej techniki wymagają zachowania "bitów wiekowych" dla linii pamięci podręcznej i śledzenia "Najmniej ostatnio używanej" linii pamięci podręcznej opartej na bitach wiekowych. W takiej implementacji, za każdym razem, gdy używana jest linia podręczna, zmienia się wiek wszystkich innych linii podręcznych. LRU jest w rzeczywistości rodziną algorytmów buforowania, której członkami są między innymi: 2Q Theodore Johnson i Dennis Shasha oraz LRU/K Pata O'Neila, Betty O'Neil i Gerharda Weikuma.
- Ostatnio używany (MRU): Ten algorytm najpierw usuwa ostatnio używane elementy. Ten mechanizm buforowania jest powszechnie używany do buforowania pamięci baz danych.
- Pseudo-LRU (PLRU): Są pewne przypadki, w których LRU jest bardzo trudny do wdrożenia. W takich przypadkach może wystarczy wiedzieć, że w większości przypadków jeden z ostatnio używanych elementów jest usuwany. Algorytm PLRU może być tam wykorzystany, ponieważ do pracy potrzebuje tylko jeden bit na jeden element pamięci podręcznej.
- 2-drożny zestaw asocjacyjny: dla szybkich cache'ów CPU, gdzie nawet PLRU jest zbyt wolny. Adres nowego elementu jest używany do obliczenia jednej z dwóch możliwych lokalizacji w cache'u, do których można się dostać. LRU tych dwóch elementów jest odrzucany. Wymaga to jednego bitu na parę linii pamięci podręcznej, aby wskazać, która z nich była ostatnio używana.
- Direct-mapped cache: dla cache'ów CPU o najwyższej prędkości, gdzie nawet 2-drożne cache asocjacyjne są zbyt wolne. Adres nowej pozycji jest używany do obliczenia jednej lokalizacji w pamięci podręcznej, do której można się dostać. Cokolwiek było tam wcześniej, jest odrzucane.
- Najrzadziej używany (LFU): LFU liczy, jak często dana pozycja jest potrzebna. Te, które są używane rzadziej, są odrzucane jako pierwsze.
- Adaptive Replacement Cache (ARC): stale utrzymuje równowagę pomiędzy LRU i LFU, aby poprawić łączny wynik.
- Algorytm buforowania Multi Queue (MQ): (przez Y. Zhou J.F. Philbin i Kai Li).
Inne rzeczy do rozważenia:
- Pozycje o różnych kosztach: zachować pozycje, których uzyskanie jest kosztowne, np. te, których uzyskanie zajmuje dużo czasu.
- Rzeczy zajmujące więcej miejsca w skrytce: Jeśli przedmioty mają różne rozmiary, w pamięci podręcznej może być konieczne wyrzucenie dużego przedmiotu w celu przechowania kilku mniejszych.
- Przedmioty, które wygasają z czasem: Niektóre cache przechowują informacje, które wygasają (np. cache wiadomości, cache DNS, lub cache przeglądarki internetowej). Komputer może wyrzucić elementy, które wygasają wraz z upływem czasu. W zależności od wielkości pamięci podręcznej nie jest konieczny dalszy algorytm buforowania do odrzucania elementów.
Różne algorytmy istnieją również w celu utrzymania spójności pamięci podręcznej. Odnosi się to tylko do sytuacji, gdy wiele niezależnych pamięci podręcznych jest używanych dla tych samych danych (np. wiele serwerów baz danych aktualizujących jeden wspólny plik danych).
Które lokalizacje pamięci mogą być buforowane przez które lokalizacje pamięci podręcznej
Pytania i odpowiedzi
P: Co to jest Algorytm Cache?
O: Algorytm Cache to algorytm służący do zarządzania pamięcią podręczną lub grupą danych. Decyduje on, który element powinien zostać usunięty z pamięci podręcznej, gdy jest ona pełna.
P: Co to jest współczynnik trafień?
O: Współczynnik trafień opisuje, jak często żądanie może zostać obsłużone z cache.
P: Co to jest latencja?
A: Latencja opisuje, jak długo można uzyskać element z bufora.
P: Co to jest optymalny algorytm Belady'ego?
O: Optymalny algorytm Belady'ego, znany również jako algorytm jasnowidza, jest wydajnym algorytmem buforowania, który zawsze odrzuca informacje, które nie będą potrzebne przez najdłuższy czas w przyszłości. Tego wyniku nie da się na ogół zastosować w praktyce, ponieważ wymaga on przewidywania, co będzie potrzebne w dalekiej przyszłości.
P: Jak działa zasada LRU (Least Recently Used)?
O: LRU usuwa w pierwszej kolejności ostatnio używane elementy i wymaga śledzenia, co było używane kiedy, poprzez użycie "bitów wieku" dla każdej linii pamięci podręcznej i śledzenie, która z nich była ostatnio używana na podstawie bitów wieku. Za każdym razem, gdy linia pamięci podręcznej jest używana, wiek wszystkich innych linii pamięci podręcznej jest odpowiednio zmieniany.
P: Jak działa funkcja Most Recently Used (MRU)?
O: MRU usuwa w pierwszej kolejności ostatnio używane elementy i ten mechanizm buforowania jest powszechnie stosowany w pamięci podręcznej baz danych.
P: Jakie inne algorytmy istnieją, aby utrzymać spójność pamięci podręcznej?
O: Istnieją różne algorytmy utrzymywania spójności pamięci podręcznej, gdy wiele niezależnych pamięci podręcznych jest używanych dla wspólnych danych, takich jak wiele serwerów baz danych aktualizujących jeden wspólny plik danych.
