Beládyho algoritmedit
nejúčinnějším algoritmem ukládání do mezipaměti by bylo vždy zahodit informace,které nebudou v budoucnu potřeba nejdéle. Tento optimální výsledek je označován jako Bélád ‚ s optimal algorithm / simply optimal replacement policy nebo jasnovidný algoritmus. Vzhledem k tomu, že je obecně nemožné předpovědět, jak daleko budou v budoucnu potřebné informace, není to v praxi obecně implementovatelné. Praktické minimum lze vypočítat až po experimentování a lze porovnat účinnost skutečně zvoleného algoritmu mezipaměti.
v okamžiku, kdy dojde k chybě stránky, je některá sada stránek v paměti. V příkladu je sekvence ‚5‘, ‚0‘, ‚1‘ je přístupný rámem 1, rámem 2, rámem 3. Poté, když je přístup „2“, nahrazuje hodnotu „5“, která je v rámci 1, protože předpovídá, že hodnota “ 5 “ nebude v blízké budoucnosti přístupná. Protože operační systém pro všeobecné použití v reálném životě nemůže ve skutečnosti předpovědět, kdy bude přístup k ‚5‘, Béládyho algoritmus nemůže být v takovém systému implementován.
First in first out (FIFO)Edit
pomocí tohoto algoritmu se mezipaměť chová stejným způsobem jako fronta FIFO. Cache vyloučí bloky v pořadí, v jakém byly přidány, bez ohledu na to, jak často nebo kolikrát byly přístupné předtím.
Last in first out (LIFO) nebo First in last out (FILO)Edit
pomocí tohoto algoritmu se mezipaměť chová stejným způsobem jako zásobník a přesně opačným způsobem jako fronta FIFO. Mezipaměť vystěhuje blok přidaný Naposledy jako první bez ohledu na to, jak často nebo kolikrát byl dříve přístupný.
Least recently used (LRU)Edit
zahodí nejdříve naposledy použité položky. Tento algoritmus vyžaduje sledování toho, co bylo použito, když, což je drahé, pokud se chcete ujistit, že algoritmus vždy zahodí nejméně nedávno použitou položku. Obecné implementace této techniky vyžadují zachování „věkových bitů“ pro řádky mezipaměti a sledování“ nejméně Nedávno použité “ řádky mezipaměti na základě věkových bitů. Při takové implementaci se při každém použití řádku mezipaměti změní věk všech ostatních řádků mezipaměti. LRU je vlastně rodina ukládání do mezipaměti algoritmů s členy včetně 2Q Theodore Johnson a Shasha Dennis, a LRU/K Pat O ‚neil, Betty O‘ neil a Gerhard Weikum.
přístupová sekvence pro níže uvedený příklad je B C D E D F.
Ve výše uvedeném příkladu, jakmile A B C D se instaluje do bloků s pořadová čísla (Přírůstek 1 pro každý nový Přístup) a až E je přístupná, to je slečna, a to musí být nainstalován v jednom z bloků. Podle algoritmu LRU, protože A má nejnižší hodnost (a (0)), e nahradí a.
ve druhém posledním kroku je D přístupný, a proto je pořadové číslo Aktualizováno.
LRU, stejně jako mnoho jiných náhradních politiky, může být charakterizována pomocí přechodu stavu pole ve vektorovém prostoru, který rozhoduje o dynamické mezipaměti změny stavu podobné, jak elektromagnetické pole určuje pohyb nabitých částic v něm umístěny.
Čas vědom nejméně naposledy použité (TLRU)Upravit
Čas vědom Nejméně naposledy Použité (TLRU) je varianta LRU určen pro situace, kde je uložen obsah v mezipaměti platný čas života. Algoritmus je vhodný v aplikacích síťové mezipaměti, jako jsou sítě zaměřené na informace (ICN), sítě pro doručování obsahu (CDN) a distribuované sítě obecně. Tlru zavádí nový termín: TTU (čas k použití). TTU je časové razítko obsahu / stránky, které stanoví dobu použitelnosti obsahu na základě lokality obsahu a oznámení vydavatele obsahu. Díky tomuto časovému razítku založenému na lokalitě poskytuje TTU větší kontrolu místnímu správci při regulaci síťového úložiště.V algoritmu TLRU, když přijde část obsahu, uzel mezipaměti vypočítá místní hodnotu TTU na základě hodnoty TTU přiřazené vydavatelem obsahu. Lokální hodnota TTU se vypočítá pomocí lokálně definované funkce. Jakmile se vypočítá lokální hodnota TTU, provede se nahrazení obsahu na podmnožině celkového obsahu uloženého v uzlu mezipaměti. Tlru zajišťuje, že méně populární a malý obsah života by měl být nahrazen příchozím obsahem.
naposledy použité (MRU)úpravy
zahodí, na rozdíl od LRU, naposledy použité položky jako první. V nálezy prezentovány na 11. VLDB konference, Chou a DeWitt poznamenal, že „Když je soubor opakovaně snímán v referenční vzor, MRU je nejlepší náhrada algoritmus.“Následně, další vědci představí na 22. VLDB konferenci poznamenal, že pro náhodný přístup vzorů a opakované skeny přes velké soubory dat (někdy známou jako cyklický přístup vzory) MRU mezipaměti algoritmy mají více hitů než LRU vzhledem k jejich tendenci zachovat starší data. Algoritmy MRU jsou nejužitečnější v situacích, kdy je položka starší, tím je pravděpodobnější, že bude přístupná.
přístupová sekvence pro níže uvedený příklad je B C D E C D B.
zde se b C D umístí do mezipaměti, protože je stále k dispozici místo. Na 5. přístup E, vidíme, že blok, který držel D, je nyní nahrazen E, protože tento blok byl použit Naposledy. Další přístup k C a při dalším přístupu k D, C je nahrazen, protože to byl blok přístupný těsně před D a tak dále.
Pseudo-LRU (PLRU)Edit
Pro CPU cache s velkými asociativita (obecně >4 způsoby), náklady na implementaci LRU stává prohibitivní. V mnoha mezipaměti CPU postačuje schéma, které téměř vždy zahodí jednu z nejméně nedávno používaných položek, takže mnoho návrhářů CPU si vybere algoritmus PLRU, který potřebuje pouze jeden bit na položku mezipaměti.PLRU má obvykle o něco horší miss poměr, má o něco lepší latenci, používá o něco méně energie než LRU a nižší režijní náklady ve srovnání s LRU.
následující příklad ukazuje, jak bity fungují jako binární strom 1-bitových ukazatelů, které ukazují na méně nedávno použitý podstrom. Po řetězci ukazatele k uzlu listu identifikuje náhradního kandidáta. Při přístupu jsou všechny ukazatele v řetězci od uzlu listu přístupové cesty k kořenovému uzlu nastaveny tak, aby ukazovaly na podstrom, který neobsahuje přístupovou cestu.
přístupová sekvence je B C D E.
princip je zde jednoduchý, pokud se podíváme pouze na ukazatele šipek. Pokud existuje přístup k hodnotě, řekněte “ A “ a nemůžeme ji najít v mezipaměti, načteme ji z paměti a umístíme ji do bloku, kde šipky právě směřují, a to shora dolů. Poté, co jsme umístili tento blok, otočíme stejné šipky tak, aby ukazovaly opačným směrem. Ve výše uvedeném příkladu vidíme, jak bylo umístěno „A“, následované „B“, „C A „D“. Pak jako cache se stal plně “ E „nahrazuje“ A „protože to je tam, kde šipky směřovaly na to čas, a šipky, které vedly k“ A “ byly obráceně v opačném směru. Šipky pak vedly k ‚B‘, což bude blok nahrazen na další cache chybět.
Random replacement (RR)Edit
náhodně vybere kandidátskou položku a v případě potřeby ji zahodí, aby se vytvořil prostor. Tento algoritmus nevyžaduje uchovávání informací o historii přístupu. Pro svou jednoduchost byl použit v procesorech ARM. Připouští efektivní stochastickou simulaci.
přístup sekvence pro níže uvedený příklad je A B C D E B D F
Segmentované LRU (SLRU)Upravit
SLRU cache je rozdělena do dvou segmentů, zkušební segmentu a chráněné segmentu. Linky v každém segmentu jsou seřazeny od nejvíce po nejméně nedávno přístupné. Data z chyb jsou přidána do mezipaměti na Naposledy přístupném konci zkušebního segmentu. Zásahy jsou odstraněny z místa, kde se v současné době nacházejí, a přidány do Naposledy přístupného konce chráněného segmentu. Linky v chráněném segmentu tak byly zpřístupněny nejméně dvakrát. Chráněné segmentu je omezená, takže migrace linky od zkušební segmentu chráněné segmentu může donutit migrace LRU-line v chráněné segmentu na naposledy použité (MRU) konec zkušební segmentu, což tento řádek další šanci být přístupné předtím, než je nahrazen. Limit velikosti chráněného segmentu je parametr SLRU, který se mění podle vzorců pracovního zatížení I/O. Kdykoli musí být data vyřazena z mezipaměti, řádky jsou získány z konce LRU zkušebního segmentu.
nejméně často používané (LFU)úpravy
počítá, jak často je položka potřebná. Ty, které se používají nejméně často, jsou nejprve vyřazeny. Funguje to velmi podobně jako u LRU s tím rozdílem, že místo ukládání hodnoty toho, jak nedávno byl přístup k bloku, ukládáme hodnotu toho, kolikrát byl přístup. Takže samozřejmě při spuštění přístupové sekvence nahradíme blok, který byl použit nejméně krát z naší mezipaměti. Např., pokud byl A použit (přístupný) 5krát a B byl použit 3krát a další C A D byly použity 10krát, nahradíme B.
nejméně časté nedávno používané (LFRU)editace
nejméně časté nedávno používané (LFRU) schéma nahrazení mezipaměti kombinuje výhody schémat LFU a LRU. LFRU je vhodný pro ‚v síti‘ mezipaměť aplikací, jako jsou Informace-centric networking (ICN), Content Delivery Networks (Cdn) a distribuovány sítí obecně. V LFRU je mezipaměť rozdělena na dva oddíly nazvané privilegované a neprivilegované oddíly. Privilegovaný oddíl lze definovat jako chráněný oddíl. Pokud je obsah velmi populární, je zasunut do privilegovaného oddílu. Náhradní privilegované oddílu se provádí takto: LFRU vyloučí obsah z neprivilegované oddíl, tlačí obsah z privilegovaných oddíl k neoprávněnému rozdělení, a konečně vloží nový obsah do privilegované oddíl. Ve výše uvedeném postupu HŽP se používá pro privilegované rozdělení a přibližný LFU (ALFU) režim se používá pro neprivilegované oddíl, odtud zkratka LFRU.
Základní myšlenkou je odfiltrovat lokálně populární obsah pomocí schématu ALFU a posunout populární obsah do jednoho z privilegovaných oddílů.
Lfu s dynamickým stárnutím (LFUDA)editovat
varianta s názvem LFU s dynamickým stárnutím (LFUDA), který používá dynamické stárnutí přizpůsobit posuny v sadě populárních objektů. Přidává Faktor věku mezipaměti k počtu referencí, když je do mezipaměti přidán nový objekt nebo když je existující objekt znovu odkazován. LFUDA zvyšuje věk mezipaměti při vystěhování bloků nastavením na hodnotu klíče vystěhovaného objektu. Věk mezipaměti je tedy vždy menší nebo roven minimální hodnotě klíče v mezipaměti. Předpokládejme, že když byl objekt v minulosti často přístupný a nyní se stává nepopulárním, zůstane v mezipaměti po dlouhou dobu, čímž zabrání jeho nahrazení nově nebo méně populárními objekty. Toto dynamické stárnutí je tedy zavedeno, aby se snížil počet takových objektů, čímž se stanou způsobilými k nahrazení. Výhodou LFUDA je, že snižuje znečištění mezipaměti způsobené LFU, když jsou velikosti mezipaměti velmi malé. Pokud jsou velikosti mezipaměti velké, stačí několik rozhodnutí o výměně a znečištění mezipaměti nebude problém.
Nízká inter-referenční data set (LIRS)Upravit
LIRS je nahrazovací algoritmus s lepší výkon než HŽP, a mnoho dalších novější algoritmy výměny. Toho je dosaženo použitím reuse distance jako metriky pro dynamicky řazené přístupné stránky k provedení náhradního rozhodnutí. LIRS účinně řešit limity LRU pomocí aktuálnost hodnotit Inter-Referenční Aktuálnost (IRR) pro výrobu náhradního rozhodnutí.
na výše uvedeném obrázku „x“ představuje, že blok je přístupný v čase t. Předpokládejme, že pokud je blok A1 přístupný v čase 1, pak se recence stane 0, protože se jedná o první přístupný blok a IRR bude 1, protože předpovídá, že A1 bude znovu přístupný v čase 3. V době 2 od přístupu A4 se recence stane 0 pro A4 a 1 pro A1, protože A4 je Naposledy přístupný objekt a IRR se stane 4 a bude pokračovat. V čase 10 bude mít algoritmus lir dvě sady lir set = {A1, A2} a hir set = {A3, A4, A5}. Nyní v čase 10, pokud je přístup k A4, dojde k chybě. Algoritmus LIRS nyní vystěhuje A5 místo A2 kvůli své největší aktuálnosti.
CLOCK-PROEDIT
LRU algoritmus nemůže být přímo implementován v kritické cestě počítačových systémů, jako jsou operační systémy, kvůli jeho vysoké režii. Pro implementaci se běžně používá aproximace LRU, tzv. hodiny. Podobně, CLOCK-Pro je aproximace lir pro nízkonákladovou implementaci v systémech. CLOCK-Pro je v rámci základní hodiny, ale má tři hlavní odlišné zásluhy. Za prvé, CLOCK-Pro má tři “ hodinové ručičky „na rozdíl od jednoduché struktury hodin, kde se používá pouze jedna“ ruka“. Se třemi rukama je CLOCK-Pro schopen měřit vzdálenost opětovného použití přístupů k datům přibližným způsobem. Za druhé jsou zachovány všechny zásluhy lir, jako je rychlé vystěhování jednorázových přístupových a / nebo nízkých datových položek lokality. Zatřetí, složitost CLOCK-Pro je stejná jako u CLOCK, a proto je snadné jej implementovat za nízkou cenu. Implementace vyrovnávací paměti vyrovnávací paměti v aktuální verzi Linuxu je kombinací LRU a CLOCK-Pro.
Adaptive replacement cache (ARC)Edit
neustále vyvažuje mezi LRU a LFU, aby se zlepšil kombinovaný výsledek. ARC zlepšuje na SLRU pomocí informace o nedávno vypuzen cache položky dynamicky nastavit velikost chráněného segmentu a zkušební segmentu, aby se co nejlépe využít dostupný prostor mezipaměti. Adaptivní náhradní algoritmus je vysvětlen na příkladu.
AdaptiveClimb (AC)Upravit
Používá nedávný hit/miss upravit skok, kde ve stoupání některý hit přepínače pozice jeden slot na vrchol, a v LRU hit přepínače v poloze hit na vrchol. Tedy těžit z optimality stoupání, když je program v pevném rozsahu, a rychlého přizpůsobení novému rozsahu, jak to dělá LRU. Podporujte také sdílení mezipaměti mezi jádry uvolněním doplňků, pokud jsou odkazy na horní část mezipaměti.
Hodiny s adaptivní náhradní (AUTO)Upravit
Kombinuje výhody Adaptive Replacement Cache (ARC) a HODINY. Auto má výkon srovnatelný s obloukem a podstatně překonává LRU i hodiny. Stejně jako ARC, auto je samoladící a nevyžaduje žádné uživatelem zadané magické parametry. Používá 4 dvojitě propojené seznamy: dvě hodiny T1 a T2 a dva jednoduché seznamy LRU B1 A B2. Hodiny T1 ukládají stránky založené na“ aktuálnosti „nebo“ krátkodobém nástroji“, zatímco T2 ukládá stránky s „frekvencí“ nebo „dlouhodobým nástrojem“. T1 a T2 obsahují stránky, které jsou v mezipaměti, zatímco B1 a B2 obsahují stránky, které byly nedávno vystěhovány z T1 a T2. Algoritmus se snaží zachovat velikost těchto seznamů B1≈T2 A B2≈T1. Nové stránky se vkládají do T1 nebo T2. Pokud dojde k zásahu ve velikosti B1 T1, zvýší se a podobně, pokud dojde k zásahu ve velikosti B2 T1 se sníží. Použité adaptační pravidlo má stejný princip jako v ARC, investujte více do seznamů, které při přidání více stránek poskytnou více zásahů.
Multi queue (MQ)Edit
algoritmus multi queue nebo mq byl vyvinut pro zlepšení výkonu vyrovnávací paměti druhé úrovně pro např. vyrovnávací paměť serveru. Je představen v článku Zhou, Philbin, a Li. mezipaměť MQ obsahuje počet front LRU m: Q0, Q1, …, Qm-1. Zde hodnota m představuje hierarchii založenou na životnosti všech bloků v dané frontě. Například pokud j>i, bloky v Qj budou mít delší životnost než bloky v Qi. Kromě toho existuje další historie vyrovnávací paměti Qout, fronta, která udržuje seznam všech identifikátorů bloku spolu s jejich přístupovými frekvencemi. Když je Qout plný, nejstarší identifikátor je vystěhován. Bloky zůstat v LRU front pro danou životnost, která je definována dynamicky MQ algoritmus maximální časová vzdálenost mezi dvěma přístupy do stejného souboru, nebo počet vyrovnávací paměti bloků podle toho, která hodnota je větší. Pokud blok nebyl během své životnosti odkazován, je degradován z Qi na Qi−1 nebo vystěhován z mezipaměti, pokud je v Q0. Každá fronta má také maximální počet přístupů; pokud je blok ve frontě Qi přístupný více než 2i krát, je tento blok povýšen na Qi+1, dokud není přístupný více než 2i+1 krát nebo jeho životnost vyprší. V rámci dané fronty, bloky jsou řazeny podle aktuálnosti přístupu, podle LRU.
vidíme z obr. jak jsou fronty m LRU umístěny do mezipaměti. Viz také z obr. jak qout ukládá identifikátory bloků a jejich odpovídající přístupové frekvence. a byl umístěn v Q0, protože byl přístupný pouze jednou nedávno, a můžeme zkontrolovat v Qout, jak byly b A c umístěny v Q1 a Q2, protože jejich přístupové frekvence jsou 2 a 4. Fronta, ve které je blok umístěn, je závislá na přístupové frekvenci (f) jako log2 (f). Když je vyrovnávací paměť plná, první blok bude vystěhován bude hlava Q0 v tomto případě. Pokud je přístupná, ještě jednou se to bude pohybovat na Q1 níže b.
Koš: Kontejner na ukládání do mezipaměti algoritmus pro sloučeniny objectsEdit
Koš je kontejner na bázi flash ukládání do mezipaměti mechanismus, který identifikuje rozdílné (heterogenní) kontejnery, kde bloky v něm obsažené mají velmi různý přístup vzorů. Pannier používá strukturu fronty přežití založenou na prioritních frontách k hodnocení kontejnerů na základě jejich doby přežití, což je úměrné živým datům v kontejneru. Pannier je postaven na základě segmentovaného LRU (S2LRU), který odděluje teplá a studená data. Pannier také používá vícestupňový regulátor zpětné vazby k škrticí klapce flash zapisuje, aby byla zajištěna životnost blesku.