13-rasm. Eng so'nggi sahifalarga murojaatni saqlash uchun LRU algoritmidagi stekdan foydalanish.
LRU algoritmiga yaqin bo’lgan algoritm LRU algoritmiga yaqin bo’lgan bir nechta algoritmlar mavjud bo’lib, bu algoritmlarda LRU algoritmining kamchiliklarini kamaytirish uchun turli xil yaxshilangan yoki soddalashtirilgan g’oyalar tatbiq qilingan.
1. Bog’lanish (havola) biti (reference bit). Bu algoritmda har bir sahifa bit bilan bog’lanadi, dastlab bu bit 0 ga teng. Sahifaga murojaat vaqtida bitga 1 o’rnatiladi. Sahifalarni almashtirish vaqtida bit qiymati 0 ga teng bo’lgan sahifa (agar shunday sahifa mavjud bo’lsa) ushbu sahifa almashtiriladi, ya’ni murojaat bo’lmagan sahifa almashtiriladi. Algoritmaning ushbu versiyasi sahifalar jadvalidan minimal qiymatni qidirishdan voz kechish imkonini beradi. Lekin bu LRU ga nisbatan unchalik optimal emas.
2. Ikkinchi imkoniyat (second chance). Algoritmning ushbu versiyasida sahifalar jadvalidagi har bir elementda saqlanadigan mos yozuvlar - bog’lanish biti va soati ko’rsatkichi ishlatiladi. Sahifalarni almashtirish soat ko’rsatkichiga asoslanadi. Agar sahifa almashtirilishi kerak (soat ko’rsatkichi bo’yicha) va bog’lanish biti 1 ga teng bo’lsa, u holda quyidagi amallar bajariladi:
- bog’lanish bitini 0 ga o’rnatish;
- sahifani xotirani qoldirish;
- aynan shu qoidalar bo’yicha keyingi sahifani almashtirish (soat ko’rsatkichi bo’yicha).
Bu algoritm quyidagi evristik asoslarga ega. Eng uzoq vaqt ishlatilmagan sahifa, xuddi undan foydalanish uchun ikkinchi imkoniyat berilgandek, ya’ni vaqt o’tishi bilan uzoq vaqt davomida murojaat qilinmagan sahifaga murojaat ehtimoli kuchayadi degan evristik taxmin qilinadi.
Ikkinchi imkoniyat algoritmining sxemasi 14-rasmda keltirilgan.
14-rasm. Ikkinchi imkoniyat algoritmi.
Hisoblagichli algoritmlar LRU algoritmi g'oyasi bilan bog'liq g'oya – har bir sahifaga murojaatlar soni hisoblagichda saqlanadi. Ushbu g’oyaga asoslanadigan ikkita algoritm mavjud:
- Least Frequently Used (LFU) algoritmi: sahifalarni hisoblagichning minimal qiymati (eng kam murojaat qilingani) bilan almashtirish;
- Most Frequently Used (MFU) algoritmi: hisoblagichning maksimal qiymati bilan sahifalarni almashtirish. Ushbu algoritm minimal hisoblagichli sahifa yaqinda yuklanganligi va u kelajakda faol ishlatilishi mumkin degan ehtimol mavjudligi uchun u xotirada qoladi, degan g’oyaga asoslanadi.
