Kesh, yoki kesh (ingl. cache, frans. cacher — «yashirmoq»; talaffuzi [kæʃ] — «kesh») — tezkor kirish imkoniyatiga ega oraliq bufer bo‘lib, unda eng ko‘p so‘ralishi ehtimoli bo‘lgan maʼlumotlar saqlanadi. Keshdagi maʼlumotlarga murojaat qilish sekinroq xotiradan yoki masofaviy manbadan dastlabki maʼlumotlarni olishga qaraganda tezroq kechadi. Biroq keshning sig‘imi dastlabki maʼlumotlar saqlanadigan xotira hajmiga nisbatan ancha cheklangan.
Tarixi
«Cache» so‘zi kompyuter texnologiyalariga oid maʼnoda ilk bor 1967-yilda «IBM Systems Journal» jurnalida nashr etish uchun maqola tayyorlanayotgan paytda ishlatilgan. Maqola 85-model xotirasini takomillashtirishga bag‘ishlangan bo‘lib, bu model IBM System/360 turkumida ishlab chiqilayotgan edi. Jurnal muharriri Layl Jonson «yuqori tezlikdagi bufer» o‘rniga mazmunni yaxshiroq ifodalaydigan atama topishni so‘radi. Biroq mos takliflar bo‘lmagach, o‘zi «cache» so‘zini taklif qildi. Maqola 1968-yil boshida nashr etildi, mualliflar IBM tomonidan mukofotlandi, ularning ishlanmasi keng tarqaldi va keyinchalik takomillashtirildi. «Kesh» so‘zi esa tez orada kompyuter adabiyotlarida umumqabul qilingan atamaga aylandi.
Ishlash tamoyili

