Vahemälu

Allikas: Vikipeedia

Vahemälu[1][2][3][4] (inglise cache; prantsuse cacher – peita; IPA: [kæʃ]) on komponent, mis hoiustab andmeid nende kiireks uuesti kasutamiseks. Vahemälust andmete lugemine on kiirem kui lähteandmete lugemine muutmälust (RAM) või kõvakettalt. Vahemälu kasutamise tulemusena väheneb korduvalt kasutatavate andmete lugemiseks kulunud aeg ja suureneb üldine tulemuslikkus arvutisüsteemis.

Ajalugu[muuda | redigeeri lähteteksti]

Esimest korda kasutati sõna "cache" elektroonilises kontekstis aastal 1967 artiklis, mis kirjutati avaldamiseks ajakirjas IBM Systems Journal. Artikkel puudutas mälu parandamist väljatöötataval mudelil 85-seeriast IBM System/360. Ajakirja toimetaja Lyle Johnson palus välja mõelda tabavam termin kui "ülikiire puhver”, kuid ideede puudumise tõttu soovitas ta ise sõna "cache". See artikkel ilmus 1968. aasta alguses, autorid pälvisid IBM preemia, nende töö levis ja on hiljem parandatud, aga sõna "cache" hakati peagi kasutama arvutialases kirjanduses nagu üldtunnustatud terminit.

Tööpõhimõte[muuda | redigeeri lähteteksti]

CPU mälu vahemälu diagramm

Vahemälu on suure juurdepääsukiirusega mälu, mille eesmärk on saavutada vähima juurdepääsuajaga ligipääs andmetele, mis sisalduvad püsimälus (edaspidi "põhimälus"). Vahemälu kasutatakse keskprotsessoris (CPU), kõvaketastel, brauserites, veebiserverites, DNS-is ja WINS-is.

Vahemälu koosneb kirjete kogumist. Iga kirje on seotud andmeühikuga või andmete plokiga (väikese osaga andmetest), mis on andmeühiku koopia püsimälus. Igal sissekandel on tunnus-ID, mis määratleb andmeühikute vastavuse vahemälus nende koopiatega põhimälus.

Kui vahemälu kasutaja (CPU, veebibrauser, operatsioonisüsteem) soovib andmeid, uuritakse kõigepealt vahemälu. Kui vahemälus leitakse kirje ID-ga, mis sobib otsitud andmeühiku ID-ga, siis kasutatakse andmeelementide vahemälu. Seda nimetatakse vahemälu tabamuseks (cache hit). Kui vahemälust ei leitud kirjet, mis sisaldab otsitud ID-d, siis loetakse see põhimälust vahemällu ja on sealt edaspidistel vahemälu otsingutel kättesaadav. Seda nimetatakse vahemälu möödalask (cache miss). Vahemälust leitud tulemuste protsenti võrreldes päringutega nimetatakse cache tabamuse tasemeks või tabamuse koefitsiendiks.

Näiteks veebilehitseja kontrollib URL-s küsitud veebilehe lokaalse koopia olemasolu ketta lokaalses vahemälus. Selle näite puhul on URL tunnus, aga veebilehe sisu – andmete osa.

Kui vahemälu maht on piiratud, siis möödalase puhul võib olla vastu võetud otsus loobuda mõnest salvestisest vaba ruumi tekitamiseks. Väljajäetava salvestise valikuks kasutatakse erinevaid algoritmide väljasurumisi. Kui modifitseeritakse vahemälu andmete osasid, toimub nende ajakohastamine põhimälus. Viivitust ajas vahemälu andmete muutmise ja põhimälu uuendamise vahel kontrollib nn kirjete poliitika.

Write-through vahemälus kutsub iga muudatus esile sünkroonse andmete uuendamise põhimälus.

Write-back vahemälu uuendamine toimub andmeelementide eemaldamisel perioodiliselt või kliendi päringu järel. Et jälgida modifitseeritud andmeelemente, säilitavad vahemälu kirjed modifitseerimise tunnuse (“muudetud”). Möödalask write-back cache'st võib nõuda kahte pöördumist põhimälu juurde: esiteks vahemälust andmeelementide üleskirjutamiseks, teiseks vajaliku andmeelemendi lugemiseks.

Juhul, kui andmeid põhimälus saab muuta sõltumata vahemälust, võib vahemälu kirje muutuda mitteaktuaalseks. Vahemälude vahelisi koostööprotokolle, mis säilitavad andmete kooskõlastust, nimetatakse vahemälu sidususe protokollideks.

Keskprotsessori vahemälu[muuda | redigeeri lähteteksti]

