Mavzu: xotirani taqsimlash usullari

2. Dinamik xotira taqsimoti
Dinamik xotira ajratish dastur bajarilayotgan vaqtda amalga oshiriladi. Bu erda xotira dasturning ob'ektlari dastur ishlayotgan vaqtda birinchi marta foydalanilishi kerak bo'lganda ajratiladi. Kerakli ma'lumotlarning haqiqiy hajmi ish vaqtida ma'lum bo'ladi, shuning uchun u dasturga aniq xotira maydonini ajratadi va shu bilan xotirani isrof qilishni kamaytiradi. Dinamik xotira taqsimoti dasturni bajarish uchun moslashuvchanlikni ta'minlaydi. Chunki u dastur uchun qancha xotira maydoni talab qilinishini hal qilishi mumkin. Agar dastur etarlicha katta bo'lsa, unda hozirda foydalaniladigan dasturning turli qismlarida dinamik xotira taqsimoti amalga oshiriladi. Bu xotira sarfini kamaytiradi va tizimning ish faoliyatini yaxshilaydi. Xotirani dinamik ravishda taqsimlash tizim ustidan ortiqcha yuk hosil qiladi. Ba'zi taqsimlash operatsiyalari dasturning bajarilishi davomida qayta-qayta bajariladi, bu esa dasturning sekin bajarilishiga olib keladi. Dinamik xotirani ajratish operatsion tizimdan maxsus yordamni talab qilmaydi. Dinamik xotirani taqsimlash usulidan foydalanish uchun dasturni loyihalash dasturchining zimmasida. Shunday qilib, dinamik xotira taqsimoti moslashuvchan, lekin statik xotira taqsimotiga qaraganda sekinroq.
Statik va dinamik xotira ajratishning afzalliklari
Statik xotirani taqsimlash
Statik xotira taqsimoti xotirani jarayonga tayinlashning samarali usulini ta'minlaydi.Barcha xotira tayinlash operatsiyalari bajarish boshlanishidan oldin amalga oshiriladi. Shunday qilib, dasturni bajarish vaqtida xotirani taqsimlash operatsiyalari uchun qo'shimcha xarajatlar yo'q.
Statik xotirani taqsimlash tezroq bajarilishini ta'minlaydi, chunki bajarilish vaqtida dasturga ajratilgan xotirada vaqtni yo'qotish shart emas.
Dinamik xotirani taqsimlash
Dinamik xotira taqsimoti xotirani jarayonga belgilashning moslashuvchan usulini ta'minlaydi. Dinamik xotira taqsimoti xotira sarfini kamaytiradi, chunki u ushbu dasturni bajarish jarayonida jarayonga xotirani tayinlaydi. Shunday qilib, u dastur tomonidan talab qilinadigan aniq xotira hajmidan xabardor. Agar dastur katta bo'lsa, dinamik xotira ajratish dasturning turli qismlarida amalga oshiriladi. Xotira dasturning hozirda ishlatilayotgan qismiga biriktirilgan. Bu shuningdek, xotira isrofgarchiligini kamaytiradi va haqiqatan ham tizim ish faoliyatini yaxshilaydi.
Statik va dinamik xotira ajratishning kamchiliklari
Statik xotirani taqsimlash
Statik xotirani taqsimlashda tizim dasturning xotira talabini bilmaydi. Shunday qilib, u dastur uchun zarur bo'lgan xotirani taxmin qilishi kerak. Statik xotira taqsimoti xotirani yo'qotishga olib keladi. Chunki u dastur tomonidan talab qilinadigan xotira hajmini taxmin qiladi. Shunday qilib, agar taxminiy o'lcham kattaroq bo'lsa, bu xotirani yo'qotishga olib keladi, aks holda taxminiy o'lcham kichikroq bo'lsa, dastur noto'g'ri ishlaydi.
Dinamik xotirani taqsimlash
Dinamik xotirani taqsimlash usuli xotirani jarayonga uni bajarish vaqtida tayinlash uchun qo'shimcha xarajatlarga ega. Ba'zan dasturni bajarish jarayonida xotirani ajratish harakatlari bir necha marta takrorlanadi, bu esa qo'shimcha xarajatlarga olib keladi. Amalga oshirish vaqtida xotirani taqsimlashning qo'shimcha xarajatlari ma'lum darajada bajarilishini sekinlashtiradi. Xotirani ajratish dastur yoki jarayon uchun xotira manzilini belgilaydi.
Xotirani taqsimlashda statik xotira ajratish va dinamik xotira ajratishning ikkita usuli mavjud. Statik xotirani taqsimlash samaradorlikni ta'minlaydi, chunki u xotirani bajarilishi boshlanishidan oldin jarayonga tayinlaydi. Shunday qilib, dasturni bajarish paytida xotirani ajratish operatsiyasi uchun ortiqcha yuk yo'q, bu dasturning tezroq bajarilishiga olib keladi. Statik xotirani ajratishda kerakli xotira hajmi dastur bajarilishidan oldin ma'lum bo'lishi kerak. Statik xotira ajratish jarayonga taxminiy xotira maydonini belgilaydi, chunki u dastur tomonidan talab qilinadigan xotira hajmini bilmaydi. Bu xotirani behuda sarflashga olib keladi. Dinamik xotirani ajratish dasturni bajarish vaqtida amalga oshiriladi. Shunday qilib, u xotirani isrof qilishdan saqlaydigan dasturga aniq xotira miqdorini ajratadi. Dinamik xotira taqsimoti dasturning bajarilishini sekinlashtiradigan dasturni bajarish paytida xotirani taqsimlash operatsiyasining qo'shimcha xarajatlariga ega.
Dinamik xotira ajratish xotirani taqsimlashda moslashuvchanlikni ta'minlaydi, go'yo dastur etarlicha katta bo'lsa, u dasturlarning turli qismlarida xotirani ajratish operatsiyalarini bajaradi va xotirani isrof qilishni kamaytiradi. Operatsion tizim samarali va moslashuvchan bajarish uchun statik va dinamik xotira ajratishning eng yaxshi aralashmasini olishi mumkin.
Dinamik xotirani boshqarish muntazam xotira ajratish va bo'sh joyni bo'shatishni talab qiladi. Ushbu maqolada x otirani ajratish uchun ishlatilishi mumkin bo'lgan bir nechta usullar keltirilgan. Malloc (xotirani ajratish) yoki bo'sh funksiyani chaqirish, ajratilgan xotira manziliga havolaga olib keladi yoki u har safar chaqirilganda boshqalar foydalanishi uchun xotirani bo'shatadi. Dinamik xotirani boshqarish muntazam xotira ajratish va bo'sh joyni tozalashni talab qiladi. Bo'shatilgan bo'sh joy bilan bir qatorda ishlatilgan joy bilan nima qilish kerak? Keyingi malloc qo'ng'irog'i uchun qaysi manzillar/uyalardan foydalanish kerakligini qanday aniqlaymiz? Xotirani boshqarishning uchta usuli mavjud, biz ushbu savollarni hal qilishda foydalanishimiz mumkin, biz ularni batafsil muhokama qilamiz. Quyidagi jadval 1024 baytlik bitta katta xotira blokining joriy holatini ko'rsatadi. Xotirani ajratish uchun har bir usul uni qanday ishlatishini ko'rib chiqamiz.

