Välimuistialgoritmi
Välimuistialgoritmi on algoritmi, jota käytetään välimuistin tai tietoryhmän hallintaan. Kun välimuisti on täynnä, se päättää, mikä kohde on poistettava välimuistista. Sana hit rate kuvaa sitä, kuinka usein pyyntöä voidaan palvella välimuistista. Termi latenssi kuvaa, kuinka kauan välimuistissa oleva kohde voidaan saada käyttöön. Välimuistin algoritmit ovat kompromissi osumisasteen ja viiveen välillä.
- Tehokkain välimuistialgoritmi olisi hävittää aina tiedot, joita ei tarvita pisimpään tulevaisuudessa. Tätä optimaalista tulosta kutsutaan Beladyn optimaaliseksi algoritmiksi tai selvänäkijäalgoritmiksi. Koska on yleensä mahdotonta ennustaa, kuinka kaukana tulevaisuudessa tietoa tarvitaan, tätä ei yleensä voida toteuttaa käytännössä. Käytännön minimi voidaan laskea vasta kokeilujen jälkeen, ja voidaan verrata tosiasiallisesti valitun välimuistialgoritmin tehokkuutta optimaaliseen minimiin.
- Viimeksi käytetyt kohteet (LRU): Poistaa vähiten käytetyt kohteet ensin. Tämä algoritmi edellyttää sen seuraamista, mitä on käytetty milloin. Tämä on kallista, jos halutaan varmistaa, että algoritmi poistaa aina vähiten käytetyn kohteen. Tämän tekniikan yleiset toteutukset edellyttävät, että välimuistirivien "ikäbitit" säilytetään ja "viimeksi käytetyn" välimuistirivin seuranta perustuu ikäbitteihin. Tällaisessa toteutuksessa kaikkien muiden välimuistirivien ikä muuttuu aina, kun välimuistiriviä käytetään. LRU on itse asiassa välimuistialgoritmien perhe, jonka jäseniä ovat muun muassa seuraavat: 2Q, jonka ovat laatineet Theodore Johnson ja Dennis Shasha, sekä LRU/K, jonka ovat laatineet Pat O'Neil, Betty O'Neil ja Gerhard Weikum.
- Viimeksi käytetty (MRU): Tämä algoritmi poistaa viimeksi käytetyt kohteet ensin. Tätä välimuistimekanismia käytetään yleisesti tietokantojen muistin välimuisteissa.
- Pseudo-LRU (PLRU): LRU on tietyissä tapauksissa hyvin vaikea toteuttaa. Tällaisissa tapauksissa voi riittää tieto siitä, että useimmissa tapauksissa yksi viimeksi käytetyistä kohteista poistetaan. Tällöin voidaan käyttää PLRU-algoritmia, koska se tarvitsee toimiakseen vain yhden bitin kutakin välimuistitietoa kohti.
- 2-suuntainen assosiatiivinen sarja: nopeisiin suorittimen välimuisteihin, joissa jopa PLRU on liian hidas. Uuden elementin osoitteen perusteella lasketaan yksi kahdesta mahdollisesta paikasta välimuistissa, johon se saa mennä. Näistä kahdesta LRU hylätään. Tämä vaatii yhden bitin jokaista välimuistiriviparia kohti, jotta voidaan osoittaa, kumpi näistä kahdesta oli viimeksi käytetty.
- Suorakartoitettu välimuisti: nopeimmille suorittimen välimuisteille, joissa jopa 2-suuntaiset assosiatiiviset välimuistit ovat liian hitaita. Uuden elementin osoitteen perusteella lasketaan välimuistissa yksi paikka, johon se saa mennä. Se, mikä oli siellä aiemmin, hylätään.
- Vähiten käytetty (LFU): LFU: LFU laskee, kuinka usein kohdetta tarvitaan. Harvimmin käytetyt hylätään ensin.
- Adaptive Replacement Cache (ARC): Tasapainottaa jatkuvasti LRU:n ja LFU:n välillä parantaakseen yhdistettyä tulosta.
- Multi Queue (MQ) -salausalgoritmi: (Y. Zhou, J.F. Philbin ja Kai Li).
Muita huomioon otettavia asioita:
- Kustannuksiltaan erilaiset esineet: Pidä esineet, joiden hankkiminen on kallista, esim. esineet, joiden hankkiminen kestää kauan.
- Kohteet vievät enemmän välimuistia: Jos kohteet ovat erikokoisia, välimuisti voi haluta hylätä suuren kohteen ja varastoida useita pienempiä.
- Esineet, jotka vanhenevat ajan myötä: Esimerkiksi uutisten välimuisti, DNS-välimuisti tai verkkoselaimen välimuisti. Tietokone saattaa hylätä kohteita, koska ne ovat vanhentuneet. Välimuistin koosta riippuen ei välttämättä tarvita muuta välimuistialgoritmia kohteiden hylkäämiseksi.
Välimuistitiedostojen yhtenäisyyden ylläpitämiseksi on myös olemassa erilaisia algoritmeja. Tämä koskee vain tilannetta, jossa samaan dataan käytetään useita toisistaan riippumattomia välimuisteja (esimerkiksi useat tietokantapalvelimet päivittävät yhtä yhteistä datatiedostoa).
Mitkä muistipaikat voidaan tallentaa välimuistiin millä välimuistipaikoilla?
Kysymyksiä ja vastauksia
K: Mikä on välimuistialgoritmi?
A: Välimuistialgoritmi on algoritmi, jota käytetään välimuistin tai tietoryhmän hallintaan. Se päättää, mikä kohde poistetaan välimuistista, kun se on täynnä.
K: Mikä on osumisaste?
V: Osuma-aste kuvaa sitä, kuinka usein pyyntöä voidaan palvella välimuistista.
K: Mitä latenssi kuvaa?
V: Viive kuvaa sitä, kuinka kauan välimuistissa oleva kohde voidaan saada käyttöön.
K: Mikä on Beladyn optimaalinen algoritmi?
V: Beladyn optimaalinen algoritmi, joka tunnetaan myös nimellä selvännäkijäalgoritmi, on tehokas välimuistialgoritmi, joka hylkää aina tiedot, joita ei tarvita pisimpään tulevaisuudessa. Tätä tulosta ei yleensä voida toteuttaa käytännössä, koska se edellyttää ennustamista siitä, mitä tarvitaan pitkälle tulevaisuuteen.
K: Miten LRU (Least Recently Used) toimii?
V: LRU poistaa vähiten käytetyt kohteet ensin, ja se edellyttää, että seurataan, mitä on käytetty milloin, käyttämällä "ikäbittejä" jokaiselle välimuistiriville ja seuraamalla ikäbittien perusteella, mikä niistä on käytetty vähiten äskettäin. Aina kun välimuistiriviä käytetään, kaikkien muiden välimuistirivien ikää muutetaan vastaavasti.
K: Miten MRU (Most Recently Used) toimii?
V: MRU poistaa viimeksi käytetyt kohteet ensin, ja tätä välimuistimekanismia käytetään yleisesti tietokantojen muistin välimuistissa.
K: Mitä muita algoritmeja on olemassa välimuistin yhtenäisyyden ylläpitämiseksi?
V: On olemassa erilaisia algoritmeja välimuistien yhtenäisyyden ylläpitämiseksi, kun jaettuun dataan käytetään useita itsenäisiä välimuisteja, kuten useita tietokantapalvelimia, jotka päivittävät yhtä jaettua datatiedostoa.
