Cache algoritm
Cache-algoritm on algoritm, mida kasutatakse vahemälu või andmegrupi haldamiseks. Kui vahemälu on täis, otsustab see, milline kirje tuleks vahemälust kustutada. Sõna hit rate kirjeldab, kui sageli saab vahemälust päringut teenindada. Mõiste latentsus kirjeldab, kui kaua on võimalik vahemällu salvestatud objekti saada. Vahemälu algoritmid on kompromiss tabavuse ja latentsuse vahel.
- Kõige tõhusam vahemälu algoritm oleks alati ära visata teave, mida ei vajata kõige kauem tulevikus. Seda optimaalset tulemust nimetatakse Belady optimaalseks algoritmiks või selgeltnägija algoritmiks. Kuna üldiselt on võimatu ennustada, kui kaugel tulevikus teavet vajatakse, ei ole see üldjuhul praktikas rakendatav. Praktilist miinimumi saab arvutada alles pärast katsetamist ja võrrelda tegelikult valitud vahemälu algoritmi tõhusust optimaalse miinimumiga.
- Viimati kasutatud (LRU): kustutab kõige vähem kasutatud elemendid esimesena. See algoritm nõuab jälgimist, mida millal kasutati. See on kallis, kui tahetakse tagada, et algoritm viskab alati kõige vähem kasutatud objekti. Selle meetodi üldised rakendused nõuavad vahemäluridade "vanusebittide" säilitamist ja "viimati kasutatud" vahemäluridade jälgimist vanusebittide alusel. Sellise rakenduse puhul muutub iga kord, kui vahemälurida kasutatakse, kõigi teiste vahemäluridade vanus. LRU on tegelikult vahemälualgoritmide perekond, mille liikmed on järgmised: Theodore Johnsoni ja Dennis Shasha 2Q ning Pat O'Neili, Betty O'Neili ja Gerhard Weikumi LRU/K.
- Viimati kasutatud (MRU): See algoritm kustutab kõige viimati kasutatud elemendid esimesena. Seda vahemälumehhanismi kasutatakse tavaliselt andmebaaside mälu vahemäludes.
- Pseudo-LRU (PLRU): On teatud juhtumeid, kus LRU-d on väga raske rakendada. Sellistel juhtudel võib piisata teadmisest, et enamasti kustutatakse üks kõige vähem kasutatud elementidest. Seal võib kasutada PLRU algoritmi, sest see vajab töötamiseks ainult ühte bitti iga vahemälu elemendi kohta.
- 2-suunaline assotsiatiivne kogum: kiire protsessori vahemälu jaoks, kus isegi PLRU on liiga aeglane. Uue elemendi aadressi alusel arvutatakse üks kahest võimalikust kohast vahemälus, kuhu see võib minna. LRU kahest visatakse kõrvale. Selleks on vaja ühte bitti iga vahemälu rea paari kohta, et näidata, kumba neist kahest on viimati kasutatud.
- Otse kaardistatud vahemälu: kõige kiirematele protsessori vahemäludele, kus isegi 2-suunalised assotsiatiivsed vahemälud on liiga aeglased. Uue elemendi aadressi alusel arvutatakse üks koht vahemälus, kuhu see võib minna. See, mis oli seal enne, jäetakse kõrvale.
- Kõige harvemini kasutatav (LFU): LFU loeb, kui sageli on eset vaja. Kõige harvemini kasutatavad esemed visatakse esimesena kõrvale.
- Adaptive Replacement Cache (ARC): tasakaalustab pidevalt LRU ja LFU vahel, et parandada kombineeritud tulemust.
- Multi Queue (MQ) vahemälu algoritm: (Y. Zhou J.F. Philbin ja Kai Li).
Muud asjad, mida tuleks arvesse võtta:
- Erineva maksumusega esemed: hoidke alles esemed, mille hankimine on kallis, nt need, mille hankimine võtab kaua aega.
- Suurema vahemälu hõivavad esemed: Kui esemed on erineva suurusega, võib vahemälu tahta visata suure elemendi, et salvestada mitu väiksemat.
- Esemed, mis aeguvad aja jooksul: Mõned vahemälud säilitavad teavet, mis aegub (nt uudiste vahemälu, DNS vahemälu või veebibrauseri vahemälu). Arvuti võib elemendid ära visata, sest nende kehtivusaeg on lõppenud. Sõltuvalt vahemälu suurusest ei pruugi edasine vahemälu algoritm elementide kõrvalejätmiseks olla vajalik.
Erinevad algoritmid on olemas ka vahemälu sidususe säilitamiseks. See kehtib ainult olukorras, kus samade andmete jaoks kasutatakse mitut sõltumatut vahemälu (näiteks mitu andmebaasiserverit, mis uuendavad ühte ühist andmefaili).
Milliseid mälukohti saab vahemällu salvestada milliste vahemälukohtade kaupa
Küsimused ja vastused
K: Mis on vahemälu algoritm?
V: Cache-algoritm on algoritm, mida kasutatakse vahemälu või andmegrupi haldamiseks. See otsustab, millised elemendid tuleks vahemälust kustutada, kui see on täis.
K: Mis on tabamuse määr?
V: Osutamismäär kirjeldab, kui sageli saab vahemälust päringut teenindada.
K: Mida kirjeldab latentsus?
V: Viivitus kirjeldab, kui kaua on võimalik vahemällu salvestatud objekti saada.
K: Mis on Belady optimaalne algoritm?
V: Belady optimaalne algoritm, mida nimetatakse ka selgeltnägija algoritmiks, on tõhus vahemälualgoritm, mis heidab alati kõrvale teabe, mida ei vajata kõige kauem tulevikus. Seda tulemust ei saa üldjuhul praktikas rakendada, sest see eeldab, et tuleb ennustada, mida vajatakse kaugele tulevikku.
K: Kuidas töötab LRU (Least Recently Used)?
V: LRU kustutab kõige harvemini kasutatud elemendid esimesena ja nõuab, et iga vahemäluriba puhul jälgitakse, mida millal kasutati, kasutades "vanusebitte" ja jälgides vanusebittide põhjal, millist neist kasutati kõige vähem. Iga kord, kui vahemälu rida kasutatakse, muudetakse vastavalt ka kõigi teiste vahemäluridade vanust.
K: Kuidas töötab kõige hiljuti kasutatud (MRU)?
V: MRU kustutab kõige viimati kasutatud elemendid esimesena ja seda vahemälumehhanismi kasutatakse tavaliselt andmebaaside mälu vahemäludes.
K: Millised muud algoritmid on olemas vahemälu sidususe säilitamiseks?
V: Erinevad algoritmid on olemas vahemälu sidususe säilitamiseks, kui jagatud andmete jaoks kasutatakse mitut sõltumatut vahemälu, näiteks kui mitu andmebaasiserverit ajakohastavad ühte ühist andmefaili.
