Ikkinchi imkoniyat

Sahifalarni almashtirishning optimal algoritmi
Sahifalarni almashtirish strategiyalaridan biri quyidagicha: eng ko’p vaqt davomida ishlatilmaygan sahifalar almashtiriladi. Bu sog’lom fikr nuqtai nazaridan juda oqilona strategiya: sahifa avvalgi oxirgi marta ishlatilgan bo'lsa, unda asosiy xotiraga shunchalik kam kerak bo'ladi. Ushbu algoritmni bir xil so'rovlar qatori va har bir jarayon uchun maksimal to'rtta freymlar bilan ishlatish misolini ko'rib chiqamiz:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Bundan ko’rish qiyin emaski, hammasi bo’lib, 6 ta sahifa hatoliklari bo’ladi (FIFO algoritmidan farq qiladi, ya’ni unda 10 sahifa xatoligi mavjud edi). FIFO algoritmi uchun 9-rasmda ishlatilgan so'rovlar qatori bilan sahifalarni almashtirishning optimal algoritmidan foydalanish misoli 11-rasmda keltirilgan.

11-rasm. Sahifalarni almashtirishning optimal algoritmini qo’llashga misol.
Least Recently Used (LRU) algoritmi
Sahifalarni almashtirishning bu algoritmi quyidagi printsipga asoslanadi: Eng so’ngi ishlatilgan sahifalar almashtiriladi.
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 so’rovlar qatori qo’llanilgan misolda sahifa xatoliklari soni 4 ga teng bo’ladi.
Shunga qaramay, shuni yodda tutish kerakki, tizim tomonidan sahifaga oxirgi kirish vaqti haqida ma'lumotdan foydalanish oxirgi marta kirish vaqtining qiymatini (time stamp) sahifalar jadvalining har bir elementida saqlashni talab qiladi. Sahifalar jadvalining har bir elementida hisoblagich saqlanadi. Har safar sahifalar jadvalining ba'zi elementlari orqali sahifaga murojaat qilinganda tizim soati (clock) tarkibi uning hisoblagich maydoniga ko'chiriladi.
Agar sahifaning konfiguratsiyasini o’zgartirish talab qilinsa, sahifalar jadvalining barcha elementlarining hisoblagich maydonini tahlil qilish zarur bo’ladi, ya’ni aynan keyingi qadamda qaysi sahifa almashtirilishi aniqlanishi zarur bo’ladi. Sahifalar jadvalining minimal hisoblagich qiymatli elementini aniqlash uchun massvida minimal elementni topish algoritmini qo’llash talab qilinadi, bu algoritmning qiyinlik darajasi O  bo’lib, bu yerda n – sahifalar jadvalining uzunligi.
Aynan yuqorida keltirilgan algoritmlar (9-rasm va 11-rasmlar)da ishlatilgan so’rovlar qatorida sahifalarni almashtirishning LRU algoritmini qo’llashga misol 12-rasmda keltirilgan.

12-rasm. Sahifalarni almashtirishning LRU algoritmining qo’llanishiga misol.
Ushbu algoritmni optimallashtirish uchun, ya’ni har bir sahifani almashtirishda sahifalar jadvalidan minimal elementni qidirishdan qochish uchun, stekli amalga oshirish qo’llaniladi - Dlya optimizatsii dannogo algoritma, chtobы izbejat’ poiska minimal’nogo elementa tablitsы stranits pri kajdom zameщenii stranits, ispol’zuetsya stekovaya realizatsiya – sahifa tartib raqamlarini saqlovchi stek ikkibog’lamli ro’yxat shaklida bo’ladi. Sahifaga murojaat vaqtida u ro’yxat boshiga siljitiladi (buning uchun 6 ta ko’rsatkichlarni o’zgartirish talab etiladi). Algoritmning bunday modifikatsiya qilinishi sahifalarni almashtirish uchun qidirish talab etilmaydi.
13-rasmda LRU algoritmidagi eng so'nggi sahifalarga murojaatni saqlash uchun stekdan foydalanishga misol keltirilgan.