algorytm Bélády ’ ego
najskuteczniejszym algorytmem buforowania byłoby zawsze odrzucanie informacji, które nie będą potrzebne przez dłuższy czas w przyszłości. Ten optymalny wynik jest określany jako algorytm optymalny Bélády’ego / po prostu optymalna Polityka zastępowania lub algorytm jasnowidzenia. Ponieważ zazwyczaj nie można przewidzieć, jak daleko w przyszłości informacje będą potrzebne, nie jest to na ogół możliwe do wdrożenia w praktyce. Praktyczne minimum można obliczyć dopiero po eksperymentach i można porównać skuteczność faktycznie wybranego algorytmu cache.
w momencie wystąpienia błędu strony, niektóre zbiory stron są w pamięci. W przykładzie Sekwencja '5′, '0′, '1′ jest dostępny odpowiednio przez klatkę 1, klatkę 2, klatkę 3. Następnie, gdy’ 2 'jest dostępne, zastępuje wartość’ 5′, która znajduje się w klatce 1, ponieważ przewiduje, że wartość’ 5 ’ nie będzie dostępna w najbliższej przyszłości. Ponieważ rzeczywisty system operacyjny ogólnego przeznaczenia nie jest w stanie przewidzieć, kiedy ” 5 ” będzie dostępne, algorytm Bélády 'ego nie może być zaimplementowany na takim systemie.
First in first out (FIFO)Edytuj
używając tego algorytmu cache zachowuje się tak samo jak Kolejka FIFO. Pamięć podręczna usuwa bloki w kolejności, w jakiej zostały dodane, bez względu na to, jak często lub ile razy były dostępne wcześniej.
Last in first out (LIFO) lub First in last out (FILO)Edytuj
używając tego algorytmu cache zachowuje się w taki sam sposób jak stos i dokładnie odwrotnie jak Kolejka FIFO. Pamięć podręczna najpierw usuwa blok dodany Ostatnio, bez względu na to, jak często i ile razy był wcześniej dostępny.
ostatnio używane (LRU)Edycja
najpierw usuwa ostatnio używane elementy. Ten algorytm wymaga śledzenia tego, co było używane kiedy, co jest drogie, jeśli chce się upewnić, że algorytm zawsze odrzuca najmniej ostatnio używany element. Ogólne implementacje tej techniki wymagają zachowania ” bitów wieku „dla linii pamięci podręcznej i śledzenia” najmniej ostatnio używanych ” linii pamięci podręcznej na podstawie bitów wieku. W takiej implementacji, za każdym razem, gdy używana jest linia pamięci podręcznej, zmienia się Wiek wszystkich innych linii pamięci podręcznej. LRU jest właściwie rodziną algorytmów buforujących z członkami, w tym 2Q przez Theodore Johnson i Dennis Shasha, i LRU/K przez Pat O 'Neil, Betty O’ neil i Gerhard Weikum.
Sekwencja dostępu dla poniższego przykładu to B C D E D F.
w powyższym przykładzie, gdy B C D zostanie zainstalowany w blokach z numerami sekwencji (przyrost 1 dla każdego nowego dostępu) i gdy dostęp do E jest uzyskany, jest to miss I musi być zainstalowany w jednym z bloków. Zgodnie z algorytmem LRU, ponieważ A Ma najniższą rangę (a (0)), E zastąpi A.
w drugim ostatnim kroku D jest dostępny i dlatego numer sekwencji jest aktualizowany.
LRU, podobnie jak wiele innych polityk zastępczych, można scharakteryzować za pomocą pola przejściowego stanu w przestrzeni wektorowej, które decyduje o dynamicznych zmianach stanu pamięci podręcznej, podobnie jak pole elektromagnetyczne determinuje ruch umieszczonej w nim naładowanej cząstki.
time aware Least recently used (TLRU)Edytuj
Time aware Least Recently Used (TLRU) jest wariantem LRU przeznaczonym do sytuacji, gdy zawartość przechowywana w pamięci podręcznej ma prawidłowy czas życia. Algorytm jest odpowiedni w aplikacjach pamięci podręcznej sieci, takich jak Information-centric networking (ICN), Content Delivery Networks (CDNs) i ogólnie w sieciach rozproszonych. TLRU wprowadza nowy termin: TTU (Time To Use). TTU jest znacznikiem czasowym treści / strony, który określa czas użyteczności treści w oparciu o lokalizację treści i ogłoszenie wydawcy treści. Ze względu na ten znacznik czasu oparty na lokalizacji, TTU zapewnia większą kontrolę lokalnemu administratorowi w celu regulacji w pamięci sieciowej.W algorytmie TLRU, gdy pojawia się fragment zawartości, węzeł pamięci podręcznej oblicza lokalną wartość TTU na podstawie wartości TTU przypisanej przez wydawcę zawartości. Lokalna wartość TTU jest obliczana przy użyciu lokalnie zdefiniowanej funkcji. Po obliczeniu lokalnej wartości TTU wymiana zawartości jest wykonywana na podzbiorze całkowitej zawartości przechowywanej w węźle pamięci podręcznej. TLRU zapewnia, że mniej popularne i małe treści life powinny być zastąpione przychodzącymi treściami.
ostatnio używane (Mru)Edytuj
odrzucenia, w przeciwieństwie do LRU, ostatnio używane pozycje jako pierwsze. W ustaleniach przedstawionych na 11.konferencji VLDB Chou i DeWitt zauważyli, że „gdy plik jest wielokrotnie skanowany we wzorze referencyjnym, MRU jest najlepszym algorytmem zastępczym.”Następnie inni badacze prezentujący na 22. konferencji VLDB zauważyli, że w przypadku wzorców dostępu losowego i powtarzanych skanów nad dużymi zbiorami danych (czasami znanych jako cykliczne wzorce dostępu) algorytmy pamięci podręcznej MRU mają więcej trafień niż LRU ze względu na tendencję do zatrzymywania starszych danych. Algorytmy MRU są najbardziej przydatne w sytuacjach, w których im starszy element jest, tym bardziej prawdopodobne jest uzyskanie do niego dostępu.
Sekwencja dostępu dla poniższego przykładu to B C D E C D B.
tutaj, B C D są umieszczane w pamięci podręcznej, ponieważ jest jeszcze wolne miejsce. Na piątym dostępie e widzimy, że blok, który posiadał D, jest teraz zastąpiony E, ponieważ ten blok był ostatnio używany. Kolejny dostęp do C i przy następnym dostępie do D, C jest zastępowany, ponieważ był blokiem dostępnym tuż przed D i tak dalej.
Pseudo-LRU (PLRU)Edycja
dla pamięci podręcznych PROCESORA z dużą asocjacyjnością (ogólnie > 4 sposoby), koszt implementacji LRU staje się wygórowany. W wielu buforach procesora, schemat, który prawie zawsze odrzuca jeden z najmniej ostatnio używanych elementów, jest wystarczający, więc wielu projektantów procesorów wybiera algorytm PLRU, który do działania potrzebuje tylko jednego bitu na element pamięci podręcznej.PLRU zazwyczaj ma nieco gorszy współczynnik miss, ma nieco lepsze opóźnienie, zużywa nieco mniej mocy niż LRU i niższe koszty ogólne w porównaniu do LRU.
poniższy przykład pokazuje, jak bity działają jako binarne drzewo 1-bitowych wskaźników, które wskazują na mniej ostatnio używane poddrzewo. Podążając za łańcuchem wskaźników do węzła liści identyfikuje kandydata zastępczego. Po uzyskaniu dostępu wszystkie wskaźniki w łańcuchu od węzła leaf, do węzła root, są ustawione na wskazywanie podzbioru, który nie zawiera drogi, do której uzyskano dostęp.
Sekwencja dostępu to B C D E.
zasada tutaj jest prosta do zrozumienia, jeśli spojrzymy tylko na wskaźniki strzałek. Gdy jest dostęp do wartości, powiedzmy „a”, a nie możemy jej znaleźć w pamięci podręcznej, to ładujemy ją z pamięci i umieszczamy w bloku, w którym są aktualnie skierowane strzałki, przechodząc od góry do dołu. Po umieszczeniu tego bloku odwracamy te same strzałki, aby wskazywały w przeciwną stronę. W powyższym przykładzie widzimy, jak umieszczono 'a’, a następnie’ B’, 'C i’D’. Następnie, gdy pamięć podręczna stała się pełna ” E ” zastąpiła „a”, ponieważ to tam strzałki wskazywały w tym czasie, a strzałki, które prowadziły do „a”, zostały odwrócone, aby wskazać w przeciwnym kierunku. Strzałki następnie doprowadziły do 'B’, który będzie blok zastąpiony na następnym miss cache.
Random replacement (RR)Edytuj
losowo wybiera kandydat i odrzuca go, aby zrobić miejsce w razie potrzeby. Algorytm ten nie wymaga przechowywania żadnych informacji o historii dostępu. Ze względu na swoją prostotę został użyty w procesorach ARM. Pozwala na skuteczną symulację stochastyczną.
Sekwencja dostępu w poniższym przykładzie to B C D E B D F
Segmented LRU (SLRU)Edit
pamięć podręczna SLRU jest podzielona na dwa segmenty, segment próbny i segment chroniony. Linie w każdym segmencie są uporządkowane od najbardziej do najmniej ostatnio dostępnych. Dane z pudeł są dodawane do pamięci podręcznej na ostatnim końcu segmentu próbnego. Odsłony są usuwane z miejsca, w którym obecnie SIĘ ZNAJDUJĄ, i dodawane do ostatnio dostępnego końca segmentu chronionego. Linie w chronionym segmencie były zatem dostępne co najmniej dwa razy. Segment chroniony jest skończony, więc migracja linii z segmentu próbnego do segmentu chronionego może wymusić migrację linii LRU w segmencie chronionym do ostatnio używanego (MRU) końca segmentu próbnego, dając tej linii kolejną szansę na dostęp przed wymianą. Limit rozmiaru chronionego segmentu jest parametrem SLRU, który zmienia się w zależności od wzorców obciążenia We/Wy. Ilekroć dane muszą zostać usunięte z pamięci podręcznej, linie są uzyskiwane z końca LRU segmentu próbnego.
Least-frequently used (LFU)Edytuj
oblicza, jak często element jest potrzebny. Te, które są używane najmniej często, są najpierw odrzucane. Działa to bardzo podobnie do LRU z tą różnicą, że zamiast zapisywać wartość tego, jak ostatnio blok został uzyskany, przechowujemy wartość, ile razy został uzyskany. Tak więc oczywiście podczas uruchamiania sekwencji dostępu zastąpimy blok, który był używany najmniej razy z naszej pamięci podręcznej. Na przykład, jeśli A było używane (dostępne) 5 razy, a b było używane 3 razy, a inne C i D były używane po 10 razy, zastąpimy B.
najmniej częste ostatnio używane (lfru)Edytuj
schemat wymiany pamięci podręcznej najmniej częste ostatnio używane (Lfru) łączy zalety schematów LFU i LRU. LFRU nadaje się do aplikacji pamięci podręcznej „w sieci”, takich jak sieci zorientowane na informacje (ICN), sieci dostarczania treści (CDN) i ogólnie sieci rozproszone. W LFRU pamięć podręczna jest podzielona na dwie partycje o nazwie privileged i unprivileged partitions. Partycja uprzywilejowana może być zdefiniowana jako partycja chroniona. Jeśli treść jest bardzo popularna, jest pchana do partycji uprzywilejowanej. Wymiana partycji uprzywilejowanej odbywa się w następujący sposób: LFRU usuwa zawartość z partycji nieuprzywilejowanej, wypycha zawartość z partycji uprzywilejowanej do partycji nieuprzywilejowanej, a na koniec wstawia nową zawartość do partycji uprzywilejowanej. W powyższej procedurze LRU jest używany dla partycji uprzywilejowanej, a przybliżony schemat LFU (ALFU) jest używany dla partycji nieuprzywilejowanej, stąd Skrót LFRU.
podstawową ideą jest filtrowanie popularnej zawartości za pomocą schematu ALFU i wypychanie popularnej zawartości na jedną z uprzywilejowanych partycji.
LFU z dynamicznym starzeniem (lfuda)Edytuj
wariant o nazwie LFU z dynamicznym starzeniem (Lfuda), który wykorzystuje dynamiczne starzenie do dostosowania zmian w zestawie popularnych obiektów. Dodaje współczynnik wieku pamięci podręcznej do liczby odniesień, gdy nowy obiekt jest dodawany do pamięci podręcznej lub gdy istniejący obiekt jest ponownie odwoływany. LFUDA zwiększa wiek pamięci podręcznej podczas eksmitowania bloków, ustawiając ją na wartość klucza obiektu eksmitowanego. Tak więc wiek pamięci podręcznej jest zawsze mniejszy lub równy minimalnej wartości klucza w pamięci podręcznej. Załóżmy, że gdy obiekt był często dostępny w przeszłości, a teraz staje się niepopularny, pozostanie w pamięci podręcznej przez długi czas, zapobiegając tym samym zastąpieniu go przez nowo lub mniej popularne obiekty. Tak więc to dynamiczne starzenie się jest wprowadzane w celu zmniejszenia liczby takich obiektów, co czyni je kwalifikującymi się do wymiany. Zaletą LFUDA jest to, że zmniejsza zanieczyszczenie pamięci podręcznej spowodowane przez LFU, gdy rozmiary pamięci podręcznej są bardzo małe. Gdy rozmiary pamięci podręcznej są duże, niewiele decyzji dotyczących wymiany jest wystarczających i zanieczyszczenie pamięci podręcznej nie będzie problemem.
Low inter-reference recency set (LIRS)Edit
LIRS jest algorytmem wymiany strony o ulepszonej wydajności w stosunku do LRU i wielu innych nowszych algorytmów wymiany. Osiąga się to poprzez wykorzystanie odległości ponownego użycia jako wskaźnika dynamicznego rankingu stron, do których uzyskano dostęp, w celu podjęcia decyzji o zastąpieniu. LIRS skutecznie rozwiązuje granice LRU, wykorzystując recencję do oceny Recencji międzyludzkiej (IRR) w celu podjęcia decyzji o zastąpieniu.
na powyższym rysunku, „x” oznacza, że blok jest dostępny w czasie t. Załóżmy, że jeśli blok A1 jest dostępny w czasie 1, to aktualność będzie równa 0, ponieważ jest to pierwszy blok, do którego uzyskano dostęp, A IRR będzie równe 1, ponieważ przewiduje, że A1 będzie ponownie dostępne w czasie 3. W czasie 2 od uzyskania dostępu do A4, aktualność wyniesie 0 dla A4 i 1 dla A1, ponieważ A4 jest Ostatnio dostępnym obiektem, a IRR stanie się 4 i będzie działać dalej. W czasie 10 algorytm LIRS będzie miał dwa zestawy lir set = {A1, A2} i HIR set = {A3, A4, A5}. Teraz w czasie 10, jeśli jest dostęp do A4, miss występuje. Algorytm LIRS będzie teraz eksmitował A5 zamiast A2 ze względu na jego największą aktualność.
CLOCK-proedit
algorytm LRU nie może być bezpośrednio zaimplementowany w krytycznej ścieżce systemów komputerowych, takich jak systemy operacyjne, ze względu na wysokie koszty. Do implementacji powszechnie używane jest przybliżenie LRU, zwane zegarem. Podobnie CLOCK-Pro jest przybliżeniem LIRS dla niskiego kosztu wdrożenia w systemach. CLOCK-Pro jest pod podstawowym RAM zegara, ale ma trzy główne zalety. Po pierwsze, CLOCK-Pro ma trzy ” wskazówki zegara „w przeciwieństwie do prostej struktury zegara, w której używana jest tylko jedna” ręka”. Za pomocą trzech rąk CLOCK-Pro jest w stanie w przybliżeniu zmierzyć odległość ponownego wykorzystania danych. Po drugie, wszystkie zalety LIRS są zachowane, takie jak szybkie eksmisje jednorazowego dostępu i/lub niskie pozycje danych o lokalizacji. Po trzecie, złożoność CLOCK-Pro jest taka sama jak CLOCK, dzięki czemu jest łatwy do wdrożenia przy niskich kosztach. Implementacja wymiany bufora w obecnej wersji Linuksa jest połączeniem LRU i CLOCK-Pro.
Adaptive replacement cache (ARC)Edit
stale balansuje między LRU i LFU, aby poprawić łączny wynik. ARC ulepsza SLRU, używając informacji o ostatnio usuniętych elementach pamięci podręcznej, aby dynamicznie dostosować rozmiar chronionego segmentu i segmentu próbnego, aby jak najlepiej wykorzystać dostępną przestrzeń pamięci podręcznej. Algorytm adaptacyjnego zastępowania jest wyjaśniony na przykładzie.
AdaptiveClimb (AC)Edit
wykorzystuje ostatnie trafienie / chybienie do regulacji skoku, gdzie w climb każde trafienie przełącza pozycję o jedno miejsce na górę, a w LRU hit przełącza pozycję trafienia na górę. W ten sposób, korzystając z optymalności wznoszenia, gdy program znajduje się w stałym zakresie, i szybkiej adaptacji do nowego zakresu, tak jak robi to LRU. Obsługuje również współdzielenie pamięci podręcznej między rdzeniami, zwalniając Dodatki, gdy odniesienia są do górnej części pamięci podręcznej.
Zegar Z Adaptive replacement (CAR)Edit
łączy zalety Adaptive Replacement Cache (ARC) i zegara. Samochód ma osiągi porównywalne z łukiem i znacznie przewyższa zarówno LRU, jak i zegar. Podobnie jak ARC, samochód jest samoistny i nie wymaga żadnych magicznych parametrów określonych przez użytkownika. Wykorzystuje 4 podwójnie połączone listy: dwa zegary T1 i T2 oraz dwie proste listy LRU B1 i B2. Zegar T1 przechowuje strony oparte na „recency” lub „short term utility”, podczas gdy T2 przechowuje strony z” frequency „lub”long term utility”. T1 i T2 zawierają te strony, które znajdują się w pamięci podręcznej, podczas gdy B1 i B2 zawierają strony, które zostały niedawno usunięte odpowiednio z T1 i T2. Algorytm stara się utrzymać rozmiar tych list B1≈T2 i B2≈T1. Nowe strony są wstawiane W T1 lub T2. Jeśli jest trafienie w B1 rozmiar T1 jest zwiększany i podobnie jeśli jest trafienie w B2 rozmiar T1 jest zmniejszany. Zastosowana reguła adaptacji ma taką samą zasadę jak w ARC, inwestuj więcej w listy, które dadzą więcej odsłon, gdy więcej stron zostanie dodanych do niej.
Multi queue (mq)Edit
algorytm multi queue lub mq został opracowany w celu poprawy wydajności bufora drugiego poziomu np. bufora bufora serwera. Został wprowadzony w artykule przez Zhou, Philbina i Li. pamięć podręczna MQ Zawiera m liczby kolejek LRU: Q0, Q1, …, Qm-1. Tutaj wartość m reprezentuje hierarchię opartą na żywotności wszystkich bloków w danej kolejce. Na przykład, jeśli j>i, bloki w Qj będą miały dłuższą żywotność niż te w Qi. Oprócz nich istnieje inny bufor historii Qout, kolejka, która utrzymuje listę wszystkich identyfikatorów bloków wraz z ich częstotliwościami dostępu. Gdy qout jest pełny, najstarszy identyfikator jest eksmitowany. Bloki pozostają w kolejkach LRU przez dany okres życia, który jest dynamicznie definiowany przez algorytm mq jako maksymalna odległość czasowa między dwoma dostępami do tego samego pliku lub liczba bloków pamięci podręcznej, w zależności od tego, która z tych wartości jest większa. Jeśli blok nie został odwołany w ciągu swojego życia, jest on zdegradowany z Qi do Qi−1 lub eksmitowany z pamięci podręcznej, jeśli znajduje się w Q0. Każda kolejka ma również maksymalną liczbę dostępu; jeśli blok w kolejce Qi jest dostępny więcej niż 2i razy, blok ten jest promowany do Qi+1, dopóki nie będzie dostępny więcej niż 2i+1 razy lub jego żywotność wygaśnie. W ramach danej kolejki bloki są klasyfikowane według aktualności dostępu, zgodnie z LRU.
widać z Rys. jak kolejki m LRU są umieszczane w pamięci podręcznej. Zobacz też z Rys. jak Qout przechowuje identyfikatory bloków i odpowiadające im częstotliwości dostępu. a został umieszczony w Q0, ponieważ dostęp do niego był ostatnio tylko raz i możemy sprawdzić w Qout, jak B i c zostały umieszczone odpowiednio w Q1 i Q2, ponieważ ich częstotliwości dostępu wynoszą 2 i 4. Kolejka, w której blok jest umieszczony, jest zależna od częstotliwości dostępu(f) jako log2(f). Gdy bufor jest pełny, pierwszym blokiem, który zostanie eksmitowany, będzie szef Q0 W tym przypadku a. jeśli dostęp do a zostanie uzyskany jeszcze raz, przeniesie się do Q1 poniżej b.
Pannier: algorytm buforowania obiektów złożonych oparty na Kontenerachedytuj
Pannier to oparty na kontenerach mechanizm buforowania flash, który identyfikuje rozbieżne (heterogeniczne) kontenery, w których przechowywane w nich bloki mają bardzo różne wzorce dostępu. Pannier używa struktury kolejki przetrwania opartej na kolejce priorytetowej, aby uszeregować kontenery na podstawie ich czasu przetrwania, który jest proporcjonalny do danych aktywnych w kontenerze. Pannier zbudowany jest w oparciu o segmentowane LRU (S2LRU), które segreguje gorące i zimne dane. Pannier wykorzystuje również wieloetapowy kontroler sprzężenia zwrotnego do dławienia zapisów flash, aby zapewnić trwałość lampy błyskowej.