Kešatmiņa

Kešatmiņa (no angļu: cache — 'krātuve') ir atmiņa, kurai pieejas laiks ir ievērojami mazāks nekā operatīvajai atmiņai. Kešatmiņu izmanto kā buferatmiņu starp procesoru un operatīvo atmiņu. Ar kešatmiņas palīdzību samazinās vidējais piekļūšanas laiks un palielinās kopējais datora sistēmas ražīgums. Tiešā piekļūšana pie datiem, kas atrodas kešatmiņā, ar programmu pieeju nav iespējama.

Vēsture

Pirmo reizi vārdu „kešatmiņa” datorkontekstā izmantoja 1967. gadā, kad žurnālā „IBM Systems Journal” publicēšanai tika sagatavots raksts par atmiņas pilnveidošanu jaunajā modeļā 85 no sērijas IBM System/360. Žurnāla redaktors Lails Džonsons palūdza izdomāt aprakstošāko terminu nekā „ātrgaitas buferis”, bet ideju trūkuma dēļ pats piedāvāja vārdu „kešatmiņa”. Raksts bija publicēts 1968. gada sākumā, tā autori saņēma prēmiju no IBM. Viņu darbs izplatījās un rezultātā tika uzlabots, bet vārdu „kešatmiņa” drīz pēc tam sāka izmantot datora literatūrā kā parasto terminu.

Funkcionēšana

Centrālā procesora kešatmiņas diagramma

Kešatmiņa- tā ir atmiņa ar liela ātruma piekļūšanu, kas paredzēta paātrinātai datu pieejamībai. Šie dati pastāvīgi tiek saturēti atmiņā ar mazāko piekļūšanas ātrumu. Kešatmiņu izmanto centrālie procesori, cietais disks, pārlūkprogrammas, tīmekļa serveri, DNS un WINS servera dienesti.

Kešatmiņa sastāv no ierakstu komplekta. Katrs ieraksts tiek asociēts ar datu elementu vai ar datu bloku (nelielu datu daļu), kas ir datu elementa kopija pamatatmiņā. Katram ierakstam ir identifikators, kas noteic atbilstību starp datu elementiem kešatmiņā un to kopijām pamatatmiņā.

Kad kešatmiņas klients (centrālais procesors, tīmekļa pārlūks, operatīvā sistēma) griežas pie datiem, vispirms tiek pētīta kešatmiņa. Ja kešatmiņā ir atrasts ieraksts ar identifikatoru, kas sakrīt ar pieprasītā datu elementa identifikatoru, tad tiek izmantoti kešatmiņas datu elementi. Tādu gadījumu sauc par keša trāpījumu (angļu: cache hit). Ja ieraksts, kas satur pieprasīto datu elementu, nav atrasts kešatmiņā, tad tas tiek lasīts no pamatatmiņas uz kešatmiņu, un kļūst par pieejamo nākamreiz. Tādā gadījumā nav keša trāpījums (angļu: cache miss). Proporciju, kas parāda piekļuves, kuru rezultāti ir keša trāpījumi, sauc par trāpījumu biežumu (angļu: cache rate), kas ir keša efektivitātes rādītājs.

Piemēram, tīmekļa pārlūks pārbauda lokālajai kešatmiņai uz diska tīmekļa lapas lokālās kopijas esamību, kas atbilst pieprasītajam URL. Šajā piemērā URL ir identifikators, bet tīmekļa lapas saturs ir datu elementi.

Ja kešatmiņai ir ierobežots apjoms, tad (angļu: cache miss) (nav keša trāpījums) gadījumā var būt pieņemts lēmums par kāda ieraksta atteikšanu, lai atbrīvotu telpu. Atteikta ieraksta izvēlei tiek izmantoti dažādi atteikšanas algoritmi. Ja kešatmiņa tiktu atslēgta, sistēma tiktu traucēta, informācija tiktu saglabāta diskā.

Kad kešatmiņā notiek datu elementu modifikācija, izpildās arī to atjaunošana pamatatmiņā. Laika aizkavēšanās starp datu modifikāciju kešatmiņā un pamatatmiņas atjaunošanu tiek kontrolētas ar tā saucamo ierakstīšanas politiku.