Kesh — kirish tezligi yuqori bo‘lgan xotira bo‘lib, kirish tezligi pastroq xotirada (keyingi o‘rinlarda «asosiy xotira») doimiy saqlanadigan maʼlumotlarga murojaat qilishni tezlashtirish uchun mo‘ljallangan. Keshlashdan markaziy protsessorlar, qattiq disklar, brauzerlar, veb-serverlar, DNS va WINS.
Kesh yozuvlar to‘plamidan iborat. Har bir yozuv asosiy xotiradagi maʼlumot elementining nusxasi bo‘lgan maʼlumot elementi yoki maʼlumotlar bloki (maʼlumotlarning kichik qismi) bilan bog‘langan. Har bir yozuvning o‘z identifikatori mavjud bo‘lib, u ko‘pincha teg deb ataladi. Bu teg keshdagi maʼlumot elementlari bilan ularning asosiy xotiradagi nusxalari o‘rtasidagi moslikni belgilaydi.
Keshdan foydalanuvchi dastur yoki qurilma (markaziy protsessor, veb-brauzer, operatsion tizim) maʼlumotga murojaat qilganda, avval kesh tekshiriladi. Agar unda so‘ralgan maʼlumot elementi identifikatoriga mos identifikatorli yozuv topilsa, keshdagi maʼlumotdan foydalaniladi. Bunday holat keshga tushish (cache hit) deb ataladi. Agar keshda kerakli maʼlumot elementi joylashgan yozuv topilmasa, u asosiy xotiradan keshga o‘qib olinadi va keyingi murojaatlar uchun foydalanish mumkin bo‘ladi. Bunday holat keshga tushmaslik (cache miss) deb ataladi. Keshga murojaatlar orasida kerakli maʼlumot topilgan holatlar ulushi muvaffaqiyatli murojaatlar darajasi yoki muvaffaqiyatli murojaatlar koeffitsiyenti deb ataladi.
Masalan, veb-brauzer so‘ralgan URL manziliga mos veb-sahifaning mahalliy nusxasi diskdagi keshda bor-yo‘qligini tekshiradi. Bu misolda URL identifikator, veb-sahifa tarkibi esa maʼlumot elementlari hisoblanadi.
Kesh hajmi cheklangan bo‘lsa, maʼlumot topilmaganida joy bo‘shatish uchun ayrim yozuvlarni olib tashlashga qaror qilinishi mumkin. Qaysi yozuvni chiqarishni tanlashda turli almashtirish algoritmlari.
Keshdagi maʼlumot elementlari o‘zgartirilganda, bu o‘zgarishlar asosiy xotiraga ham yoziladi. Keshdagi maʼlumot o‘zgartirilishi bilan asosiy xotiraning yangilanishi orasidagi kechikish yozish siyosati.
Keshda darhol yozish qo‘llanganda har bir o‘zgarish asosiy xotiradagi maʼlumotning sinxron yangilanishiga sabab bo‘ladi.
Keshda kechiktirilgan yozish (yoki orqaga yozish) qo‘llanganda yangilash maʼlumot elementi keshdan chiqarilganda, davriy ravishda yoki mijoz so‘roviga ko‘ra bajariladi. O‘zgartirilgan maʼlumot elementlarini kuzatish uchun kesh yozuvlarida o‘zgarganlik belgisi (o‘zgartirilgan yoki «iflos») saqlanadi. Kechiktirilgan yozish qo‘llanadigan keshda maʼlumot topilmasa, asosiy xotiraga ikki marta murojaat qilish talab etilishi mumkin: birinchisi — almashtirilayotgan maʼlumotlarni keshdan xotiraga yozish, ikkinchisi — kerakli maʼlumot elementini o‘qish uchun.
Agar asosiy xotiradagi maʼlumot keshdan mustaqil ravishda o‘zgartirilishi mumkin bo‘lsa, keshdagi yozuv eskirgan bo‘lib qolishi mumkin. Keshlar o‘rtasidagi maʼlumotlar izchilligini taʼminlovchi o‘zaro ishlash protokollari kesh kogerentligini taʼminlash protokollari.
Apparat darajasida amalga oshirilishi
Markaziy protsessor keshi
Ish chastotasi oshib borayotgan protsessorlar va operativ xotira (RAM) quyi tizimining unumdorligi ortishi natijasida maʼlumot uzatish interfeysi hisoblash tizimining tor bo‘g‘iniga aylandi.
Operativ xotiraning takt chastotasi protsessornikidan ancha past bo‘lsa, kesh xotira unumdorlikni sezilarli oshirishi mumkin. Ayrim protsessor modellarida registrlarga qaraganda sekinroq bo‘lgan operativ xotiraga (RAM) murojaat vaqtini qisqartirish uchun o‘z keshi mavjud (ushbu registrlar va kiritish-chiqarish buferlarini nolinchi darajali kesh deb hisoblash mumkin). Kesh xotiraning takt chastotasi odatda markaziy protsessor chastotasidan uncha past bo‘lmaydi.
Quyidagi imkoniyatni qo‘llab-quvvatlaydigan protsessorlarda — virtual manzillashda — ko‘pincha kichik va yuqori tezlikdagi manzillarni tarjima qilish buferi (TLB) qo‘llanadi. Uning tezligi muhim, chunki xotiraga har bir murojaatda u tekshiriladi.
Turli keshlar (bitta yoki bir nechta protsessordagi) o‘rtasidagi sinxronlash muammosi kesh kogerentligi.
Kesh xotiraning turli darajalari o‘rtasida axborot almashishning, yaʼni kesh arxitekturasining uch turi mavjud: inklyuziv, eksklyuziv va noeksklyuziv.
Eksklyuziv kesh xotira turli kesh darajalarida saqlanayotgan maʼlumotlarning takrorlanmasligini nazarda tutadi (bu yondashuvni afzal ko‘ruvchi kompaniya — AMD).
Noeksklyuziv keshda turli darajadagi keshlar istalgan tarzda ishlashi mumkin.
Protsessor keshining darajalari
Markaziy protsessor keshi bir necha darajaga bo‘linadi. Keshlar darajasining eng ko‘p soni — to‘rtta. Universal protsessorda hozirgi vaqtda darajalar soni uchtagacha yetishi mumkin. Odatda N+1-darajadagi kesh xotira N-darajadagi kesh xotiraga qaraganda hajman kattaroq, ammo unga murojaat qilish va maʼlumot uzatish tezligi pastroq bo‘ladi.
- Eng tezkor kesh birinchi darajali kesh — L1 cache (level 1 cache) hisoblanadi. U protsessorning ajralmas qismi bo‘lib, protsessor bilan bitta kristallda joylashadi va uning funksional bloklariga kiradi. Zamonaviy protsessorlarda L1 odatda ikkiga — buyruqlar (instruksiyalar) keshi va maʼlumotlar keshiga bo‘linadi (Garvard arxitekturasi). Aksariyat protsessorlar L1 keshisiz ishlay olmaydi. L1 protsessor chastotasida ishlaydi va odatda unga har bir taktda murojaat qilish mumkin. Ko‘pincha bir vaqtning o‘zida bir nechta o‘qish va yozish amallarini bajarish mumkin.
- Tezkorlik bo‘yicha ikkinchi o‘rinda ikkinchi darajali kesh — L2 cache turadi. U ham odatda L1 kabi protsessor bilan bitta kristallda joylashgan. Protsessorlarning dastlabki versiyalarida L2 ona platadagi alohida xotira mikrosxemalari to‘plami sifatida amalga oshirilgan. L2 hajmi 128 kbaytdan 1—12 Mbaytgacha. Zamonaviy ko‘p yadroli protsessorlarda bir kristallda joylashgan ikkinchi darajali kesh yadrolar o‘rtasida taqsimlangan xotira hisoblanadi: keshning umumiy hajmi n Mbayt bo‘lsa, har bir yadroga n/c Mbayt to‘g‘ri keladi; bunda c — protsessor yadrolari soni.
- Uchinchi darajali keshning tezligi eng past, biroq uning hajmi juda katta — 24 Mbaytdan ortiq bo‘lishi mumkin. L3 oldingi darajadagi keshlarga qaraganda sekinroq, ammo operativ xotiradan baribir sezilarli darajada tezroq. Ko‘p protsessorli tizimlarda u umumiy foydalanishda bo‘ladi va turli L2 keshlaridagi maʼlumotlarni sinxronlash uchun mo‘ljallangan.
- To‘rtinchi darajali kesh ham mavjud. Undan foydalanish faqat ko‘p protsessorli yuqori unumdorlikdagi serverlar va meynfreymlar uchun maqsadga muvofiq. Odatda u alohida mikrosxema shaklida amalga oshiriladi.
Keshning assotsiativligi
Kesh xotiraning asosiy xususiyatlaridan biri — assotsiativlik darajasi — uning mantiqiy segmentlarga bo‘linishini ifodalaydi. Bunga sabab shuki, kerakli maʼlumotni topish uchun keshning barcha satrlarini ketma-ket ko‘rib chiqish o‘nlab takt talab qiladi va markaziy protsessorga o‘rnatilgan xotiradan foydalanishdagi yutuqni yo‘qqa chiqaradi. Shu bois operativ xotira kataklari kesh xotira satrlariga qatʼiy bog‘lanadi (har bir satrda belgilangan manzillar to‘plamiga tegishli maʼlumotlar joylashishi mumkin), bu qidirish vaqtini sezilarli qisqartiradi.
Kesh hajmi bir xil bo‘lganda assotsiativlik darajasi yuqoriroq bo‘lgan sxema sekinroq, ammo samaraliroq bo‘ladi (to‘rt oqimli amalga oshirishdan keyin har bir oqimga to‘g‘ri keladigan «nisbiy samaradorlik» o‘sishi kichik bo‘ladi).
Tashqi maʼlumot saqlash qurilmalarini keshlash
Ko‘pgina periferik maʼlumot saqlash qurilmalari ishni tezlashtirish uchun ichki keshdan foydalanadi. Xususan, qattiq disklarda 1 dan 256 Mbaytgacha kesh xotira ishlatiladi (NCQ/TCQni qo‘llab-quvvatlaydigan modellarda undan so‘rovlarni saqlash va qayta ishlash uchun foydalaniladi); CD/DVD/BD disk o‘qish qurilmalari ham qayta murojaatni tezlashtirish uchun o‘qilgan axborotni keshlaydi.
Operatsion tizim ham operativ xotiraning bir qismini disk amallarini keshlash uchun ishlatadi (masalan, o‘z kesh xotirasiga ega bo‘lmagan tashqi qurilmalar, jumladan, qattiq disklar, flesh xotira va disketlar uchun). Ko‘pincha qattiq diskni keshlashga bo‘sh turgan (jarayonlarga ajratilmagan) operativ xotiraning barchasi beriladi.
Tashqi maʼlumot saqlash qurilmalarini keshlash quyidagi omillar bilan bog‘liq:
- protsessorning operativ xotiraga murojaat qilish tezligi tashqi saqlash qurilmalari xotirasiga qaraganda yuzlab va undan ham ko‘p marta yuqori;
- diskli maʼlumot saqlash qurilmalari (qattiq, egiluvchan va optik disklar) ketma-ket joylashgan bir nechta blokni o‘qish va yozishda eng yuqori unumdorlikka erishadi. Diskning turli joylariga yakka-yakka murojaat qilinganda esa unumdorlik keskin pasayadi, bu o‘qish-yozish kallagi mexanik yuritmasining inersiyasi bilan bog‘liq.
- tashqi saqlash qurilmalari xotirasining turli bloklariga murojaat qilish chastotasi nihoyatda notekis:
- ayrim bloklardan bir nechta jarayon bir vaqtda o‘qish va yozish uchun foydalanishi (masalan, maʼlumotlar bazalarida)
- ayrim bloklar juda tez-tez o‘qilishi (indeks fayllari, fayl tizimidagi kataloglar)
- ayrim bloklarga juda tez-tez yozilishi (log fayllari, jurnallar, maʼlumotlar bazalari; fayl tizimi metamaʼlumotlari).
O‘qishda kesh blokni bir marta o‘qib, uning bitta nusxasini barcha jarayonlar uchun operativ xotirada saqlash va blok tarkibini (diskdan so‘rash bilan taqqoslaganda) «bir zumda» taqdim etish imkonini beradi. «Oldindan so‘rash» usuli ham mavjud: operatsion tizim fon rejimida kerakli blokdan keyingi bir nechta blokni ham keshga o‘qib oladi.
Yozishda kesh qisqa yozuvlarni saqlash qurilmalari samaraliroq qayta ishlaydigan kattaroq yozuvlarga birlashtirish yoki oraliq o‘zgarishlarni diskka yozmaslik imkonini beradi. Bunda blokning barcha oraliq holatlari jarayonlarga operativ xotiradan ko‘rinadi.
Tashqi saqlash qurilmalarini keshlash kiritish-chiqarish amallaridan foydalanishni optimallashtirish orqali tizim unumdorligini sezilarli oshiradi. Texnologiyaning afzalligi — fayllar bilan ishlaydigan ilovalar mantig‘ini o‘zgartirmagan holda xotira va diskdan foydalanishni dasturlarga sezilmas tarzda avtomatik optimallashtirishidir.
Yozishni keshlashning kamchiligi — dastur yozish so‘rovini yuborgan payt bilan blokning diskka haqiqiy yozilishi orasidagi vaqt oralig‘i hamda yozish amallari bajarilish tartibining o‘zgarishi. Elektr taʼminoti uzilganda yoki tizim qotib qolganda bu maʼlumot yo‘qolishiga yoxud tuzilmalar nomuvofiqligiga olib kelishi mumkin. Muammo majburiy davriy sinxronlash (keshning o‘zgartirilgan satrlarini yozish) va fayl tizimlarida jurnallash orqali yumshatiladi.
Dasturiy darajada amalga oshirilishi
Keshlashdagi yozish siyosati
Maʼlumotlarni o‘qishda kesh xotira unumdorlikni aniq oshiradi. Maʼlumotlarni yozishda esa tezlik yutug‘iga faqat ishonchlilikni pasaytirish evaziga erishish mumkin. Shu sababli turli ilovalarda kesh xotiraga yozishning har xil siyosatlari tanlanadi.
Kesh xotirada yozishning ikkita asosiy siyosati mavjud — to‘g‘ridan-to‘g‘ri yozish (write-through) va kechiktirilgan yozish (write-back):
- To‘g‘ridan-to‘g‘ri yozish — maʼlumot bevosita asosiy xotiraga yoziladi (va keshda takrorlanadi), yaʼni yozish keshlanmaydi.
- Kechiktirilgan yozish — maʼlumot avval keshga yoziladi. Asosiy xotiraga yozish esa keyinroq (keshdan chiqarilganda yoki muayyan vaqt o‘tgach) bajarilib, qo‘shni kataklarga bir nechta yozish amali bir operatsiyaga birlashtiriladi. Orqaga yozish texnologiyasi asosiy xotiradagi maʼlumotni maʼlum muddat eskirgan holatda qoldiradi. Markaziy protsessorning o‘zi bu tafovutni sezmaydi, lekin tizim shinasining boshqa boshqaruvchi qurilmasi (DMA kontrolleri yoki PCI shinasidagi bus-master qurilmasi) xotiraga murojaat qilishidan avval keshdagi maʼlumot majburiy ravishda asosiy xotiraga yozilishi kerak. Ko‘p protsessorli tizimda orqaga yozish qo‘llansa, turli protsessorlarning keshlari o‘zaro muvofiqlashtirilishi (yoki protsessorlar bitta umumiy kesh xotiradan foydalanishi) lozim.
Kechiktirilgan yozishli keshning ishlash algoritmi
Dastlab barcha bufer sarlavhalari bo‘sh buferlar ro‘yxatiga joylanadi. Jarayon blokni o‘qimoqchi yoki o‘zgartirmoqchi bo‘lsa, quyidagi algoritmni bajaradi:
- Berilgan raqamli bufer sarlavhasini xesh-jadvaldan izlaydi;
- topilgan bufer band bo‘lsa, uning bo‘shashishini kutadi;
- agar bufer xesh-jadvalda topilmasa, bo‘sh buferlar ro‘yxatining oxiridan birinchi buferni oladi;
- agar bo‘sh buferlar ro‘yxati bo‘sh bo‘lsa, almashtirish algoritmi bajariladi (quyiga qarang);
- agar olingan bufer «iflos» deb belgilangan bo‘lsa, uning tarkibi tashqi xotiraga asinxron tarzda yoziladi.
- bufer xesh-jadvalga kiritilgan bo‘lsa, uni jadvaldan olib tashlaydi;
- buferni yangi raqam bilan xesh-jadvalga kiritadi.
Jarayon olingan buferga maʼlumotni o‘qiydi va keyin uni bo‘shatadi. Agar maʼlumot o‘zgartirilgan bo‘lsa, jarayon buferni bo‘shatishdan oldin uni «iflos» deb belgilaydi. Bo‘shatilgan bufer bo‘sh buferlar ro‘yxatining boshiga joylanadi.
Shunday qilib:
- agar jarayon biror blokni buferga o‘qigan bo‘lsa, boshqa jarayon shu blokni o‘qiyotganda buferni operativ xotiradan topishi ehtimoli yuqori;
- tashqi xotiraga maʼlumot yozish faqat «toza» buferlar yetishmaganda yoki so‘rov bo‘yicha amalga oshiriladi.
Almashtirish algoritmi
Bo‘sh buferlar ro‘yxati bo‘sh bo‘lsa, buferni almashtirish algoritmi bajariladi. Almashtirish algoritmi kesh unumdorligiga sezilarli taʼsir qiladi. Quyidagi algoritmlar mavjud:
- Asosiy vosita — taymer:
- Asosiy vosita — hisoblagich:
Qaysi algoritmni tanlash maʼlumotlarni keshlash strategiyasiga bog‘liq. Agar maʼlumotlar yaqin vaqt ichida albatta qayta ishlatilsa, LRU eng samarali bo‘ladi. Aksincha, maʼlumotlar yaqin vaqt ichida qayta ishlatilmasligi aniq bo‘lsa, MRU eng samarali hisoblanadi. Ilova maʼlumotlarning muayyan to‘plami uchun keshlash strategiyasini aniq belgilasa, kesh eng samarali ishlaydi.
Operatsion tizim tomonidan keshlash
Operativ xotira keshi quyidagi qismlardan iborat:
- tegishli tashqi xotira qurilmasi maʼlumotlar blokining uzunligiga teng buferlarga ajratilgan operativ xotira sahifalari to‘plami;
- tegishli bufer holatini tavsiflaydigan bufer sarlavhalari to‘plami;
- xesh-jadval — blok raqami bilan uning sarlavhasi o‘rtasidagi moslikni saqlovchi jadval;
- bo‘sh buferlar ro‘yxatlari.
Internet sahifalarini keshlash
Axborot tarmoq orqali uzatilayotganda internet sahifalarini keshlashdan foydalanish mumkin. Bu tez-tez so‘raladigan hujjatlarni (oraliq) proksi-serverlarda yoki foydalanuvchi kompyuterida saqlash jarayoni bo‘lib, ularni manba serverdan doimo qayta yuklash zaruratini yo‘qotish va trafikni kamaytirishga xizmat qiladi. Shu tariqa maʼlumot foydalanuvchiga yaqinroq joylashtiriladi. Keshlashni boshqarish HTTP sarlavhalari orqali amalga oshiriladi.
Veb-sahifalarni keshlashning yana bir usuli — «teskari proksi» yoki muayyan saytning CMS tizimidan foydalanishdir. Bu saytga kiruvchilar soni ko‘p bo‘lganda server yuklamasini kamaytiradi. Keshlash operativ xotirada ham, fayl keshida ham amalga oshirilishi mumkin. Keshlashning kamchiligi shundaki, bir brauzerda kiritilgan o‘zgarishlar maʼlumotni keshdan oladigan boshqa brauzerda darhol aks etmasligi mumkin.
Ish natijalarini keshlash
Ko‘plab dasturlar oraliq yoki yordamchi ish natijalarini har safar kerak bo‘lganda qayta hisoblamaslik uchun biror joyga yozib qo‘yadi. Bu ishni tezlashtiradi, ammo qo‘shimcha xotira (operativ yoki disk xotirasi) talab qiladi. Bunday keshlashga maʼlumotlar bazalarini indekslash.
Adabiyotlar
- Bax M. J. UNIX operatsion tizimining arxitekturasi