B blokklánc a cache algoritmusa
a leghatékonyabb gyorsítótárazási algoritmus az lenne, ha mindig eldobnánk azokat az információkat, amelyekre a jövőben a leghosszabb ideig nem lesz szükség. Erre az optimális eredményre hivatkozunk B. A. C. A. C. A. C. optimális algoritmusa / egyszerűen optimális helyettesítési politika vagy a tisztánlátó algoritmus. Mivel általában lehetetlen megjósolni, hogy a jövőben milyen információkra lesz szükség, ez általában nem valósítható meg a gyakorlatban. A gyakorlati minimumot csak kísérletezés után lehet kiszámítani, és össze lehet hasonlítani a ténylegesen kiválasztott gyorsítótár algoritmus hatékonyságát.
abban a pillanatban, amikor egy oldal hiba lép fel, néhány oldalkészlet a memóriában van. A példában a ‘5’, ‘0’, ‘1’ az 1., 2., 3. képkockával érhető el. Ezután a ‘2’ elérésekor az ‘5’ értéket helyettesíti, amely az 1.keretben van, mivel azt jósolja, hogy az ‘ 5 ‘ értéket a közeljövőben nem fogják elérni. Mert az igazi élet általános célú operációs rendszer nem tudja igazából megjósolni, mikor az ” 5 ” lesz elérhető, Bélády az Algoritmus nem lehet végrehajtani egy ilyen rendszer.
First in first out (FIFO)Szerkesztés
ezzel az algoritmussal a gyorsítótár ugyanúgy viselkedik, mint egy FIFO sor. A gyorsítótár kilakoltatja a blokkokat a hozzáadásuk sorrendjében, tekintet nélkül arra, hogy milyen gyakran vagy hányszor jutottak hozzá korábban.
Last in first out (LIFO) vagy First in last out (FILO)Szerkesztés
ezzel az algoritmussal a gyorsítótár ugyanúgy viselkedik, mint egy verem, és pontosan ellentétes módon, mint egy FIFO sor. A gyorsítótár kilakoltatja a legutóbb hozzáadott blokkot, tekintet nélkül arra, hogy milyen gyakran vagy hányszor használták korábban.
legkevésbé használt (LRU)Szerkesztés
először a legkevésbé használt elemeket dobja ki. Ez az algoritmus megköveteli annak nyomon követését, hogy mikor használták, ami drága, ha meg akarjuk győződni arról, hogy az algoritmus mindig eldobja a legkevésbé használt elemet. Ennek a technikának az általános megvalósítása megköveteli az “age bitek” megtartását a gyorsítótár-sorokhoz, és a “legkevésbé használt” gyorsítótár-vonal nyomon követését az age-bitek alapján. Egy ilyen megvalósításban minden gyorsítótár-sor használatakor az összes többi gyorsítótár-sor kora megváltozik. Az LRU valójában egy gyorsítótárazási algoritmuscsalád, amelynek tagjai: Theodore Johnson és Dennis Shasha 2Q, valamint Pat O ‘Neil, Betty O’ Neil és Gerhard Weikum LRU/K.
az alábbi példa hozzáférési sorrendje A B C D E D F.
a fenti példában egyszer egy B C D lesz telepítve a blokkokat sorszámmal (növekmény 1 minden új hozzáférés), és amikor E érhető el, ez egy miss, és meg kell telepíteni az egyik blokk. Az LRU algoritmus szerint, mivel A a legalacsonyabb rangú (a(0)), E helyettesíti A.
a második utolsó lépésben d érhető el, ezért a sorszám frissül.
az LRU, mint sok más helyettesítési házirend, jellemezhető egy vektortér állapotátmeneti mezőjével, amely úgy dönt, hogy a dinamikus gyorsítótár állapotváltozása hasonló ahhoz, ahogyan egy elektromágneses mező meghatározza a benne elhelyezett töltött részecske mozgását.
Time aware Last recently used (Tlru)Szerkesztés
A Time aware lastly Recently Used (Tlru) az LRU egy olyan változata, amelyet arra a helyzetre terveztek, amikor a gyorsítótárban tárolt tartalom érvényes élettartammal rendelkezik. Az algoritmus alkalmas hálózati gyorsítótár alkalmazásokban, például Információközpontú hálózatokban (ICN), tartalomszolgáltató hálózatokban (CDN) és általában elosztott hálózatokban. A TLRU új kifejezést vezet be: TTU (ideje használni). A TTU egy tartalom/oldal időbélyegzője, amely meghatározza a tartalom használhatóságának idejét a Tartalom helye és a tartalom kiadójának bejelentése alapján. Ennek a helységen alapuló időbélyegzőnek köszönhetően a TTU nagyobb ellenőrzést biztosít a helyi rendszergazdának a hálózati tárolás szabályozásához.A TLRU algoritmusban, amikor egy tartalom megérkezik, a gyorsítótár-csomópont kiszámítja a helyi TTU értéket a tartalomszolgáltató által hozzárendelt TTU érték alapján. A helyi TTU értéket egy helyileg definiált függvény segítségével számítják ki. A helyi TTU érték kiszámítása után a tartalom cseréje a gyorsítótár csomópontban tárolt teljes tartalom egy részhalmazán történik. A TLRU biztosítja, hogy a kevésbé népszerű és kis élettartamú tartalmakat a bejövő tartalommal helyettesítsék.
legutóbb használt (MRU)Szerkesztés
eldobja, ellentétben az LRU-val, először a legutóbb használt elemeket. A 11. VLDB konferencián bemutatott eredményekben Chou és Dewitt megjegyezte, hogy “amikor egy fájlt ismételten beolvasnak egy referenciamintában, az MRU a legjobb helyettesítő algoritmus.”Ezt követően a 22. VLDB konferencián bemutatott más kutatók megjegyezték, hogy a véletlen hozzáférési minták és a nagy adatkészletek (más néven ciklikus hozzáférési minták) ismételt vizsgálata során az MRU gyorsítótár algoritmusainak több találata van, mint az LRU-nak, mivel hajlamosak a régebbi adatok megőrzésére. Az MRU algoritmusok a leghasznosabbak olyan helyzetekben, amikor minél régebbi egy elem, annál valószínűbb, hogy hozzáférnek hozzá.
az alábbi példa hozzáférési sorrendje A B C D E C D B.
itt egy B C D kerül a gyorsítótárba, mivel még van szabad hely. Az 5. hozzáférésnél E, látjuk, hogy a D-t tartó blokkot most E váltja fel, mivel ezt a blokkot Legutóbb használták. Egy másik hozzáférés A C-hez, a következő hozzáférés A D-hez, A C helyébe lép, mivel ez volt a blokk, amelyet közvetlenül a D előtt értek el, és így tovább.
Pseudo-LRU (PLRU)Szerkesztés
nagy asszociativitású CPU gyorsítótárak esetén (általában >4 módon) az LRU megvalósítási költsége megfizethetetlenné válik. Sok CPU gyorsítótárban elegendő egy olyan séma, amely szinte mindig eldobja a legkevésbé használt elemek egyikét, ezért sok CPU-tervező olyan PLRU algoritmust választ, amelynek működéséhez gyorsítótár-elemenként csak egy bitre van szükség.A PLRU-nak általában valamivel rosszabb a kihagyási aránya, kissé jobb a késleltetése, valamivel kevesebb energiát használ, mint az LRU, és alacsonyabb az általános költségek az LRU-hoz képest.
a következő példa azt mutatja be, hogy a bitek hogyan működnek bináris faként 1 bites mutatókból, amelyek a kevésbé használt részfára mutatnak. Miután a mutató láncot a levél csomópont azonosítja a csere jelölt. Hozzáférés esetén a lánc összes mutatója az elérhető út levélcsomópontjától a gyökércsomópontig úgy van beállítva, hogy olyan részfára mutasson, amely nem tartalmazza a megnyitott utat.
a hozzáférési sorrend A B C D E.
az elv itt egyszerűen érthető, ha csak a nyílmutatókat nézzük. Ha van hozzáférés egy értékhez, mondjuk ‘A’, és nem találjuk meg a gyorsítótárban, akkor betöltjük a memóriából, és elhelyezzük azt a blokkot, ahol a nyilak jelenleg mutatnak, fentről lefelé haladva. Miután elhelyeztük azt a blokkot, ugyanazokat a nyilakat megfordítjuk, így az ellenkező irányba mutatnak. A fenti példában azt látjuk, hogyan került az ‘A’, majd ‘B’, ‘C ‘és’D’. Aztán, ahogy a gyorsítótár megtelt, az’ E ‘helyébe’ A ‘lépett, mert abban az időben a nyilak erre mutattak, az’ A ‘ – hoz vezető nyilakat pedig az ellenkező irányba fordították. A nyilak ezután a ‘B’ – hez vezettek, amely a következő gyorsítótár kihagyásakor kicserélt blokk lesz.
véletlenszerű csere (RR)Szerkesztés
véletlenszerűen kiválaszt egy jelölt elemet, és eldobja, hogy szükség esetén helyet kapjon. Ez az algoritmus nem igényel semmilyen információt a hozzáférési előzményekről. Az egyszerűség kedvéért ARM processzorokban használták. Elismeri a hatékony sztochasztikus szimulációt.
az alábbi példa hozzáférési sorrendje egy B C D E B D F
szegmentált LRU (SLRU)Szerkesztés
az SLRU gyorsítótár két szegmensre oszlik, egy próbaidős szegmensre és egy védett szegmensre. Az egyes szegmensek sorai a leginkább a legkevésbé elérettektől vannak rendezve. A hiányzó adatok hozzáadódnak a gyorsítótárhoz a próbaidő szegmens Legutóbb elérhető végén. A lekérések eltávolításra kerülnek az aktuális tartózkodási helyükről, és hozzáadódnak a védett szegmens Legutóbb elérhető végéhez. A védett szegmens vonalait tehát legalább kétszer sikerült elérni. A védett szegmens véges, így egy vonal vándorlása a próbaidős szegmensből a védett szegmensbe kényszerítheti a védett szegmens LRU vonalának migrációját a próbaidős szegmens legutóbb használt (MRU) végére, ezzel újabb esélyt adva ennek a vonalnak a hozzáférésre, mielőtt kicserélnék. A védett szegmens méretkorlátja egy SLRU paraméter, amely az I/O munkaterhelési mintáktól függően változik. Amikor az adatokat el kell dobni a gyorsítótárból, a sorok a próbaidős szegmens LRU végéből származnak.
legkevésbé gyakran használt (Lfu)Szerkesztés
Számolja, hogy milyen gyakran van szükség egy elemre. Azokat, amelyeket a legkevésbé használnak, először eldobják. Ez nagyon hasonlít az LRU-hoz, azzal a különbséggel, hogy ahelyett, hogy tárolnánk annak értékét, hogy egy blokkhoz milyen nemrégiben férnek hozzá, azt tároljuk, hogy hányszor férnek hozzá. Tehát természetesen egy hozzáférési sorrend futtatása közben kicserélünk egy blokkot, amelyet a gyorsítótárból a legkevesebb alkalommal használtunk. Például, ha A – T 5-ször, B-T 3-szor, másokat C-t és D-t 10-szer használtunk, akkor a B-t helyettesítjük.
legkevésbé gyakori legutóbb használt (LFRU)Szerkesztés
a legkevésbé gyakori legutóbb használt (LFRU) gyorsítótár csere séma egyesíti az LFU és az LRU rendszerek előnyeit. Az LFRU alkalmas ‘In network’ cache alkalmazásokhoz, mint például az Információközpontú hálózatok (ICN), a tartalomszolgáltató hálózatok (CDN) és általában az elosztott hálózatok. Az LFRU-ban a gyorsítótár két partícióra oszlik, amelyeket privilegizált és privilegizált partícióknak neveznek. A privilegizált partíció védett partícióként definiálható. Ha a tartalom nagyon népszerű, akkor a privilegizált partícióba kerül. A privilegizált partíció cseréje a következőképpen történik: az LFRU kiüríti a tartalmat a privilegizált partícióról, a tartalmat a privilegizált partícióról a privilegizált partícióra tolja, végül új tartalmat szúr be a privilegizált partícióba. A fenti eljárásban az LRU-t használjuk a privilegizált partícióhoz, és egy közelített LFU (ALFU) sémát használunk a privilegizált partícióhoz, ezért az LFRU rövidítés.
Az alapötlet az, hogy kiszűrjük a helyileg népszerű tartalmat az ALFU sémával, és a népszerű tartalmat az egyik privilegizált partícióra toljuk.
lfu dinamikus öregedéssel (LFUDA)Edit
a dinamikus öregedéssel rendelkező LFU (Lfuda) nevű változat, amely dinamikus öregedést használ a népszerű objektumok eltolódásának befogadására. Hozzáadja a gyorsítótár kor tényezőjét a referenciaszámhoz, amikor új objektumot ad hozzá a gyorsítótárhoz, vagy ha egy meglévő objektumot újra hivatkoznak. Az LFUDA növeli a gyorsítótár életkorát a blokkok kilakoltatásakor azáltal, hogy a kilakoltatott objektum kulcsértékére állítja. Így a gyorsítótár kora mindig kisebb vagy egyenlő a gyorsítótár minimális kulcsértékével. Tegyük fel, hogy amikor egy objektumhoz a múltban gyakran hozzáfértek, és most népszerűtlenné válik, hosszú ideig a gyorsítótárban marad, megakadályozva ezzel az újonnan vagy kevésbé népszerű objektumok cseréjét. Tehát ez a dinamikus öregedés bevezetésre kerül, hogy csökkentse az ilyen tárgyak számát, ezáltal alkalmassá téve őket a cserére. Az lfuda előnye, hogy csökkenti az LFU által okozott gyorsítótár-szennyezést, ha a gyorsítótár mérete nagyon kicsi. Ha a gyorsítótár mérete nagy, kevés helyettesítési döntés elegendő, és a gyorsítótár szennyezése nem jelent problémát.
Low inter-reference recency set (LIRS)Szerkesztés
a LIRS egy oldalcsere-algoritmus, amely jobb teljesítményt nyújt az LRU-hoz és sok más újabb helyettesítő algoritmushoz képest. Ez úgy érhető el, hogy az újrafelhasználási távolságot metrikaként használja a dinamikusan rangsorolt oldalak számára a helyettesítési döntés meghozatalához. A LIR-ek hatékonyan kezelik az LRU határait azáltal, hogy a közelmúlt segítségével értékelik az Inter-Reference Recency-t (IRR) a helyettesítési döntés meghozatalához.
a fenti ábrán az ” x ” azt jelenti, hogy egy blokk t időpontban érhető el. Tegyük fel, hogy ha az A1 blokkot az 1.időpontban érjük el, akkor a Recency 0 lesz, mivel ez az első megnyitott blokk, az IRR pedig 1 lesz, mivel azt jósolja, hogy az A1 újra elérhető lesz a 3. időben. Abban az időben, amikor a 2 az A4 elérése óta, a legutóbbi 0 lesz az A4-nél és 1 Az A1-nél, mert az A4 a legutóbb elérhető objektum, az IRR pedig 4 lesz, és folytatódik. A 10. időpontban a LIRS algoritmusnak két Lir set = {A1, A2} és HIR set = {A3, A4, A5} halmaza lesz. Most a 10. időben, ha van hozzáférés az A4-hez, hiányzik. LIRS algoritmus most kilakoltatja A5 helyett A2, mert a legnagyobb közelmúltban.
CLOCK-ProEdit
az LRU algoritmus a magas rezsi miatt nem valósítható meg közvetlenül a számítógépes rendszerek, például az operációs rendszerek kritikus útjában. A megvalósításhoz általában az LRU, az úgynevezett óra közelítését használják. Hasonlóképpen, a CLOCK-Pro a LIR-ek közelítése a rendszerek alacsony költségű megvalósításához. CLOCK-Pro alatt az alapvető óra keret, de három fő különálló érdemei. Először is, a CLOCK-Pro-nak három “óraműje” van, ellentétben az óra egyszerű felépítésével, ahol csak egy “kezét” használják. A három kézzel a CLOCK-Pro képes hozzávetőleges módon mérni az adathozzáférések újrafelhasználási távolságát. Másodszor, a LIR-ek minden érdeme megmarad, például az egyszeri hozzáférés és/vagy az alacsony helymeghatározási adatok gyors kilakoltatása. Harmadszor, a CLOCK-Pro összetettsége megegyezik a CLOCKÉVAL, így könnyen megvalósítható alacsony költséggel. A Linux jelenlegi verziójában a puffer gyorsítótár cseréje az LRU és a CLOCK-Pro kombinációja.
adaptív csere gyorsítótár (ARC)szerkesztés
folyamatosan egyensúlyoz az LRU és az LFU között, hogy javítsa a kombinált eredményt. Az ARC javítja az SLRU-t azáltal, hogy a legutóbb kilakoltatott gyorsítótár-elemekre vonatkozó információkat használja a védett szegmens és a próbaidős szegmens méretének dinamikus beállításához, hogy a rendelkezésre álló gyorsítótár-helyet a lehető legjobban kihasználhassa. Az adaptív csere algoritmust a példa magyarázza.
AdaptiveClimb (AC)Edit
a legutóbbi találatot / kihagyást használja az ugrás beállításához, ahol a mászásban bármelyik találat az egyik helyet a tetejére, az LRU találatban pedig a találat helyzetét a tetejére kapcsolja. Így kihasználva a mászás optimalitását, amikor a program rögzített hatókörben van, és a gyors alkalmazkodást egy új hatókörhöz, ahogy az LRU teszi. Támogatja a gyorsítótár megosztását a magok között az extrák kiadásával is, amikor a hivatkozások a gyorsítótár felső részére vonatkoznak.
óra adaptív csere (autó)Edit
egyesíti az előnyeit adaptív csere Cache (ARC) és óra. Az autó teljesítménye hasonló az ARC – hez, és jelentősen felülmúlja mind az LRU-t, mind az órát. Az ARC-hez hasonlóan az autó is önhangoló, és nem igényel felhasználó által megadott mágikus paramétereket. 4 kétszeresen összekapcsolt listát használ: két órát T1 és T2 és két egyszerű LRU listát B1 és B2. A T1 clock a “recency” vagy a “short term utility” alapján tárolja az oldalakat, míg a T2 a “frequency” vagy a “long term utility”oldalakat tárolja. A T1 és a T2 azokat az oldalakat tartalmazza, amelyek a gyorsítótárban vannak, míg a B1 és a B2 olyan oldalakat tartalmaz, amelyeket nemrégiben kilakoltattak a T1-ből és a T2-ből. Az algoritmus megpróbálja fenntartani a B1-es T2-es és B2-es T1-es listák méretét. Új oldalak kerülnek beillesztésre a T1 vagy T2 – be. Ha van egy hit B1 mérete T1 növekszik, és hasonlóképpen, ha van egy hit B2 mérete T1 csökken. Az alkalmazott adaptációs szabálynak ugyanaz az elve, mint az ARC-ben, fektessen be többet olyan listákba, amelyek több találatot adnak, ha több oldalt adnak hozzá.
többsoros (mq)Szerkesztés
a többsoros algoritmust vagy MQ-t úgy fejlesztették ki, hogy javítsa a második szintű puffer gyorsítótár teljesítményét pl. szerver puffer gyorsítótár. Az MQ gyorsítótár m számú LRU várólistát tartalmaz: Q0, Q1,…, Qm-1. Itt az M értéke egy hierarchiát képvisel az adott sor Összes blokkjának élettartama alapján. Például, ha j> i, a QJ blokkok élettartama hosszabb lesz, mint a Qi-ben. Ezen kívül van egy másik előzmény puffer Qout, egy sor, amely fenntartja az összes Blokkazonosító listáját a hozzáférési frekvenciájukkal együtt. Amikor a Qout megtelt, a legrégebbi azonosítót kilakoltatják. A blokkok egy adott élettartamig az LRU sorokban maradnak, amelyet az MQ algoritmus dinamikusan határoz meg, hogy az ugyanazon fájlhoz való két hozzáférés közötti maximális időbeli távolság vagy a gyorsítótár blokkok száma legyen, amelyik nagyobb. Ha egy blokkra az élettartama alatt nem hivatkoztak, akkor Qi−ről Qi-1-re redukálják, vagy kilakoltatják a gyorsítótárból, ha Q0-ban van. Minden sornak maximális hozzáférési száma is van; ha a Qi sorban lévő blokkhoz több mint 2i-szor férnek hozzá, akkor ezt a blokkot Qi+1-re léptetik elő, amíg 2i+1-nél több alkalommal nem érik el, vagy élettartama lejár. Egy adott várólistán belül a blokkokat az LRU szerint a hozzáférés frissessége rangsorolja.
az ábrán látható. hogyan kerülnek az m LRU sorok a gyorsítótárba. Lásd az ábrát is. hogyan tárolja a qout a blokkazonosítókat és azok megfelelő hozzáférési frekvenciáit. az a-T Q0-ba helyezték, mivel nemrégiben csak egyszer volt elérhető, és a Qoutban ellenőrizhetjük, hogy a b és c hogyan került a Q1 és Q2-be, mivel hozzáférési frekvenciájuk 2 és 4. A sor, amelyben egy blokk kerül függ hozzáférési frekvencia(f) mint log2 (f). Amikor a gyorsítótár megtelt, az első kilakoltatandó blokk a Q0 feje lesz ebben az esetben a. Ha a-t még egyszer elérik, akkor a B alatti Q1-re lép.
Pannier: konténer alapú gyorsítótárazási algoritmus összetett objektumokhozszerkesztés
a Pannier egy konténer alapú flash gyorsítótárazási mechanizmus, amely azonosítja a divergens (heterogén) konténereket, ahol az ott tárolt blokkok nagyon eltérő hozzáférési mintákkal rendelkeznek. A Pannier prioritás-várólista alapú túlélési várólista-struktúrát használ a tárolók túlélési idejük alapján történő rangsorolásához, amely arányos a tárolóban lévő élő adatokkal. A Pannier a szegmentált LRU (S2LRU) alapján épül fel, amely elkülöníti a meleg és hideg adatokat. A Pannier egy többlépcsős visszacsatoló vezérlőt is használ a vaku írásának fojtására a vaku élettartamának biztosítása érdekében.