Kešatmiņā ar tūlītēju ierakstu katra atjaunošana rada sinhronizētu datu atjaunošanu pamatatmiņā. Kešatmiņā ar ierakstu atpakaļ (angļu: write-back) (vai pretēju ierakstīšanu) atjaunošana notiek datu elementu izspiešanas gadījumā, periodiski vai pēc klienta pieprasījuma. Modificēto datu elementu novērošanai kešatmiņas ieraksti glabā modifikācijas pazīmi. Kļūda kešatmiņā ar atliekošu ierakstīšanu var pieprasīt divas griešanās pie pamatatmiņas: pirmo- kešatmiņas aizvietojamo datu ierakstīšanai, otro- nepieciešamā datu elementa lasīšanai. Gadījumā, ja dati pamatatmiņā var būt mainīti neatkarīgi no kešatmiņas, tad kešatmiņas ierakstīšana var kļūt par neaktuālo. Mijiedarbības protokolus starp kešatmiņām, kas saglabā datu saskaņošanu, sauc par kešatmiņas koherences protokoliem.

Centrālā procesora kešs

Dažādiem centrālo procesoru modeļiem ir sava kešatmiņa, lai minimizētu piekļūšanas laiku operatīvajai atmiņai (RAM), kas ir lēnāka nekā reģistri. Ar kešatmiņas palīdzību ražīguma līmenis var būt augstāks, gadījumā, kad operatīvās atmiņas takts frekvence ir ievērojami mazāka nekā centrālā procesora takts frekvence. Takts frekvence kešatmiņai parasti ir nedaudz mazāka nekā centrālā procesora frekvence.

Procesoros ar virtuālās adresācijas atbalstu bieži tiek ieviests neliels un ātrs adrešu pārveidošanas buferis (TLB). Tā ātrums ir svarīgs, tāpēc ka adrešu pārveidošanas buferis vienmēr tiek aptaujāts sakarā ar griešanos pie atmiņas.

Kešatmiņas līmeņi

Kešatmiņas līmeņi

Centrālā procesora kešs tiek sadalīts dažādos līmeņos. Pašlaik universālajā procesorā līmeņu skaits var sasniegt 3. Līmeņa N+1 kešatmiņa parasti ir lielāka pēc izmēra un lēnāka pēc datu pieejamības un nodošanas ātruma nekā N līmeņa kešatmiņa. Visātrākā atmiņa ir pirmā līmeņa kešs (primārā kešatmiņa) — L1 cache, kas atrodas pašā procesora mikroshēmā. Pēc būtības, tā ir neatņemama procesora daļa, tāpēc ka kopā ar procesoru atrodas uz viena kristāla, un tie ir funkcionālo bloku sastāvdaļas. Modernos procesoros kešs L1 bieži tiek sadalīts par diviem kešiem: komandu (instrukciju) kešs un datu kešs. Procesoru lielākā daļa bez L1 keša nevar funkcionēt. L1 kešs strādā ar procesora frekvenci, un griešanās pie tā var notikt katrā taktī. Ir iespēja vienlaikus izpildīt dažādas operācijas (lasīšana / ierakstīšana). Pieejamības latentums bieži vienāds ar 2—4 kodola taktīm. Apjoms parasti ir neliels- ne vairāk kā 128 Kb.

Otro vietu pēc ātruma ieņem otrā līmeņa kešs (sekundārā kešatmiņa) — L2- cache, kas kā atsevišķa mikroshēma var atrasties mikroprocesora korpusā. Vecos procesoros — mikroshēmu komplekts uz sistēmplates. L2 keša apjoms ir no 128 Kb līdz 1-2 Mb. Modernos daudzkodolu procesoros otrā līmeņa kešs, kas atrodas uz kristāla, ir dalīta lietojuma atmiņa. Kad keša kopējais apjoms ir nM Mb, uz katru kodolu ir nM/nC Mb, kur nC- procesora kodolu skaits. L2 keša latentums, kas atrodas uz kodola kristāla, parasti sastāda no 8 līdz 20 kodola taktīm.

Trešā līmeņa kešs nav tik ātrs, tomēr tas var būt diezgan liels — vairāk nekā 24 Mb. L3 kešs ir lēnāks nekā iepriekšējie keši, bet tas ir ievērojami ātrāks nekā operatīvā atmiņa. Daudzprocesoru sistēmās tas atrodas vispārīgā lietošanā un tiek lietots dažādu L2 datu sinhronizācijai. Dažreiz pastāv arī ceturtā līmeņa kešs, kas parasti atrodas atsevišķā mikroshēmā. Ceturtā līmeņa kešu lieto augsta ražīguma serveri un lieldatori.

Sinhronizācijas problēmu starp dažādiem kešiem (kā viena, tā arī vairāku procesoru) risina keša koherence. Pastāv trīs informācijas apmaiņas varianti starp dažādu līmeņu kešatmiņām, jeb keša arhitektūra: inkluzīvā, ekskluzīvā un neekskluzīvā. Inkluzīvā arhitektūra nozīmē augšējā līmeņa keša informācijas dublēšanu apakšējā līmeņa kešā. Tam dod priekšrocību firma Intel. Ekskluzīvā kešatmiņa nozīmē informācijas unikalitāti, kas atrodas keša dažādos līmeņos. Tam dod priekšrocību firma Advanced Micro Devices. Neekskluzīvajā arhitektūrā keši var uzvesties dažādi.

