Memory Allocation - life-prog
rögzített elosztási
A legtöbb tároló rendszerek, feltesszük, hogy az operációs rendszer némi rögzített részét a fő memória és a többi fő memória használat céljára rendelkezésre áll több folyamat által. A legegyszerűbb a rendelkezésre álló memória kezelése rendszer - ez a területekre rögzített határok forgalmazás.
partícióméreteket
Ábra. 7.2 ábra két példát mutat a rögzített elosztási. Az egyik lehetőség az, hogy szakaszai azonos méretű. Ebben az esetben minden olyan eljárás, melynek mérete nem haladja meg a partíció méretét lehet tölteni bármikor elérhető partíciót. Ha minden partíció elfoglalt, és nincs folyamatban a készenléti állapotot vagy a munka, az operációs rendszer képes eltávolítani eljárás bármely részén, és töltse le a másik folyamatot, ezáltal processzor.
Ha partíciókat az azonos méretű, két nehézségeket.
A program lehet, hogy túl nagy ahhoz, hogy helyezze a szakaszban. Ebben az esetben, a programozónak kell fejleszteni egy programot, amely a matricák, úgyhogy bármikor szüksége volt csak egy része a fő memória. Ha a modul szükséges, ami jelenleg nem létezik a fő memóriában, a felhasználói program maga kell tölteni ezt a modult a program memória rész (függetlenül attól, hogy a kód vagy adat modul).
Használja főmemóriával ugyanakkor rendkívül hatékony. Bármely program, függetlenül annak méretétől, elfoglalja a teljes szakasz. Tehát a mi példánkban, kevesebb mint egy megabájt méretű program is elfoglalják az egész szakasz 8 MB; Így továbbra is kihasználatlan blokk 7 Mbyte. Ez a jelenség a megjelenése nem használt tárolási annak a ténynek köszönhető, hogy a letölthető blokk kisebb rész az úgynevezett belső tagoltságát (belső fragmentáció).
Hogy ezekkel a nehézségekkel (bár nem teljesen kiküszöbölni) lehet segítségével a szakaszok különböző méretű (lásd. Ábra. 7.2 b). Ebben az esetben a méret 16 MB a program tehet anélkül, matricák, és szakaszai kis mérete csökkenti a belső töredezettség letöltésekor kis programok.
elhelyezési algoritmus
Abban az esetben, ha a szakaszok azonos méretű, razmeschenieprotsessov memória egy triviális feladat. Nem számít, hogy melyik szabad szakaszok a folyamat felteszik. Ha minden a szakaszok az alkalmazott eljárás, akik nem állnak készen az azonnali használatra, ezek közül bármelyik lehet rakodni szabad memória egy új folyamat. Eldöntése, hogy mely folyamat kirak - ütemezési probléma (megbeszéljük ezt a 4. rész „tervezése”).
Amikor a szakaszok különböző méretű, két lehetséges megközelítés a cél processzor memóriájában szakaszok. A legegyszerűbb módja az, hogy dolgozza fel az egyes elhelyezett legkisebb részén, amely képes teljesen aktív befogadására protsess.1 Ebben az esetben minden egyes szakasz értelmében ütemező sorban, amely tárolja kiürített memória folyamatok ebben a részben a memóriát (lásd. Ábra. 7.3 is). Az előnye ennek a módszernek, hogy a folyamat lehet osztani a memóriát szakaszok érdekében, hogy minimalizálják a belső töredezettség.
Bár ez a módszer tűnik optimálisnak a szempontból az egyes rész, ez nem optimális a szempontból a rendszer egészére. Képzeljük el, hogy a rendszerben ábrán látható. 7.2,6, egy bizonyos időpontban nincs folyamatban mérete 12-16 MB. Ennek eredményeként egy részén 16 MB üres lesz, miközben ez sikeresen alkalmazható kisebb folyamatokat. Így egy előnyös megközelítés az, hogy egyetlen sorban minden folyamat (lásd. Ábra. 7.3, b). Abban a pillanatban, amikor a betölteni kívánt folyamat a fő memóriában, a legkisebb szabad partíció van kiválasztva erre, amely képes befogadni ezt a folyamatot. Ha az összes partíció foglalt, dönt a kiadás egyikük. Úgy látszik, ez szükséges, hogy részesítsék előnyben a folyamat elfoglaló legkisebb osztály, amely képes befogadni a letölthető folyamatot. Lehetőség van, hogy vegye figyelembe egyéb tényezők, mint például a folyamat prioritása vagy állapotának (elzáródott, vagy aktív).
A különböző méretű szakaszok felhasználása felett szakaszok azonos méretű nagyobb rugalmasságot biztosít az ezzel a módszerrel. Továbbá áramkörök rögzített partíciók viszonylag egyszerű, minimális követelményeket az operációs rendszer; a felső a processzor kicsi. Azonban ezek a rendszerek komoly hátránya.
A partíciók száma meghatározott időpontjában rendszer generációs, korlátozza az aktív (nem felfüggesztett) folyamatok.
Mivel a partíció mérete az előre idején a hőtermelő rendszer, kis folyamatokat vezet hatékony memória használatára. Olyan környezetben, ahol a követelmények előre ismert a memóriában az összes olyan feladatot, a használata a leírt programok indokolt lehet, de a legtöbb esetben a hatékonyságát ez a technológia rendkívül alacsony.
Fix kiosztás jelenleg kevéssé használják. Egy példa a sikeres operációs rendszer használja ezt a technológiát szolgálhat a korai operációs rendszer IBM mainframe OS / MFT (multitasking rögzített mennyiségű zadach- Multiprogramming rögzített feladatok számát).
dinamikus elosztás
elhelyezési algoritmus
Mivel a memória lezárás többletköltséget CPU idő, az operációs rendszer fejlesztők számára, hogy intelligens döntéseket, hogyan kell a memóriát folyamatok (képletesen szólva, hogyan dugja lyukak). Amikor a pillanatban a boot folyamat vosnovnom memória, és van néhány szabad memória blokkok megfelelő méretű, az operációs rendszernek kell döntenie, hogy melyik szabad blokk használni.
Mondhatjuk három fő algoritmusok - a legalkalmasabbak, első-fit, a következő megfelelő. Mindegyikük természetesen csak az egyik szabad blokk mérete elég nagy ahhoz, hogy elférjen folyamatot. A módszer kiválasztja a legjobban illeszkedő blokk, amelynek mérete a legközelebb a cél; első illeszkedő módszerrel ellenőrzi az összes szabad blokkok a kezdetektől, és kiválasztja az első memória elegendő nagyságú hely a folyamatot. A módszer a következő megfelelő munkát, ugyanúgy, mint az eljárás első-fit, de kezd, hogy ellenőrizze a helyet, ahol a egység le utoljára (miután elérte a végét memória, ő folytatja a munkát az elején).
Ábra. 7,5, és egy példát mutat a memória konfiguráció után több elhelyezések és a kirakodás folyamatok memória. Egység volt utoljára használt Mok mérete 22 MB, amely-ben alakult 14 szakasz Mbyte. Ábra. 7,5,6 mutatja a különbséget a legjobb technológia, az első és a következő megfelelő teljesítése során a megkeresett elosztása mérete 16 MByte blokk. Módszer legjobban illeszkedő ellenőrzi az összes szabad blokkok, és kiválasztja a leginkább hasonló blokk mérete 18 Mbyte, hagyva fragmens 2 Mbyte. Az eljárás első illő ebben a helyzetben marad szabad hely fragmensméretnek használt MB, és egy alkalmas módszer a következő - 20 MB.
Hogy ezen eljárások lenne a legjobb, ez függ a pontos szekvenciáját töltési és kisütési folyamatok és méretüket. Ugyanakkor tudjuk beszélni néhány általános következtetéseket (lásd. [BREN89], [SHOR75], [BAYS77]). Jellemzően az első megfelelő algoritmus nemcsak könnyebb, hanem a gyorsabb és jobb eredményt biztosít. következő párosítási algoritmus általában ad egy kicsit rosszabb eredményt. Ez annak a ténynek köszönhető, hogy a következő megfelelő algoritmus is hajlamos gyakoribb megjelenése memória felszabadítása végén memóriát. Ennek eredményeként, a legnagyobb szabad memória blokkokat (amely jellemzően a végén található a memória) gyorsan bontani kisebb fragmensek, és ezért, ha a módszer a következő megfelelő tömítést kell végezni gyakrabban. Másrészt, az első illeszkedő algoritmus általában kicsi alom kezdődő szabad memória blokkok, amelyek növekedéséhez vezet a keresési időt egy későbbi alkalmas egységet. Legjobban illeszkedő módszer, annak ellenére, hogy nevét, általában a legrosszabb. Mivel megkeresi a blokkokat a legközelebb a kívánt méretet, hagy számos kisebb egység. Ennek eredményeként, bár az egyes szentelt pazarolja a lehető legkisebb mennyiségű memória, a fő memória nagyon gyorsan eltömődik sok kis egység teljesítésének elmulasztása minden kérést (úgy, hogy amikor az algoritmus memória tömörítést kell végezni sokkal gyakrabban).
csere algoritmus
A multitasking rendszer segítségével dinamikus elosztása történik, ha az összes folyamat a fő memória zárolt állapotban, és a folyamat további memória elegendő is a tömörítés után. Veszteségek elkerülése CPU idő várta a megjelenése egy aktív folyamat, az operációs rendszer képes eltávolítani az egyik folyamat a fő memória, és így helyet csináljon az új folyamat vagy eljárás készenléti állapotot. operációs rendszer feladata -, hogy melyik folyamatot kell rakodni a memóriából. Mivel a téma a csere algoritmus felül kell vizsgálni részletesen kapcsolatban különböző virtuális memória rendszerek, mégis elhalasztja vita ebben a kérdésben.
iker rendszer
A rögzített és a memória dinamikus hátrányokkal. Fix kiosztás korlátozza az aktív folyamatok és hatékonyan használja memóriában között eltérés partíciók mérete és folyamatok. Dinamikus elosztás végrehajtása nehezebb, és magában foglalja overhead memória tömörítést. Egy érdekes kompromisszum ebben a tekintetben a rendszer társaik ([KNUT97], [RBTE77]).
A két rendszer memóriát blokkok mérete 2 <К
21 - a minimális méret a kiosztott memória blokk;
2U - a legnagyobb elosztását a blokk; Általánosságban elmondható, 2 és képviseli a mérete a teljes memória felosztható.
Kezdetben minden rendelkezésre álló helyet a forgalmazás kezelik egy egységként 2U méretű. Kérésekor mérete s, oly módon, hogy 2u-l void get_hole (int i)
ha (i = = (U + 1))
<Ошибка>;
if (<Список 1 пуст>)
get_hole (i + l);
<Разделить дыру на двойники>;
<Поместить двойники в списокi>;
>
<Взять первую дыру из спискаi>;
>
Ábra. 7.6 egy példa a blokk a kezdeti mérete 1 Mbyte. Egy első kérelem - 100 KB (128 KB szükséges blokk mérete érte); Erre a kezdeti blokk két részre van osztva twin 512-Kbyte. Ezek közül az első van osztva ikrek 256 KB, és viszont, az első, hogy egy elválasztási ikrek is feleződik. Az egyik kapott dupla méretű 128 KB áll kérelem A. Az alábbi lekérdezés igényel 256KB. Ez a blokk áll rendelkezésre, és kiosztott. A folyamat a szétválasztás és egyesülési páros, ha szükséges. Megjegyezzük, hogy a felszabadulás után az E blokk egyesítése ikrek 128 KB egy mondatban mérete 256 KB, ami viszont azonnal összeolvadt a párja.
Ábra. 7.7 ábrázolja a rendszer megduplázza a bináris fa, azonnal kiadása után a blokk B. A levelek jelentik a jelenlegi memória kiosztás. Ha két ikrek a leveleket, akkor legalább az egyikük van elfoglalva; különben meg kell egyesíteni egy nagyobb blokk.