Bo‘linish (fragmentatsiya)
Bo‘linish (fragmentatsiya) - bu xotiraning kichik o‘lchamdagi, qo‘shni bo‘lmagan maydonlarga bo‘linishidir. Bo‘linishni (fragmentatsiyani) ikkita turi mavjud: tashqi bo‘linish va ichki bo‘linish.
Tashqi bo‘linish
Xotiraning umumiy maydoni so‘rovni qondirish yoki undagi jarayonni o‘tkazish uchun yetarli, ammo u o‘zaro bog‘liq bo‘lmaydi, shuning uchun undan foydalanib bo‘lmaydi.
Ichki bo‘linish
Jarayonga belgilangan xotira bloki kattaroqdir. Xotiraning bir qismi ishlatilmay qoladi, chunki undan boshqa jarayon foydalana olmaydi. Quyidagi diagrammada bo‘linish qanday qilib xotira yo‘qolishiga olib kelishi va siqish texnikasidan foydalanib, bo‘lingan xotiradan ko‘proq bo‘sh xotirani yaratish uchun foydalanish mumkinligi ko‘rsatilgan.
Ichki bo‘linish xotirani taqsimlashning aniq algoritmini qo‘llagan tizim natijasida yuzaga kelishi mumkin, so‘rovga javoban xotira talab qilinganiga nisbatan biroz kattaroq ajratiladi.
3.11- rasm. Siqishdan oldingi xotiradagi bo‘linish
3.12- rasm. Siqishdan keyingi xotira
Masalan, kattaligi ikkita sahifaga qadar bo‘lgan. Xotirani sahifali tashkil etish ushbu ma’ruzada keyinchalik batafsil muhokama qilinadi.
O‘zgaruvchan qismli sxemalar
Bundan oldingi ko‘rib chiqilgan xotirani taqsimlash sxemalarida (belgilangan qismlar va dinamik qismlar) mavjud muammolarni (bo‘linishlarni oldini olish uchun) yechimi o‘zgaruvchan dinamik qismlarni ishlab chiqish edi.
Qoida bo‘yicha svoping (almashtirish) tizimi belgilangan qismlarga asoslanishi mumkin. Ammo dinamik taqsimlash yoki o‘zgaruvchi qismli sxemalar samarali hisoblanadi. Chunki ular hamma jarayonlar to‘liq ravishda xotirada joylashganda, yani svoping bo‘lmagan hollarda qo‘llaniladi.
Bu holda, boshida xotira butunlay bo‘sh va oldindan qismlarga bo‘lingan bo‘lmaydi. Yangi ishga tushirilayotgan vazifaga qat’iy ravishda kerakli xotiraning o‘zi ajratiladi (undan ko‘p emas). Jarayon chiqarilgandan so‘ng, xotira vaqtincha bo‘shatiladi. Bir qancha vaqt o‘tgandan so‘ng xotira turli o‘lchamdagi o‘zgaruvchan sonli qismlardan iborat bo‘lib qoladi. Yonma-yon bo‘lgan bo‘sh joylar birlashtirilishi mumkin.
Ushbu xotirani taqsimlash sxemasi yordamida xotira menejeri barcha bo‘sh bloklarni bir joyga to‘plash va bir xotira blokini yetarlicha katta qilish (kirishni kutayotgan ba’zi yoki barcha
vazifalarni joylashtirish uchun) va ularni siqish uchun dasturlarni o‘zgartiradi. Xotirani siqish operatsion tizim tomonidan xotira maydonining bo‘lingan (fragmentatsiya) qismlarini tiklash (defragmentatsiya) uchun amalga oshiriladi. Lekin bu oson ish emas. Birinchidan, xotiradagi har bir dastur bir-biriga qo‘shni bo‘lishi uchun ko‘chirilishi kerak, so‘ngra har bir manzil va har bir dasturdagi manzilga bog‘lanish, dasturning xotirada yangi joylashishini hisobga olgan holda sozlanishi kerak.
Tashqi bo‘linish
Vazifalar ro‘yhati: Vazifa 1 = 8K
Asosiy xotira
10K
18K
30K
62K
92K
Asosiy xotira
Asosiy xotira
Vazifa 2 = 16K Vazifa 4 = 32K Vazifa 5 = 48K Vazifa 6 = 84K(kutmoqda)
108K
Vazifa 1 (8K)
|
|
Vazifa 4 (32K)
|
|
Vazifa 2 (16K)
|
Vazifa 5 (48K)
|
|
Vazifa 1 (8K)
|
Vazifa 4 (32K)
|
Vazifa 2 (16K)
|
Vazifa 5 (48K)
|
|
Vazifa 1 (8K)
|
Vazifa 4 (32K)
|
Vazifa 2 (16K)
|
Vazifa 5 (48K)
|
Vazifa 6 (84K)
|
|
156K
(a)
(b)
(c)
3.13- rasm. O‘zgaruvchan qismli sxemaga misol
Dastlabki 10 Kb xotirani egallaydigan, operatsion tizimni xotirani siqishdan oldingi va keyingi uchta rasmi. 6-vazifa uchun 84 Kb kerak bo‘lsa, (a) tashqi bo‘linishdagi dastlabki xotira tuzilishi 96 Kbni tashkil qiladi. Siqishdan so‘ng (b) darhol tashqi bo‘linish bartaraf etildi, bu esa 6-vazifa uchun joy yaratishga imkon berdi, yuklangandan keyin (c) da ko‘rsatilgan.
Almashtirish (swapping)
Tizimni qayta ishlash jarayonida foydalanuvchi jarayoni turli xil holatlarda bo‘lishi mumkin. Xususan, vaqtni taqsimlash rejimida amalga oshirilsa, masalan, foydalanuvchi terminal orqasida keyingi buyruqni ko‘rib chiqsa yoki o‘z dasturining manba kodini o‘zgartirsa,
jarayon bir muncha vaqt harakatsiz bo‘lishi mumkin. Bunday hollarda, jarayon operatsion tizim tomonidan diskka ko‘chirilishi mumkin, chunki u egallagan xotira ayni paytda boshqa faol jarayon uchun zarurdir. Almashtirish (swapping) - bu operatsion tizimning faol bo‘lmagan jarayon tasvirini diskka o‘tkazish (yozish) yoki faol jarayonni asosiy xotiraga ko‘chirish (o‘qish) uchun harakatlaridir. Bunday harakatlarni bajarish zarurati asosiy xotiraning yetishmasligidan kelib chiqadi. Almashtirish (swapping) jarayoni quyidagi 3.14- rasmda keltirilgan.
3.14- rasm. Almashtirish jarayoni
Zahira maydoni (backing store) - bu operatsion tizim tomonidan ko‘chiriladigan jarayonlar tasvirlarini (fayllarni o‘tkazish) saqlash uchun foydalaniladigan disk xotirasi maydoni. Zahira maydoni iloji boricha samarali tashkil etiladi: xotiradagi barcha jarayon tasvirlariga to‘g‘ridan-to‘g‘ri kirishni ta’minlaydi (masalan, jarayon raqami jadvali orqali). O‘tkazish va ko‘chirish algoritmining eng mashhur versiyasi bu: ustuvorliklarga asoslanib o‘tkazish va ko‘chirish; yuqori ustuvorlikga ega jarayonlar bajariladi, past ustuvorlikga ega jarayonlar diskka o‘tkaziladi.
O‘tkazishga sarflanadigan eng katta vaqt - bu ma’lumotlarni uzatish harajatidir: to‘liq jarayon tasviri katta hajmdagi xotirani
egallashi mumkin. Umumiy o‘tkazish vaqti o‘tkaziladigan ma’lumotlarning hajmiga mutanosibdir. Keng tarqalgan operatsion tizimlarda - UNIX, Linux, Windows va boshqalar – o‘tkazish va ko‘chirish (swapping) bo‘yicha har xil strategiyalar amalga oshiriladi. Almashtirish jarayoni odatda ishlashga ta’sir qilsada, parallel ravishda bir nechta katta jarayonlarni boshqarishga yordam beradi, shuning uchun almashtirish ham xotirani siqish usuli sifatida tanilgan. O‘zgartirish jarayoni uchun talab qilinadigan umumiy vaqt butun jarayonni ikkinchi darajali diskka ko‘chirish uchun zarur bo‘lgan vaqtni, so‘ngra jarayonni asosiy xotirani tiklash uchun zarur bo‘lgan vaqtni o‘z ichiga oladi. Aytaylik, foydalanuvchi jarayoni 2048 KB hajmda va almashish amalga oshiriladigan standart qattiq diskda ma’lumot uzatish tezligi sekundiga 1 MB ni tashkil qiladi. Xotiraga yoki 1000K hajmdagi jarayonning haqiqiy uzatilishi 2000 millisekundga to‘g‘ri keladi. Endi, kirish va chiqish vaqtini hisobga olgan holda, jarayon asosiy xotirani tiklash uchun raqobatlashganda 4000 millisekund va boshqa qo‘shimcha xarajatlarni talab qiladi.
Sahifali xotira
Yuqorida tavsiflangan sxemalarda xotiradan samarali foydalanilmaydi, shuning uchun ham xotirani taqsimlashning zamonaviy sxemalarida jarayonni operativ xotirada uzluksiz blok sifatida joylashtirish ko‘zda tutilmagan. Zamonaviy operatsion tizimlarda, vazifani asosiy xotiraga yuklashdan oldin u sahifalar (Pages) deb nomlangan qismlarga bo‘linadi.
Sahifali xotira - bu xotirani boshqarish usuli bo‘lib, unda jarayonning manzil maydoni bir xil hajmdagi sahifalar deb ataladigan bloklarga bo‘linadi (hajmi 2 daraja, 512 dan 8192 baytgacha). Jarayon hajmi sahifalar soni bilan o‘lchanadi. Xuddi shu tarzda, asosiy xotira doimiy o‘lchamdagi (fizik) xotiraning kichik bloklariga bo‘linadi, ular kadrlar deb nomlanadi va asosiy xotirani optimallashtirish va tashqi qismlarga bo‘lmaslik uchun kadr hajmi sahifa o‘lchamiga teng bo‘lib qoladi.
Xotirani sahifali tashkil etishda eng oddiy va eng keng tarqalgan usul (yoki paging), xotiraning ham mantiqiy manzilli maydoni, ham fizik maydonini bir xil o‘lchamdagi sahifa va bloklar to‘plami ko‘rinishida tashkil etishdir. Bunda mantiqiy sahifalar (page) yuzaga keladi va ularga mos fizik xotira birliklari - fizik sahifalar yoki sahifa
kadrlari deb ataladi (page frames). Sahifalar (va sahifa kadrlari) odatda 2 sonini darajasidan iborat bo‘lgan belgilangan qat’iy uzunlikka egadir va ular bir-biri bilan kesishmaydi. Har bir kadr ma’lumotlarning bir sahifasini o‘z ichiga oladi xotirani bunday tashkil etishda tashqi bo‘linish (fragmentatsiya) bo‘lmaydi va ichki bo‘linishdan kelib chiqadigan yo‘qotish faqat oxirgi sahifalardan kelib chiqadigan yo‘qotish bilan chegaralanadi.
Sahifali tizimda mantiqiy manzil - tartiblangan juftlikdan (p, d) iborat, bu yerda p virtual xotira sahifasi tartib raqami, d esa bu sahifa doirasidagi element o‘rnini bildiradi. Manzil manzilini sahifalarga bo‘lish xisoblash tizimi tomonidan, dasturchi aralashmagan holda amalga oshiriladi. Shuning uchun ham, manzil, operatsion tizim nuqtai nazaridangina ikki o‘lchamlidir, dasturchi nuqtai nazaridan esa jarayon manzili chiziqli hisoblanadi.
Yuqorida keltirilgan sxema, jarayonlarni to‘liq joylashtirish uchun kadrlarning uzluksiz sohasi yetarli bo‘lmagan hollarda ham, jarayonni yuklash imkonini beradi. Ammo, bu sxemada manzilni translyatsiyalash uchun bitta asos registri yetarli emas. Mantiqiy manzillarni fizik manzillarda aks ettirish, mantiqiy sahifalarni fizik sahifalarda aks ettirishga keltiriladi va operativ xotirada saqlanadigan sahifalar jadvalidan iborat bo‘ladi. Ba’zida, sahifalar jadvali – jadval ko‘rinishidagi chiziqli bo‘lakli funksiya ham deyiladi. Mantiqiy manzilning bog‘lanishi 3.15-rasmda ko‘rsatilgan.
Bunda bajariladigan jarayon v = (p, d) mantiqiy manzilga murojaat qiladi, va aks ettirish mexanizmi sahifa tartib raqami r ni sahifalar jadvalidan qidiradi, bu sahifa r* sahifa kadrida joylashganligini aniqlaydi va real manzil r* ni d ga aylantiradi.
Xotirani sahifali tashkil etish (Paging) deyarli barcha operatsion tizimlarda ishlatiladigan eng keng tarqalgan xotirani boshqarish algoritmidir.
Sahifalar jadvali (page table) protsessorning maxsus registrida manzillashtiriladi va kadrlar raqamini mantiqiy manzil bo‘yicha aniqlashga yordam beradi.
Bu asosiy masaladan tashqari sahifalar jadvali qatorida yozilgan atributlar yordamidan aniq sahifaga murojaat nazorati va uni himoyasini tashkil etish mumkin.
3.15- rasm. Xotirani sahifali tashkil etishda mantiqiy va fizik manzillarning bog‘lanishi
3.16- rasm. Sahifani tashkil qilishga misol
Manzillar translatsiyasi
Sahifa manzili mantiqiy manzil deb ataladi va sahifa raqami va sahifani almashtirish bilan ifodalanadi.
Mantiqiy manzil = sahifa raqami + sahifani almashtirish
Kadr manzili fizik manzil deb ataladi va kadr raqami va sahifani almashtirish bilan ifodalanadi.
Fizik manzil = kadr raqami + sahifani almashtirish
Sahifalar xaritasi jadvali deb nomlangan ma’lumotlar tuzilishi protsessor sahifasi va fizik xotiradagi kadr o‘rtasidagi munosabatni kuzatish uchun ishlatiladi.
Tizim har qanday sahifaga kadr ajratganda, u mantiqiy manzilni fizik manzilga aylantiradi va dasturni bajarish paytida foydalaniladigan sahifalar jadvalida yozuvni yaratadi.
3.17- rasm. Sahifa va kadrni almashtirish sxemasi
Jarayonni bajarish kerak bo‘lganda, uning tegishli sahifalari har qanday mavjud bo‘lgan xotira kadrlariga yuklanadi. Aytaylik, sizda 8Kb dastur mavjud, ammo sizning xotirangiz belgilangan vaqtda atigi 5Kb sig‘dira oladi, shunda sahifa kontseptsiyasi paydo bo‘ladi. Kompyuter operativ xotirasida joy qolmaganida, operatsion tizim bo‘sh yoki keraksiz sahifalarni ikkinchi darajali xotiraga ko‘chiradi,
boshqa operatsiyalar uchun operativ xotirani bo‘shatadi va dastur tomonidan kerak bo‘lganda ularni qaytarib beradi. Ushbu jarayon dasturning to‘liq bajarilishi mobaynida davom etadi, unda operatsion tizim bo‘sh sahifalarni asosiy xotiradan olib tashlaydi va ularni ikkinchi darajali xotiraga yozadi va dastur tomonidan talab qilinganda ularni qaytarib beradi.
Sahifali xotira afzalliklari va kamchiliklari
Almashtirishning afzalliklari va kamchiliklari ro‘yxati quyidagicha:
Sahifali xotira tashqi bo‘linishni kamaytiradi, ammo baribir ichki bo‘linishdan aziyat chekmoqda.
Sahifali xotira oson amalga oshiriladi va xotirani boshqarishning samarali usuli hisoblanadi.
Bir xil o‘lchamdagi sahifalar va kadrlar tufayli, almashish juda oson.
Sahifalar jadvali qo‘shimcha xotira maydonini talab qiladi, shuning uchun u operativ xotirasi kichik bo‘lgan tizim uchun mos kelmasligi mumkin.
Sahifalar jadvallarini amalga oshirish
Assotsiativ (kesh) xotiradan foydalanish. Sahifalar jadvali – bu fizik xotiraning uzluksiz qismi. Tizimda sahifalar jadvaliga ko‘rsatuvchi va uning uzunligini saqlovchi sahifalar jadvalining bazaviy registri (page table base register – PTBR) mavjud. Shunday qilib sahifalar ko‘rinishda tashkil etilganida xotiradan foydalanishning barcha hollarida xotiraga amalda bir marta emas, balki ikki marta murojaat etish talab etiladi – birinchisi sahifalar jadvaliga, ikkinchisi bevosita ma’lumotlar yoki buyruqga. Bu holatda xotiraning boshqarishni soddaroq usullariga nisbatan ma’lum kamchiligi va sahifali tashkil etishni samarasizligidir. Yorliqli arxitekturali tizimlarda, masalan “Elbrus”, sahifalar jadvali registrida (foydalanuvchining sahifalar jadvali registri – FSJR) sahifalar jadvalining deskriptori mavjud va unda uning manzilidan tashqari uzunligi ham bor. Ikki murojaat muammosi sahifalarning assotsiativ xotirasi (cache), yoki boshqacha nomlanganda translyatsiya manzillari buferi (translation lookaside buffer – TLB)ni kiritish yo‘li bilan hal etiladi. Assotsiativ xotira mazmunan – bu (sahifa raqami, kadr raqami)
turdagi juftlarning assotsiativ ro‘yxati. Uning ishlash tezligi asosiy xotira va registrlarga nisbatan anchagina yuqoriroq. Assotsiativ xotiradan foydalanish bilan manzillar translyatsiyasi sxemasi o‘zgaradi: agar mantiqiy manzildagi sahifaning raqami assotsiativ xotirada topilsa, u holda uning elementidan kadrning tegishli raqami chiqariladi. Agarda sahifaning raqami assotsiativ xotirada bo‘lmasa, u oddiy tarzda sahifalar jadvalidan olinadi, lekin assotsiativ xotiraga kiritiladi. Shunday qilib assotsiativ xotirada eng ko‘p foydalaniladigan sahifalar to‘g‘risida axborot yig‘ilib boriladi. TLB dan foydalanilgan holda manzillarni translyatsiya qilish modifikatsiyalangan sxemasi 3.18- rasmda tasvirlangan.
3.18- rasm. Assotsiativ xotiradan foydalalanib manzillarni translyatsiya qilish sxemasi
TLB dan foydalanilgan holda xotiraga murojaat etishning o‘rtacha vaqtini baholash.
Taxmin qilaylik – assotsiativ qidiruv o‘rtacha vaqtning α birligini talab etadi. Xotira siklini 1 deb qabul qilamiz. Yana bir ko‘rsatkichni kiritamiz – 0 dan 1 gacha (hit ratio), u sahifaning raqami necha marta (o‘rtacha) TLB da topiladi – sahifa raqamining assotsitativ xotirada bo‘lishining empirik ehtimolligi. Murojaat vaqtining matematik kutilishini hisoblaymiz - Effective Access Time (EAT). Sahifa raqami TLB da topilmaslik ehtimolligi 1 ga teng.
Xotiraning himoyalanishi
Sahifali tashkil etish yordamida manzillashda balki mantiqiy manzil noto‘g‘ri shakllangan va uning sahifa raqami protsessorning mantiqiy xotirasi chegarasidan chiqib ketadi. Noto‘g‘ri manzillashdan himoyalanish sahifalar jadvalining har bir elementida qo‘shimcha bitni valid-invalid saqlash va tekshirish yo‘li bilan amalga oshirilishi mumkin. Valid qiymati shu raqamli sahifa protsessorning mantiqiy xotirasiga tegishliligini ko‘rsatadi, invalid qiymati – nimadir to‘g‘ri emasligini bildiradi. Valid-invalid biti yordamida protsessor xotirasini himoyalashni tashkil etish 3.19-rasmda tasvirlangan.
Misolda jarayon 0 dan 5 gacha bo‘lgan raqamlar bilan belgilangan oltita mantiqiy sahifalarga ega. “6” va “7” elementlar jarayonning mantiqiy sahifalariga mos emas, shuning uchun ularda valid-invalid bitlar invalid qiymatida o‘rnatilgan. Shuning uchun mantiqiy manzil bo‘yicha “6” yoki “7” raqamli sahifalarga murojaat qilishga bo‘lgan urunishida noto‘g‘ri manzillash bo‘yicha to‘xtalish ro‘y beradi.
Qo‘shni xotirani taqsimlash
Xotirani taqsimlashning eng oddiy va eng keng tarqalgan algoritmi qo‘shni xotirani taqsimlashdir - bitta qo‘shni xotira maydonida foydalanuvchi jarayonlari uchun xotirani taqsimlash.
Asosiy xotira bir-biriga qarab "o‘sadigan" ikkita qo‘shni qismlarga bo‘linadi: OTning doimiy qismi va uzilish vektori - pastki manzillarda, foydalanuvchi jarayonlari – manzil bo‘yicha. Har bir jarayon uchun ko‘chirish registri unga ajratilgan xotira maydonining boshlanishini, chegara registri mantiqiy manzillar oralig‘ining
uzunligini o‘z ichiga oladi. Har bir mantiqiy manzil chegara registri tarkibidan kichik bo‘lishi kerak.
|
|
Sahifa 0
|
Sahifa 1
|
Sahifa 2
|
|
|
Sahifa 3
|
Sahifa 4
|
Sahifa 5
|
|
|
