Virtual xotira tushunchasi. Virtual xotirani sahifali tashkil etish

Sahifalarni almashtirishning qisqa algoritmini quyidagicha rasmiylashtirish mumkin

• 1. Talab qilingan sahifa diskda qaerda joylashganligini topish.
• 2. Bo’sh freymni topish:
• -Agar bo’sh freym bo'lsa, undan foydalanish.
• -Agar bo'sh freymlar bo'lmasa, freymni tanlash uchun sahifani almashtirish algoritmidan foydalanish - "qurbon"ni aniqlash.
• 3. Talab qilingan sahifaning tarkibini yangi bo'shatilgan freymga o'qish (joylashtirish). Freymlar va sahifalar jadvallarini o'zgartirish.
• 4. Jarayonning bajarilishini davom ettirish.

Sahifalarni almashtirish algoritmlari

• FIFO (First-In-First-Out) algoritmi. Sahifalarni almashtirishning eng oddiy algoritmi –asosiy xotiraga o'qilgan birinchi freym har doim jabrlanuvchi sifatida tanlanadi. Ushbu algoritmning qo’llanilishiga misol.
• So’rovlar satri quyidashi ko’rinishga ega bo’lsin: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
• 1-holat: 3 ta freym (bitta jarayon uchun 3 sahifa bir vaqtning o’zida xotirada bo’lishi mumkin). Uchta jarayon bo'lsin. Ularning sahifalar jadvallari quyidagicha bo'ladi:
• (1, 2, 3) (4, 1, 2) (5, 3, 4).
• Bunday holda, 9 ta sahifa xatoligi mavjud (mashq sifatida tekshiring).
• 2-holat: 4 ta freym. Oldingidek, 3 ta jarayon bo’lsin. Bu holda sahifalar jadvali quyidagicha bo’ladi:
• (1, 2, 3, 4) (5, 1, 2, 3) (4, 5)
• Jarayon avvalgi holatga qaraganda ko'proq bo'sh freymlarga ega bo'lishiga qaramay, bu holda 10 (!) sahifada xatolik borligini ko’rish mumkin.

FIFO algoritmining ishlashiga misol

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 ishlatilgan so'rovlar qatori bilan sahifalarni almashtirishning optimal algoritmidan foydalanish misoli quyidagi rasmda keltirilgan.