Eslatma: Ushbu blogda biz faqat First Fit algoritmini ko'rib chiqamiz, garchi bu usullarning har biri o'z foydalanish holatlariga ega. Umuman olganda, birinchi moslamaga ustunlik beriladi.

Birinchi Fit
Birinchi moslash usulida bepul ro'yxat so'ralgan o'lchamga ega bo'lgan birinchi bepul blokni topish uchun ketma-ket o'tkaziladi.
Blok topilgach, quyida keltirilgan ikkita amaldan biri bajariladi:
Agar o'lcham so'ralgan miqdorga teng bo'lsa, u bepul ro'yxatdan o'chiriladi.
Aks holda, u ikki qismga bo'linadi. Bu erda birinchi qism ro'yxatda qoladi va ikkinchisi ajratiladi.Ikkinchi qismni ajratishning sababi shundaki, ro'yxatni yangilash operatsiyasidan faqat erkin tugun hajmini o'zgartirish orqali oldini olish mumkin. Keling, 200 baytni ajratishga harakat qilaylik va strukturaning qanday o'zgarishini tushunamiz.

Ko'rinib turibdiki, xotira ikkinchi bo'limda ajratilgan, oldingi blok birinchi qismga ishora qiladi. Agar birinchi qism ishlatilgan bo'lsa, ikkinchi bo'limga ishora qilib, o'zgartirish ro'yxatda amalga oshirilishi kerak edi. Endi algoritmni ko'rib chiqamiz:

