Välimuistialgoritmit ( enostoalgoritmit , ennaltaehkäisykäytännöt ja "korvausalgoritmit/käytännöt") – tietojenkäsittelytieteessä tämä on ohjeiden optimointi : erityinen tietokoneohjelma tai laitteiston tukema rakenne, joka pystyy hallitsemaan tietokoneeseen tallennettujen tietojen välimuistia . Kun välimuisti on täynnä, algoritmin on valittava, mitä siitä tarkalleen pitää poistaa, jotta se pystyy kirjoittamaan (välimuistiin) uutta, ajantasaisempaa tietoa. Näiden algoritmien laitteistototeutus sisältää ajastimen , laskurin tai molempien yhdistelmän käytön.
Välimuistin "osumaprosentti" viittaa siihen, kuinka usein etsimäsi tiedot löytyvät välimuistista. Tehokkaammat häätökäytännöt pitävät kirjaa eniten käytetyistä tiedoista, mikä parantaa osumaprosenttia (samalla välimuistin koosta).
Välimuistin "latenssi" viittaa siihen, kuinka nopeasti välimuisti voi palauttaa pyydetyt tiedot välittömästi pyynnön jälkeen (jos "osuma" tapahtuu). Nopeammat häätöstrategiat pitävät tyypillisesti kirjaa vähiten käytetyistä tiedoista – tai suoraan kartoitetun välimuistin tapauksessa tiedon puutteesta – lyhentääkseen tietojen päivittämiseen kuluvaa aikaa.
Jokainen siirtymästrategia on kompromissi osumanopeuden ja viiveen välillä.
Tehokkain häätösääntö on hylätä välimuistista tiedot, joita ei tarvita pisimpään tulevaisuudessa. Tätä optimaalista välimuistialgoritmia on kutsuttu Beladi- algoritmiksi tai ennakointialgoritmiksi . Koska yleisessä tapauksessa on mahdotonta ennustaa, milloin tarkalleen tätä tietoa tarvitaan seuraavan kerran, käytännössä (taas kerran, yleisessä tapauksessa) tällainen toteutus on mahdotonta. Käytännön minimi voidaan laskea vain empiirisesti, minkä jälkeen nykyisen välimuistialgoritmin tehokkuutta voidaan verrata siihen.
Vähiten käytetty (LRU): Ensinnäkin pisin käyttämätön syrjäytetään. Tämä algoritmi vaatii kirjaamaan, mitä on käytetty ja milloin, mikä voi olla melko kallista, varsinkin jos sinun on tehtävä lisävarmennus varmistaaksesi. Tämän menetelmän yleinen toteutus edellyttää "ikäbitin" säilyttämistä välimuistiriveille, ja siten seuraa vähiten käytettyjä rivejä (eli vertaamalla tällaisia bittejä). Tällaisessa toteutuksessa joka kerta, kun välimuistiriville käytetään, kaikkien muiden rivien "ikä" muuttuu. LRU on itse asiassa välimuistialgoritmien perhe, joka sisältää Theodore Johnsonin ja Dennis Schashan 2Q :n ja Pat O'Neillin, Betty O'Neillin ja Gerhard Weikumin LRU/K:n.
Viimeksi käytetyt (MRU): Toisin kuin LRU, viimeksi käytetty esine häädetään ensin. Lähteen mukaan [1] : "Kun tiedostoa tarkistetaan määräajoin round robin -tyylillä, MRU on paras häätöalgoritmi." [2] -julkaisussa kirjoittajat korostavat myös, että satunnaispääsymenetelmissä ja suurten tietojoukkojen syklisessä skannauksessa (jota joskus kutsutaan round robin -malleiksi), MRU-välimuistialgoritmeilla on enemmän osumia kuin LRU:ssa, koska niillä on taipumus säilyttää vanhaa dataa. MRU-algoritmit ovat hyödyllisimpiä tapauksissa, joissa mitä vanhempi elementti, sitä enemmän siihen pääsee käsiksi.
Pseudo-LRU (PLRU): Välimuistissa, jossa on suuri assosiatiivisuus (yleensä yli 4 kanavaa), LRU:n toteuttamiseen tarvittavat resurssit ovat liian suuria. Jos käytäntö riittää lähes aina hylkäämään vähiten käytetyn merkinnän, niin tässä tapauksessa voidaan käyttää PLRU-algoritmia, joka vaatii vain yhden bitin välimuistin merkintää kohti.
Segmentoitu LRU (tai SLRU): "SLRU-välimuisti on jaettu kahteen segmenttiin: kokeilujaksoon ja suojattuun segmenttiin. Kunkin segmentin linjat on järjestetty eniten käytetystä vähiten käytettyyn. Tiedot poissaoloista lisätään välimuistiin ja kokeilujakson viimeksi käytettyjen elementtien alueelle. Osumien tiedot poistetaan missä tahansa ja lisätään suojatun segmentin usein käytettyjen elementtien alueelle. Suojattuja segmenttirivejä käytetään siten vähintään kahdesti. Suojattu segmentti on rajoitettu. Tällainen linjan siirto kokeilusegmentistä suojattuun segmenttiin voi aiheuttaa sen, että suojatun segmentin viimeksi käytetty (LRU) rivi siirretään kokeilusegmentin MRU-alueelle, mikä antaa tälle linjalle toisen mahdollisuuden käyttää ennen sen käyttöä. häädetty. Suojatun segmentin koko on SLRU-parametri, joka vaihtelee I/O-mallin mukaan. Aina kun tiedot on poistettava välimuistista, rivejä pyydetään mittaussegmentin LRU-päästä. [3] »
Kaksisuuntainen assosiatiivisuus koskee nopeita prosessorien välimuistia , joissa jopa PLRU on liian hidas. Uuden elementin osoitetta käytetään laskemaan toinen kahdesta mahdollisesta sijainnista välimuistissa (tälle varatulle alueelle). LRU-algoritmin mukaan kaksi elementtiä siirretään. Se vaatii yhden bitin parille välimuistiriville osoittamaan, mitä viimeksi käytetty.
Suora kartoitettu välimuisti : Nopeille prosessorin välimuistille, joissa kaksisuuntaisen assosiatiivisen välimuistin suorituskyky puuttuu. Uuden elementin osoitetta käytetään välimuistin sijainnin laskemiseen (tälle varatulle alueelle). Kaikki entinen vaihdetaan.
Vähiten käytetty (LFU): LFU laskee, kuinka usein elementtiä käytetään. Ne elementit, joita käytetään harvimmin, estetään ensin.
Adaptive Replacement Cache (ARC): [4] tasapainottaa jatkuvasti LRU:n ja LFU:n välillä, mikä parantaa lopputulosta.
Multi Queue (MQ) -välimuistialgoritmi : [5] (kehittäjät Y. Zhu, J. F. Philbin ja Kai Li).
Seuraavat kohdat otetaan huomioon:
Välimuistin yhtenäisyyden varmistamiseksi on myös erilaisia algoritmeja . Tämä koskee vain tapauksia, joissa käytetään useita itsenäisiä välimuistia samojen tietojen tallentamiseen (esimerkiksi useat tietokantapalvelimet päivittävät yhteisen datatiedoston).