Algoritmus vyrovnávacej pamäte
Algoritmus vyrovnávacej pamäte je algoritmus používaný na správu vyrovnávacej pamäte alebo skupiny údajov. Keď je vyrovnávacia pamäť plná, rozhodne, ktorá položka sa má z vyrovnávacej pamäte odstrániť. Slovo hit rate (miera zásahu) opisuje, ako často môže byť požiadavka obslúžená z vyrovnávacej pamäte. Výraz latencia opisuje, za ako dlho možno získať položku z vyrovnávacej pamäte. Aloritmy vyrovnávacej pamäte sú kompromisom medzi rýchlosťou zásahu a oneskorením.
- Najefektívnejším algoritmom ukladania do vyrovnávacej pamäte by bolo vždy zahodiť informácie, ktoré nebudú v budúcnosti najdlhšie potrebné. Tento optimálny výsledok sa označuje ako Beladyho optimálny algoritmus alebo jasnovidecký algoritmus. Keďže vo všeobecnosti nie je možné predpovedať, ako ďaleko v budúcnosti bude informácia potrebná, v praxi je tento algoritmus spravidla nerealizovateľný. Praktické minimum sa dá vypočítať až po experimentovaní a možno porovnať účinnosť skutočne zvoleného algoritmu vyrovnávacej pamäte s optimálnym minimom.
- Najmenej používané (LRU): najprv odstráni najmenej používané položky. Tento algoritmus vyžaduje sledovanie toho, čo bolo kedy použité. Je to nákladné, ak chceme zabezpečiť, aby algoritmus vždy vyradil najmenej použitú položku. Všeobecné implementácie tejto techniky vyžadujú uchovávanie "bitov veku" pre riadky vyrovnávacej pamäte a sledovanie "najmenej použitého" riadku vyrovnávacej pamäte na základe bitov veku. Pri takejto implementácii sa pri každom použití riadku vyrovnávacej pamäte zmení vek všetkých ostatných riadkov vyrovnávacej pamäte. LRU je v skutočnosti rodina algoritmov vyrovnávacej pamäte, ktorej členmi sú: 2Q od Theodora Johnsona a Dennisa Shasha a LRU/K od Pata O'Neila, Betty O'Neilovej a Gerharda Weikuma.
- Najnovšie použité (MRU): Tento algoritmus vymaže ako prvé naposledy použité položky. Tento mechanizmus ukladania do vyrovnávacej pamäte sa bežne používa pre databázové vyrovnávacie pamäte.
- Pseudo-LRU (PLRU): V niektorých prípadoch je implementácia LRU veľmi náročná. V takýchto prípadoch môže stačiť vedieť, že vo väčšine prípadov sa vymaže jedna z najmenej používaných položiek. Tam sa môže použiť algoritmus PLRU, pretože na svoju činnosť potrebuje len jeden bit na položku vyrovnávacej pamäte.
- 2-cestná asociatívna sada: pre vysokorýchlostné vyrovnávacie pamäte CPU, kde je aj PLRU príliš pomalá. Adresa novej položky sa používa na výpočet jedného z dvoch možných miest v cache, kam sa môže umiestniť. LRU z týchto dvoch sa vyradí. To si vyžaduje jeden bit na dvojicu riadkov vyrovnávacej pamäte, aby sa označilo, ktoré z týchto dvoch miest bolo naposledy použité.
- Priamo mapovaná vyrovnávacia pamäť: pre najrýchlejšie vyrovnávacie pamäte CPU, kde sú aj 2-cestné asociatívne vyrovnávacie pamäte príliš pomalé. Adresa nového prvku sa použije na výpočet jedného miesta v cache, kam sa môže dostať. Čokoľvek, čo tam bolo predtým, sa vyradí.
- Najmenej často používané (LFU): LFU počíta, ako často je položka potrebná. Tie, ktoré sa používajú najmenej často, sa vyradia ako prvé.
- Adaptívna náhradná vyrovnávacia pamäť (ARC): neustále vyvažuje medzi LRU a LFU s cieľom zlepšiť kombinovaný výsledok.
- Algoritmus vyrovnávacej pamäte Multi Queue (MQ): Philbin a Kai Li).
Ďalšie veci, ktoré je potrebné zvážiť:
- Položky s rôznou cenou: ponechajte si položky, ktorých získanie je drahé, napr. tie, ktorých získanie trvá dlho.
- Položky, ktoré zaberajú viac medzipamäte: Ak majú položky rôznu veľkosť, môže sa stať, že cache bude chcieť vyradiť veľkú položku, aby sa do nej uložilo niekoľko menších.
- Položky, ktorých platnosť sa časom končí: Niektoré vyrovnávacie pamäte uchovávajú informácie, ktorých platnosť uplynie (napr. vyrovnávacia pamäť správ, vyrovnávacia pamäť DNS alebo vyrovnávacia pamäť webového prehliadača). Počítač môže vyradiť položky, pretože ich platnosť vypršala. V závislosti od veľkosti vyrovnávacej pamäte nemusí byť potrebný žiadny ďalší algoritmus na vyradenie položiek.
Existujú aj rôzne algoritmy na udržiavanie koherencie vyrovnávacej pamäte. To sa týka len situácie, keď sa pre rovnaké údaje používa viacero nezávislých vyrovnávacích pamätí (napríklad viacero databázových serverov aktualizuje jeden zdieľaný súbor údajov).
Ktoré miesta pamäte možno ukladať do vyrovnávacej pamäte pomocou ktorých miest vyrovnávacej pamäte
Otázky a odpovede
Otázka: Čo je to algoritmus vyrovnávacej pamäte?
Odpoveď: Algoritmus vyrovnávacej pamäte je algoritmus používaný na správu vyrovnávacej pamäte alebo skupiny údajov. Rozhoduje o tom, ktorá položka sa má z vyrovnávacej pamäte vymazať, keď je plná.
Otázka: Čo je to miera zásahov?
Odpoveď: Hit rate opisuje, ako často môže byť požiadavka obslúžená z vyrovnávacej pamäte.
Otázka: Čo opisuje latencia?
Odpoveď: Latencia opisuje, za ako dlho možno získať položku z vyrovnávacej pamäte.
Otázka: Čo je Beladyho optimálny algoritmus?
Odpoveď: Beladyho optimálny algoritmus, známy aj ako jasnovidecký algoritmus, je efektívny algoritmus vyrovnávacej pamäte, ktorý vždy vyradí informácie, ktoré nebudú v budúcnosti najdlhšie potrebné. Tento výsledok sa vo všeobecnosti nedá realizovať v praxi, pretože si vyžaduje predvídať, čo bude potrebné v ďalekej budúcnosti.
Otázka: Ako funguje systém LRU (Least Recently Used)?
Odpoveď: LRU odstraňuje najmenej používané položky ako prvé a vyžaduje si sledovanie toho, čo sa kedy použilo, pomocou "vekových bitov" pre každý riadok vyrovnávacej pamäte a sledovanie toho, ktorý z nich sa použil najmenej nedávno na základe vekových bitov. Pri každom použití riadku vyrovnávacej pamäte sa zodpovedajúcim spôsobom zmení vek všetkých ostatných riadkov vyrovnávacej pamäte.
Otázka: Ako funguje funkcia MRU (Most Recently Used)?
Odpoveď: MRU najprv odstráni naposledy použité položky a tento mechanizmus ukladania do vyrovnávacej pamäte sa bežne používa pre databázové vyrovnávacie pamäte.
Otázka: Aké ďalšie algoritmy existujú na udržiavanie koherencie vyrovnávacej pamäte?
Odpoveď: Existujú rôzne algoritmy na udržiavanie koherencie vyrovnávacej pamäte, keď sa pre zdieľané údaje používa viacero nezávislých vyrovnávacích pamätí, napríklad keď viaceré databázové servery aktualizujú jeden zdieľaný súbor údajov.