Keša asociativitāte

Viens no kešatmiņas pamatraksturojumiem ir asociativitātes līmenis, kas atspoguļo tās loģisko segmentāciju. Ja būtu tā, ka nepieciešamo datu meklēšanai vajadzētu secīgi pārskatīt visas keša rindas, kas prasītu vairākas taktis, tad nebūtu nekāda labuma no centrālā procesora atmiņas. Tāpēc operatīvās atmiņas šūniņas stipri tiek saistītas ar kešatmiņas rindām (katrā rindā var būt dati no adresu fiksētā komplekta), kas nozīmīgi samazina meklēšanas laiku. Ar katru operatīvās atmiņas šūniņu var būt saistīta vairāk nekā viena kešatmiņas rinda. Piemēram, n- kanālu asociativitāte (angļu: n- way set associative) nozīmē, ka kādas operatīvās atmiņas adreses informācija var glabāties n kešatmiņas vietās. Kad keša apjoms ir vienāds, shēma ar lielāko asociativitāti ir ne pārāk ātra, taču ir efektīvāka.

Ārējo datu nesēju kešs

Daudzas datu glabāšanas perifērijas iekārtas izmanto kešu, lai paātrinātu darbu. Piemēram, cietie diski izmanto kešatmiņu no 1 līdz 64 Mb (modeļi ar NCQ/TCQ izmanto to pieprasījumu glabāšanai un apstrādei). CD/DVD/BD diski izmanto kešu informācijas nolasīšanā, lai paātrinātu atkārtotas griešanās. Operatīvā sistēma arī izmanto operatīvās atmiņas daļu disku operāciju kešam (piemēram, ārējām ierīcēm, kurām nav savas kešatmiņas, tai skaitā cietajiem diskiem, zibatmiņai, elastīgajiem diskiem).

Ārējo datu nesēju keša izmantošanas faktori:

1. procesora ātrums pie operatīvās atmiņas ir vairākas reizēs lielāks nekā pie ārējo datu nesēju atmiņas;
2. dažus ārējo datu nesēju atmiņas blokus vienlaikus izmanto vairāki procesori. Ir jēga vienu reizi nolasīt bloku, un pēc tam vienu bloka kopiju glabāt operatīvajā sistēma visiem procesoriem;
3. pie dažiem operatīvās atmiņas blokiem piekļūšana notiek biežāk nekā pie citiem. Tāpēc keša izmantošana tādiem blokiem kopumā palielina sistēmas ražīgumu;
4. dažiem ārējo datu nesēju atmiņas blokiem nav vajadzīgs obligāts ieraksts pēc modifikācijas, un keša izmantošana tādiem blokiem optimizē ievades/izvades izmantošanu.

Operatīvās atmiņas kešs

Operatīvās atmiņas kešs sastāv no šādiem elementiem:

1. operatīvās atmiņas lappušu komplekts. Lappuses tiek sadalītas pa buferiem un ir vienādas pēc atbilstošas iekārtas ārējās atmiņas datu bloka garuma;
2. buferu virsrakstu komplekts, kas apraksta atbilstoša bufera stāvokli;
3. hešs tabulas, kas satur numura atbilstību bloka virsrakstam;
4. brīvo buferu saraksts.

Keša ar ierakstu atpakaļ (write-back) darba algoritms

Sākumā visi buferu virsraksti atrodas brīvo buferu sarakstā. Ja procesors gatavojas bloka nolasīšanai vai modifikācijai, tad tas izpilda kādu no šiem algoritmiem:

1. mēģina atrast bufera virsrakstu ar uzdotu numuru hešs tabulā;
2. gadījumā, ja iegūtais buferis ir aizņemts, procesors gaida tā atbrīvošanu;
3. gadījumā, ja buferis netiek atrasts hešs tabulā, procesors ņem pirmo buferi no brīvā saraksta gala;
4. gadījumā, ja brīvo buferu saraksts ir tukšs, tad tiek izpildīts izspiešanas algoritms;
5. gadījumā, ja iegūtais buferis ir „netīrs”, procesors izpilda asinhronu bufera satura ierakstu ārējā atmiņā;
6. noņem buferi no hešs tabulas, ja buferis ticis novietots tajā;
7. novieto buferi ar jauno numuru hešs tabulā.

Procesors lasa datus, kurus ieguva buferis, un pēc tam atbrīvo to. Modifikācijas gadījumā procesors pirms bufera atbrīvošanas atzīmē to kā „netīru”. Atbrīvošanas gadījumā buferis tiek novietots brīvo buferu saraksta sākumā.

