Virtual xotira tushunchasining moslashishi

7-rasm. Qurbon sahifani diskka yuklash bilan sahifalarni almashtirish.
Sahifalarni almashtirish bosqichlari: 1 – qurbonni diskka yuklash; 2 – sahifalarni jadvalidagi uning elementini o’zgartirish (valid biti invalidga almashadi); 3 – talab qilingan sahifani bo’shatilgan (qurbon-sahifadan) joyga yuklash; 4 – sahifalar jadvalining elementini yangi sahifa uchun o’zgartirish (invalid biti validga almashadi; yuklangan sahifaning fizik adresi eslab qolinadi).
Sahifalarni almashtirish algoritmlari
Yuqoridagilardan ko'rinib turibdiki, sahifalarni almashtirishning optimal algoritmini qidirish quyidagi mezonga asoslanishi kerak: sahifaning xatolik koefitsienti p ning kamayishiga erishish kerak.
Algoritmni xotiraga kirishning ma'lum bir satrida (so'rovlar satrida) sinab ko'rish va berilgan so'rovlar satri uchun sahifadagi xatolar sonini aniqlash orqali baholash mumkin. Quyida keltirilgan ushbu bo'limdagi barcha disk xotira misollarida so'rovlar qatori quyidagicha ko'rinadi:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
Sahifa xatoliklari sonining asosiy xotiradagi freymlar soniga bog'liqligi grafigi 8-rasmda tasvirlangan.

8-rasm. Sahifa xatoliklari sonining freymlar soniga bog’liqlik grafigi.
Umuman olganda, tasvirdan ko'rinib turibdiki, munosabatlar teskari proporsionaldir: freymlar qancha ko'p bo'lsa, sahifa xatoliklari shunchalik kam bo’ladi. Shu bilan birga, ushbu qonuniyatda quyida muhokama qilinadigan anomaliyalar ham mavjud.
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.
Bu anomaliya Belady anomaliya deyiladi.
Umuman olganda, yuqorida aytib o'tilganidek, bog'liqlik shundan iboratki, jarayon qancha freymlarga ega bo'lsa (yetarli miqdordagi freymlar bilan), shunchalik kam sahifadagi xatoliklar bo’ladi.
Jarayon uchun maksimal freymlar soni 3 ga teng bo'lganda, sahifalarni almashtirish uchun FIFO algoritmining ishlashining namunasi 9-rasmda keltirilgan.

9-rasm. FIFO algoritmining ishlashiga misol.
10-rasmda Belady anomaliyasini tasvirlovchi, FIFO algoritmi bilan sahifalardagi xatoliklar sonining freymlar soniga bog'liqligi chizmasi ko'rsatilgan.

10-rasm. Sahifalarni almashtirishda FIFO algoritmini qo’llashdagi Belady anomaliyasi.