Mitmed keskprotsessori (CPU) mudelid omavad oma vahemälu selleks, et minimeerida ligipääsu põhimälule (muutmälu), mis on aeglasem kui registrid. Vahemälu võib anda olulise jõudluse kasvu, juhul kui RAM-i taktsagedus on oluliselt väiksem keskprotsessori CPU taktsagedusest. Vahemälu taktsagedus ei ole tavaliselt palju väiksem kui CPU.

Virtuaalse adresseerimise toega protsessoritesse on sageli lisatud väike kiirelt tegutsev aadresside translatsiooni puhver (inglise TLB). Selle kiirus on oluline, kuna teda vajatakse igal mälusse pöördumisel.

Vahemälu tasemed[muuda | redigeeri lähteteksti]

Keskprotsessori CPU vahemälu on jaotatud mitmeks tasandiks. Käesoleval ajal võib universaalses protsessoris olla kuni 3 tasandit. Vahemälu tasand N+1 on üldiselt mõõtmetelt suurem ja andmete kättesaadavuse ja andmeedastuse kiiruselt aeglasem, kui vahemälu tase N. Kõige kiirem mälu on esimese taseme vahemälu L1. Tegelikult on ta protsessori lahutamatu osa, kuna asub protsessoriga ühel ja samal kristallil ja kuulub funktsioneerivate plokkide koosseisu. Protsessorites on vahemälu L1 tavaliselt jagatud kaheks vahemäluks, käskude (juhised) vahemälu ja andmete vahemälu (Harvardi arhitektuur). Enamik protsessoreid ei saa ilma L1 vahemäluta töötada. L1 vahemälu töötab protsessori sagedusel ja üldjuhul võib pöördumine tema poole toimuda iga takti ajal. Paljudel juhtudel on võimalik läbi viia mitu loe/kirjuta toimingut samaaegselt. Juurdepääsu latentsus võrdub tavaliselt 2–4 tuuma takti. Maht on tavaliselt väike – alla 128 kB.

Kiiruselt teine on L2-vahemälu – teise taseme vahemälu. Tavaliselt asub ka see kristallil nagu L1. Vanades protsessorites on mikroskeemid emaplaadil. L2 maht on 128 kB kuni 1–12 MB. Tänapäevastes multi-core protsessorites teise tasandi vahemälu, asudes samal kristallil ja on eraldi kasutatav mälu, kus vahemälu maht võrdub nM MB ja iga tuuma vahemähe on nM/nC MB, kus nC võrdub protsessori tuumade arvuga. Üldiselt tuuma kristallil paikneva L2 vahemälu moodustab 8–20 tuuma takti.

Kolmanda taseme vahemälu on kõige väiksema kiirusega, kuid võib olla väga muljetavaldava suurusega – rohkem kui 24 MB. L3 vahemälu on aeglasem kui eelnimetatud, kuid siiski tunduvalt kiirem muutmälust. Mitmeprotsessorilistes süsteemides on üldkasutatav ja mõeldud erinevate andmete sünkroniseerimiseks L2 vahemälu.

Mõnikord on olemas ka neljas vahemälu tasand, mis asub tavaliselt eraldi mikrokiibil. Neljanda tasandi vahemälu on õigustatud ainult suure jõudlusega serverites ja suurarvutites.

Erinevate vahemälude sünkroonimise probleemid (nii ühe kui ka mitme protsessori puhul) lahendab vahemälu koherentsus (cache coherence). On olemas kolm infovahetuse võimalust erinevate vahemälude tasandite vahel, või nagu öeldakse, vahemälu arhitektuuri: inklusiivne, eksklusiivne ja mitteeksklusiivne. Inklusiivne arhitektuur eeldab ülemise tasandi vahemälu info dubleerimist alumises tasandis (eelistab Intel). Eksklusiivne vahemälu eeldab erinevatel tasanditel oleva informatsiooni unikaalsust (AMD). Mitteeksklusiivses võivad vahemälud käituda nagu soovivad.

Vahemälu assotsiatiivsus[muuda | redigeeri lähteteksti]

Üks põhilisi vahemälu omadusi – assotsiatiivsuse tase – näitab tema loogilist segmenteerimist. Asi on selles, et vajalike andmete otsimiseks vahemälu kõikide ridade järjestikune skanneerimine nõuaks kümneid takte ja muudaks kasutuks sisseehitatud keskprotsessori mälu kasutamise. Seepärast on muutmälu pesikud jäigalt seotud vahemälu ridade külge (igal real võivad olla fikseeritud aadresside komplektide andmed), mis vähendab oluliselt otsingu aega. Iga RAM pesik võib olla seotud rohkem kui ühe vahemälu reaga: näiteks, n- kanali assotsiatiivsus (inglise n-way set associative) tähendab, et mõne operatiivmälu aadressi informatsioon võib olla hoiul n asukohas vahemälus.

