Vazifalar ro‘yxati:
10K
20K
35K
55K
V1 tugatildi V4 tugatildi
10K
Operatsion tizim
|
|
Vazifa 2 (15K)
|
Vazifa 3 (20K)
|
|
20K
35K
55K
V5 (5K) V6 (30K)
10K
Operatsion tizim
|
Vazifa 5 (5K)
|
|
Vazifa 2 (15K)
|
Vazifa 3 (20K)
|
Vazifa 6 (30K)
|
|
15K
20K
35K
55K
85K
105K
Vazifani kiritish uchun dastlabki xotirani ajratish (a)
105K
1 va 4 vazifalar tugatilgandan so‘ng (b)
105K
Keyin, 5 va 6 vazifalar kiritildi (c)
V3 tugatildi
10K
Operatsion tizim
|
Vazifa 5 (5K)
|
|
Vazifa 2 (15K)
|
|
Vazifa 6 (30K)
|
|
15K
20K
35K
55K
85K
V7 (10K) V8 (30K)
10K
15K
Vazifa 2 (15K)
20K
Vazifa 7
(10K)
35K
45K
Vazifa 6 (30K)
55K
85K
V8 (30K)
kutishi kerak
105K
3 vazifa bajarilgandan so‘ng (d)
105K
Keyin, 7 vazifa kiritildi (e)
3.8- rasm. Qismlarni dinamik taqsimlashda asosiy xotiradan foydalanish
Xotiranitaqsimlashningumumiyvazifasimavjud: bo‘shxotiramaydonlariro‘yxativaturlio‘lchamdagibandqilinganmaydon larro‘yxatimavjud. Ushbu muammoni hal qilish uchun quyidagi algoritmlar (strategiyalar) qo‘llaniladi: birinchi mos usul (First-Fit algorithm), eng yaxshi moslash usuli (Best-Fit algorithm) va eng yomon moslash usuli (Worst-Fit algorithm).
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.
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.
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
Hisoblagichni 1 ga o‘rnatish
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
Vazifani kutish navbatiga qo‘yish
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
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
xotira blokini (0) = 99999 ishga tushirish
boshlang‘ich xotira yo‘qotilishi = xotira bloki (0) – vazifa hajmini hisoblash
Indeksni = 0 ga sozlash
Hisoblagichni 1 ga o‘rnatish
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
Agar indeks = 0 bo‘lsa
Unda, vazifani kutish navbatiga qo‘yish Keyin
xotira maydoniga (pastki indeks) vazifani yuklash bo‘sh/band xotira ro‘yxatlarini o‘rnatish
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
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.
|
