Alocarea spatiului liber

ALOCAREA SPATIULUI LIBER. TIPURI DE ALOCATOARE

1. Alocatorul cu harti de resurse

Acest alocator foloseste un vector de structuri care descriu fiecare bloc liber. Iata un exemplu ce utilizeaza o harta a resurselor.

Fig. 5. 8. Harta resurselor in alocatorul cu harta de resurse.

(a)

(b)

Fig. 5.9. Harti de memorie in alocatorul cu harti de resurse.

Intr-un alt mod de reprezentare, fiecare bloc liber contine lungimea blocului liber si adresa urmatorului bloc liber. Astfel, blocurile libere sunt tinute intr-o structura de lista simplu inlantuita. Cand alocatorul vrea sa gaseasca un bloc liber, pleaca de la adresa primului bloc liber si parcurge lista de blocuri libere pana gaseste unul de dimensiune corespunzatoare. Pentru exemplul anterior, harta memoriei arata ca in  fig. 5.9.(b).

Acest tip de alocare, cu harti de resurse, este simplu dar destul de ineficient. Din cauza fragmentarii, complexitatea operatiilor este mare. Este posibil ca, dupa un anumit timp, lista de blocuri sa contina foarte multe blocuri mici a caror traversare sa fie inutila si foarte costisitoare.

2. Alocatorul cu puteri ale lui 2 (metoda camarazilor)

La alocatorul prezentat anterior, cel cu harti de resurse, principalul dezavantaj este dat de cautarea unui bloc de dimensiune potrivita printre blocurile libere. Pentru a contracara acest lucru, o solutie este de a crea blocuri de dimensiuni diferite, crescatoare ca lungime, care sa prezinte o oferta mai buna in cautare. In acest sens se poate impune ca dimensiunea unui bloc sa fie o putere a lui 2, deci ca un bloc sa aiba 2^k octeti. Tehnica de alocare este urmatoarea: daca dimensiunea unei cereri sde alocare nu este o putere a lui 2, atunci se aloca o zona a carei dimensiune este puterea imediat superioara a lui 2, cu alte cuvinte,  daca cererea de alocare are dimensiunea cuprinsa intre 2^k si 2^k+1, se alege zona cu dimensiunea 2^k+1. Metoda se mai numeste si metoda injumatatirii, pentru ca, practic, daca exista o cerere de alocare de dimensiunea 2^k si aceasta nu exista, atunci se alege o zona libera de dimensiune 2^k+1, mai mare (dubla), care este impartita in doua parti egale. Dupa un numar finit de astfel de operatii se obtine o zona cu dimensiunea dorita si alocarea este satisfacuta.

Implementarea acestei metode este asemanatoare cu cea precedenta cu mentiunea ca pentru alocatorul cu puteri ale lui 2 exista liste separate pentru fiecare dimensiune 2^k pentru care exista cel putin o zona libera. Mai trebuie mentionat faptul ca, atunci cand doua zone invecinate de dimensiune 2^k devin libere, ele sunt regrupate pentru a forma o singura zona libera de dimensiune 2^k+1 . De aici si numele de metoda camarazilor.

3. Alocatorul Fibonacci

Acest alocator este asemanator cu alocatorul cu puteri ale lui 2, dar in loc sa divizeze o zona libera in doua subzone egale, o imparte in alte doua de dimensiuni diferite. La fel ca in sirul lui Fibonacci, o zona a_i este:

a_i = a_i-1 + a_i-2

Cand un proces isi termina executia intr-o zona ocupata, aceasta devine libera si pot aparea urmatoarele situatii:

-zona eliberata se afla intre doua zone libere si atunci cele trei zone se regrupeaza intr-o singura zona libera;

-zona eliberata se afla intre o zona libera si una ocupata si atunci se unesc cele doua zone libere;

-zona eliberata se afla intre doua zone ocupate si atunci zona eliberata este adaugata listelor zonelor disponibile.

4. Alocatorul Karels -Mckusick

