Eroul avea obiceiul de a pune bucati de țigară într-o pungă de piele și de a le folosi pentru a face noi țigări. Astfel, conform dictatelor legii inexorabile a mediilor, el a fumat o parte din acest tutun de mai mulți ani.
T. Pratchett
Cu alocarea dinamică a memoriei, se creează cereri de alocare a memoriei în timpul executării sarcinii. Alocarea dinamică, prin urmare, este în contrast cu cea statică. când se formează cereri în etapa de compilare a programului. În cele din urmă, ambele și alte cereri sunt adesea procesate de același algoritm de alocare a memoriei în kernelul OS. Dar, în multe cazuri, alocarea statică poate fi implementată în moduri mult mai simple decât alocarea dinamică. Principala dificultate este că atunci când alocarea statică apare nefiresc - și, prin urmare, este foarte rar necesară - abilitatea de a abandona memoria alocată anterior. Cu o alocare dinamică, adesea trebuie să oferiți posibilitatea de a elimina blocurile solicitate, astfel încât memoria liberă să poată fi utilizată pentru a satisface cererile ulterioare. Astfel, în loc de un simplu distribuitor de delimitare dinamic între memoria utilizată și disponibilă (care este suficientă în cazurile simple de distribuție statică) trebuie să păstreze o listă a posibilelor zone de memorie liber nelegat, numit piscină sau morman.
Multe secvențe de cereri de memorie și sări din aceasta poate duce la faptul că toată memoria disponibilă este rupt în blocuri de dimensiuni mici, și să încerce să elibereze un bloc mare va eșua, chiar dacă suma lungimilor unități mici disponibile mult mai necesare. Acest fenomen se numește fragmentare a memoriei (Figura 4.3). Uneori este folosit un termen mai precis - fragmentarea externă (ceea ce va fi discutat mai târziu despre fragmentarea internă). În plus, un număr mare de blocuri necesită o căutare lungă. Există, de asemenea, multe dificultăți mici de diferite tipuri. Din fericire, omenirea sa ocupat mult timp de problema alocării memoriei și au fost găsite multe soluții bune sau acceptabile.
În funcție de problema care se rezolvă, se folosesc diferite strategii pentru căutarea blocurilor de memorie libere. De exemplu, un program poate aloca blocuri de aceeași dimensiune sau mai multe dimensiuni fixe. Acest lucru facilitează foarte mult rezolvarea sarcinilor de defragmentare și căutarea pieselor RAM gratuite.
Există situații în care blocurile sunt eliberate în ordinea opusă celei în care au fost alocate. Acest lucru vă permite să reduceți alocarea memoriei la structura de stivă, adică să reveniți la o memorare simplă a limitei dintre memoria ocupată și cea liberă.
Există, de asemenea, situații în care unele blocuri ocupate pot fi mutate din memorie - atunci există posibilitatea defragmentării memoriei. Deplasarea blocurilor de memorie ocupate pentru a uni zonele libere. De exemplu, funcția realloc () din implementările anterioare ale sistemului UNIX ar putea fi utilizată în acest scop.
Fig. 4.3. Fragmentarea externă
În funcțiile standard de bibliotecă ale limbilor de nivel înalt, cum ar fi
.. malloc / liber / realloc în C, noi / aruncați în Pascal, etc algoritmi concepute pentru cazul cel mai frecvent este utilizat în general: programul cere blocuri de dimensiuni aleatorii la întâmplare și, de asemenea, le eliberează în mod aleatoriu.
Cu toate acestea, solicitările aleatorii nu sunt de departe cea mai gravă opțiune. Chiar fără a cunoaște detaliile strategiei de gestionare a heapului, este destul de ușor să construim un program care "va strica viața" multor algoritmi comuni (exemplul 4.2).
Exemplul 4.2. Exemplu de secvență de cereri de memorie
în timp ce (TRUE) void * bl = malloc (aleatoriu (10)); / * Dimensiunea aleatorie de la 0 la 10 octeți * / void * b2 = malloc (aleator (10) +10); L. de la 10 la 20 octeți * /
dacă (N == NULL B2 == NULL) / * Dacă nu există memorie * /
pauză; / * ieși din buclă * /
liber (b1);
void * L3 = malloc (150);
/ * Cel mai probabil, memoria nu va fi alocată * /
Ca urmare a executării unui astfel de program, toată memoria disponibilă va fi "tăiată în tăiței": între oricare două blocuri libere, va fi plasat un bloc ocupat de dimensiuni mai mici (Figura 4.4)
Fig. 4.4. Rezultatul programului din exemplul 4.2
Din fericire, Exemplul 4.2 are un caracter artificial. În programele reale, o astfel de situație este rară și deseori se dovedește a fi mai bine să se fixeze programul decât să se facă modificări algoritmului de gestionare a heapului universal.
Exemplul de mai sus se bazează pe ipoteza că sistemul alocă blocuri de memorie pentru noi, dimensiunea cărora corespunde cu cea solicitată cu precizia unui octet. Dacă unitatea minimă de alocare este de 32 de octeți, exemplul nostru extern nu va cauza nici o fragmentare externă: pentru fiecare solicitare se va aloca un bloc. Dar ne confruntăm cu problema opusă, care se numește fragmentare internă: în cazul în care sistemul este capabil să rydelyat numai blocuri care sunt multipli de 32 de biți, și avem într-adevăr nevoie de 15 sau 47 de biți, 17 de biți per bloc vor fi pierdute (vezi Figura 4.5.).
Fig. 4.5. Fragmentare internă
Fig. 4.6. Antisortirovka
Fig. 4.7. Etichete asociate
Fig. 4.8. Combinarea folosind etichete asociate
remarcă
Este într-adevăr este un mare avantaj, deoarece este mult mai ușor de detectat erori cu indicii, care, în instrucțiunea Zortech C / C ++ spune ca „programatorii experimentați auzit că spunând [o eroare cu indicii - ed.]., Fade și ascunde sub tabel "([Zortech v3.xj).
Fig. 4.9. Fragmente în implementarea malloc din GNU LibC
Exemplul 4.3. Implementarea malloc / gratuit în GNU LibC. Funcția __default_morecore este prezentată în Exemplul 4.1.
/ * Dacă unele fragmente din acest bloc sunt libere, includeți acest fragment în lista de fragmente după primul fragment liber al acestui bloc. * /
next = (lista struct *) ptr;
next-> next = prev-> next;
următorul-> prev = prev;
prev-> next = next;
dacă (următorul-> următor! = NULL) next-> next-> prev = next;
++_heapinf [bloc] .busy.info.frag.nfree;
altfel
/ * Nu există fragmente libere în acest bloc, așa că includeți acest fragment în lista fragmentelor și anunțăți că acesta este primul fragment liber din acest bloc. * /
prev = (lista struct *) ptr;
_heapinfo [bloc]. info. frag. nfree = 1;
_heapinfo [bloc]. info. frag. primul = (int nesemnificat int)
((lungimea nesemnată int) ((char *) ptr - (char *) NULL)% tip BLOCKSIZE »); prev-> next = _fraghead [type]. prev-> prev = _fraghead [type]; prev-> prev-> next = prev; dacă (prev-> next! = NULL)
prev-> next-> prev = prev;
pauză;
/ * Întoarceți memoria la heap. * / void
_ libc_free (ptr) _ ptr_t ptr; inscrie struct aliniere * 1;
dacă (ptr == NULL) retur;
pentru (1 = _aligned_blocks; 1! = NULL; 1 = l-> următor) dacă (l-> aligned == ptr)
l-> aliniat = NULL;
/ * Marcați un element de listă ca fiind gratuit. * /
ptr = l-> exactă;
pauză;
dacă (_ free_hook! = NULL) (* _ free_hook) (ptr);
altfel
_free_internal (ptr);
#include
#ifdef elf_alias
elf_alias (gratuit, gratuit);
# endif
Principalele dezavantaje ale acestui algoritm includ imposibilitatea estimării timpului de căutare a unui bloc adecvat, ceea ce îl face inacceptabil pentru sarcini în timp real. Pentru aceste sarcini, este necesar un algoritm care este capabil să găsească un bloc adecvat de memorie pentru un timp fix (de preferință mic) sau să dea un răspuns rezonabil că nu există un bloc adecvat.
Cea mai ușoară modalitate de a rezolva această problemă este dacă avem nevoie de blocuri de mai multe dimensiuni fixe (a se vedea Figura 4.10). Am combinat blocuri de fiecare dimensiune în lista noastră. Dacă nu există nimic în lista de blocuri de mărimea necesară, ne uităm la lista blocurilor mai mari. Dacă este ceva acolo, am tăiat acest bloc în părți, le dăm unul la programul solicitant, iar al doilea. Este adevărat că, dacă dimensiunile blocurilor necesare nu sunt multipli unul de altul, ce vom face cu restul?
Pentru a rezolva această problemă, trebuie să introducem unele restricții privind dimensiunea blocurilor alocate. De exemplu, puteți solicita ca aceste dimensiuni sunt egale cu numerele lui Fibonacci (secvența de numere întregi, în cazul în care Fi + 1 = Fi + Fi-1. În acest caz, dacă avem nevoie să byte Fi și este disponibil numai Fi unitate de dimensiuni + 1. Noi putem obține cu ușurință două blocuri - unul dintre dimensiunea dorită, iar cealaltă - Fi-1, care nu este, de asemenea pierdut Da, orice restricție privind mărimea duce la fragmentarea internă, dar este mare această taxă pentru bloc de timp de căutare securizată ..?
Fig. 4.10. Alocarea blocurilor de dimensiuni fixe
Fig. 4.11. Algoritmul gemeni
Există, de asemenea, aplicații mai complexe ale abordării descrise mai sus. De exemplu, Novell Netware bazin de memorie liber este format din 4 rafale în trepte de 16 octeți (pentru o dimensiune a blocului de 16, 32, 48, 64 bytes), 3 cozi pasul 64 octeți (pentru dimensiunea de 128 de unități, 192, 256 octeți) și cincisprezece cozi pasul 256 octeți (de la 512 octeți la 4 KB). Pentru interogări mai mari, întreaga pagină este evidențiată. Este curios că capabilitățile în timp real ale acestei strategii sofisticate nu sunt practic utilizate în NetWare.
De exemplu, dacă driverul de interfață de rețea constată că nu are buffere gratuite pentru a primi următorul pachet de date, acesta nu încearcă să aloce un tampon nou utilizând algoritmul standard. În schimb, driver-ul ignoră pur și simplu datele primite, crescând doar contorul de pachete pierdute. Un proces separat de sistem monitorizează starea acestui contor și numai atunci când depășește un anumit prag pentru un anumit interval de timp alocă driverului un nou buffer.
O astfel de abordare a datelor de utilizator poate parea cinic, dar trebuie să ne amintim că transferul de date prin rețea pot fi alte motive pentru pierderea de pachete, cum ar fi date corupte din cauza interferențelor electromagnetice. Prin urmare, toate protocoalele de rețea la nivel înalt oferă mijloace de transmitere a pachetelor în caz de pierdere, indiferent de cauza cauzată de această pierdere. Pe de altă parte, în sistemele în timp real, ignorarea datelor pe care încă nu le putem accepta și procesa este o strategie destul de comună, deși nu întotdeauna acceptabilă.
Articole similare
Trimiteți-le prietenilor: