U. R. Xamdamov, dj. B. Sultanov, S. S. Parsiyev, U. M. Abdullayev

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.