Kešavimas - tam tikras optimizavimo procesas, kurio metu dažniau naudojami duomenų elementai daromi lengviau pasiekimais, nei tie, kurie naudojami retai. Dažniausiai kešavimas naudojamas kompiuteriuose, juo pagrįstas virtualios atminties veikimas.

Kešavimas pagrįstas praktiniu pastebėjimu, kad dažniausiai naudojami duomenys (pvz., 80% aktyviausiai naudotų duomenų) sudaro mažąją visų duomenų dalį (pvz., 20% iš naudojamų duomenų apimties). Išskyrus sistemą į dvi dalis, viena kurių būtų brangesnė, bet greitesnė, o kita lėtesnė, bet pigi, galima už mažesnę kainą gauti našesnę sistemą.

Pvz., jei 20% atminties 2 kartus pagreitinsime, kad ir už dvigubą kainą, o likusią atminties dalį dvigubai atpiginsime, kad ir gaudami 2 kartus mažesnį našumą, rezultatas bus geresnis, nei turint vieno lygmens atmintį: 80% skaičiavimų vyks 2 kartus greičiau (per 40% pirminės sistemos naudoto laiko), o tik 20% vyks 2 kartus lėčiau (irgi per 40% laiko), kitaip tariant, bendras sistemos našumas bus didesnis (skaičiavimams prireiks 80% to laiko, kurio būtų reikėję pirminei sistemai). Tuo pat metu, bendra panaudotos atminties kaina irgi liks mažesne - 80% nuo pirminės sistemos kainos.

Naudojant kešavimo metodus, susiduriama tik su viena problema: tenka prognozuoti, kokius duomenis reikia pasiekti greičiau, o kokius galima atidėti, kitaip tariant, reikia duomenis tam tikru būdu išskaidyti į kešuojamus segmentus, o paskui - juos reitinguoti, sprendžiant, ar reikia juos laikyti greitesnėje ar lėtesnėje atminties dalyje. Yra sukurta nemažai įvairių algoritmų, skirtų kešavimui, tačiau daugelis iš jų reikalauja arba didelių papildomų atminties kiekių, arba gana sudėtingų skaičiavimų. Vienas iš paprastesnių algoritmų (laikrodžio algoritmas) veikia maždaug taip:

Naudojama atmintis skaidoma segmentais, kiekvienas iš jų gauna skaitliuką. Kiekvieną kartą, kreipiantis į atitinkamą segmentą, skaitliukas didinamas vienetu, tol kol nepasiekia maksimalios ribos. Tuo atveju, jei skaitliukas yra didesnis už iš anksto nustatytą (kešavimo) ribą, segmentas perkeliamas į greitesnę atminties dalį. Jei greitesnėje atminties dalyje esantis segmentas naudojamas retai (jo skaitliukas mažesnis už kešavimo ribą), jis permetamas į lėtesnę atmintį. Tam, kad atmesti retai naudojamus segmentus, nepriklausomai nuo kitų sistemų dirba programa, kuri visų iš eilės segmentų skaitliukus kas tam tikrą laiko tarpą mažina (ši programa, panašiai, kaip laikrodžio rodyklė, eina per visus segmentų skaitliukus). Tuo atveju, jei greita atminties dalis naudojama pilnai, "rodyklė" sukasi greičiau, o jei greitosios atminties panaudojimas - tik dalinis, rodyklė sukasi lėtai. Tokiu būdu dažnai naudojami segmentai atskiriami nuo retai naudojamų.

Kešavimo metodai naudojami labai plačiai, pačiose įvairiausiose kompiuterijos srityse:

• Procesoriai turi kešus, kurie pagreitina kreipimąsi į atmintį.
• Kompiuteriai turi virtualią atmintį, kuri leidžia už labai mažą kainą gauti daug, tegul ir lėtesnės atminties.
• Lėtai veikiančios duomenų skaitymo iš diskų ar tinklo operacijos pagreitinamos, duomenis kuriam laikui išsaugant operacinėje kompiuterio atmintyje.

Informatika Algoritmai

Cache | Cache | Cache | Cache | Cache | Memoria caché | Välimuisti | Mémoire cache | זיכרון מטמון | Cache | Gyorsítótár | Cache | Cache | キャッシュ (コンピュータシステム) | 캐시 | Cache | Cache | Cache | Cache | Кеш-память | Rýchla vyrovnávacia pamäť | Cache | แคช | Önbellek | 高速缓存