Béládyn algoritmimedit
tehokkain välimuistialgoritmi olisi hävittää aina tiedot, joita ei tulevaisuudessa tarvita pisimpään. Tätä optimaalista tulosta kutsutaan béládyn optimaaliseksi algoritmiksi / yksinkertaisesti optimaaliseksi korvauspolitiikaksi tai selvänäkijän algoritmiksi. Koska on yleensä mahdotonta ennustaa, kuinka pitkälle tulevaisuuteen tietoa tarvitaan, tämä ei yleensä ole käytännössä toteutettavissa. Käytännön minimi voidaan laskea vasta kokeilun jälkeen, ja voidaan vertailla oikeasti valitun välimuistialgoritmin tehokkuutta.
sillä hetkellä, kun sivuvirhe ilmenee, jokin joukko sivuja on muistissa. Esimerkissä sekvenssi ’5’, ’0’, ’1’ käytetään Frame 1, Frame 2, Frame 3 vastaavasti. Kun arvoa ” 2 ”käytetään, se korvaa arvon ”5”, joka on kehyksessä 1, koska se ennustaa, että arvoa ” 5 ” ei saavuteta lähitulevaisuudessa. Koska tosielämän yleiskäyttöinen käyttöjärjestelmä ei voi varsinaisesti ennustaa, milloin ” 5 ” pääsee käyttöön, béládyn algoritmia ei voida toteuttaa tällaisessa järjestelmässä.
First in first out (FIFO)Edit
käyttämällä tätä algoritmia välimuisti käyttäytyy samalla tavalla kuin FIFO-jono. Kätkö häätää lohkot siinä järjestyksessä kuin ne on lisätty, välittämättä siitä, kuinka usein tai kuinka monta kertaa niitä on käytetty aiemmin.
Last in first out (LIFO) tai First in last out (FILO)Edit
käyttämällä tätä algoritmia välimuisti käyttäytyy samalla tavalla kuin pino ja täysin päinvastaisesti kuin FIFO-jono. Välimuisti poistaa viimeksi ensin lisätyn lohkon välittämättä siitä, kuinka usein tai kuinka monta kertaa sitä on käytetty aiemmin.
vähiten käytetyt (LRU)muokkaa
hävittää ensin Vähiten käytetyt kohteet. Tämä algoritmi vaatii seurata, mitä käytettiin, kun, mikä on kallista, jos haluaa varmistaa, että algoritmi aina heittää pois vähiten käytetty kohde. Tämän tekniikan yleiset toteutukset edellyttävät välimuistilinjojen ”ikäbittien” pitämistä ja ”viimeksi käytetyn” välimuistilinjan seuraamista ikäbittien perusteella. Tällaisessa toteutuksessa kaikkien muiden välimuistirivien ikä muuttuu aina, kun käytetään välimuistiriviä. LRU on itse asiassa välimuistialgoritmien perhe, jonka jäseniä ovat muun muassa Theodore Johnsonin ja Dennis Shashan 2Q sekä Pat O ’Neilin, Betty O’ Neilin ja Gerhard Weikumin LRU/k.
alla olevan esimerkin pääsyjärjestys on A B C D E D F.
yllä olevassa esimerkissä kun B C D asennetaan lohkoihin, joissa on järjestysnumerot (Lisäys 1 jokaiselle uudelle liittymälle) ja kun E: tä käytetään, se on huti ja se on asennettava johonkin lohkoista. LRU-algoritmin mukaan koska A: lla on alin sijoitus(A(0)), E korvaa A: n.
toiseksi viimeisessä vaiheessa D: tä käytetään ja siksi järjestysnumero päivitetään.
LRU, kuten monet muutkin korvauskäytännöt, voidaan karakterisoida käyttämällä vektoriavaruudessa olevaa tilan siirtymäkenttää, joka päättää dynaamisen välimuistin tilan muutokset samalla tavalla kuin sähkömagneettinen kenttä määrää siihen sijoitetun varautuneen hiukkasen liikkeen.
Time aware least latest used (Tlru)Edit
the Time aware Least latest Used (Tlru) on LRU: n muunnelma, joka on suunniteltu tilanteeseen, jossa välimuistiin tallennetulla sisällöllä on voimassa oleva elinaika. Algoritmi soveltuu verkon välimuistisovelluksiin, kuten Tietokeskiseen verkostoitumiseen (ICN), Sisällönjakeluverkostoihin (Cdns) ja hajautettuihin verkkoihin yleensä. Tlru esittelee uuden termin: TTU (Time to Use). TTU on sisällön / sivun aikaleima, joka määrää sisällön käytettävyysajan sisällön paikkakunnan ja sisällön julkaisijan ilmoituksen perusteella. Koska tällä paikkakunnalla perustuu aikaleima, TTU tarjoaa enemmän valvontaa paikallisen järjestelmänvalvojan säännellä verkon tallennustilaa.Tlru-algoritmissa sisällön saapuessa välimuistisolmu laskee paikallisen ttu-arvon sisällön julkaisijan antaman ttu-arvon perusteella. Paikallinen TTU-arvo lasketaan käyttämällä paikallisesti määriteltyä funktiota. Kun paikallinen TTU-arvo on laskettu, sisällön korvaaminen suoritetaan välimuistisolmuun tallennetun kokonaissisällön osajoukolle. Tlru varmistaa, että vähemmän suosittu ja pieni life-sisältö on korvattava tulevalla sisällöllä.
viimeksi käytetyt (MRU)muokkaavat
poisheitetyt määrät, toisin kuin LRU, viimeksi käytetyt erät ensin. VLDB: n 11.konferenssissa esitellyissä havainnoissa Chou ja DeWitt totesivat, että ”kun tiedostoa skannataan toistuvasti referenssikuviossa, MRU on paras korvaava algoritmi.”Myöhemmin muut tutkijat esittivät 22nd VLDB konferenssi totesi, että satunnaiskäytön malleja ja toistuvia skannaa yli suuria tietojoukkoja (joskus tunnetaan syklinen access patterns) MRU cache algoritmeja on enemmän osumia kuin LRU, koska niiden taipumus säilyttää vanhempia tietoja. MRU-algoritmit ovat hyödyllisimpiä tilanteissa, joissa mitä vanhempi kohde on, sitä todennäköisemmin siihen pääsee käsiksi.
alla olevan esimerkin pääsyjärjestys on A B C D E C D B.
tässä b C D sijoitetaan välimuistiin, koska tilaa on vielä jäljellä. 5th access E, näemme, että lohko, joka piti D on nyt korvattu E, koska tämä lohko käytettiin viimeksi. Toinen pääsy C ja seuraavassa pääsy D, C korvataan, koska se oli lohko käytetään juuri ennen D ja niin edelleen.
Pseudo-LRU (PLRU)Edit
suuren assosiatiivisuuden suorittimien välimuisteissa (yleensä >4 tapaa) LRU: n toteutuskustannuksista tulee kohtuuttomia. Monissa suorittimen välimuisteissa riittää järjestelmä, joka lähes aina hävittää yhden vähiten käytetyistä kohteista, joten monet suorittimen suunnittelijat valitsevat PLRU-algoritmin, joka tarvitsee toimiakseen vain yhden bitin välimuistia kohden.PLRU: lla on tyypillisesti hieman huonompi miss-suhde, sen latenssi on hieman parempi, se käyttää hieman vähemmän tehoa kuin LRU ja pienemmät yleiskustannukset verrattuna LRU: hun.
seuraavassa esimerkissä näytetään, miten bitit toimivat 1-bittisten osoittimien binääripuuna, joka osoittaa harvemmin käytettyyn alapuuhun. Osoittimen ketjun seuraaminen lehtisolmuun tunnistaa korvaavan ehdokkaan. Kun Pääsy kaikki osoittimet ketjun käyttää tapa lehtisolmu juurisolmu on asetettu osoittamaan alatreetä, joka ei sisällä käyttää tavalla.
pääsarjakuva on B C D E.
tässä oleva periaate on helppo ymmärtää, jos tarkastellaan vain nuolen osoittimia. Kun on pääsy arvo, sanoa ”A”, ja emme löydä sitä välimuistissa, sitten lataamme sen muistista ja aseta se lohko, jossa nuolet ovat tällä hetkellä osoittaa, menee ylhäältä alas. Kun olemme asettaneet sen lohkon, käännämme samoja nuolia, jotta ne osoittavat vastakkaiseen suuntaan. Yllä olevassa esimerkissä näemme, miten ”A” oli sijoitettu, jota seuraavat ”B”, ”C ja ”D”. Sitten kun välimuisti tuli täyteen ” E ”korvasi ” A”, koska silloin nuolet osoittivat siihen aikaan, ja ”A”: een johtaneet nuolet käännettiin osoittamaan vastakkaiseen suuntaan. Tämän jälkeen nuolet johtivat ”B: hen”, joka on lohko, joka korvataan seuraavalla välimuistin missillä.
Random replacement (RR)Edit
valitsee satunnaisesti ehdokaskohteen ja hävittää sen tehdäkseen tilaa tarvittaessa. Tämä algoritmi ei vaadi tietojen säilyttämistä käyttöhistoriasta. Yksinkertaisuutensa vuoksi sitä on käytetty ARM-prosessoreissa. Se mahdollistaa tehokkaan stokastisen simuloinnin.
alla olevan esimerkin pääsyjärjestys on B C D E B D F
segmentoitu LRU (SLRU)Edit
SLRU-välimuisti on jaettu kahteen segmenttiin, koesegmenttiin ja suojattuun segmenttiin. Rivit kussakin segmentissä on tilattu eniten ja vähiten käytetty. Tiedot misseistä lisätään välimuistiin koejakson viimeisimmässä päässä. Osumat poistetaan siitä, missä ne tällä hetkellä sijaitsevat, ja lisätään suojatun segmentin viimeisimpään päähän. Suojatun segmentin radoille on siis päästy ainakin kahdesti. Suojattu segmentti on äärellinen, joten linjan siirtyminen koeaikasegmentiltä suojattuun segmenttiin voi pakottaa vastaavan rautatieyrityksen linjan siirtymisen suojatun segmentin viimeksi käytettyyn (MRU) koeaikasegmentin loppuun, mikä antaa tälle radalle toisen mahdollisuuden päästä käsiksi ennen sen korvaamista. Suojatun segmentin kokorajoitus on SLRU-parametri, joka vaihtelee I/O-työmäärien mukaan. Aina kun tiedot on poistettava välimuistista, saadaan rivit koejakson vastaavan rautatieyrityksen päästä.
vähiten käytetty (Lfu)Edit
laskee, kuinka usein tuotetta tarvitaan. Ne, joita käytetään vähiten, heitetään ensin pois. Tämä toimii hyvin samalla tavalla kuin vastaava rautatieyritys, paitsi että sen sijaan, että tallentaisimme sen arvon, kuinka äskettäin lohkoa käytettiin, Tallennamme arvon, kuinka monta kertaa sitä käytettiin. Joten tietenkin ajettaessa pääsy sekvenssi me korvata lohko, jota käytettiin vähiten kertaa meidän välimuisti. Esim. Jos A: ta käytettiin 5 kertaa ja B: tä käytettiin 3 kertaa ja muita C: tä ja D: tä käytettiin 10 kertaa kukin, korvaamme B: n.
lest frequently recently used (LFRU)Edit
Lfru) cache replacement scheme yhdistää LFU-ja LRU-järjestelmien edut. LFRU soveltuu ”verkon” välimuistisovelluksiin, kuten Tietokeskiseen verkostoitumiseen (ICN), sisällön Jakeluverkostoihin (Cdns) ja hajautettuihin verkkoihin yleensä. Lfru: ssa välimuisti on jaettu kahteen osioon, joita kutsutaan etuoikeutetuiksi ja etuoikeutetuiksi osioiksi. Etuoikeutettu osio voidaan määritellä suojatuksi osioksi. Jos Sisältö on erittäin suosittua, se työnnetään etuoikeutettuun osioon. Etuoikeutetun osion korvaaminen tapahtuu seuraavasti: LFRU poistaa sisällön etuoikeutetusta osiosta, työntää sisältöä etuoikeutetusta osiosta etuoikeutettuun osioon ja lisää lopuksi uutta sisältöä etuoikeutettuun osioon. Edellä mainitussa menettelyssä etuoikeutetulle osiolle käytetään LRU: ta ja etuoikeutetulle osiolle approksimoitua LFU-järjestelmää (ALFU), mistä seuraa lyhenne LFRU.
perusajatuksena on suodattaa paikallisesti suosittu sisältö ALFU-järjestelmän avulla ja työntää suosittu sisältö johonkin etuoikeutettuun osioon.
lfu with dynamic aging (lfuda)Edit
muunnos nimeltään Lfu with Dynamic Aging (Lfuda), joka käyttää dynaamista ikääntymistä sovittaakseen siirtymät suosittujen kohteiden joukkoon. Se lisää välimuistin ikäkertoimen referenssilukuun, kun uusi kohde lisätään välimuistiin tai kun olemassa olevaa objektia viitataan uudelleen. LFUDA kasvattaa välimuistin ikää, kun lohkot häädetään asettamalla se häädetyn objektin avainarvoksi. Näin ollen välimuistin ikä on aina pienempi tai yhtä suuri kuin välimuistin pienin avainarvo. Oletetaan, että kun esineeseen on aiemmin käytetty usein ja nyt siitä tulee epäsuosittu, se jää kätköön pitkäksi aikaa, mikä estää uusia tai vähemmän suosittuja esineitä korvaamasta sitä. Joten tämä dynaaminen vanheneminen otetaan käyttöön, jotta tällaisten esineiden määrä saadaan laskemaan, jolloin ne voidaan korvata. Lfudan etuna on se, että se vähentää lfu: n aiheuttamaa välimuistisaastetta, kun välimuistikoot ovat hyvin pieniä. Kun Välimuistikoot ovat suuria, harvat korvauspäätökset ovat riittäviä ja välimuistin saastuminen ei ole ongelma.
Low inter-reference recency set (LIRS)Edit
LIRS on sivun korvaava algoritmi, jonka suorituskyky on parantunut LRU: n ja monien muiden uudempien korvaavien algoritmien suhteen. Tämä saavutetaan käyttämällä uudelleenkäyttöetäisyys metriikka dynaamisesti paremmuusjärjestykseen käytetyt sivut tehdä korvaavan päätöksen. LIR: t käsittelevät tehokkaasti LRU: n rajoja käyttämällä viimeaikaista tilannetta vertailutietojen välisen viimeaikaisen tilanteen (IRR) arvioimiseksi korvaavan päätöksen tekemiseksi.
yllä olevassa kuvassa ”x” tarkoittaa, että lohkoon pääsee hetkellä t. Oletetaan, jos lohko A1 käytetään aikaan 1 sitten Recency tulee 0, koska tämä on ensimmäinen käytetty lohko ja IRR on 1, koska se ennustaa, että A1 käytetään uudelleen ajassa 3. Ajassa 2, koska A4: ää käytetään, recency muuttuu 0: ksi A4: lle ja 1: ksi A1: lle, koska A4 on viimeksi käytetty objekti ja IRR: stä tulee 4 ja se jatkuu. Ajalla 10 LIRS-algoritmilla on kaksi joukkoa LIR-joukko = {a1, A2} ja HIR-joukko = {A3, A4, A5}. Nyt aikaan 10 Jos on pääsy A4, miss tapahtuu. LIRS-algoritmi häätää nyt A5: n A2: n sijasta sen suurimman viimeaikaisuuden vuoksi.
CLOCK-ProEdit
LRU-algoritmia ei voida suoraan toteuttaa tietokonejärjestelmien, kuten käyttöjärjestelmien, kriittisellä polulla sen korkean ylimenokyvyn vuoksi. Toteutuksessa käytetään yleisesti LRU: n approksimaatiota, jota kutsutaan Kelloksi. Vastaavasti CLOCK-Pro on likiarvo lirs-järjestelmästä, jolla saavutetaan alhainen kustannustaso järjestelmissä. CLOCK-Pro on peruskellokehyksen alainen, mutta sillä on kolme merkittävää erillistä ansiota. Ensinnäkin CLOCK-Prossa on kolme ”kellokättä” erotuksena yksinkertaisesta kellon rakenteesta, jossa käytetään vain yhtä ”kättä”. Kolmen käden avulla CLOCK-Pro pystyy mittaamaan tietojen uudelleenkäyttöetäisyyden likimääräisesti. Toiseksi kaikki liirien ansiot säilytetään, kuten kertaluonteisten pääsyiden ja/tai vähäisten paikkatietojen nopea häätäminen. Kolmanneksi kello-Pron monimutkaisuus on sama kuin kellon, joten se on helppo toteuttaa edullisesti. Puskurivälimuistin korvaava toteutus Linuxin nykyisessä versiossa on yhdistelmä LRU: ta ja CLOCK-Pro: ta.
Adaptive replacement cache (ARC)Edit
tasapainottaa jatkuvasti LRU: n ja LFU: n välillä parantaakseen yhteistulosta. ARC parantaa JÄRJESTELMÄKAMERAJÄRJESTELMÄÄ käyttämällä tietoja äskettäin häädetyistä välimuistikohteista suojatun segmentin ja koeajan segmentin koon dynaamisesti, jotta käytettävissä olevaa välimuistitilaa voidaan hyödyntää parhaalla mahdollisella tavalla. Adaptiivinen korvausalgoritmi selitetään esimerkillä.
AdaptiveClimb (AC)Edit
käyttää viimeaikaista osumaa / hutia hypyn säätämiseen, jossa kiipelissä mikä tahansa osuma vaihtaa asennon yhdestä raosta kärkeen, ja LRU: ssa osuma vaihtaa osuman asennon yläosaan. Siten hyötyy optimaalisuudesta kiivetä, kun ohjelma on kiinteässä laajuudessa, ja nopea sopeutuminen uuteen ulottuvuuteen, kuten LRU tekee. Tue myös välimuistin jakamista ydinten kesken vapauttamalla ekstroja, kun viittaukset ovat välimuistin yläosassa.
kello adaptive replacement (Auto)Edit
yhdistää adaptiivisen korvaavan välimuistin (ARC) ja kellon edut. Auton suorituskyky on verrattavissa ARC, ja merkittävästi päihittää sekä LRU ja kello. Kuten ARC, auto on itseviritteinen eikä vaadi käyttäjän määrittämiä taikaparametreja. Se käyttää 4 kaksinkertaisesti linkitettyä luetteloa: kaksi kelloa T1 ja T2 ja kaksi yksinkertaista LRU-luetteloa B1 ja B2. T1 clock tallentaa sivuja, jotka perustuvat ” recency ”tai” short term utility”, kun taas T2 tallentaa sivuja” frequency ”tai”long term utility”. T1 ja T2 sisältävät ne sivut, jotka ovat välimuistissa, Kun taas B1 ja B2 sisältävät sivut, jotka on hiljattain häädetty T1 ja T2 vastaavasti. Algoritmi pyrkii säilyttämään näiden luetteloiden koon B1≈T2 ja B2≈T1. Uudet sivut lisätään T1: een tai T2: een. Jos on osuma B1 koko T1 kasvaa ja vastaavasti jos on osuma B2 koko T1 pienenee. Käytetyllä sopeutumissäännöllä on sama periaate kuin ARC: ssa, sijoita enemmän listoihin, jotka antavat enemmän osumia, kun siihen lisätään enemmän sivuja.
Multi queue (MQ)Edit
monijonoalgoritmi tai MQ kehitettiin parantamaan toisen tason puskurivälimuistin suorituskykyä esimerkiksi palvelinpuskurivälimuistille. Se on otettu käyttöön paperi Zhou, Philbin, ja Li. mq välimuisti sisältää m määrä LRU jonoja: Q0, Q1,…, Qm-1. Tässä m: n arvo edustaa hierarkiaa, joka perustuu kyseisen jonon kaikkien lohkojen elinikään. Esimerkiksi jos j>i, lohkojen QJ on pidempi käyttöikä kuin Qi. Näiden lisäksi on toinen historiapuskuri Qout, jono, joka ylläpitää listaa kaikista Lohkotunnisteista pääsytaajuuksineen. Kun Qout on täynnä, vanhin tunniste häädetään. Lohkot pysyvät LRU-jonoissa tietyn eliniän ajan, jonka mq-algoritmi määrittää dynaamisesti siten, että se on suurin ajallinen etäisyys kahden samaan tiedostoon pääsyn välillä tai välimuistilohkojen lukumäärä sen mukaan, kumpi on suurempi. Jos lohkoon ei ole viitattu sen elinaikana, se alennetaan Qi: stä Qi−1: een tai häädetään välimuistista, jos se on Q0: ssä. Jokaisella jonolla on myös enimmäiskäyttömäärä; jos jonossa Qi olevaa lohkoa käytetään enemmän kuin 2i kertaa, tämä lohko ylennetään arvoksi Qi+1, kunnes sitä käytetään enemmän kuin 2i+1 kertaa tai sen käyttöikä päättyy. Tietyn jonon sisällä lohkot asetetaan järjestykseen vastaavan rautatieyrityksen (LRU) mukaan pääsyajankohdan mukaan.
näemme viikunasta. miten m LRU-jonot sijoitetaan välimuistiin. Katso myös viikuna. miten Qout tallentaa lohkotunnisteet ja niitä vastaavat käyttöoikeustaajuudet. a sijoitettiin Q0 koska sitä käytettiin vain kerran äskettäin ja voimme tarkistaa Qout miten b ja c sijoitettiin Q1 ja Q2 vastaavasti niiden access taajuudet ovat 2 ja 4. Jono, johon lohko sijoitetaan, riippuu liittymistaajuudesta(f) log2(f). Kun välimuisti on täynnä, ensimmäinen häädettävä lohko on Q0: n pää tässä tapauksessa a. Jos A: ta käytetään vielä kerran, se siirtyy Q1: een B: n alapuolelle.
Pannier: kontti-pohjainen välimuistialgoritmi yhdistelmäobjekteille edit
Pannier on kontti-pohjainen flash-välimuistimekanismi, joka tunnistaa toisistaan poikkeavat (heterogeeniset) kontit, joissa niissä pidettävillä lohkoilla on hyvin vaihtelevat käyttömallit. Pannier käyttää priority-jonoon perustuvaa selviytymisjonorakennetta asettaakseen kontit paremmuusjärjestykseen niiden eloonjäämisajan perusteella, joka on verrannollinen kontissa oleviin eläviin tietoihin. Pannier perustuu segmentoituun LRU: hun (S2LRU), joka erottelee kuuman ja kylmän datan. Pannier käyttää myös monivaiheista palautetta ohjain kuristaa flash kirjoittaa varmistaa flash elinikä.