21 - ajratilgan xotira blokining minimal hajmi;
2i- eng katta taqsimlangan blok; umuman aytganda, 2i ajratish uchun mavjud bo'lgan barcha xotira hajmini ifodalaydi.
Dastlab, ajratish uchun barcha mavjud bo'sh joy 2u o'lchamdagi bitta blok sifatida ko'rib chiqiladi. s o'lchamdagi so'rov uchun, bunday 2 u-l< s<2и, butun blok ajratilgan. Aks holda, blok o'lchamlari 2u-1 bo'lgan ikkita ekvivalent egizaklarga bo'linadi. Agar 2 U-2< s<2 u-l, keyin iltimosiga ko'ra, ikkita egizakdan biri ajratiladi; aks holda, egizaklardan biri yana yarmiga bo'linadi. Bu jarayon eng kichik blok hosil bo'lgunga qadar davom etadi, uning hajmi kichik bo'lmagan 8. Egizak tizim doimo har bir o'lchamdagi 2l uchun "teshiklar" (mavjud bloklar) ro'yxatini saqlab turadi. Teshik (i+1) roʻyxatidan uni ikkiga boʻlish va i roʻyxatiga 2l oʻlchamdagi ikkita yangi teshik qoʻshish orqali olib tashlanishi mumkin. Bir juft doppelgangerlar ro'yxatda bo'lganda i bo'shatiladi, ular ro'yxatdan o'chiriladi va ro'yxatdagi bitta blokga birlashtiriladi (i+1). Quyida 2i-l o'lchamdagi so'rovni qondirish uchun rekursiv algoritm () keltirilgan. void get_hole(int i)
{
agar (i == (U+1))
< Ошибка >;
agar (< Список 1 bo'sh>)
{
get_hole(i+l);
< Teshikni egizaklarga bo'ling>;
< Поместить двойники в ro'yxatii >;
}
< Ro'yxatdagi birinchi teshikni olingi >;
}
Shaklda. 7.6 boshlang'ich hajmi 1 MB bo'lgan blokdan foydalanish misolini ko'rsatadi. Birinchi so'rov A - 100 ga KB (bu 128 KB blok hajmini talab qiladi); Buning uchun boshlang'ich blok har biri 512 KB bo'lgan ikkita egizakga bo'linadi. Ulardan birinchisi 256 KB o'lchamdagi egizaklarga bo'linadi va o'z navbatida hosil bo'lgan egizaklarning birinchisi ham yarmiga bo'linadi. Olingan 128 KB egizaklardan biri A so'roviga ajratiladi. Keyingi B so'rovi uchun 256 KB talab qilinadi. Bunday blok mavjud va ta'kidlangan. Jarayon kerak bo'lganda egizaklarni ajratish va birlashtirish bilan davom etadi. E'tibor bering, E bloki bo'shatilgandan so'ng, 128 KB egizaklar bitta 256 KB blokga birlashtiriladi, bu esa o'z navbatida darhol o'zining egizaklari bilan birlashadi.
Shaklda. 7.7-rasmda B bloki bo'shatilgandan so'ng darhol egizak tizimning binar daraxt ko'rinishi ko'rsatilgan Barglar joriy xotira taqsimotini ifodalaydi. Agar ikkita dubl barglar bo'lsa, unda ulardan kamida bittasi ishg'ol qilinadi; aks holda, ular kattaroq blokga birlashishi kerak.
Egizak tizim statsionar va dinamik taqsimlash sxemalarining kamchiliklarini bartaraf etish uchun oqilona murosaga ega, ammo zamonaviy operatsion tizimlarda peyjing va segmentatsiyaga asoslangan virtual xotiradan oshib ketadi. Biroq, egizaklar tizimi parallel dasturlarni ajratish va chiqarishning samarali vositasi sifatida parallel tizimlarda qo'llanilishini topdi (masalan, qarang). UNIX yadrosi tomonidan xotirani taqsimlash uchun egizak tizimning o'zgartirilgan versiyasidan foydalaniladi (bu haqda siz 8-bob, “Virtual xotira”da ko'proq bilib olasiz).
HARAKATLANUVCHI
Ajratishning kamchiliklaridan qochish usullarini ko'rib chiqishdan oldin, siz xotirada jarayonlarni taqsimlash bilan bog'liq muammolarni to'liq tushunishingiz kerak. Shaklda ko'rsatilgan sobit taqsimlash sxemasidan foydalanilganda. 7.3a, jarayon har doim xotiraning bir xil bo'limiga tayinlanishini kutish mumkin. Bu shuni anglatadiki, yangi jarayon uchun qaysi bo'lim tanlangan bo'lishidan qat'i nazar, bu bo'lim har doim yukni tushirish va xotiraga yuklashdan keyin ushbu jarayonni joylashtirish uchun ishlatiladi. Bunday holda siz ushbu bobning ilovasida tasvirlangan eng oddiy yuklagichdan foydalanishingiz mumkin: jarayon yuklanganda koddagi barcha nisbiy havolalar yuklangan jarayonning asosiy manzili asosida aniqlangan mutlaq xotira manzillari bilan almashtiriladi.
Agar bo'lim o'lchamlari teng bo'lsa (7.2-rasm) va turli o'lchamdagi bo'limlar uchun yagona texnologik navbat mavjud bo'lsa (7.3b-rasm), jarayon o'z ish jarayonida turli bo'limlarni egallashi mumkin. Jarayon tasviri birinchi marta yaratilganda u xotiraning qaysidir qismiga yuklanadi; keyinroq, u xotiradan olib tashlangan va qayta yuklangandan so'ng, jarayon boshqa bo'limda tugashi mumkin (oxirgi bo'lganida emas). Xuddi shu holat dinamik taqsimlashda ham mumkin. Shunday qilib, rasmda. 7.4, c va 3, 2-jarayon xotiraga joylashtirilganda turli o'rinlarni egallaydi. Bundan tashqari, siqishni amalga oshirilganda, jarayonlar ham asosiy xotiraga o'tkaziladi. Shunday qilib, jarayon tomonidan foydalaniladigan buyruqlar va ma'lumotlarning joylashuvi aniqlanmagan va jarayon har safar yuklanganda va yuklanganda (yoki ko'chirilganda) o'zgaradi. Ushbu muammoni hal qilish uchun manzillar turlarini farqlash kerak. Mantiqiy manzil - xotiradagi ma'lumotlarning joriy joylashuvidan qat'i nazar, xotira joyiga havola; ushbu xotira joyiga kirishdan oldin, mantiqiy manzilni jismoniy manzilga tarjima qilish kerak. Nisbiy manzil mantiqiy manzilning maxsus holati bo'lib, bunda manzil ma'lum bir nuqtaga (odatda dasturning boshiga) nisbatan pozitsiya bilan belgilanadi. Jismoniy manzil (mutlaq manzil sifatida ham tanilgan) bizni qiziqtirgan asosiy xotiradagi joylashuvning haqiqiy joylashuvidir.
Agar dastur nisbiy manzillardan foydalansa, bu yuklanayotgan jarayondagi barcha xotira havolalari shu dasturning boshiga nisbatan ekanligini bildiradi. Shunday qilib, dasturning to'g'ri ishlashi uchun xotiraga kiradigan buyruqni bajarish paytida nisbiy manzillarni jismoniy manzillarga aylantiradigan apparat mexanizmi talab qilinadi.
Shaklda. 7.8-rasmda manzilni tarjima qilishning keng tarqalgan usuli ko'rsatilgan. Jarayon bajarilish holatiga kirganda, asosiy xotirada jarayonning boshlang'ich manzili bilan ba'zan asosiy registr deb ataladigan maxsus protsessor registri yuklanadi. Bundan tashqari, dasturning oxirgi xotira katagining manzilini o'z ichiga olgan "chegara" (chegara) registridan foydalaniladi. Ushbu qiymatlar dastur asosiy xotiraga yuklanganda registrlarga kiritiladi. Jarayon bajarilganda, ko'rsatmalarda uchraydigan nisbiy manzillar protsessor tomonidan ikki bosqichda qayta ishlanadi. Birinchidan, mutlaq manzilni olish uchun bazaviy registrning qiymati nisbiy manzilga qo'shiladi. Keyin olingan mutlaq manzil chegara registridagi qiymat bilan taqqoslanadi. Qabul qilingan mutlaq adres berilgan jarayonga tegishli bo'lsa, buyruq bajarilishi mumkin; aks holda, ushbu xatoga mos keladigan operatsion tizim uzilishi hosil bo'ladi.
Shaklda ko'rsatilgan sxema. 7.8, dasturlarni bajarish vaqtida ularni asosiy xotiraga tushirish va yuklash imkoniyatini beradi; bundan tashqari, har bir jarayonning tasviri bazaviy va chegara registrlaridagi manzillar bilan chegaralanadi va boshqa jarayonlar tomonidan istalmagan kirishdan himoyalanadi.
Xotira ostida (xotira) bu holda kompyuterning operativ (asosiy) xotirasi nazarda tutiladi. Yagona dasturli operatsion tizimlarda asosiy xotira ikki qismga bo'linadi. Bir qismi operatsion tizim uchun (rezident monitor, yadro), ikkinchi qismi esa hozirda ishlayotgan dastur uchun. Ko'p dasturli OTda xotiraning "foydalanuvchi" qismi - hisoblash tizimining eng muhim resursi bir nechta jarayonlarni, shu jumladan OT jarayonlarini joylashtirish uchun taqsimlanishi kerak. Ushbu ajratish vazifasi operatsion tizim tomonidan maxsus xotira boshqaruvi quyi tizimi tomonidan dinamik ravishda amalga oshiriladi ( xotirani boshqarish). Ko'p vazifali tizimlar uchun xotirani samarali boshqarish juda muhimdir. Agar xotirada oz miqdordagi jarayonlar mavjud bo'lsa, u holda vaqtning muhim qismi jarayonlar kirish / chiqish kutish holatida bo'ladi va protsessor yuki past bo'ladi.
Dastlabki operatsion tizimlarda xotirani boshqarish shunchaki dastur va uning ma'lumotlarini ba'zi bir tashqi xotira qurilmasidan (temperli lenta, magnit lenta yoki magnit disk) operativ xotiraga yuklash edi. Bunday holda, xotira dastur va OT o'rtasida taqsimlangan. Ustida guruch. 6.3 Bunday sxemaning uchta varianti ko'rsatilgan. Birinchi model avval meynfreymlar va mini-kompyuterlarda ishlatilgan. Ikkinchi sxema hozirda ba'zi portativ kompyuterlar va o'rnatilgan tizimlarda qo'llaniladi, uchinchi model MS-DOS ning dastlabki shaxsiy kompyuterlari uchun odatiy edi.
2>
Do'stlaringiz bilan baham: |