Gyorsítótárazási algoritmusok ( preemption algorithms , preemption policy és "replacement algorithms / policy") - a számítástechnikában ez az utasításoptimalizálás : egy speciális számítógépes program vagy hardver által támogatott struktúra, amely képes kezelni a számítógépben tárolt információk gyorsítótárát . Amikor a gyorsítótár megtelik, az algoritmusnak ki kell választania, hogy pontosan mit kell eltávolítani belőle, hogy új, naprakészebb információkat tudjon írni (a gyorsítótárba). Ezen algoritmusok hardveres megvalósítása magában foglalja az időzítő , a számláló vagy a kettő kombinációjának használatát.
A gyorsítótárban lévő "találati arány" arra utal, hogy a keresett adatok milyen gyakran találhatók meg a gyorsítótárban. A hatékonyabb kilakoltatási szabályzatok nyomon követik a leggyakrabban használt információkhoz való hozzáférést, hogy javítsák a találati arányt (azonos gyorsítótár-méret esetén).
A gyorsítótár „latenciája” arra utal, hogy a gyorsítótár milyen gyorsan tudja visszaadni a kért adatokat közvetlenül a kérés után ("találat" esetén). A gyorsabb kilakoltatási stratégiák jellemzően nyomon követik a legkevésbé használt információkat – vagy közvetlenül leképezett gyorsítótár esetén az információhiányt –, hogy csökkentsék az információ frissítéséhez szükséges időt.
Minden eltolási stratégia kompromisszum a találati arány és a késleltetés között.
A leghatékonyabb kilakoltatási szabály az, ha a gyorsítótárból el kell dobni azokat az információkat, amelyekre a jövőben nem lesz a leghosszabb szükség. Ezt az optimális gyorsítótárazási algoritmust Beladi -algoritmusnak vagy előrelátási algoritmusnak nevezték el . Mivel általános esetben lehetetlen megjósolni, hogy legközelebb pontosan mikor lesz szükség erre az információra, a gyakorlatban (általános esetben is) egy ilyen megvalósítás lehetetlen. A gyakorlati minimumot csak empirikusan lehet kiszámítani, ami után összevethető vele az aktuális gyorsítótárazási algoritmus hatékonysága.
Legkevésbé használt (LRU): Mindenekelőtt a leghosszabb ideig használaton kívüli kerül kiszorításra. Ez az algoritmus megköveteli, hogy nyomon kövesse, hogy mit és mikor használtak, ami meglehetősen költséges lehet, különösen, ha további ellenőrzést kell végeznie a biztonság érdekében. Ennek a módszernek az általános megvalósítása megköveteli, hogy a gyorsítótár soraihoz egy "életkor bitet" tartsunk, és ezzel nyomon követjük a legkevésbé használt sorokat (vagyis az ilyen bitek összehasonlításával). Egy ilyen megvalósításban minden egyes gyorsítótár-sor elérésekor az összes többi sor „életkora” megváltozik. Az LRU valójában egy gyorsítótárazási algoritmuscsalád , amely magában foglalja a Theodore Johnson és Dennis Schasha által készített 2Q -t, valamint Pat O'Neill, Betty O'Neill és Gerhard Weikum LRU/K-ját.
Legutóbb használt (MRU): Az LRU-val ellentétben a legutóbb használt elemet helyezik ki először. A forrás szerint [1] : "Ha egy fájlt időszakonként körbevizsgálnak, az MRU a legjobb kilakoltatási algoritmus." A [2] -ban a szerzők azt is hangsúlyozzák, hogy a véletlen hozzáférésű sémák és a nagy adathalmazok ciklikus pásztázása esetén (ezt néha körmérkőzéses sémáknak is nevezik) az MRU gyorsítótárazási algoritmusok több találatot érnek el az LRU-hoz képest, mivel hajlamosak megőrizni a régi adatokat. Az MRU algoritmusok olyan esetekben a leghasznosabbak, amikor minél régebbi az elem, annál több hozzáférés történik hozzá.
Pseudo-LRU (PLRU): A nagy asszociativitással rendelkező gyorsítótárak (általában több mint 4 csatornát) esetén az LRU megvalósításához szükséges erőforrások túl nagyok lesznek. Ha a házirend elegendő ahhoz, hogy szinte mindig eldobja a legkevésbé használt bejegyzést, akkor ebben az esetben a PLRU algoritmus használható, amely gyorsítótár-bejegyzésenként csak egy bitet igényel.
Szegmentált LRU (vagy SLRU): „Az SLRU gyorsítótár két szegmensre van osztva: egy próbaszegmensre és egy védett szegmensre. Az egyes szegmensek sorai a leggyakrabban használttól a legkevésbé használtig vannak rendezve. A kihagyásokra vonatkozó adatok hozzáadódnak a gyorsítótárhoz és a próbaszegmens utoljára használt elemeihez. A találatokra vonatkozó adatokat a rendszer eltávolítja, bárhol is található, és hozzáadja a védett szegmens gyakran használt elemeinek területéhez. A védett szegmenssorok így legalább kétszer érhetők el. A védett szegmens korlátozott. Egy ilyen vonalátvitel a próbaszegmensről a védett szegmensre azt eredményezheti, hogy a védett szegmensben az utoljára használt (LRU) sor átkerül a próbaszegmens MRU területére, így ez a vonal egy második esélyt ad a használatára, mielőtt az kilakoltatták. A védett szegmens mérete egy SLRU paraméter, amely az I/O sémától függően változik. Amikor adatokat kell kiüríteni a gyorsítótárból, a rendszer sorokat kér a vizsgáló szegmens LRU végétől. [3] »
A kétirányú asszociativitás a nagy sebességű processzor gyorsítótáraira vonatkozik , ahol még a PLRU is túl lassú. Az új elem címe a gyorsítótárban (az erre kijelölt területen) lévő két lehetséges hely egyikének kiszámítására szolgál. Az LRU algoritmus szerint két elemet eltolunk. Egy bitet igényel néhány gyorsítótár-sorhoz , hogy jelezze, melyiket használták utoljára.
Közvetlen leképezett gyorsítótár : Nagy sebességű processzoros gyorsítótárak számára, ahol a kétirányú asszociatív gyorsítótár teljesítménye hiányzik. Az új elem címe a gyorsítótárban (az erre kijelölt területen) lévő hely kiszámítására szolgál. Mindent kicserélnek, ami korábban volt.
Least Frequently Used (LFU): Az LFU számolja, hogy milyen gyakran használnak egy elemet. Azok az elemek, amelyekhez a legritkábban férnek hozzá, először megelőzhetők.
Adaptive Replacement Cache (ARC): [4] folyamatosan egyensúlyoz az LRU és az LFU között, ami javítja a végeredményt.
Multi Queue (MQ) gyorsítótárazási algoritmus : [5] (fejlesztő: Y. Zhu, J. F. Philbin és Kai Li).
A következő pontokat veszik figyelembe:
Különféle algoritmusok is rendelkezésre állnak a gyorsítótár koherenciájának biztosítására . Ez csak olyan esetekben érvényes, amikor több független gyorsítótárat használnak ugyanazon információk tárolására (például több adatbázis-kiszolgáló frissít egy közös adatfájlt).