14-mavzu. Kesh xotira xususiyatlari, asosiy va kesh xotiralarga murojaat qilish algoritmlari

Almashish algoritmlari.
To’g’ri akslanuvchi keshda har bir blokning o’rni ma’lum, bloklarni almashtirish strategiyasi shart emas. Assotsiatv va to’plam-assotsiativ keshda esa bloklarni turli usullarda almashtirish mumkin. Keshga yangi blokni joylashda u to’lgan bo’lsa, kesh kontrolleri bloklardan birini o’chirishni tanlashi zarur. Buni qanday hal qilishiga esa tizimning unumdorligi bog’liq bo’ladi. Asosiy g’oya shundayki, xotirada yaqin orada kerak bo’ladigan bloklar uchun joy qolishi kerak. Buni qanday aniqlash mumkin? Bu yerda murojaatlarni lokallashtirish prinsipi (tamoyili) ga suyanish mumkin. Ma’lum sohadagi takrorlanuvchi komandalar, ma’lum vaqt oralig’ida ishlatilib turilar ekan, yaqinda murojaat qilingan bloklarga yana murojaat qilish ehtimoli yuqoriroq bo’ladi. Shu sababdan eng uzoq vaqt davomida murojaat qilinmagan blokk endi ehtiyoj sezilmasli ehtimoli yuqori bo’ladi. Bunday algoritm eng uzoq vaqt ishlatilmagan bloklarni o’chirish algoritmi deyiladi (Last Recentli Used - LRU).
LRUni ishlatish uchun kesh-kontroller barcha bloklarga murojaatni kuzatib borishi kerak. Har bir blokka 2 razryadli hisoblagich ishlatiladi. Dastlab barcha bloklarning hisoblagichlari 0 ga teng bo’ladi. Har murojaatda hisoblagich 1 ga oshadi. Keshda keraklo blok mavjud bo’lmasa, yangi keluvchi blok uchun joy mavdud bo’lsa, yangi blok uchun 0 qiymat o’rnatiladi, keshda mavjud barcha hisoblagichlar qiymati 1 ga oshiriladi. Agar to’plam to’lgan bo’lsa, hisoblagich ko’rsatkichi 3 ga teng blok o’chiriladi,uning o’rniga yangi blok yoziladi. Barcha hisoblagishlarning qyimati 1 ga oshiriladi. Ko’rinib turibdiki, barcha bloklarning ko’rsatkichlari har xil bo’ladi.
LRU algoritmi keng qo’llaniladi. Ba’zi hollarda uni qo’llash unumdorlikni pasayishiga olib keladi, masalan massiv elementlariga ketma-ket murojaat qilishda, agar massiv ko’p sonli bo’lib, keshga sig’masa va shu kabi holatlarda.