Birinchisiga nisbatan optimal taqsimlash (Best-Fit Versus First-Fit

Birinchisiga nisbatan optimal taqsimlash (Best-Fit Versus First-Fit
Allocation)
Birinchi (First-Fit Allocation) mos keladigan taqsimlash
sxemasidan foydalanib, 1-vazifa birinchi mavjud bo‘sh joyni talab
qiladi va egallaydi. Operatsion tizim mos qismni qidirmaydi, lekin
yetarli hajmga ega bo‘lgan eng yaqin joylashgan xotira qismiga ishni
taqsimlaydi.
Ushbu qismlar birinchi mos keladigan xotirani ajratish (birinchi
qism talablariga javob beradi) yoki eng yaxshi (yo‘qotishlarning eng
kam miqdori, talablarga javob beradigan eng kichik qism) xotira
taqsimoti (Best-Fit Allocation) asosida ajratilishi mumkin. Ikkala
sxemada ham xotira menejeri bo‘sh yoki foydalanilgan qismlarning
(bo‘sh/band) xotira ro‘yxatlarini hajmiga yoki joylashishiga qarab
tashkil qiladi. Eng yaxshi mos keladigan taqsimlash usuli bo‘sh/band
bo‘lgan ro‘yxatlarni kichikdan kattasiga qarab tartiblaydi. Birinchi
mos usul (first-fit method) xotira maydonlari tomonidan tashkil
etilgan bo‘sh/band bo‘lmagan ro‘yxatlarni, past darajali xotiradan
yuqori darajali xotiraga qadar saqlaydi. Ularning har biri ma’lum bir
taqsimlash sxemasining ehtiyojlariga qarab o‘z afzalliklariga ega - eng
yaxshi taqsimlash usuli odatda xotira maydonidan unumli
foydalanishni ta’minlaydi, birinchi mos taqsimlash algoritmi tezroq
taqsimlashni amalga oshiradi.
Birinchi mos keladigan sxemadan foydalanib, 1- vazifa birinchi
bo‘sh joyni talab qiladi. 2- vazifa, birinchi qismni talab qiladi,
joylashishi uchun yetarlicha katta, ammo 3- vazifani bajarish uchun
yetarlicha katta bo‘lgan oxirgi blokni talab qiladi. Shuning uchun, 3-
vazifa (yulduzcha bilan belgilangan) 75 Mb foydalanilmagan xotira
maydoni (ichki qism) mavjud bo‘lsa ham, katta blok paydo
bo‘lguncha kutishi kerak. E’tibor bering, xotira ro‘yxati xotira
maydoniga qarab tartiblangan.
106
3.9- rasm. Birinchi mos keladigan sxemadan foydalanish
Xotiradan foydalanish hajmi oshirildi, ammo xotirani taqsimlash
jarayoni ko‘proq vaqtni talab etadi. Bundan tashqari, ichki bo‘linish
kamaygan bo‘lsa ham, u to‘liq yo‘q qilinmadi.
Birinchi mos keladigan algoritm, xotira menejeri uchun ikkita
ro‘yxatni saqlaydi, birinchisi bo‘sh xotira bloklari va ikkinchisi band
qilingan xotira bloklari. Operatsiya har bir vazifa hajmini har bir
xotira blokining o‘lchami bilan mos keladigan yetarlicha katta blok
topilmaguncha taqqoslaydigan oddiy sikldan iborat. Keyin vazifa
ushbu xotira blokida saqlanadi va xotira menejeri keyingi navbatni
kirish navbatidan olish uchun sikldan chiqadi. Agar butun ro‘yxat
behuda qidirilsa, u holda vazifa kutish navbati ichiga joylashtiriladi.
Keyin xotira menejeri keyingi vazifani tanlaydi va jarayonni
takrorlaydi.
Eng yaxshi taqsimlash sxemasi mos keladi. 1-vazifa 2 va 3-
vazifalar kabi eng yaqin bo‘sh qismda taqsimlanadi. 4-vazifa eng mos
bo‘lmasa ham, bo‘sh bo‘lgan yagona qismga taqsimlangan. Ushbu
sxemada barcha to‘rtta vazifa kutishsiz qayta ishlanadi. Yodda tuting,
xotira ro‘yxati xotira hajmiga qarab tartiblangan. Ushbu sxema
yordamida xotiradan yanada samarali foydalaniladi, ammo uni amalga
oshirish sekinroq hisoblanadi.
107
3.10- rasm. Eng mos keladigan sxemadan foydalanish
Eng mos va birinchi mos keladigan algoritmlar juda farq qiladi.
Birinchi usul qanday amalga oshiriladi:
First-Fit Algoritmi
1.
Hisoblagichni 1 ga o‘rnatish
2.
Bajarishda, hisoblagich <= xotiradagi bloklar soni
Agar vazifa hajmi > xotira hajmi (hisoblagich) bo‘lsa
Unda, hisoblagich = hisoblagich + 1
Xotiraga (hisoblagich) vazifani yuklash
Bo‘sh/band xotira ro‘yhatlarini sozlash
4-bosqichga o‘tish
Tugatish
3.
Vazifani kutish navbatiga qo‘yish
4.
Keyingi vazifaga o‘tish.
3.2-jadvalda 200 bo‘sh maydonni bloklash so‘rovi faqat xotira
menejeriga berilgan (maydonlar so‘zlar, baytlar yoki tizim
boshqaradigan boshqa birlik bo‘lishi mumkin). Birinchi mos
keladigan algoritmdan foydalanib va ro‘yxatning yuqorisidan boshlab,
xotira menejeri 6785 manzilida joylashgan vazifani bajarishi uchun
yetarlicha katta bo‘lgan birinchi xotira blokini topadi. Keyin, vazifa
6785 maydondan boshlanib, keyingi 200 bo‘sh maydonni egallaydi.
Keyingi qadam, bo‘sh xotira bloki hozirda 6985 (6785 emas, balki
108
avvalgi kabi) maydonda joylashganligini va unda faqat 400 ta bo‘sh
maydon mavjudligini (oldingidek 600 emas) belgilash uchun bo‘sh
ro‘yxatni o‘rnatishdir.
3.2- jadval
Eng yaxshi moslashtirish algoritmi biroz murakkabroq, chunki
maqsad vazifa uchun mos keladigan eng kichik xotira blokini
topishdir:
Best-Fit Algoritmi
1. xotira blokini (0) = 99999 ishga tushirish
2. boshlang‘ich xotira yo‘qotilishi = xotira bloki (0) – vazifa
hajmini hisoblash
3. Indeksni = 0 ga sozlash
4. Hisoblagichni 1 ga o‘rnatish
5. Hisoblagich < = xotiradagi bloklar soni bo‘lsa bajarish
Agar vazifa hajmi > xotira hajmi (hisoblagich) bo‘lsa
Unda, hisoblagich = hisoblagich + 1
Keyin
Xotiradagi yo‘qotish = xotira hajmi (hisoblagich) – vazifa hajmi
Agar boshlang‘ich xotira yo‘qotishlari > xotira yo‘qotishlari
Unda, indeks = hisoblagich
boshlang‘ich xotira yo‘qotishlari = xotira yo‘qotishlari
hisoblagich = hisoblagich + 1
Bajarishni tugatish
6. Agar indeks = 0 bo‘lsa
Unda, vazifani kutish navbatiga qo‘yish
Keyin
109
xotira maydoniga (pastki indeks) vazifani yuklash
bo‘sh/band xotira ro‘yxatlarini o‘rnatish
7. Keyingi vazifaga o‘tish.
Eng yaxshi moslangan algoritm bilan bog‘liq muammolardan
biri shundaki, tanlovni amalga oshirishdan oldin, butun jadvalni
qidirishi kerak, chunki xotira bloklari fizik xotirada joylashgan joyiga
qarab ketma-ket saqlanadi (3.10-rasmda ko‘rsatilganidek, xotira
qismlari hajmiga qarab emas). Tizim xotira qismining o‘lchamlari
oshib boradigan tartibda ro‘yxatni doimiy ravishda tiklash algoritmini
ishlab chiqishi mumkin, ammo bu qo‘shimcha xarajatlarni keltirib
chiqaradi va uzoq muddatda qayta ishlash vaqtidan unumli
foydalanishi mumkin emas. Eng yaxshi mos keladigan algoritm faqat
bo‘sh xotira bloklari ro‘yxati bilan tasvirlangan.
3.3- jadval
Ushbu jadvalda eng yaxshi mos keladigan algoritmdan
foydalangan holda, so‘rovdan oldingi va keyingi har bir xotira
blokining holatini ko‘rsatadi. Jadvalda 200 ta bo‘sh joyni bloklash
to‘g‘risidagi so‘rov endigina xotira menejeriga jo‘natildi. Eng yaxshi
mos keladigan algoritmni qo‘llagan holda va ro‘yxatning yuqorisidan
boshlab, xotira menejeri barcha ro‘yxatni qidiradi va 7600 manzilidan
boshlab xotira blokini topadi, bu vazifani bajarish uchun yetarlicha
katta bo‘lgan eng kichik blokdir. Xotira menejeri eng yaxshi mos
keladigan algoritmdan foydalanib, ro‘yxatning yuqori qismidan
boshlab, butun ro‘yxatni qidiradi va 7600 manzilidan boshlanadigan
xotira blokini topadi, bu vazifani bajarish uchun yetarlicha katta
bo‘lgan eng kichik blokdir. Ushbu blokni tanlash bo‘sh joyni bexuda
110
sarflashni kamaytiradi (faqatgina 5K bo‘sh joy yo‘qotiladi, bu to‘rtta
alternativ blokga qaraganda kamroq). Keyin vazifa 7600 manzildan
boshlanib, keyingi 200 ta manzilni egallaydi.
Eng yomon moslash usuli: ro‘yxatdan eng mos keladigan eng
katta maydonni tanlashdir. Nima uchun eng katta? Bo‘linishning
oldini olish uchun (bo‘linish muammosi ushbu ma’ruzada batafsil
ko‘rib chiqiladi). Birinchi va ikkinchi strategiyalarni qo‘llash quyidagi
nuqtai nazardan yaxshiroq: bajarilish tezligi va ishlatilgan xotiraning
minimal hajmi bo‘yicha. Biroq, ulardan foydalanish bo‘linishni
keltirib chiqarishi mumkin.
|