Kešatmiņas algoritms
Kešatmiņas algoritms ir algoritms, ko izmanto kešatmiņas vai datu grupas pārvaldībai. Kad kešatmiņa ir pilna, tas izlemj, kurš vienums ir jāizdzēš no kešatmiņas. Vārds hit rate (trāpījumu biežums) raksturo, cik bieži pieprasījums var tikt apkalpots no kešatmiņas. Termins latence apraksta, cik ilgi var saņemt kešatmiņā esošo elementu. Kešatmiņas aloritmi ir kompromiss starp trāpījumu skaitu un kavēšanos.
- Visefektīvākais kešēšanas algoritms būtu vienmēr izmest informāciju, kas nebūs nepieciešama visilgāk nākotnē. Šo optimālo rezultātu dēvē par Beladija optimālo algoritmu jeb gaišreģa algoritmu. Tā kā parasti nav iespējams paredzēt, cik tālu nākotnē informācija būs nepieciešama, praksē tas parasti nav īstenojams. Praktisko minimumu var aprēķināt tikai pēc eksperimenta, un var salīdzināt faktiski izvēlētā kešēšanas algoritma efektivitāti ar optimālo minimumu.
- Vismazāk pēdējā laikā izmantotie (LRU): vispirms tiek dzēsti vismazāk izmantotie vienumi. Šis algoritms prasa sekot līdzi tam, kas un kad tika izmantots. Tas ir dārgi, ja vēlamies nodrošināt, lai algoritms vienmēr izmet vismazāk izmantoto elementu. Šīs metodes vispārējā implementācijā kešatmiņas līnijām ir jāuzglabā "vecuma biti" un, pamatojoties uz vecuma bitiem, jāseko līdzi "vismazāk pēdējā laikā izmantotajai" kešatmiņas līnijai. Šādā implementācijā katru reizi, kad tiek izmantota kešlīnija, mainās visu pārējo kešlīniju vecums. LRU faktiski ir kešatmiņas algoritmu saime, kurā ietilpst šādi algoritmi: Teodora Džonsona (Theodore Johnson) un Denisa Šašas (Dennis Shasha) izstrādātais 2Q un Pata O'Nīla (Pat O'Neil), Betijas O'Nīlas (Betty O'Neil) un Gerharda Veikuma (Gerhard Weikum) izstrādātais LRU/K.
- Pēdējo reizi izmantots (MRU): Šis algoritms vispirms izdzēš visnesenāk izmantotos vienumus. Šo kešēšanas mehānismu parasti izmanto datubāzes atmiņas kešatmiņā.
- Pseido-LRU (PLRU): Ir gadījumi, kad LRU ir ļoti grūti īstenot. Šādos gadījumos var pietikt ar to, ka vairumā gadījumu tiek dzēsts viens no vismazāk izmantotajiem elementiem. Šajā gadījumā var izmantot PLRU algoritmu, jo tā darbībai ir nepieciešams tikai viens bits katram kešatmiņas elementam.
- 2-virzienu asociatīvais komplekts: ātrdarbīgiem procesora kešatmiņas kešatmiņas procesoriem, kur pat PLRU ir pārāk lēna. Jaunā elementa adrese tiek izmantota, lai aprēķinātu vienu no divām iespējamām vietām kešatmiņā, kur to drīkst ievietot. LRU no abām tiek noraidīta. Tam nepieciešams viens bits katram kešatmiņas līniju pārim, lai norādītu, kura no šīm divām vietām bija vismazāk izmantotā.
- Tiešā kartētā kešatmiņa: visātrākajiem procesora kešatmiņas režīmiem, ja pat divvirzienu asociatīvā kešatmiņa ir pārāk lēna. Jaunā elementa adrese tiek izmantota, lai aprēķinātu vienu vietu kešatmiņā, kur to drīkst ievietot. Tas, kas tur bija pirms tam, tiek noraidīts.
- Visretāk izmantotie (LFU): LFU aprēķina, cik bieži ir nepieciešams konkrētais priekšmets. Vismazāk izmantotās preces tiek izmestas pirmās.
- Adaptīvā aizvietošanas kešatmiņa (Adaptive Replacement Cache, ARC): pastāvīgi balansē starp LRU un LFU, lai uzlabotu kopējo rezultātu.
- Vairāku rindu (MQ) kešēšanas algoritms: Zhou J.F. Philbin un Kai Li).
Citas lietas, kas jāņem vērā:
- Priekšmeti ar atšķirīgām izmaksām: saglabājiet priekšmetus, kuru iegūšana ir dārga, piemēram, priekšmetus, kuru iegūšanai nepieciešams ilgs laiks.
- Vienības, kas aizņem vairāk kešatmiņas: Ja vienībām ir atšķirīgi izmēri, kešatmiņā var būt nepieciešams izmest lielu vienību, lai uzglabātu vairākas mazākas vienības.
- Priekšmeti, kuru derīguma termiņš ar laiku beidzas: Dažās kešatmiņas tiek saglabāta informācija, kuras derīguma termiņš beidzas (piemēram, ziņu kešatmiņa, DNS kešatmiņa vai tīmekļa pārlūkprogrammas kešatmiņa). Dators var izmest vienumus, jo to derīguma termiņš ir beidzies. Atkarībā no kešatmiņas lieluma papildu kešēšanas algoritms, kas izmet vienumus, var nebūt nepieciešams.
Pastāv arī dažādi algoritmi kešatmiņas saskaņotības uzturēšanai. Tas attiecas tikai uz gadījumiem, kad vieniem un tiem pašiem datiem tiek izmantoti vairāki neatkarīgi kešatmiņas serveri (piemēram, vairāki datubāzes serveri, kas atjaunina vienu koplietošanas datu datni).
Kuras atmiņas vietas var tikt kešētas, kuras kešatmiņas vietas
Jautājumi un atbildes
J: Kas ir kešatmiņas algoritms?
A: Kešatmiņas algoritms ir algoritms, ko izmanto kešatmiņas vai datu grupas pārvaldībai. Tas izlemj, kurš vienums jāizdzēš no kešatmiņas, kad tā ir pilna.
J: Kas ir trāpījuma rādītājs?
A: Hit rate raksturo, cik bieži pieprasījums var tikt izpildīts no kešatmiņas.
J: Ko raksturo latence?
A: Latence raksturo, cik ilgi var saņemt kešatmiņā esošo elementu.
J: Kas ir Beladija optimālais algoritms?
A: Beladija optimālais algoritms, ko dēvē arī par gaišreģa algoritmu, ir efektīvs kešatmiņas algoritms, kas vienmēr izmet informāciju, kura nebūs vajadzīga visilgākā laika posmā nākotnē. Šo rezultātu parasti nav iespējams īstenot praksē, jo tam nepieciešams paredzēt, kas būs vajadzīgs tālā nākotnē.
J: Kā darbojas LRU (Least Recently Used)?
A: LRU vispirms dzēš vismazāk nesen izmantotos elementus, un tam ir jāseko līdzi tam, kas un kad tika izmantots, izmantojot "vecuma bitus" katrai kešatmiņas līnijai un izsekojot, kura no tām tika izmantota vismazāk nesen, pamatojoties uz vecuma bitiem. Katru reizi, kad tiek izmantota kešatmiņas līnija, attiecīgi tiek mainīts visu pārējo kešatmiņas līniju vecums.
J: Kā darbojas visnesenāk izmantotais (MRU)?
A: MRU vispirms izdzēš visnesenāk izmantotos vienumus, un šo kešēšanas mehānismu parasti izmanto datubāzu atmiņas kešatmiņā.
J: Kādi citi algoritmi pastāv, lai saglabātu kešatmiņas saskaņotību?
A; Pastāv dažādi algoritmi, lai saglabātu kešatmiņas saskaņotību, ja koplietojamiem datiem izmanto vairākas neatkarīgas kešatmiņas, piemēram, ja vairāki datubāzes serveri atjaunina vienu koplietojamu datu datni.