Secinājumi:

1. ja procesors nolasīja kādu bloku buferī, tad ir liela varbūtība, ka cits procesors, lasot šādu bloku, atradīs buferi operatīvajā atmiņā;
2. datu ierakstīšana ārējā atmiņā notiek tikai tad, kad nepietiek „tīru” buferu, vai pēc pieprasījuma.

Izspiešanas algoritms

Ja brīvo buferu saraksts ir tukšs, tad tiek izpildīts bufera izspiešanas algoritms. Šis algoritms būtiski ietekmē keša ražīgumu. Pastāv šādi algoritmi:

1. LRU (Least Recently Used)- izspiež visilgāk neizmantotu buferi;
2. MRU (Most Recently Used)- izspiež pēdējo izmantoto buferi;
3. LFU (Least Frequently Used)- izspiež visretāk izmantotu buferi;
4. ARC (Adaptive Replacement Cache)- izspiešanas algoritms, kas kombinē LRU un LFU. Tiesības uz šo algoritmu pieder IBM.

Algoritma veida izmantošana ir atkarīga no datu keša stratēģijas. LRU ir efektīvāks, ja dati garantēti tiks atkārtoti izmantoti tuvākajā laikā. MRU ir efektīvāks, ja dati garantēti netiks atkārtoti izmantoti tuvākajā laikas. Gadījumā, ja pielikums tieši norāda uz kādu datu keša stratēģiju, tad kešs funkcionēs efektīvāk.

Kešatmiņas ierakstīšanas politika

Datu lasīšanas procesā kešatmiņa dod noteiktu priekšrocību ražīgumā. Datu ierakstīšanas procesā priekšrocību var gūt, tikai samazinot uzticamību. Tāpēc dažādos pielikumos var būt izvēlēta tāda vai cita kešatmiņas ierakstīšanas politika.

Pastāv divi kešatmiņas ierakstīšanas politikas veidi: write-through (ieraksts caur) un write-back (ieraksts atpakaļ):

1. write- through (ieraksts caur) — ierakstīšana notiek tieši pamatatmiņā un tiek dublēta kešā.
2. write-back (ieraksts atpakaļ) — darbojas pēc principa, ka datus ieraksta kešā. Ierakstīšana pamatatmiņā notiek vēlāk (izspiešanas procesā vai pēc kāda laika), grupējot vienā operācijā dažas ieraksta operācijas blakusšūniņās. Write-back tehnoloģija uz kādu laiku padara datus pamatatmiņā par neaktuāliem. Pats centrālais procesors nekonstatē šo neaktuālitāti, tomēr pirms griešanās pie citas galvenās sistēmas atmiņas, kešam piespiesti vajadzētu būt ierakstītam atmiņā. Write-back izmantošanas gadījumā daudzprocesoru sistēmā dažādu centrālo procesoru kešiem jābūt saskaņotiem (jeb vajag, lai procesori izmantoja vienu kešatmiņu).

Tīmekļa lapu kešs

Procesā, kad informācija tiek nodota tīklā, var būt izmantots tīmekļa lapu kešs. Tas ir bieži pieprasīto dokumentu glabāšanas process uz starpniekserveriem vai lietotāja mašīnas, ar mērķi novērst to pastāvīgo lejupielādi no servera — avota un samazināt datplūsmu. Tādēļ informācija pārvietojas tuvāk lietotājam. Keša vadīšanu realizē ar HTTP- virsrakstu palīdzību. Tīmekļa lapu kešu var realizēt arī ar konkrētās mājas lapas CMS palīdzību, kas samazina servera slodzi lapas biežas apmeklēšanas gadījumā. Keša process var notikt kā atmiņā, tā arī failu kešā.

Tīmekļa kešs ir mehānisms tīmekļa dokumentu, piemēram, HTML lapu un attēlu pagaidu uzglabāšanai, lai samazinātu tīkla noslodzi, serveru noslodzi un aiztures problēmas. Tīkla kešs kā mehānisms saglabā sevī cauri plūstošo informāciju. Turpmāk pieprasījumi var tikt apmierināti no keša, tomēr tas var notikt tikai gadījumos, kad izpildās zināmi nosacījumi.

Darbu rezultātu kešs

Daudzas programmas ieraksta darba starplaika rezultātus vai palīgrezultātus jebkurā vietā, lai tos neaprēķinātu katru reizi, kad tie būtu vajadzīgi. Tas paātrina darbu, bet pieprasa papildatmiņu (operatīvo vai diska). Par piemēru var būt datu bāzu indeksācija.