Alocare dinamică a memoriei

Cu alocarea dinamică a memoriei , în informatică , ne referim la alocarea memoriei pentru utilizarea unui program în timpul execuției sale.

Această metodă este utilizată pentru a distribui posesia unor cantități limitate de memorie între diferite bucăți de date și cod. Un obiect alocat dinamic rămâne dinamic atâta timp cât nu este repartizat în mod explicit, nici de către programator, nici de către un colector de gunoi ; acest comportament este foarte diferit de cel utilizat pentru alocarea automată sau statică a memoriei. În jargon se spune că un astfel de obiect are o durată de viață dinamică .

Acțiunea de a satisface o cerere de alocare, care se ocupă cu căutarea și găsirea unui bloc de memorie neutilizată de o anumită dimensiune în grămadă (a se vedea mai jos), este o problemă care nu este ușor de rezolvat. Au fost propuse diverse soluții, inclusiv:

Principala problemă pentru majoritatea algoritmilor de alocare a memoriei dinamice este de a evita fragmentarea internă și externă încercând să mențină eficiența alocării și alocării. Mai mult, majoritatea algoritmilor folosiți sunt supuși problemei că un număr mare de alocări mici poate provoca o mare risipă de memorie datorită acumulării de metadate ; din acest motiv, mulți programatori preferă să evite această problemă folosind uneori o strategie numită chunking .

Alocarea blocurilor de dimensiuni fixe

O soluție este de a avea o listă legată de LIFO de blocuri de memorie de o dimensiune prestabilită. Această tehnică funcționează incredibil de bine pentru sistemele integrate simple.

Algoritm Buddy

O altă soluție posibilă este utilizarea unui alocator care utilizează algoritmul de prieteni . În acest fel, memoria este alocată de un bloc mare de memorie, a cărui dimensiune este o putere de două. Dacă blocul este mai mare de două ori mai mare decât este necesar, acesta este împărțit în două. Una dintre jumătăți este aleasă și procesul se repetă recursiv (verificând dimensiunea și eventual împărțind la jumătate) până când blocul obținut este suficient de mare pentru utilizare (cu alte cuvinte, atunci când divizarea ulterioară la doi ar face-o mai mică din memoria necesară mărimea).

Toate segmentele de memorie de aceeași dimensiune (ceea ce se numește prieten în engleză ) sunt stocate într-o listă ordonată legată sau într-un copac . Când un bloc este eliberat, acesta este comparat cu vecinul său: dacă ambele sunt de aceeași dimensiune, atunci acestea sunt combinate și plasate în lista de prieteni de dimensiuni puțin mai mari. Când este solicitat un bloc, alocatorul își va începe căutarea printre blocuri de dimensiuni suficiente, evitând diviziunile inutile.

De asemenea, trebuie amintit că utilizarea unor astfel de alocatori nu este limitată doar la sistemele în timp real , ci mai degrabă este utilizată și în diferite sisteme de operare (cum ar fi în nucleul Linux ).

Alocare de memorie bazată pe heap

În alocarea memoriei bazate pe heap, memoria este alocată într-un bloc mare de memorie neutilizată numită heap (care nu are nimic de-a face cu structura de date cu același nume , dar are de-a face cu semnificația argoului a cuvântului „o grămadă de ceva"). Mărimea memoriei care urmează să fie alocată poate fi determinată în timpul rulării și durata de viață a alocării nu depinde de procedura curentă sau de cadrul de stivă . Regiunea de memorie alocată este accesată indirect, de obicei printr-o referință. Algoritmul exact utilizat pentru organizarea zonei de memorie și a operațiunilor de alocare / repartizare este de obicei ascuns în spatele unei interfețe abstracte ( ascunderea informațiilor ) și ar putea utiliza oricare dintre metodele enumerate mai sus.

În schimb, memoria stivei de apeluri este de obicei limitată ca dimensiune și durata de viață a alocărilor depinde de durata de viață a funcțiilor corespunzătoare.

Stivă de apeluri

Programatorul poate aloca heap-ul prin intermediul funcțiilor speciale. Folosind limbajul C , puteți utiliza funcții

 void * malloc (size_t n)

sau

 void * calloc (size_t nelem, size_t dimelem)

care vă permit să alocați porțiuni de memorie în heap.

De obicei, sistemul de operare nu se ocupă de gestionarea heap-ului și, prin urmare, alocarea și alocarea memoriei în acest segment sunt responsabilitatea programatorului . De fapt, de fiecare dată când memoria este alocată prin intermediul funcțiilor (de exemplu în C) menționate mai sus, este recomandabil să alocați memoria alocată folosind funcția

 void free (nul *)

Limbi precum Java Oracle folosesc memoria heap pentru stocarea instanțelor de obiecte care persistă într-un program care rulează prin mașina virtuală Java .

În Java, utilizarea memoriei heap este total transparentă pentru programator, deoarece există mecanisme automate pentru gestionarea heap-ului utilizat, așa cum s-a menționat, pentru stocarea instanțelor de obiect.

Alocarea memoriei heap utilizate pentru obiecte are loc automat prin colectorul de gunoi , un fir al mașinii virtuale Java care are grijă să elibereze memoria heap utilizată de obiecte care nu mai sunt menționate în instanța de program.

Probleme de stivă și de coliziune

Să ne imaginăm spațiul de adrese ca o serie de stive de conținut. Fiecare dintre aceste stive este o parte a memoriei dedicate unei funcții și se numește „cadru de stivă”.

Fiind organizate într-un teanc, atunci când sunt adăugate, acestea sunt plasate în mod ideal una peste alta. În acest fel, ultimul care trebuie adăugat este, de asemenea, primul care trebuie utilizat (ultimul intrat, primul ieșit); după primul, ceilalți urmează până când ajungeți la primul adăugat care se află în partea de jos a grămezii.

În timpul executării instanțelor de program , heap și stack pot intra în coliziune .
Evident, acest tip de situație poate provoca erori în timpul rulării. Sistemele de operare oferă mecanisme pentru a modifica pragurile de mărime ale acestor două segmente ( segmentul stivei și segmentul de date ). Aceste mecanisme sunt, de exemplu , apeluri de sistem . În Unix , puteți utiliza apelul de sistem

 brk (2)

Ultima placă (adică cea din partea de jos a stivei) este segmentul de text, așa - numitul segment de cod , indicat de

 CS: IP

și conține instrucțiunile limbajului mașinii din program și este doar în citire.

Bibliografie

Donald Knuth . The Art of Computer Programming v. 1; Algoritmi fundamentali , ediția a treia. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Secțiunea 2.4: Alocarea dinamică a stocării, pp. 435–456.

Elemente conexe

linkuri externe

(EN) Alocarea dinamică a stocării: un sondaj și o revizuire critică a lui Paul R. Wilson, Mark S. Johnstone, Michael Neely și David Boles.
( EN ) Dynamic Storage Allocation (DSA) de Herbert Glarner, un program care descrie tehnici eficiente de alocare
( EN ) Algoritmi simpli de alocare a memoriei în comunitatea OSDEV

Portal IT : accesați intrările Wikipedia care se ocupă cu IT