Alocarea memoriei

ALOCAREA MEMORIEI

Alocarea memoriei este efectuata de catre alocatorul de memorie care tine contabilitatea zonelor libere si ocupate din memorie, satisface cererea pentru noi zone si reutilizeaza zonele eliberate.

Alocarea memoriei se face ierarhic; la baza acestei ierarhii se afla sistemul de operare care furnizeaza utilizatorilor portiuni de memorie iar utilizatorul, la randul sau, gestioneaza portiunea primita de la SO dupa necesitatile sale.

1. Alocarea de memorie in limbaje

de programare

Exista o clasificare a limbajelor de programare din punct de vedere al alocarii de memorie:

1)-Limbaje care nu pot aloca memorie. Este cazul limbajelor mai vechi (Fortran, Cobol). In aceste limbaje, utilizatorul nu poate aloca dinamic memorie in momentul executiei ci inaintea executiei programului.

2)-Limbaje cu alocare si delocare explicita. Aceste limbaje permit utilizatorului sa ceara, pe parcursul executiei, noi zone de memorie si sa returneze memoria utilizata. Este cazul functiilor new si free in PASCAL si new si delete sau malloc si free din C si C++.

3)-Limbaje cu colectoare de gunoaie (garbage collection). In aceste limbaje, utilizatorul nu specifica niciodata cand vrea sa elibereze o zona de memorie. Compilatorul si o serie de functii care se executa simultan cu programul deduc singure care dintre zone nu sunt necesare si le recupereaza.

Avantajele acestui limbaj sunt:

-utilizatorul este scutit de pericolul de a folosi zone de memorie nealocate, prevenind astfel aparitia unor bug-uri ;

-exista siguranta ca in orice moment, o zona de memorie utilizata nu este dealocata.

Dezavantajele limbajului:

-alocarea este impredictibila in timp, adica nu se stie exact in care moment se va produce;

-nu se poate sti daca zona de memorie utilizata va fi sau nu utilizata in viitor, deci este posibil ca un program sa pastreze alocate zone de memorie care-i sunt inutile.

Aceasta tehnica de alocare este intalnita in limbajele  Lisp si Java.

Mentionam ca majoritatea alocatoarelor din nucleele sistemelor de operare comerciale sunt de tipul 1) si 2). Exista si nuclee ale sistemelor de operare cu alocatoare de tipul 3), cum ar fi sistemele Mach sau Digital.

2. Caracteristici ale alocatoarelor

Vom prezenta cateva caracteristici ale alocatoarelor dupa care se poate evalua calitatea acestora.

1)-Timp de operatie. Este timpul necesar unei operatii de alocare/dealocare. Acest timp depinde de tipul alocatorului, fiecare alocator trebuind sa execute un numar de operatii pentru fiecare functie. Cu cat memoria disponibila este mai mare cu atat timpul de executie a unui apel este mai mare.

2)-Fragmentarea. O problema cu care se confrunta alocatoarele este faptul ca aproape niciodata ele nu pot folosi intreaga memorie disponibila, pentru ca mici fragmente de memorie raman neutilizate. Aceste pierderi apar in urma impartirii spatiului disponibil de memorie in fragmente neocupate in totalitate de programe. Fragmentarea poate fi :

-fragmentare externa;

-fragmentare interna;

Fragmentarea externa apare ori de cate ori exista o partitie de memorie disponibila, dar nici un program nu incape in ea.

Se demonstreaza ca atunci cand avem de-a face cu alocari de blocuri de marimi diferite, fragmentarea externa este inevitabila. Singurul mod de a reduce fragmentarea externa este compactarea spatiului liber din memorie prin mutarea blocurilor dintr-o zona in alta.

Fragmentarea interna este data de cantitatea de memorie neutilizata intr-o partitie blocata ( ocupata partial de un program).

Pentru a nu avea fragmentare interna ideal ar fi ca fiecare program sa aiba exact dimensiunea partitiei de memorie in care este incarcat, lucru aproape imposibil.

3)-Concurenta. Aceasta caracteristica se refera la gradul de acces concurent la memorie. Este cazul mai ales la sistemele cu multiprocesor, cu memorie partajata. Un alocator bine scris va permite un grad mai ridicat de concurenta, pentru a exploata mai bine resursele sistemului.

4)-Grad de utilizare. Pe langa faptul ca memoria este fragmentata, alocatorul insusi mentine propriile structuri de date pentru gestiune. Aceste structuri ocupa un loc in memorie, reducand utilizarea ei efectiva.

3. Tipuri de alocare

In sistemul de gestiune a memoriei exista doua tipuri de adrese:

-adrese fizice;

-adrese logice.