Acest alocator a fost construit in 1988 si este o varianta imbunatatita a alocatorului cu puteri ale lui 2. Metoda are avantajul ca elimina risipa pentru cazul blocurilor care au dimensiuni exact puteri ale lui 2. Exista doua imbunatatiri majore.

a) Blocurile ocupate isi reprezinta lungimea intr-un vector mare de numere v[k]=t , ceea ce inseamna ca pagina k are blocuri de dimensiunea t, unde t este o putere a lui 2. De exemplu :

In acest exemplu, pagina 3 are blocuri de 512 octeti, pagina 6 are blocuri de 64 octeti etc.

b) O alta imbunatatire este modul de calcul al rotunjirii unei puteri a lui 2. Se utilizeaza operatorul conditional din C (expresie 1? expresie 2: expresie 3;). Nu se folosesc instructiuni ci numai operatori si in felul acesta creste viteza de executie.

Acest alocator a fost utilizat pentru BDS UNIX.

5. Alocatorul "slab"

Alocatorul "slab" este inspirat din limbajele orientate pe obiecte. Are zone de memorie diferite pentru obiecte diferite, formand un fel de mozaic, de unde si numele "slab" care in engleza inseamna lespede. Iata cateva particularitati ale acestui alocator:

- alocatorul incearca, cand cauta zone noi, sa nu acceseze prea multe adrese de memorie pentru a nu umple cache-ul  microprocesorului cu date inutile; spunem ca alocatorul este de tip small foot print (urma mica).

- alocatorul incearca sa aloce obiecte in memorie astfel incat doua obiecte sa nu fie in aceeasi linie in cache-ul de date;

-alocatorul incearca sa reduca numarul de operatii de initializare asupra noilor obiecte alocate.

Alocatorul "slab" consta dintr-o rutina centrala care creeaza alocatoare pentru fiecare obiect. Rutina primeste ca parametri numele obiectului, marimea obiectului, constrangerile de aliniere si pointere pentru o functie construita si o functie destinatar.

Fiecare alocator are propria lui zona de memorie in care exista numai obiecte de acelasi tip. Astfel exista o zona de pagini numai cu fisiere, o zona de pagini numai cu date, etc. Toate obiectele dintr-o zona au aceeasi dimensiune.

Fiecare alocator are o lista de obiecte care au fost de curand dealocate si le refoloseste atunci cand i se cer noi obiecte. Deoarece obiectele au fost dealocate, nu mai trebuie initialiate din nou.

Atunci cand un alocator nu mai are memorie la dispozitie, el cere o noua pagina in care scrie obiecte noi. Pentru ca obiectele nu au fost niciodata initializate , alocatorul cheama constructorul pentru a initializa un nou obiect.

Fig 5.10. Alocatorul "slab".

Fiecare obiect are propriul lui alocator care are in paginile sale obiecte alocate si libere. In fiecare pagina, primul obiect alocat incepe la alta adresa, pentru a incarca uniform liniile din cache-ul microprocesorului. Fiecare pagina mai poseda anumite structuri de date, folosite in acest scop, ca ,de exemplu, lista dublu inlantuita a tuturor paginilor pentru un anumit obiect.

Fiecare alocator foloseste propriile lui pagini la fel ca alocatorul cu puteri ale lui 2. La sfarsitul unei pagini alocatorul rezerva o zona pentru o structura de date care descrie cum este acea pagina ocupata. Primul obiect din pagina este plasat la  o distanta aleatoare de marginea paginii; acest plasament are efectul de a pune obiecte din pagini diferite la adrese diferite.

Alocatorul "slab" poate returna sistemului de paginare paginile total nefolosite. El are o urma mica deoarece majoritatea cererilor acceseaza o singura pagina. Acest tip de alocator risipeste ceva resurse datorita modului de plasare in pagina si pentru ca are zone diferite pentru fiecare tip de obiect.

Alocatorul slab este utilizat in sistemul de operare Solaris 2.4.