Vahemälude sama mahu juures suure assotsiatiivsusega skeem on mitte nii kiire, kuid tõhusam.

Väliste kõvaketaste puhverdamine[muuda | redigeeri lähteteksti]

Paljud andmesalvestuse välisseadmed, eriti kõvakettad, kasutavad vahemälu töö kiirendamiseks vahemälu 1–64 MB (NCQ/TCQ toetusega mudelid kasutavad seda päringute hoiustamiseks ja töötlemiseks), CD/DVD/BD-plaatide lugemisseadmed samuti puhverdavad loetavat teavet, et sama info poole teistkordne pöördumine oleks kiirem. Samuti kasutab operatsioonisüsteem osa muutmälust kettaoperatsioonide vahemäluna (sh väliste seadmete jaoks, millel endal ei ole vahemälu, nt. kõvakettad, flash-mälu, CD).

Väliste kõvaketaste puhverdamist õigustavad järgnevad tegurid:

  1. protsessori juurdepääsu kiirus muutmällu on mitu korda suurem kui väliste kõvaketaste mällu;
  2. väliste kõvaketaste mõningaid mäluplokke kasutavad mitmed protsessid samaaegselt ja on mõttekas lugeda plokki üks kord, seejärel hoida muutmälus üks koopia plokist kõikide protsesside jaoks;
  3. pöördumine mõningate muutmälus olevate plokkide poole esineb palju sagedamini kui teistele, seega selliste plokkide jaoks puhverdamise kasutamine üldiselt suurendab süsteemi jõudlust.
  4. mõned väliste kõvaketaste mäluplokid ei nõua peale muutmist kohest salvestamist ja selliste plokkide puhul vahemälu kasutamine optimeerib sisend-väljund kasutamise.

Puhverdamine operatsioonisüsteemi kaudu[muuda | redigeeri lähteteksti]

Muutmälu vahemälu koosneb järgmistest elementidest:

  1. muutmälu lehekülgede hulk, mis on jagatud puhvriteks, mis on pikkuselt võrdsed vastava välismälu seadme andmeplokiga;
  2. puhvrite nimetuste kogu, mis kirjeldavad vastava puhvri seisukorda;
  3. hash tabelid, mis sisaldavad ploki numbri vastavust nimetusele;
  4. vabade puhvrite nimekiri.

Write-back vahemälu töö algoritm[muuda | redigeeri lähteteksti]

Algselt on kõik puhvrite nimetused paigutatud vabade puhvrite nimekirja. Kui protsess kavatseb lugeda või muuta plokki, siis ta täidab järgmise algoritmi:

  1. püüab leida hash tabelis (räsitabelis) puhvri nimetuse antud numbriga;
  2. juhul, kui antud puhver on hõivatud, ootab tema vabanemist;
  3. juhul, kui puhvrit hash tabelis ei leita, võtab esimese vaba puhvri vabade puhvrite nimekirja lõpust;
  4. juhul, kui vabade puhvrite nimekiri on tühi, toimub algoritmi nihe (vt allpool);
  5. juhul, kui antud puhver on märgitud kui “määrdunud”, kirjutab puhvri sisu asünkroonselt välisesse mällu;
  6. eemaldab puhvri hash tabelist, kui see oli sinna paigutatud;
  7. asetab uue numbriga puhvri hash tabelisse.

Protsess loeb andmed saadud puhvrisse ja vabastab selle. Kui toimub muutmine, siis enne vabastamist protsess märgib puhvri kui “määrdunud”. Vabastamisel asetatakse puhver vabade puhvrite nimekirjas ette.

Seega:

  1. kui protsess luges mingi ploki puhvrisse, on tõenäoline, et teine protsess leiab selle ploki lugemiseks puhvri muutmälust.
  2. välisesse mällu kirjutatakse andmed ainult siis, kui ei ole “puhtaid” puhvreid või nõudmise korral.

Väljasurumise algoritm[muuda | redigeeri lähteteksti]

Kui vabade puhvrite nimekiri on tühi, siis tehakse puhvris algoritmi nihe. Algoritmi nihe mõjutab oluliselt vahemälu tootlust. On olemas järgmised algoritmid:

  1. LRU (Least Recently Used) – välja surutakse puhver, mis on kõige kauem kasutamata;
  2. MRU (Most Recently Used) – välja surutakse viimati kasutatud puhver;
  3. LFU (Least Frequently Used) – välja surutakse kõige harvem kasutatud puhver;
  4. ARC (Adaptive Replacement Cache) – väljasurumise algoritm, LRU JA LFU kombinatsioon, patenteeritud IBM.

