Heap (memorie)

Un heap ( eng.  heap ) în informatică și programare  este numele unei structuri de date care implementează memoria aplicației alocată dinamic .

Dimensiunea heap  - cantitatea de memorie alocată de sistemul de operare (OS) pentru a stoca heap (sub heap).

Cum funcționează

Când începe un proces , sistemul de operare alocă memorie pentru a găzdui heap-ul. În viitor, memoria pentru heap (sub heap) poate fi alocată dinamic.

Programul utilizator, folosind funcții precum , poate obține pointeri către zonele de memorie aparținând heap-ului. Programele folosesc heap-ul pentru a găzdui structuri de date create dinamic. Programul poate elibera memorie folosind funcții precum . malloc()free()

Memoria heap poate fi împărțită în utilizată (alocată unui program care utilizează sau funcții similare) și liberă ( neocupată sau deja eliberată folosind funcții sau funcții similare). malloc()free()

Pentru a stoca informații despre ce zonă a heap-ului este ocupată și care este liberă, se folosește de obicei o zonă suplimentară de memorie.

Înainte de a începe programul, heap-ul este inițializat, timp în care memoria alocată heap-ului este marcată ca liberă.

O funcție ca aceasta face ceva de genul: malloc()

• caută prin lista zonelor de memorie utilizate/libere alocate pe heap, căutând o zonă liberă de o dimensiune adecvată;
• în caz de lipsă de memorie liberă, poate solicita memorie suplimentară de la OS;
• adaugă zona găsită la lista zonelor ocupate (sau marchează zona ca ocupată);
• returnează un pointer la începutul zonei de memorie;
• dacă dintr-un motiv sau altul nu a fost posibilă alocarea memoriei, raportează o eroare (de exemplu, returnează ).malloc()NULL

O funcție ca aceasta face ceva de genul: free()

• caută prin lista zonelor de memorie ocupate/libere alocate pe heap, căutând zona specificată;
• elimină zona găsită din lista zonelor de memorie ocupate;
• adaugă zona găsită la lista de zone libere (sau marchează zona ca liberă).

Programul poate fi sigur că între apelurile la funcții precum și , zona de memorie marcată ca ocupată nu va fi realocată. După un apel sau o funcție similară, zona de memorie va fi eliberată și mai târziu poate fi reutilizată sau dată sistemului de operare. Folosirea unui pointer către o zonă eliberată de memorie va face ca programul să se blocheze sau să ruleze imprevizibil. malloc()free()free()

Algoritmi și performanță

Heap-ul este o zonă adiacentă de memorie împărțită în zone ocupate și libere (blocuri) de diferite dimensiuni.

Informațiile despre zonele libere și ocupate ale heapului pot fi stocate în liste de diferite formate. Performanța funcțiilor precum și depinde direct de formatul de listă selectat , deoarece aceste funcții își petrec cea mai mare parte a timpului căutând lista de zone adecvate. malloc()free()

Pentru a mări dimensiunea heap -ului și a funcțiilor similare, utilizați un apel de sistem (apelați o funcție OS). În acest caz, are loc o schimbare de context de la spațiul utilizatorului la spațiul nucleului sistemului de operare și viceversa. Căutarea în lista zonelor heap utilizate/libere este mai rapidă decât schimbarea contextului, deci este mai profitabil să folosiți o singură dată un apel de sistem pentru a aloca o zonă mare de memorie pentru heap și apoi alocați zone mai mici programului din zona mare existentă în timp ce mentinerea unei liste de zone folosite/libere. malloc()

Numărul de elemente incluse în lista zonelor heap ocupate/libere poate fi redus prin îmbinarea elementelor care conțin informații despre zone succesive. Acest lucru va reduce timpul de parcurgere a listei.

Fiecare element al listei poate stoca adresa unei zone de memorie, dimensiunea acesteia, informații despre zona următoare (pentru căutare înainte) și/sau anterioară (pentru căutare inversă).

Exemplu de implementare

Creați mai multe liste pentru a stoca informații despre zone de dimensiuni identice sau similare. Selectați lista în funcție de dimensiunea zonei.

Vezi și

• memorie dinamică
• NUL

• malloc()
• gratuit()