Distribuție fixă
În majoritatea schemelor de gestionare a memoriei, vom presupune că sistemul de operare ocupă o parte fixă din memoria principală și că restul memoriei principale este disponibilă pentru utilizarea în numeroase procese. Cea mai simplă schemă de control pentru această memorie disponibilă este alocarea acesteia regiunilor cu granițe fixe.
Dimensiunile secțiunilor
În Fig. 7.2 prezintă două exemple de distribuție fixă. O posibilitate este să folosiți secțiuni de aceeași dimensiune. În acest caz, orice proces, a cărui dimensiune nu depășește dimensiunea partiției, poate fi descărcată în orice partiție disponibilă. Dacă toate partițiile sunt ocupate și nu există nici un proces într-o stare de pregătire sau de muncă, sistemul de operare poate descărca de proces din orice secțiune și de a descărca un alt proces, oferind astfel un procesor.
Când folosiți partiții cu aceeași dimensiune, există două dificultăți.
Programul poate fi prea mare pentru a fi plasat în secțiune. În acest caz, programatorul trebuie să dezvolte un program care folosește suprapuneri, astfel încât oricând să aibă nevoie de o singură secțiune din memoria principală. Când aveți nevoie de un modul care nu este în prezent în memoria principală, programul de utilizator trebuie să încarce modulul în secțiunea de memorie a programului (indiferent dacă modulul este cod sau date).
Utilizarea memoriei principale este extrem de ineficientă în același timp. Orice program, indiferent de mărimea sa, ocupă întreaga secțiune. Deci, în exemplul nostru, un program mai mic decât un megabyte va ocupa încă întreaga partiție de 8 MB; în timp ce 7 MB din bloc rămân neutilizate. Acest fenomen al apariției memoriei neutilizate datorită faptului că blocul încărcat este mai mic decât partiția se numește fragmentare internă.
Este posibilă combaterea acestor dificultăți (deși nu este complet eliminată) prin utilizarea secțiunilor de dimensiuni diferite (a se vedea Figura 7.2, b). În acest caz, un program cu o dimensiune de 16 MB poate face fără suprapuneri, iar partițiile mici pot reduce fragmentarea internă atunci când descarcă programe mici.
Algoritmul plasamentului
În cazul în care partițiile au aceeași dimensiune, alocarea proceselor din memorie este o sarcină trivială. Nu contează în care dintre partițiile libere procesul va fi plasat. Dacă toate partițiile sunt ocupate de procese care nu sunt pregătite pentru o funcționare imediată, oricare dintre ele poate fi descărcată pentru a elibera memoria pentru noul proces. Deciderea procesului care trebuie descărcat este sarcina planificatorului (vom vorbi despre acest lucru în partea 4, "Planificare").
Atunci când partițiile au dimensiuni diferite, există două abordări posibile pentru asignarea procesoarelor la partițiile de memorie. Cel mai simplu mod este de a procesa fiecare găzduit în secțiunea cea mai mică capabilă pe deplin activă găzdui protsess.1 În acest caz, pentru fiecare secțiune necesită coadă Scheduler, care stochează evacuate din procesele de memorie pentru această secțiune a memoriei (vezi. Fig. 7.3 , a). Avantajul acestei abordări este acela că procesele pot fi distribuite între partițiile de memorie, astfel încât să se minimizeze fragmentarea internă.
Deși această metodă pare a fi optimă din punctul de vedere al unei secțiuni separate, aceasta nu este optimă din punct de vedere al sistemului în ansamblu. Să ne imaginăm că în sistemul arătat în Fig. 7.2.6, la un moment dat nu există o dimensiune a procesului de la 12 la 16 MB. Ca rezultat, o partiție de 16 MB va fi goală, în timp ce ar putea fi utilizată cu mai puțin succes de procese. Astfel, o abordare mai preferabilă este folosirea unei coadă pentru toate procesele (a se vedea figura 7.3, b). În momentul în care doriți să încărcați procesul în memoria principală, selectați cea mai mică partiție disponibilă care poate găzdui procesul. Dacă toate secțiunile sunt ocupate, ar trebui să decideți să eliberați unul dintre ele. Aparent, ar trebui să dați prioritate procesului care ocupă cea mai mică secțiune care poate găzdui procesul de încărcare. De asemenea, puteți lua în considerare alți factori, cum ar fi prioritatea procesului sau starea sa (este blocată sau activă).
Folosind secțiuni de diferite dimensiuni în comparație cu utilizarea secțiunilor de aceeași dimensiune oferă o flexibilitate suplimentară acestei metode. În plus, schemele cu partiții fixe sunt relativ simple, necesită cerințe minime de sistem de operare; supratensiunea procesorului este mică. Cu toate acestea, aceste scheme prezintă dezavantaje serioase.
Numărul de partiții definite la momentul generării sistemului limitează numărul de procese active (nu sunt suspendate).
Deoarece dimensiunile partițiilor sunt setate în avans, la momentul generării sistemului, procesele mici duc la utilizarea ineficientă a memoriei. În medii unde cerințele de memorie pentru toate sarcinile sunt cunoscute în avans, aplicarea schemei descrise poate fi justificată, dar în majoritatea cazurilor eficiența acestei tehnologii este extrem de scăzută.
În prezent, distribuția fixă nu este practic utilizată. Un exemplu de sistem de operare de succes care utilizează această tehnologie poate servi drept sistem de operare IBM pentru mainframe OS / MFT (multitasking cu un număr fix de sarcini - Multiprogramming cu un număr fix de sarcini).
Distribuția dinamică
Algoritmul plasamentului
Deoarece sigiliul de memorie este un cost suplimentar de timp CPU, sistemul de operare are nevoie de dezvoltator pentru a lua decizii inteligente cu privire la modul de alocare a proceselor de memorie (la figurat vorbind, cum să conectați găuri). În cazul în care momentul memoriei vosnovnom procesului de boot, și există unele blocuri de memorie libere de mărime suficientă, sistemul de operare trebuie să decidă care blocul liber să-l folosească.
Putem lua în considerare trei algoritmi principale - cele mai potrivite, primul-fit, următorul caz. Toate acestea, desigur, limitată la o singură dimensiune a blocului liber suficient de mare pentru a se potrivi procesului. Metoda selectează un bloc de potrivire cel mai bun a cărui dimensiune este cel mai aproape de țintă; primă metodă se potrivesc scanează toate blocurile gratuite de la început și selectează prima memorie suficientă în dimensiuni pentru a se adapta procesului. Metoda urmatoarelor lucrari potrivite in acelasi mod ca prima metoda potrivita, dar incepe verificarea de la locul unde a fost alocat ultimul bloc (dupa ce a ajuns la sfarsitul memoriei continua sa functioneze de la inceput).
În Fig. 7.5, a arată un exemplu de configurare a memoriei după un număr de alocări și procese de descărcare din memorie. Ultimul bloc folosit a fost Mok, de 22 MB, în care a fost creată o partiție de 14 MB. În Fig. 7,5,6 arată diferența dintre cele mai bune, prima și următoarea, potrivită pentru o cerere de alocare bloc de 16 MB. Metoda cu cea mai bună potrivire se uită prin toate blocurile libere și alege cel mai apropiat bloc în mărime de 18 MB, lăsând un fragment de 2 MB. Metoda primului adecvat în această situație lasă un fragment de memorie liberă de dimensiune b Mbytes, iar metoda următorului adecvat este de 20 MB.
Care dintre aceste metode este cea mai bună va depinde de secvența exactă a proceselor de încărcare și descărcare și a dimensiunilor acestora. Cu toate acestea, putem vorbi despre unele concluzii generalizate (vezi [BREN89], [SHOR75], [BAYS77]). De obicei, algoritmul primei metode potrivite nu este doar mai simplu, ci și mai rapid și oferă rezultate mai bune. Algoritmul următorului cel potrivit, de regulă, oferă rezultate ușor mai slabe. Acest lucru se datorează faptului că următorul algoritm adecvat arată o tendință de a aloca mai des memoria din blocurile libere la sfârșitul memoriei. Ca rezultat, cele mai mari blocuri de memorie liberă (care sunt de obicei localizate la sfârșitul memoriei) sunt împărțite rapid în fragmente mai mici și, prin urmare, atunci când se folosește următoarea metodă adecvată, compactarea ar trebui efectuată mai des. Pe de altă parte, algoritmul primului corespunzător blochează, de obicei, începutul memoriei cu blocuri libere libere, ceea ce duce la o creștere a timpului de căutare a unui bloc adecvat în viitor. Metoda celor mai potrivite, spre deosebire de numele lor, este, de regulă, cea mai gravă. Din moment ce caută blocuri care au cea mai mare dimensiune față de blocurile necesare, el lasă în urmă multe blocuri foarte mici. Ca rezultat, deși este pierdut cel mai mic număr posibil de memorie pentru fiecare alocare, memoria principală este foarte rapid înfundată de multe blocuri mici, care nu pot satisface nici o interogare (deci cu acest algoritm, multiplexarea memoriei ar trebui să se facă mult mai des).
Algoritmul de substituție
Într-un sistem de multitasking care utilizează alocarea dinamică, vine un moment în care toate procesele din memoria principală sunt într-o stare blocată și nu există suficientă memorie pentru procesul suplimentar, chiar după compactare. Pentru a evita pierderea timpului procesorului pentru a aștepta eliberarea procesului activ, sistemul de operare poate descărca unul din procesele din memoria principală și astfel poate elibera spațiu pentru noul proces sau proces în stare gata. Sarcina sistemului de operare este de a determina ce proces ar trebui să fie descărcat din memorie. Din moment ce tema algoritmului de substituție va fi analizată în detaliu în legătură cu diferite scheme de memorie virtuală, pentru moment vom amâna dezbaterea acestei probleme.
Sistemul de gemeni
Atât alocările de memorie fixă cât și dinamică au dezavantajele acestora. Distribuția fixă limitează numărul de procese active și utilizează în mod ineficient memoria atunci când există o discrepanță între dimensiunile partițiilor și proceselor. Alocarea dinamică este mai complexă și include cheltuieli generale pentru memoria de compactare. Un compromis interesant în acest sens este sistemul de gemeni ([KNUT97], [РБТЕ77]).
În sistemul de gemeni, memoria este distribuită de blocuri de mărimea 2, la <К
21 - dimensiunea minimă a blocului de memorie alocat;
2i - cel mai mare bloc alocat; în general, 2i reprezintă dimensiunea tuturor memoriei disponibile pentru alocare.
La început, tot spațiul disponibil pentru distribuție este considerat ca un singur bloc de dimensiune 2u. Pentru o interogare cu mărime s, astfel încât 2u-l void get_hole (int i)
dacă (i = (U + 1))
<Ошибка>;
dacă (<Список 1 пуст>)
get_hole (i + l);
<Разделить дыру на двойники>;
<Поместить двойники в списокi>;
>
<Взять первую дыру из спискаi>;
>
În Fig. 7.6 prezintă un exemplu de utilizare a unui bloc cu o dimensiune inițială de 1 MB. Prima interogare A este de 100 KB (necesită un bloc de 128 KB pentru aceasta); În acest scop, blocul inițial este împărțit în două contrapărți de 512 KB. Primul dintre ele este împărțit în gemeni de 256 KB, iar la rândul său, primul dintre gemenii care rezultă este de asemenea împărțit în jumătate. Una dintre gemenii rezultate de 128 KB este alocată solicitării A. Următoarea interogare B necesită 256 KB. Un astfel de bloc este disponibil și alocat. Procesul continuă cu separarea și fuzionarea de gemeni, dacă este necesar. Rețineți că, după eliberarea blocului E, 128 KB gemeni se îmbină într-un bloc de 256 KB, care, la rândul său, se îmbină cu omologul său.
În Fig. 7.7 prezintă reprezentarea sistemului de gemeni sub forma unui copac binar, imediat după eliberarea blocului B. Frunzele reprezintă alocarea curentă a memoriei. Dacă două gemeni sunt frunze, atunci cel puțin unul este ocupat; în caz contrar, ele trebuie să se integreze într-un bloc mai mare.