Algoritem predpomnilnika
Algoritem predpomnilnika je algoritem, ki se uporablja za upravljanje predpomnilnika ali skupine podatkov. Ko je predpomnilnik poln, se odloči, kateri element je treba izbrisati iz predpomnilnika. Beseda hit rate (stopnja zadetkov) opisuje, kako pogosto je mogoče iz predpomnilnika postreči z zahtevo. Izraz zakasnitev opisuje, kako dolgo je mogoče dobiti element iz predpomnilnika. Aloritmi predpomnilnika so kompromis med stopnjo zadetkov in zakasnitvijo.
- Najučinkovitejši algoritem za predpomnjenje bi bil, da bi vedno zavrgli informacije, ki jih v prihodnosti ne bomo potrebovali najdlje. Ta optimalni rezultat se imenuje Beladyjev optimalni algoritem ali jasnovidni algoritem. Ker je na splošno nemogoče predvideti, kako daleč v prihodnosti bodo informacije potrebne, tega v praksi na splošno ni mogoče izvesti. Praktični minimum je mogoče izračunati šele po eksperimentiranju, učinkovitost dejansko izbranega algoritma predpomnilnika pa je mogoče primerjati z optimalnim minimumom.
- Najmanjkrat uporabljeni (LRU): najprej izbriše najmanjkrat uporabljene elemente. Pri tem algoritmu je treba spremljati, kaj je bilo kdaj uporabljeno. To je drago, če želimo zagotoviti, da algoritem vedno zavrže najmanj uporabljen element. Splošne izvedbe te tehnike zahtevajo, da se za vrstice predpomnilnika hranijo "starostni biti" in da se na podlagi starostnih bitov sledi vrstici predpomnilnika, ki je "najmanj uporabljena". Pri taki izvedbi se ob vsaki uporabi vrstice predpomnilnika spremeni starost vseh drugih vrstic predpomnilnika. LRU je pravzaprav družina algoritmov predpomnilnika, ki vključuje naslednje člane: 2Q Theodorja Johnsona in Dennisa Shashe ter LRU/K Pata O'Neila, Betty O'Neil in Gerharda Weikuma.
- Najnovejše uporabljene (MRU): Ta algoritem najprej izbriše nazadnje uporabljene elemente. Ta mehanizem predpomnjenja se pogosto uporablja za predpomnilnike podatkovnih baz.
- Psevdo-LRU (PLRU): V nekaterih primerih je LRU zelo težko izvesti. V takih primerih je morda dovolj, da vemo, da se v večini primerov izbriše eden od najmanj uporabljenih elementov. Tu se lahko uporabi algoritem PLRU, saj za svoje delovanje potrebuje le en bit na element predpomnilnika.
- dvosmerni asociativni niz: za hitre predpomnilnike procesorjev, kjer je tudi PLRU prepočasen. Naslov novega elementa se uporabi za izračun enega od dveh možnih mest v predpomnilniku, kamor se lahko postavi. LRU od obeh se zavrže. To zahteva en bit na par vrstic predpomnilnika, da se označi, katera od obeh je bila nazadnje uporabljena.
- Predpomnilnik z neposrednim prikazom: za najhitrejše predpomnilnike procesorja, kjer so tudi dvosmerni asociativni predpomnilniki prepočasni. Naslov novega elementa se uporabi za izračun ene lokacije v predpomnilniku, kamor se sme premakniti. Vse, kar je bilo tam prej, se zavrže.
- Najredkeje uporabljeni (LFU): LFU šteje, kako pogosto je element potreben. Predmeti, ki se uporabljajo najmanj pogosto, se zavržejo prvi.
- Prilagodljivi nadomestni predpomnilnik (ARC): nenehno usklajuje med LRU in LFU ter tako izboljša skupni rezultat.
- Algoritem predpomnilnika za več čakalnih vrst (MQ): Philbin in Kai Li).
Druge stvari, ki jih je treba upoštevati:
- Predmeti z različnimi stroški: obdržite predmete, ki jih je drago pridobiti, npr. tiste, za katere je potrebno veliko časa.
- Predmeti, ki zasedajo več predpomnilnika: Če so predmeti različnih velikosti, bo predpomnilnik morda želel zavreči velik predmet, da bi shranil več manjših.
- Predmeti, ki s časom potečejo: Nekateri predpomnilniki hranijo informacije, ki potečejo (npr. predpomnilnik za novice, predpomnilnik DNS ali predpomnilnik spletnega brskalnika). Računalnik lahko zavrže elemente, ker jim je potekel rok trajanja. Glede na velikost predpomnilnika morda ne bo potreben dodaten algoritem za zavračanje elementov.
Obstajajo tudi različni algoritmi za vzdrževanje koherence predpomnilnika. To velja le za primere, ko se za iste podatke uporablja več neodvisnih predpomnilnikov (na primer več strežnikov podatkovnih zbirk, ki posodabljajo eno skupno datoteko s podatki).
Katera pomnilniška mesta je mogoče shraniti v predpomnilnik, katera mesta predpomnilnika
Vprašanja in odgovori
V: Kaj je algoritem predpomnilnika?
O: Algoritem predpomnilnika je algoritem, ki se uporablja za upravljanje predpomnilnika ali skupine podatkov. Z njim se odloči, kateri element je treba izbrisati iz predpomnilnika, ko je ta poln.
V: Kaj je stopnja zadetkov?
O: Stopnja zadetkov opisuje, kako pogosto je mogoče iz predpomnilnika obdelati zahtevo.
V: Kaj opisuje zakasnitev?
O: Zakasnitev opisuje, kako dolgo je mogoče dobiti element iz predpomnilnika.
V: Kaj je Beladyjev optimalni algoritem?
O: Beladyjev optimalni algoritem, znan tudi kot jasnovidni algoritem, je učinkovit algoritem predpomnilnika, ki vedno zavrže informacije, ki jih v prihodnosti ne bomo potrebovali najdlje. Tega rezultata na splošno ni mogoče izvesti v praksi, ker zahteva predvidevanje, kaj bo potrebno daleč v prihodnosti.
V: Kako deluje sistem LRU (Least Recently Used)?
O: LRU najprej izbriše najmanj nedavno uporabljene elemente in zahteva sledenje, kaj je bilo kdaj uporabljeno, z uporabo "bitov starosti" za vsako vrstico predpomnilnika in sledenjem, katera je bila nazadnje uporabljena na podlagi bitov starosti. Vsakič, ko je uporabljena vrstica predpomnilnika, se starost vseh drugih vrstic predpomnilnika ustrezno spremeni.
V: Kako deluje funkcija MRU (Most Recent Used)?
O: MRU najprej izbriše nazadnje uporabljene elemente in ta mehanizem predpomnjenja se pogosto uporablja za predpomnilnike podatkovnih baz.
V: Kateri drugi algoritmi obstajajo za ohranjanje skladnosti predpomnilnika?
O: Obstajajo različni algoritmi za ohranjanje skladnosti predpomnilnika, kadar se za skupne podatke uporablja več neodvisnih predpomnilnikov, na primer več strežnikov zbirke podatkov, ki posodabljajo eno samo skupno datoteko s podatki.