Ühe või teise algoritmi kasutamine sõltub andmete puhverdamise strateegiast. LRU on kõige efektiivsem, kui on tagatud, et andmeid kasutatakse korduvalt lähitulevikus. MRU on kõige efektiivsem, kui on tagatud, et andmeid ei kasutata korduvalt lähitulevikus. Kui taotlus määratleb selgesõnaliselt teatud hulga andmete puhverdamise strateegia, töötab vahemälu kõige tõhusamalt.

Tarkvara puhverdamine[muuda | redigeeri lähteteksti]

Üleskirjutamise poliitika puhverdamisel[muuda | redigeeri lähteteksti]

Vahemälu annab andmete lugemisel tootlikkuses suure kasu. Andmete üleskirjutamisel võib suur kasu tulla ainult usaldusväärsuse vähenemise hinnaga. Seega, erinevate juurdelisamiste puhul saab valida ühe või teise vahemälu üleskirjutamise poliitika.

On olemas kaks peamist vahemälu üleskirjutamise poliitikat – write-through cache ja write-back cache:

  1. write-through – üleskirjutamine toimub vahetult põhimällu (ja dubleeritakse vahemällu), st üleskirjutus ei ole puhverdatud;
  2. write-back – andmete üleskirjutamine toimub vahemällu. Kirjutamine põhimällu tehakse hiljem (väljatõrjumise või aja möödumise järel), rühmitades ühes operatsioonis mitu üleskirjutuse operatsiooni kõrvalasuvatesse pesikutesse. Write-back'i töötlemise tehnoloogia teeb mõneks ajaks andmed põhimälus ebaolulisteks, keskprotsessori jaoks need ebaolulisused ei ole märgatavad, kuid enne teise juhtiva mälusüsteemi siini poole pöördumist (DMA controller, sinihaldur-PCI siini seadmed) tuleb vahemälu salvestada mällu sunniviisiliselt. Kui kasutada write-back'i mitmeprotsessilises süsteemis, siis erinevate keskprotsessorite vahemälud peavad olema kooskõlastatud (või peavad protsessorid kasutama sama vahemälu).

Veebilehtede puhverdamine[muuda | redigeeri lähteteksti]

Informatsiooni ülekandmise protsessis läbi võrgu on võimalik kasutada veebilehtede puhverdamist – tihti küsitud dokumentide ladustamise protsessi (vahepealsetes) Proxy serverites või kasutaja arvutis, eesmärgiga takistada nende pidevat laadimist algserverist ja vähendada liikumist. Sellega teave lähendatakse kasutajale. Vahemälu juhtimine toimub HTTP-päiste abil.

Ühe võimalusena võib veebilehe puhverdamine toimuda konkreetse lehe CMSi abil, et alandada koormust serverile suure kasutatavuse puhul. Puhverdada saab nii mällu kui ka faili vahemällu.

Töötulemuste puhverdamine[muuda | redigeeri lähteteksti]

Paljud programmid kirjutavad ükskõik kuhu vahepealsed ja abistavad töötulemused (ajutised, esialgsed), et mitte otsida neid iga kord, kui neid vajatakse. See kiirendab tööd, kuid nõuab lisamälu (põhimälu muutmälu või optiline andmekandja). Sellise puhverdamise näiteks on andmebaaside indekseerimine.

Vaata ka[muuda | redigeeri lähteteksti]

Viited[muuda | redigeeri lähteteksti]

  1. Большой толковый словарь русского языка / автор, сост. и гл. ред. С. А. Кузнецов. 2000 г. РАН Институт лингвистических исследований
  2. Захаренко Е. Н., Комарова Л. Н., Нечаева И. В. Новый словарь иностранных слов. М.: 2003
  3. Толковый словарь по вычислительной технике. Microsoft Press, из-во «Русская Редакция», 1995
  4. Русский орфографический словарь: около 180 000 слов / Российская академия наук. Институт русского языка им. В. В. Виноградова / О. Е. Иванова, В. В. Лопатин (отв. ред.), И. В. Нечаева, Л. К. Чельцова. — 2-е изд., испр. и доп. — М.: 2004. — 960 с.

Kasutatud kirjandus[muuda | redigeeri lähteteksti]

  • М. Дж. Бах. Архитектура операционной системы UNIX
  • Duane Wessels, Web Caching (O'Reilly and Associates, 2001)

Lisa lugemiseks[muuda | redigeeri lähteteksti]

Välislingid[muuda | redigeeri lähteteksti]