Cache algoritmus
A gyorsítótár algoritmus egy gyorsítótár vagy adatcsoport kezelésére használt algoritmus. Amikor a gyorsítótár megtelt, eldönti, hogy melyik elemet kell törölni a gyorsítótárból. A találati arány szó azt írja le, hogy egy kérést milyen gyakran lehet kiszolgálni a gyorsítótárból. A késleltetés kifejezés azt írja le, hogy mennyi idő alatt érhető el a gyorsítótárban tárolt elem. A gyorsítótár algoritmusok a találati arány és a késleltetés közötti kompromisszumot jelentik.
- A leghatékonyabb gyorsítótárazási algoritmus az lenne, ha mindig azokat az információkat dobnánk ki, amelyekre a jövőben a leghosszabb ideig nem lesz szükség. Ezt az optimális eredményt Belady optimális algoritmusának vagy clairvoyant algoritmusnak nevezik. Mivel általában lehetetlen megjósolni, hogy az információra milyen hosszú időn belül lesz szükség, ez a gyakorlatban általában nem valósítható meg. A gyakorlati minimumot csak kísérletezés után lehet kiszámítani, és a ténylegesen választott cache-algoritmus hatékonyságát össze lehet hasonlítani az optimális minimummal.
- Legutóbb használt (LRU): a legkevésbé használt elemeket törli először. Ez az algoritmus megköveteli annak nyomon követését, hogy mit mikor használtak. Ez költséges, ha azt akarjuk, hogy az algoritmus mindig a legkevésbé használt elemet dobja ki. Ennek a technikának az általános megvalósításai megkövetelik a cache-sorok "korbitjeinek" vezetését és a "Legutóbb használt" cache-sorok nyomon követését a korbitek alapján. Az ilyen megvalósításban minden alkalommal, amikor egy gyorsítótár-sort használnak, az összes többi gyorsítótár-sor kora megváltozik. Az LRU tulajdonképpen a gyorsítótárazási algoritmusok egy családja, amelynek tagjai a következők: Theodore Johnson és Dennis Shasha által készített 2Q és Pat O'Neil, Betty O'Neil és Gerhard Weikum által készített LRU/K.
- Legutóbb használt (MRU): Ez az algoritmus először a legutóbb használt elemeket törli. Ezt a gyorsítótárazási mechanizmust általában az adatbázisok memória gyorsítótárában használják.
- Pszeudo-LRU (PLRU): Vannak bizonyos esetek, amikor az LRU-t nagyon nehéz megvalósítani. Ilyen esetekben elég lehet tudni, hogy a legtöbb esetben az egyik legkevésbé használt elemet törlik. A PLRU algoritmus ott használható, mert a működéséhez csak egy bitre van szüksége gyorsítótárelemenként.
- 2-way set associative: nagy sebességű CPU gyorsítótárakhoz, ahol még a PLRU is túl lassú. Egy új elem címét arra használjuk, hogy kiszámítsuk a gyorsítótár két lehetséges helyének egyikét, ahová kerülhet. A kettő közül az LRU-t elvetjük. Ehhez a gyorsítótár sorpáronként egy bitre van szükség, amely jelzi, hogy a kettő közül melyik volt a legkevésbé használt.
- Közvetlen leképezésű gyorsítótár: a legnagyobb sebességű CPU gyorsítótárakhoz, ahol még a 2-utas asszociatív gyorsítótárak is túl lassúak. Az új elem címét arra használjuk, hogy kiszámítsuk a gyorsítótárban azt az egy helyet, ahová az elem kerülhet. Ami korábban ott volt, azt el kell dobni.
- Legkevésbé gyakran használt (LFU): Az LFU azt számolja, hogy milyen gyakran van szükség egy elemre. A legkevésbé gyakran használtakat dobják ki először.
- Adaptive Replacement Cache (ARC): folyamatosan egyensúlyoz az LRU és az LFU között a kombinált eredmény javítása érdekében.
- Multi Queue (MQ) gyorsítótárazási algoritmus: (Y. Zhou J.F. Philbin és Kai Li).
Egyéb megfontolandó dolgok:
- Különböző költségű tételek: tartsd meg azokat a tételeket, amelyek beszerzése drága, például azokat, amelyek megszerzése hosszú időbe telik.
- Több gyorsítótárat foglaló elemek: Ha az elemek különböző méretűek, előfordulhat, hogy a gyorsítótár el akar dobni egy nagy elemet, hogy több kisebbet tároljon.
- Idővel lejáró tételek: Egyes gyorsítótárak olyan információkat tárolnak, amelyek lejárnak (pl. egy hírcache, egy DNS-cache vagy egy webböngésző cache). A számítógép eldobhat elemeket, mert azok lejártak. A gyorsítótár méretétől függően előfordulhat, hogy nincs szükség további gyorsítótárazási algoritmusra az elemek selejtezéséhez.
A gyorsítótárak koherenciájának fenntartására is léteznek különböző algoritmusok. Ez csak olyan helyzetekre vonatkozik, amikor több független gyorsítótárat használnak ugyanazon adatokhoz (például több adatbázis-kiszolgáló frissíti az egyetlen közös adatfájlt).
Mely memóriahelyeket milyen gyorsítótárhelyekkel lehet gyorsítótárazni
Kérdések és válaszok
K: Mi az a gyorsítótár algoritmus?
V: A gyorsítótár algoritmus egy gyorsítótár vagy adatcsoport kezelésére használt algoritmus. Ez dönti el, hogy melyik elemet kell törölni a gyorsítótárból, amikor az megtelt.
K: Mi a találati arány?
V: A találati arány azt írja le, hogy egy kérést milyen gyakran lehet kiszolgálni a gyorsítótárból.
K: Mit ír le a késleltetés?
V: A késleltetés azt írja le, hogy mennyi idő alatt érhető el a gyorsítótárban tárolt elem.
K: Mi a Belady-féle optimális algoritmus?
V: A Belady optimális algoritmusa, más néven clairvoyant algoritmus, egy hatékony gyorsítótárazási algoritmus, amely mindig elveti azokat az információkat, amelyekre a jövőben a leghosszabb ideig nem lesz szükség. Ez az eredmény általában nem valósítható meg a gyakorlatban, mert meg kell jósolni, hogy mire lesz szükség messze a jövőben.
K: Hogyan működik az LRU (Least Recently Used)?
V: Az LRU először a legkevésbé használt elemeket törli, és az egyes gyorsítótár-sorok "korbitjeinek" használatával követni kell, hogy mit mikor használtak, és a korbitek alapján nyomon kell követni, hogy melyik volt a legkevésbé használt. Minden egyes alkalommal, amikor egy gyorsítótár-sort használnak, az összes többi gyorsítótár-sor kora ennek megfelelően módosul.
K: Hogyan működik a Legutóbb használt (MRU)?
V: Az MRU először a legutóbb használt elemeket törli, és ezt a gyorsítótárazási mechanizmust általában adatbázis-memória gyorsítótárakban használják.
K: Milyen más algoritmusok léteznek a gyorsítótár-koherencia fenntartására?
V: Különböző algoritmusok léteznek a gyorsítótár-koherencia fenntartására, amikor több független gyorsítótárat használnak megosztott adatokra, például több adatbázis-kiszolgáló frissít egy közös adatfájlt.