Adresele fizice sunt adresele efective ale memoriei fizice. Se stie ca pentru a adresa o memorie fizica cu o capacitate de n octeti este necesar un numar de adrese egal cu log₂n .

Adresele logice, sau virtuale, sunt adresele din cadrul programului incarcat.

De obicei, in marea majoritate a alocatoarelor, in momentul incarcarii unui program sau chiar al compilarii lui, adresele fizice coincid cu cele logice. In momentul executiei acestea nu mai coincid.

Translatarea adreselor logice in adrese fizice este executata de  catre hardware-ul de mapare al memoriei.

Alocarea memoriei se poate face in doua feluri:

-alocare contigua;

-alocare necontigua.

Alocarea contigua inseamna alocarea, pentru un proces, a unei singure portiuni  de memorie fizica, portiune continua; (elemente contigue inseamna elemente care se ating spatial sau temporal).

Alocarea necontigua inseamna alocarea, pentru un proces, a mai multor portiuni separate din memoria fizica.

Alocarea memoriei se mai face in functie de cum este privita memoria. Exista doua tipuri de memorie:

-memorie reala;

-memorie virtuala.

Memoria reala consta numai in memoria interna a sistemului si este limitata de capacitatea ei.

Memoria virtuala vede ca un tot unitar memoria interna si cea externa si se permite executia unui proces chiar daca acesta nu se afla integral in memoria interna.

4. Scheme de alocare a memoriei

Exista mai multe scheme de alocare de la foarte simple la foarte complexe. In general, sunt de doua categorii:

-sisteme care transporta procesele, inainte si inapoi, intre

memoria principala si disc (swapping si paging);

- sisteme care nu fac acest lucru ( fara swapping si paging).

a)-Pentru sistemele cu alocare contigua, exista schemele:

-alocare unica;

-alocare cu partitii fixe ( alocare statica);

-alocatii cu partitii variabile (alocare dinamica);

-alocare cu swapping.

b)Pentru sistemele cu alocare necontigua:

-alocare paginata  (simpla sau la cerere);

-alocare segmentata (simpla sau la cerere);

-alocare segmentata-paginata (simpla sau la cerere).

4.1.Alocare unica

a) Alocare unica cu o singura partitie

Este un tip de alocare folosit in primele sisteme de operare care lucrau monouser. Este cea mai simpla schema in care toata memoria interna este destinata sistemului de operare, fara nici o schema de administrare a memoriei. Desigur, ea tine de domeniul istoriei.

b) Alocare unica cu doua partitii

In acest tip de alocare exista doua partitii;

-partitie pentru sistemul de operare (nucleul);

-partitie pentru utilizator.

Este cazul sistemului de operare MS-DOS. Principalul dezavantaj consta in faptul ca nu se ofera solutii pentru multiprogramare.

4.2. Alocare cu partitii fixe (alocare statica)

Memoria este impartita static in mai multe partitii, nu neaparat de dimensiuni egale. In fiecare partitie poate rula cel mult un proces, gradul de multiprogramare fiind dat de numarul partitiilor. De obicei, impartirea in partitii si dimensionarea acestora se face la inceput de catre operator. Programele sunt incarcate in memorie prin niste cozi de intrare. Este posibil ca sa existe o singura coada de intrare in memorie sau diferite cozi la diferitele partitii. Din coada de intrare un program intra in cea mai mica partitie destul de mare, insa, pentru a-l primi. Spatiul neocupat de program in aceasta partitie ramane pierdut si in acest fapt consta dezavantajul schemei. Exista atat fragmentare interna cat si fragmentare externa.

Acest tip de alocare a fost utilizat de sistemul de operare SIRIS V, in sistemele de calcul FELIX C-256/1024, sisteme care au existat si la noi in tara, in toate centrele de calcul.

In aceasta alocare aparea pentru prima data si un mecanism de protectie a memoriei care era asigurat de sistemul de chei de protectie si chei de acces.

Sistemul de memorie era impartit in pagini de 2KO si fiecare pagina avea o cheie de protectie. Aceasta era pusa printr-o instructiune cod-masina a calculatorului. Pentru ca un program sa fie rulat intr-o zona a memoriei, trebuia sa fie prezentate cheile de acces pentru fiecare pagina utilizata. La identitatea cheii de acces cu cea de protectie, se permitea accesul in pagina respectiva. Existau si chei de acces care deschideau orice cheie de protectie (de exemplu cheia de acces zero), precum si chei de protectie deschise de orice cheie de acces.

4.3. Alocare cu partitii variabile

In aceasta alocare numarul, locatia si dimensiunea partitiilor variaza dinamic. Ne mai fiind fixata dimensiunea partitiilor, care pot fi ori prea mari ori prea mici fata de program, creste mult gradul de utilizare al memoriei. In schimb se complica alocarea si dealocarea memoriei si urmarirea acestor operatii.

Cand se incarca un proces in memorie, i se aloca exact spatiul de memorie necesar, din memoria libera creandu-sedinamic o partitie. Cand se termina un proces, partitia in care a fost procesul devine memorie libera, ea unificandu-se cu spatiul de memorie libera existent pana atunci.

Pentru gestionarea unei astfel de alocari, sistemul de operare trebuie sa aiba doua tabele:

-tabela partitiilor ocupate;

-tabela partitiilor libere.

Principala problema este alegerea unui spatiu liber; aceasta alegere trebuie facuta cu minimizarea fragmentarii interne si externe. Exista anumiti algoritmi de alegere a spatiului liber.

-FFA (First Fit Algoritm), prima potrivire. Se parcurge lista spatiilor libere, care este ordonata crescator dupa adresa de inceput si se alege primul spatiu de dimensiune suficienta.

Acest algoritm este folosit in sistemul SO MINIX, creat de Tannenbaum.

-BFA (Best Fit Algoritm) , cea mai buna potrivire. Se parcurge lista spatiilor libere si se alege spatiul cu dimensiunea cea mai mica in care incape programul. In acest fel se minimizeaza fragmentarea interna. In cazul in care lista spatiului liber este ordonata crescator dupa dimensiunea spatiilor libere, se alege evident primul spatiu liber. In acest caz FFA si BFA coincid. BFA este utilizat in SO MS-DOS.

-WFA (Worst Fit Algoritm) , cea mai proasta potrivire. Se parcurge lista spatiilor libere ordonata crescator dupa dimensiune si se alege ultimul spatiu din lista.

Din punct de vedere al vitezei si al gradului de utilizare al memoriei, FFA si BFA sunt superioare strategiei WFA.

4.4. Alocarea prin swapping

In acest tip de alocare, un proces, in majoritatea cazurilor in stare de asteptare,  este evacuat temporar pe disc, eliberand memoria principala. Reluarea executiei procesului se face prin reincarcarea sa de pe disc in memoria principala. Swap inseamna a face schimb si, intr-adevar, este vorba de o schimbare de pe memoria principala pe una externa si inapoi . Problema principala in swapping este: ce procese sunt evacuate din memorie pe disc ? Exista un algoritm bazat pe prioritati, numit Rollout-Rollin, conform caruia, la aparitia unui proces cu prioritate ridicata, vor fi evacuate procesele sau procesul cu prioritatea cea mai scazuta.

O alta problema este: la ce adresa din memorie va fi readus procesul evacuat. De obicei, daca alocarea este statica, procesul va fi readus in aceeasi partitie din care a plecat. In cazul alocarii dinamice, procesul va fi adus in orice loc al memoriei.

Pentru ca alocarea prin swapping sa aiba eficienta, este necesar ca memoria externa (harddiscul) sa aiba doua caracteristici: o capacitate suficient de mare si un timp de acces foarte mic.

Capacitatea mare este necesara deoarece pe disc trebuie sa se evacueze toate imaginile proceselor, numarul lor putand ajunge, la un moment dat, foarte mare.

Timpul de acces trebuie sa fie foarte mic. In caz contrar, costul swappingului memoriedisc poate deveni inconvenabil. O conditie esentiala pentru micsorarea costului este ca timpul de executie al procesului sa fie mult mai mare decat timpul de swapping.

O alta problema apare atunci cand un proces necesita date noi in timpul executiei si, implicit, zone suplimentare de memorie.Este situatia asa numitelor procese cu dimensiune variabila in timpul executiei. Daca, datorita cererii suplimentare de memorie, se depaseste zona de memorie afectata procesului, atunci sistemul de operare trebuie sa intervina. Exista urmatoarele posibilitati:

sa incheie fortat procesul care a formulat cerere de suplimentare a memoriei si sa se considere aceasta cerere ca o eroare de executie;

-sa returneze decizia procesului, in sensul ca acesta va decide daca isi va incheia activitatea sau o va continua strict in zona de memorie care i-a fost impusa;-in cazul alocarii dinamice, sa evacueze procesul pe disc, si sa astepte eliberarea unei zone de memorie satisfacatoare pentru proces.

Trebuie mentionat ca inca suntem in modul de alocare contiguu, deci spatiul de adresare al unui proces nu poate depasi capacitatea memoriei interne.

In concluzie, putem spune ca principalul avantaj al alocarii prin swapping este faptul ca se simuleaza o memorie mai mare decat cea fizica existenta.

Principalul dezavantaj este costul swappingului care uneori poate fi destul de mare. Mecanismul de swapping este redat in Fig.5.2.

Memoria principala Memoria secundara

swapaut

(evacuare)

Fig.5.2. Mecanismul swapping.