Virtual xotira tushunchasi. Virtual xotirani sahifali tashkil etish

Sahifalarni almashtirishning optimal algoritmi

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(n) bo’lib, bu yerda n – sahifalar jadvalining uzunligi.

Sahifalarni almashtirishning LRU algoritmining qo’llanishiga misol

LRU algoritmidagi eng so'nggi sahifalarga murojaatni saqlash uchun stekdan foydalanishga misol

• Ushbu algoritmni optimallashtirish uchun, ya’ni har bir sahifani almashtirishda sahifalar jadvalidan minimal elementni qidirishdan qochish uchun, stekli amalga oshirish qo’llaniladi -– 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.