Najbardziej wydajny algorytm zastępowania pamięci podręcznej [zamknięty]

Wikipedia wymienia 11 algorytmów zastępowania pamięci podręcznej . Zakładając, że nie wiem prawie nic o aplikacji, którą zamierzam opracować, co powinienem zastosować jako „domyślny” algorytm zastępowania pamięci podręcznej?

Jeśli dobrze pamiętam z kursu OS, LRU jest najlepszym ogólnym algorytmem zastępowania pamięci podręcznej. Ale może się mylę.

Jest to również pytanie akademickie, ponieważ ogólnie pamięć główna jest tania i obfita i naprawdę nie muszę się zbytnio przejmować wielkością pamięci podręcznej.

Myślę, że najlepszą odpowiedzią jest to, że to zależy. Z mojego doświadczenia wynika, że ​​wybór algorytmów buforowania wiąże się z wieloma czynnikami.

Czynniki do rozważenia

1. Bilans odczytu / zapisu. (Jaki procent dostępu jest odczytany lub zapisany)
2. Ilość pamięci podręcznej.
3. Rodzaj nośnika znajdującego się za pamięcią podręczną. (Czy są to wolne dyski SATA czy szybkie dyski SSD?)
4. Trafienia kontra chybienia. (Jak często są przepisywane lub ponownie czytane?)
5. Średni rozmiar dostępu (służy do wyboru rozmiaru strony)
6. Jak drogie są odczyty i zapisy.

Po rozważeniu wszystkich różnych czynników musisz znaleźć algorytm pamięci podręcznej, który najlepiej sobie z tym poradzi. Powiedzmy na przykład, że masz aplikację, w której jest dużo zapisów, niektóre zapisy, odczyty ostatnio zapisanych danych i jakiś rodzaj spinningu. W takim przypadku potrzebujesz pewnego rodzaju hybrydowego algorytmu buforowania. Aby obsłużyć zapis danych, możesz potrzebować czegoś w rodzaju mądrej kolejności zapisów (WOW) i algorytmu LRU dla danych odczytanych z dysku. Powodem tego jest to, że dostęp do dysku jest bardzo kosztowny, a algorytm WOW sprawi, że zapisywanie danych będzie bardziej wydajne, a LRU będzie przechowywać często używane dane zawsze w pamięci podręcznej.

Załóżmy, że masz dyski SSD o bardzo krótkim czasie dostępu, więc możesz zdecydować się na algorytm LRU, ponieważ dostęp do dysku jest stosunkowo niedrogi.

Tak naprawdę chcę powiedzieć, że nie ma „najlepszej” odpowiedzi. Najlepszą odpowiedzią jest poznanie czynników, które Cię dotyczą, i wybranie algorytmu, który najlepiej je obsługuje.

Jak znaleźć algorytm dla siebie

Profiluj swój system. Zwykle wymaga to dodania kodu w celu prowadzenia statystyk dostępu do pamięci. Profilując możesz zobaczyć, które czynniki są dla Ciebie najważniejsze.

W przeszłości dodawałem kod do śledzenia wszystkich dostępów do pamięci przez pewien okres czasu. Potem szukam wzorów. Szukam ponownego odczytu, ponownego zapisu, dostępu sekwencyjnego, dostępu losowego itp.

Po zidentyfikowaniu ważnych elementów należy przyjrzeć się różnym typom algorytmów buforowania, aby zobaczyć, które z nich są najlepsze.

Zakładając, że nie wiesz prawie nic o aplikacji, którą zamierzasz opracować, powinieneś wiedzieć o niej więcej przed faktycznym wyborem i wdrożeniem systemu pamięci podręcznej. Innymi słowy, nie ma domyślnych implementacji: niektóre są dobre dla niektórych celów, a dla innych zupełnie złe .

Na przykład weźmy tylko dwie implementacje: najmniej używana i najmniej używana. Jak zdecydować, którego użyć przed drugim?

• LRU jest dobry, gdy masz pewność, że użytkownik będzie częściej uzyskiwał dostęp do najnowszych elementów i nigdy nie rzadziej wraca do starych. Przykład: ogólne użycie klienta poczty e-mail. W większości przypadków użytkownicy stale uzyskują dostęp do najnowszych wiadomości e-mail. Czytają je, odkładają, wracają za kilka minut, godzin lub dni itp. Mogą znaleźć się w poszukiwaniu wiadomości, którą otrzymali dwa lata temu, ale zdarza się to rzadziej niż dostęp do wiadomości, które otrzymali w ciągu ostatnich dwóch godzin.

• Z drugiej strony LRU nie ma sensu w kontekście, w którym użytkownik będzie uzyskiwał dostęp do niektórych elementów znacznie częściej niż inne. Przykład: często słucham muzyki, którą lubię i może się zdarzyć, że na 400 utworach słuchałbym tych samych pięciu co najmniej raz w tygodniu, podczas gdy będę słuchał co najwyżej raz w roku 100 utworów, których też nie lubię dużo. W takim przypadku LFU jest znacznie bardziej odpowiednie.

Biorąc tylko dwie implementacje, widzisz, że nie ma „domyślnego” algorytmu, którego można użyć, gdy nie chcesz myśleć o tym, który z nich jest lepszy lub nie masz wystarczającej ilości informacji o aplikacji. To tak, jakby pytać, czy domyślnie musisz dodać, odjąć, pomnożyć lub podzielić dwie liczby, aby znaleźć wynik rachunku różniczkowego, gdy nic o tym nie wiesz.

Dlaczego ograniczać swoje wybory tylko do Wikipedii? Jeśli masz dostęp do bazy danych badań, takich jak Biblioteka Cyfrowa ACM , znajdziesz jeszcze więcej algorytmów. Bądź również świadomy zamieszania w patentach. Na przykład ARC jest dobrym algorytmem, ale niestety jest opatentowany.

Możesz spędzić dużo czasu na agonowaniu nad „najlepszym” algorytmem lub możesz po prostu wdrożyć prosty algorytm i ROZPOCZNIĆ RESZTĘ SYSTEMU. Kiedy masz coś sprawdzalne czym martwić algorytmu.

Przedwczesna optymalizacja ...

Nie ma idealnego algorytmu pamięci podręcznej - zawsze możesz znaleźć przypadek, który zachowuje się bardzo źle.

Dlatego ważne jest, aby znać problem buforowany, aby określić ten, który będzie się zachowywał jak najgorzej.

Ponadto, należy wziąć pod uwagę, jak długo trzeba na rzeczy cache i jak długo mogą buforować rzeczy ...