p = freeblock;
alloc = null; // pointer to store the allocated size n’s address
q = null;
// find the free node which can allocate the given size n
while ( p != null && size(p) < n) {
q = p; // previous node
p = next(p);
}
// if there is block large enough found
if ( p != null ) {
s = size(p);
alloc = p + s – n; // alloc contains the address of the desired block
// if the block size matches the requested size, remove the block from the free list
if ( s == n) {
// if the match is found in the first block update the pointer of freeblock to point the next of free block
if ( q == null ) {
freeblock = next(p);
} else {
next(q) = next(p); }
} else {
size(p) = s – n; // adjust the size of the remaining free block
}
Hajmi belgilangan “n” o‘lchamidan kattaroq yoki unga teng bo‘lgan bepul bloklarning eng kichigi Best Fit yondashuvida tanlanadi. Eng yaxshi moslikni topish uchun ushbu algoritm to'liq ro'yxat bo'ylab ishlashi kerak. Keling, 200 bayt ajratishga harakat qilaylik va strukturadagi o'zgarishlarni qayd etamiz: Worst Fit texnikasidagi algoritm har doim eng katta bo'sh xotira blokining bir qismini ajratadi. Ushbu strategiyaning g'oyasi shundan iboratki, ko'pchilik so'rovlarga xizmat ko'rsatish uchun oz sonli juda katta bloklardan doimiy ravishda foydalanish orqali ko'plab kichik bloklar parchalanmagan bo'lib qoladi. Keling, 200 ni ajratishga harakat qilaylik va strukturaning qanday o'zgarishini ko'rib chiqaylik.
C++ da o‘zgaruvchilar yo statik - kompilyatsiya paytida, yo standart kutubxonadan funksiyalarni chaqirish yo‘li bilan dinamik - dasturning bajarilish paytida, joylanishi mumkin. Bu usullarni ishlatishning asosiy farqi ularning effektivligida va moslanuvchanligidadir. Statik joylashtirish birmuncha effektivroq,chunki xotira ajratish dastur bajarilishidan oldin bajariladi. Ammo uning moslanuvchanligi ancha pastroq, chunki bu holda biz joylashtiriladigan ob’yektlarning turlari va o‘lchamlarini oldindan bilishimiz zarur.Masalan, matn fayllarni qatorlarning statik massivida, uning o‘lchamini oldindan bilish zarurligidan, joylashtirish ancha qiyin. Ayniqsa, oldindan noaniq sonli elementlarni saqlash va qayta ishlash bilan bog‘liq masalalar uchun xotirani dinamik taqsimlash usulidan foydalanish qulay.

Xotirani statik va dinamik taqsimlash o‘rtasidagi asosiy farq quyidagilar:

Statik ob’yektlar nomlangan o‘zgaruvchilar bilan belgilanadi. Shu sababli bunday ob’yektlar ustida amallar bevosita ularning nomlarini ishlatish orqali amalga oshiriladi. Dinamik ob’yektlar shaxsiy nomga ega bo‘lmaydi, ular ustidagi amallar bilvosita, ya’ni ko‘rsatkichlar yordamida bajariladi;
Statik ob’yektlar uchun xotira ajratish va bo‘shatish kompilyator tomonidan avtomatik ravishda bajariladi. Dasturchining bu haqda bosh qotirishi shart emas.Dinamik ob’yektlar uchun xotira ajratish va bo‘shatish butunligicha dasturchining zimmasiga tushadi. Bu esa hal qilishda xatoga yo‘l qo‘yish mumkin bo‘lgan murakkab masaladir.Dinamik ajratilgan xotira bilan ish ko‘rish uchun new va delete
buyruqlaridan foydalaniladi.Shu paytgacha barcha misollarda xotirani statik ajratish usulidan
foydalanilib kelindi. Masalan, i o‘zgaruvchini aniqlash quyidagicha bajarilar edi: