text

Topicurile:

 

Rolul principal al unui sistem de operare este cel de management al resurselor unui calculator, in particular de management al memoriei. Daca resursele ar fi prezente din abundenta, atunci necesitatea unui manager ar fi mult mai putin stringenta.

O intrebare fireasca e urmatoarea: Ce este de fapt alocarea memoriei?
Calculatorul poseda din fabricatie o anumita cantitate de memorie (RAM). In memorie vor fi incarcate mai multe programe si datele prelucrate de ele: nucleul sistemului de operare, datele acestuia, programele utilizatorilor si datele asupra carora acestea opereaza, datele citite de la dispozitivele periferice, pachetele de date care vin si merg in reteaua in care calculatorul este conectat, bibliotecile incarcate dinamic, etc. O singura bucata mare de memorie trebuie impartita intre toate aceste entitati lacome, in asa fel incat sa fie toate multumite si sa nu se incomodeze unele pe altele. Entitatea care gestioneaza memoria, tine contabilitatea zonelor ocupate si a celor libere, care satisface cererile pentru noi zone si care re-utilizeaza zonele libere este alocatorul de memorie.

Alocarea memoriei este de obicei o treaba ierarhica; la baza ierarhiei se afla sistemul de operare, care are la dispozitie întregul RAM. Sistemul de operare da feluritelor programe ale utilizatorilor portiuni de memorie. La rîndul lor, fiecare din programe gestioneaza bucatica primita de la nucleu pentru nevoile sale interne.

O clasificare a limbajelor din punctul de vedere al alocarii memoriei le împarte în trei categorii:

  • Limbaje care nu pot aloca dinamic memorie. Din aceasta categorie fac parte cele mai ancestrale limbaje: Cobol, Fortran, Basic. În aceste limbaje (cel putin în versiunile lor initiale), utilizatorul nu poate aloca dinamic memorie de loc în momentul executiei programului; toata memoria necesara trebuie sa fie alocata înainte ca programul sa porneasca în executie.
    .
  • Limbaje cu alocare si dealocare explicita. Limbaje ca Pascal, C si C++ îi permit utilizatorului sa ceara pe parcursul executiei noi zone de memorie si sa returneze memoria folosita. Utilizatorul apeleaza pentru acest scop niste functii de biblioteca. Aceste functii au fost implementate de cel care a scris compilatorul pentru limbajul respectiv. Aceste functii cer de la sistemul de operare o bucata mare de memorie pe care apoi o împart dupa necesitati; atunci cînd toata bucata este consumata cer o alta de la nucleu. În Pascal functiile cu pricina sunt new si free, în C malloc si free iar în C++ new si delete. Ca functionare sunt extrem de similare; functiile din Pascal si C++ folosesc tipul obiectelor alocate pentru a deduce cîta memorie este necesara (de exemplu programatorul zice: ``vreau memorie pentru un vector de 10 întregi''); programatorii în C trebuie sa indice explicit de cîta memorie au nevoie (ex.: ``da-mi si mie 20 de octeti'').
    .
  • Limbaje cu colectoare de gunoaie (garbage collection). Lisp si Java folosesc un mecanism extrem de interesant, prin care utilizatorul nu specifica niciodata cînd vrea sa elibereze o zona de memorie (adica free() nu exista); compilatorul si un sistem de functii care se executa simultan cu programul (runtime system) deduc singure care dintre zone sunt nenecesare si le recupereaza. Lisp-ul aparent este un limbaj în care nu exista nici macar alocare dinamica (o functie de gen new); în realitate în Lisp fiecare obiect nou creat este automat alocat într-o zona de memorie noua, fara ca utilizatorul sa trebuiasca sa specifice asta (de exemplu cînd utilizatorul concateneaza doua liste, atunci sistemul aloca automat spatiu pentru lista rezultat).
    Din anumite puncte de vedere, tehnica colectarii de gunoaie este cea mai preferabila. Principalul ei avantaj este ca scuteste utilizatorul de pericolul de a folosi zone de memorie nealocate, prevenind astfel aparitia unor bug-uri extrem de greu de depanat. Avantajele ei nu se opresc aici: împreuna cu o disciplina de tipuri stricta, colectarea deseurilor face demonstrarea automata a corectitudinii programelor o sarcina mult mai simpla: un demonstrator de teoreme va fi întotdeauna sigur ca o zona de memorie folosita nu este dealocata.
    Pe de alta parte, colectarea de gunoaie are anumite dezavantaje: este impredictibila ca timp consumat (adica nu e clar în ce moment al executiei programului se va petrece), si este conservativa. Întrebarea daca o anumita zona de memorie va mai fi sau nu folosita de un program în viitor este în general o chestiune nedecidabila; asta înseamna ca nu se poate scrie nici un algoritm care sa raspunda la o astfel de întrebare, chiar daca are informatii complete despre programul analizat si despre datele lui de intrare. Din cauza aceasta este posibil ca un program cu colectare automata sa pastreze alocate zone de memorie care sunt în realitate inutile, pentru ca sistemul nu are cum sa demonstreze acest lucru.

In continuare vom trata sistemele de tip intermediar, cu alocare si dealocare explicita, datorita faptului ca este cel mai folosit la ora actuala, iar implementarea unui alocator cu colector va folosi idei de genul celor din alocatoarele explicite.

 

Alocarea în limbajul C

Nucleele sistemelor de operare comerciale sunt toate scrise în C, inclusiv alocatoarele de memorie din biblioteci; din cauza aceasta vom privi mai îndeaproape functiile acestui limbaj.

Programatorul în C are la dispozitie functiile malloc si prietenii ei (calloc, realloc) pentru a aloca memorie, si functia free pentru a o elibera. calloc si realloc pot fi scrise folosind malloc, asa ca nu le vom da prea mare atentie. Prototipurile acestor functii se afla în fisierul header <stdlib.h> din biblioteca standard C, prezenta pe orice sistem.

Functia malloc are un singur argument: numarul de octeti care trebuie alocati. Rezultatul functiei este un pointer generic (void*) spre zona alocata. Daca malloc nu gaseste destula memorie, atunci rezultatul apelului ei este pointerul cu valoarea 0 (NULL).

Functia free() are tot un singur argument, si nici un rezultat. Argumentul ei este un pointer obtinut de la un malloc anterior; efectul executarii ei este eliberarea zonei de memorie aflata în acel loc.

Biblioteca în care sunt implementate malloc si free mentine o pleiada de structuri de date indicînd unde se afla zonele libere si unde cele ocupate. Observati de pilda ca free nu primeste nici un fel de informatii despre cît de mare este zona dealocata; biblioteca trebuie deci sa stie acest lucru.

În cazul sistemului de operare Unix aceste functii de biblioteca sunt implementate folosind un apel de sistem2 numit sbrk. Figura 1 ilustreaza relatia dintre aceste functii. Apelul de sistem are la ca argument cantitatea ceruta de memorie (pozitiva sau negativa); efectul executarii apelului este adaugarea la sfîrsitul segmentului de date al programului a unei cantitati de memorie egale cu cea ceruta.

În mod normal malloc executa un sbrk la început pentru a obtine o cantitate mare de memorie, si apoi la fiecare apel returneaza utilizatorului cîte o bucatica din bucata mare. Daca dupa o vreme întreaga bucata mare devine ocupata, atunci malloc executa un nou sbrk.

 

Consumatori de memorie

Fiecare consumator de memorie are idiosincraziile lui; contextul în care memoria este folosita impune anumite constrîngeri asupra implementarii alocatorului.


Programele utilizatorilor
Cel mai comun consumator de memorie sunt programele utilizatorilor. Acestea pun si cele mai putine restrictii asupra alocatorului; cele mai multe programe ale utilizatorilor nu au constrîngeri severe de viteza sau spatiu, si ca atare pot implementa scheme foarte complicate, cu cost mediu mai ridicat dar care au alte trasaturi dezirabile.


Niste recomandari
Înainte de a trece la celelalte tipuri de alocatoare, permiteti-mi sa fac niste recomandari de stil în ceea ce priveste alocarea memoriei. Recomandarile sunt inspirate de indicatiile proiectului GNU, care produce software de foarte buna calitate.


Verificati întotdeauna rezultatul întors de functiile gen malloc. O eroare tipica este de a nu compara rezultatul cu 0. Cel mai recomandabil este sa folositi o functie-``învelis'' (wrapper); numele traditional al unui wrapper pentru malloc este xmalloc, de la ``checked malloc'':

/* xmalloc este un wrapper pentru malloc care verifica
rezultatele si opreste executia programului in caz
de terminare a memoriei disponibile */
void * xmalloc(size_t size)
{
void * r = malloc(size);
if (!r) {
fprintf(stderr, "Memoria virtuala este consumata\n");
exit(1);
}
return r;
}

Nu scrieti niciodata într-un buffer de o anumita marime lucruri care nu încap. Anumite functii de biblioteca, cum ar fi fgets citesc de la un periferic un sir de caractere într-un buffer. Ori, nu exista nici o limita pentru lungimea sirului tastat de utilizator; oricît de mare ar fi buffer-ul, utilizatorul poate tasta un sir mai lung. Majoritatea bug-urilor faimoase din Unix sunt de acest tip; celebrul ``Internet Worm'' din 1988, care a pus în genunchi cîteva zeci de mii de calculatoare, se baza în propagarea sa pe un astfel de bug în programul finger, care este folosit pentru a identifica utilizatori pe masini aflate la distanta. Folositi întotdeauna functii care limiteaza numarul de caractere citite, cum ar fi fgets.

Nu folositi niciodata alocarea statica. Corectitudinea programelor este mai importanta decît viteza lor de executie. De fiecare data cînd vreti sa scrieti ceva într-un buffer ne-încapator, realocati buffer-ul facîndu-l mai mare.
Functia de biblioteca realloc face chiar acest lucru: are ca argument un pointer si o noua dimensiune. Rezultatul este un nou buffer, care are dimensiunea indicata, si care contine tot vechiul continut al buffer-ului initial.


Daca folositi realloc pentru a creste în mod repetat un buffer, trebuie sa aveti grija sa nu platiti un cost amortizat prea mare pentru asta. Costul unui realloc este proportional cu marimea buffer-ului realocat, pentru ca fiecare octet trebuie copiat. Din cauza asta se recomanda ca, de fiecare data cînd realocati un buffer, sa-i dublati lungimea.


Caracteristici ale alocatoarelor

Exista o sumedenie de feluri de alocatoare diferite; în ceea ce priveste colectoarele si în ziua de azi se desfasoara cercetari care îmbunatatesc performanta. Iata aici cîteva criterii dupa care putem evalua calitatea unui alocator.


Timp pe operatie (cazul cel mai defavorabil)
Prima caracteristica este complexitatea unei operatii de alocare/dealocare. În mod normal un alocator trebuie sa execute un numar constant de operatii pentru fiecare functiune. Dar vom vedea mai jos ca adesea în cel mai rau caz alocatoarele trebuie sa execute o sumedenie de instructiuni pentru a raspunde la o singura cerere. De exemplu alocatorul cu harta de resurse, prezentat mai jos, ar putea sa aiba nevoie sa parcurga întreaga lista de blocuri de memorie neocupate pentru a gasi unul de masura potrivita. Asta înseamna ca, cu cît e mai multa memorie disponibila, cu atît executia unui apel de alocare/dealocare poate fi mai costisitoare (pentru ca lista va fi mai lunga).


Timp amortizat
O masura interesanta a costului unei alocari este timpul amortizat pentru o operatie de alocare. De exemplu daca cele mai multe operatii de alocare dureaza 1ms, dar la fiecare 500 de operatii costul executiei este de 200ms, atunci costul amortizat este de (499*1 + 1*200)/500 = 1.39ms pe operatie (costul în cazul cel mai rau ar fi 200).

Sistemele cu colectare de gunoaie au de obicei un timp amortizat mic pentru fiecare operatie, dar din cînd în cînd (atunci cînd colectorul porneste în executie), anumite operatii dureaza foarte mult. Acesta este cazul sistemelor LISP obisnuite.

Pentru ca nucleul unui sistem de operare trebuie sa faca fata unor cereri extrem de severe, în general alocatoarele din nuclee trebuie sa aiba cazul cel mai defavorabil relativ mic. Exista alocatoare care primesc niste indicatii despre urgenta operatiei: daca cel care are nevoie de memorie nu se grabeste, algoritmul îsi poate permite sa petreaca mai mult timp; altfel trebuie sa raspunda cît se poate de repede.

De exemplu nucleul trebuie sa primeasca pachete de date din retea; atunci cînd un pachet îsi face aparitia, nucleul nu poate sa astepte prea mult pentru a gasi un loc în care sa-l depoziteze, pentru ca nu are unde sa puna pachetul între timp. Daca nucleul nu reuseste sa obtina un buffer pentru o stoca pachetul, atunci de obicei pachetul este pur si simplu pierdut (asta se numeste buffer overrun). Cel care a transmis pachetul initial va trebui sa trimita o copie.


Fragmentare
Alocatoarele se mai confrunta cu o problema neplacuta: aproape niciodata nu pot folosi întreaga memorie disponibila, pentru ca mici fragmente ``se pierd'' fara a putea fi folosite.

Aceste pierderi apar din cauza ca consumatorii de memorie doresc bucati de memorie de marimi variate, care sunt greu de pus cap la cap în memoria disponibila. În functie de interfata alocatorului, exista doua tipuri de pierderi. Pentru ca pierderile apar din cauza împartirii spatiului disponibil în fragmente, aceasta problema se numeste fragmentare. Exista doua feluri de fragmentare: interna si externa.


Fragmentarea externa

Tabela 1 arata un posibil scenariu de cereri de alocare/dealocare si evolutia memoriei în timp.

Table 1: Fragmentarea externa apare datorita gaurilor aparute între zone de memorie si care sunt prea mici pentru a fi folosite. timp cerere starea memoriei


A = aloca(10)


B = aloca(5)


C = aloca(7)


dealoca(B)


D = aloca(2)

Se demonstreaza ca atunci cînd avem de-a face cu alocari de blocuri de marimi diferite, fragmentarea externa este inevitabila. Singurul mod în care putem repara ceva este de a muta blocuri dintr-o parte într-alta, compactînd spatiul liber. Dar aceasta este o operatie extrem de costisitoare ca timp, care în anumite conditii este imposibila (de exemplu atunci cînd muti ceva din memorie trebuie sa corectezi valorile tuturor pointerilor din program care puncteaza la acel obiect; pentru un limbaj ca C acest lucru este imposibil). LISP si Java folosesc uneori compactarea spatiului ocupat.

Tot compactare fac si programele care defragmenteaza discurile pentru a creste performanta accesului la fisiere.


Fragmentarea interna

Acest tip de alocare este folosit adesea pentru alocarea spatiului pe discurile magnetice, si pentru alocarea memoriei virtuale pentru procese.

Singurul mod în care putem evita fragmentarea externa este de a aloca toate obiectele de exact aceeasi marime. În acest caz orice ``gaura'' între doua obiecte poate fi folosita pentru un alt obiect. Cînd consumatorul vrea 10 sau 50 de octeti, tot 100 îi dai (de exemplu). Asta duce la risipa în interiorul fiecarui ``bloc'' alocat; aceasta este fragmentarea interna.

Structurile de date si algoritmii pentru alocarea blocurilor de marimi egale sunt mult mai simple si omogene (se pot chiar implementa partial în hardware). Din cauza asta practic toate sistemele de operare moderne aloca memoria virtuala în termeni de pagini, care au în jur de 4 kiloocteti fiecare.


Grad de utilizare

Pe lînga faptul ca spatiul se fragmenteaza, alocatorul însusi mentine propriile structuri de date pentru gestiune. Aceste structuri ocupa loc aditional, reducînd utilizarea efectiva a memoriei. De pilda, nucleele au o tabela a paginilor din RAM, în care memoreaza cum este utilizata fiecare pagina. Pentru fiecare pagina din RAM nucleul mentine la Pentium 4 octeti suplimentari; asta înseamna o risipa de 1 la mie.


Simplitate
Interfata malloc/free este foarte simpla; aproape ca nu se poate concepe ceva mai simplu. Alte alocatoare pot avea interactiuni mai complicate: de exemplu ar putea permite dealocarea doar a unui fragment dintr-o zona alocata anterior, ar putea cere ca free sa indice explicit cîta memorie trebuie dealocata, ar putea avea tot felul de argumente suplimentare referitoare la urgenta alocarii, etc.


Concurenta
În fine, o ultima dimensiune dupa care putem compara alocatoarele de memorie este gradul de acces concurent pe care îl permit. Pe un calculator cu mai multe procesoare este imaginabil ca doua procesoare vor simultan sa aloce/dealoce memorie. Pentru a preveni haosul, trebuie puse anumite restrictii asupra ordinii de executie. Zona de cod care aloca/dealoca este de obicei o regiune critica, în sensul ca nu poate fi executata de mai multe procesoare simultan3. Un alocator bine scris va permite un grad mai ridicat de concurenta, pentru a exploata mai bine resursele computationale.

 

Alocarea paginata


Aceasta alocare corespunde unui mod de organizare a memoriei ca pagini care alcatuiesc un intreg. Paginile au aceeasi marime. Aceasta impartire se face pentru ca alocarea datelor comune unui program sa fie la adrese succesive in memorie. Primul avantaj este acela al vitezei accesarii datelor; al doile avantaj este posibilitatea folosirii pointerilor de tip near. Un pointer near retine doar pozitionarea octetilor in cadrul paginii respective, adica nu se mai memoreaza numarul de ordine al paginii. Termenii consacrati pentru aceste concepte sunt: segment si offset.

O cerere de alocare a unui numar de octeti este tratata in urmatorii pasi:

  • se cauta un bloc continuu de octeti in prima pagina folosita de program
  • daca un asemenea bloc exista, se aloca blocul de octeti si se returneaza adresa de inceput a blocului
  • daca un asemenea bloc nu se gaseste in pagina curenta, se trece la pagina urmatoare
  • daca s-a cautat in toate paginile disponibile si nu s-a gasit nicaieri un bloc continuu de octeti, atunci se intoarce un cod de eroare