 |
Mihai Budiu -- mihaib+ at cs.cmu.edu
http://www.cs.cmu.edu/~mihaib/
17 decembrie 1998
``640 de kiloocteți trebuie să fie îndeajuns pentru oricine''. Aceasta este probabil cea mai faimoasă gafă a lui Bill Gates, pronunțată cîndva pe la începutul anilor '80. Enunțul este cu atît mai amuzant cu cît compania lui Gates, Microsoft, produce niște programe uriașe, pentru care resursele calculatoarelor contemporane, care au evoluat într-o rată greu de imaginat, nu sunt suficiente.
Dacă lucrurile ar fi stat așa, atunci articolul de față nu ar mai fi fost scris. Dar rata de creștere a programelor este comparabilă cu cea a capacităților memoriilor; pe de altă parte datele prelucrate de programe devin din ce în ce mai mari; audio, video, multimedia sunt mari consumatoare de spațiu.
Dacă lucrurile ar fi stat așa cum prevedea Gates, atunci sistemele de operare însele ar fi dispărut, sau ar fi arătat substanțial diferit de cele din ziua de azi; aceasta este tot o ironie, pentru că Microsoft își menține dominația în arena mondială a software-ului prin monopolul pe care îl are asupra sistemelor de operare pentru calculatoare personale. De ce spun că sistemele de operare ar fi dispărut? Pentru că rolul principal al unui sistem de operare este cel de management al resurselor unui calculator, în particular de management al memoriei. Dacă resursele ar fi prezente din abundență, atunci necesitatea unui manager ar fi mult mai puțin stringentă.
Ce este de fapt alocarea memoriei? Calculatorul posedă din fabricație o anumită cantitate de memorie (RAM). În memorie vor fi încărcate mai multe programe și datele prelucrate de ele: nucleul sistemului de operare, datele acestuia, programele utilizatorilor și datele asupra cărora acestea operează, datele citite de la dispozitivele periferice, pachetele de date care vin și merg în rețeaua în care calculatorul este conectat, bibliotecile încărcate dinamic, etc. O singură bucată mare de memorie (RAM-ul) trebuie împărțită între toate aceste entități lacome, în așa fel încît să nu se incomodeze unele pe altele. Entitatea care gestionează memoria, ține contabilitatea zonelor ocupate și a celor libere, care satisface cererile pentru noi zone și care re-utilizează zonele eliberate este alocatorul de memorie.
Alocarea memoriei este de obicei o treabă ierarhică; la baza ierarhiei se află sistemul de operare, care are la dispoziție întregul RAM. Sistemul de operare dă feluritelor programe ale utilizatorilor porțiuni de memorie. La rîndul lor, fiecare din programe gestionează bucățica primită de la nucleu pentru nevoile sale interne.
În acest text ne vom concentra asupra alocatorului de memorie din nucleele sistemelor de operare de tip Unix, dar vom privi superficial și asupra unor alte alocatoare. Un tratament excelent al subiectului puteți găsi în capitolul 12 din cartea ``Unix Internals'', de Uresh Vahalia, publicată în anul 1996 de editura Prentice Hall. Am folosit unele dintre prezentările din acea carte în scrierea acestui articol.
O clasificare a limbajelor din punctul de vedere al alocării memoriei le împarte în trei categorii:
Din anumite puncte de vedere, tehnica colectării de gunoaie este cea mai preferabilă. Principalul ei avantaj este că scutește utilizatorul de pericolul de a folosi zone de memorie nealocate, prevenind astfel apariția unor bug-uri extrem de greu de depanat. Avantajele ei nu se opresc aici: împreună cu o disciplină de tipuri strictă, colectarea deșeurilor face demonstrarea automată a corectitudinii programelor o sarcină mult mai simplă: un demonstrator de teoreme va fi întotdeauna sigur că o zonă de memorie folosită nu este dealocată.
Pe de altă parte, colectarea de gunoaie are anumite dezavantaje: este impredictibilă ca timp consumat (adică nu e clar în ce moment al execuției programului se va petrece), și este conservativă. Întrebarea dacă o anumită zonă de memorie va mai fi sau nu folosită de un program în viitor este în general o chestiune nedecidabilă; asta înseamnă că nu se poate scrie nici un algoritm care să răspundă la o astfel de întrebare, chiar dacă are informații complete despre programul analizat și despre datele lui de intrare. Din cauza aceasta este posibil ca un program cu colectare automată să păstreze alocate zone de memorie care sunt în realitate inutile, pentru că sistemul nu are cum să demonstreze acest lucru.
În acest articol vom vorbi mai ales despre sisteme de tipul intermediar, cu alocare și dealocare explicită. Motivele sunt multiple. În primul rînd majoritatea alocatoarelor din nucleele sistemelor de operare comerciale sunt de acest tip1. În al doilea rînd, chiar implementarea unui alocator cu colector va folosi idei de genul celor prezente în alocatoarele explicite. Și în al treilea rînd, colectarea gunoaielor este un subiect ceva mai dificil.
Nucleele sistemelor de operare comerciale sunt toate scrise în C, inclusiv alocatoarele de memorie din biblioteci; din cauza aceasta vom privi mai îndeaproape funcțiile acestui limbaj.
Programatorul în C are la dispoziție funcțiile malloc și prietenii ei (calloc, realloc) pentru a aloca memorie, și funcția free pentru a o elibera. calloc și realloc pot fi scrise folosind malloc, așa că nu le vom da prea mare atenție. Prototipurile acestor funcții se află în fișierul header <stdlib.h> din biblioteca standard C, prezentă pe orice sistem.
Funcția malloc are un singur argument: numărul de octeți care trebuie alocați. Rezultatul funcției este un pointer generic (void*) spre zona alocată. Dacă malloc nu găsește destulă memorie, atunci rezultatul apelului ei este pointerul cu valoarea 0 (NULL).
Funcția free() are tot un singur argument, și nici un rezultat. Argumentul ei este un pointer obținut de la un malloc anterior; efectul executării ei este eliberarea zonei de memorie aflată în acel loc.
Biblioteca în care sunt implementate malloc și free menține o pleiadă de structuri de date indicînd unde se află zonele libere și unde cele ocupate. Observați de pildă că free nu primește nici un fel de informații despre cît de mare este zona dealocată; biblioteca trebuie deci să știe acest lucru.
În cazul sistemului de operare Unix aceste funcții de bibliotecă sunt implementate folosind un apel de sistem2 numit sbrk. Figura 1 ilustrează relația dintre aceste funcții. Apelul de sistem are la ca argument cantitatea cerută de memorie (pozitivă sau negativă); efectul executării apelului este adăugarea la sfîrșitul segmentului de date al programului a unei cantități de memorie egale cu cea cerută.
În mod normal malloc execută un sbrk la început pentru a obține o cantitate mare de memorie, și apoi la fiecare apel returnează utilizatorului cîte o bucățică din bucata mare. Dacă după o vreme întreaga bucată mare devine ocupată, atunci malloc execută un nou sbrk.
|
Există o sumedenie de feluri de alocatoare diferite; în ceea ce privește colectoarele și în ziua de azi se desfășoară cercetări care îmbunătățesc performanța. Iată aici cîteva criterii după care putem evalua calitatea unui alocator.
Prima caracteristică este complexitatea unei operații de alocare/dealocare. În mod normal un alocator trebuie să execute un număr constant de operații pentru fiecare funcțiune. Dar vom vedea mai jos că adesea în cel mai rău caz alocatoarele trebuie să execute o sumedenie de instrucțiuni pentru a răspunde la o singură cerere. De exemplu alocatorul cu hartă de resurse, prezentat mai jos, ar putea să aibă nevoie să parcurgă întreaga listă de blocuri de memorie neocupate pentru a găsi unul de măsura potrivită. Asta înseamnă că, cu cît e mai multă memorie disponibilă, cu atît execuția unui apel de alocare/dealocare poate fi mai costisitoare (pentru că lista va fi mai lungă).
O măsură interesantă a costului unei alocări este timpul amortizat pentru o operație de alocare. De exemplu dacă cele mai multe operații de alocare durează 1ms, dar la fiecare 500 de operații costul execuției este de 200ms, atunci costul amortizat este de (499*1 + 1*200)/500 = 1.39ms pe operație (costul în cazul cel mai rău ar fi 200).
Sistemele cu colectare de gunoaie au de obicei un timp amortizat mic pentru fiecare operație, dar din cînd în cînd (atunci cînd colectorul pornește în execuție), anumite operații durează foarte mult. Acesta este cazul sistemelor LISP obișnuite.
Pentru că nucleul unui sistem de operare trebuie să facă față unor cereri extrem de severe, în general alocatoarele din nuclee trebuie să aibă cazul cel mai defavorabil relativ mic. Exista alocatoare care primesc niște indicații despre urgența operației: dacă cel care are nevoie de memorie nu se grăbește, algoritmul își poate permite să petreacă mai mult timp; altfel trebuie să răspundă cît se poate de repede.
De exemplu nucleul trebuie să primească pachete de date din rețea; atunci cînd un pachet își face apariția, nucleul nu poate să aștepte prea mult pentru a găsi un loc în care să-l depoziteze, pentru că nu are unde să pună pachetul între timp. Dacă nucleul nu reușește să obțină un buffer pentru o stoca pachetul, atunci de obicei pachetul este pur și simplu pierdut (asta se numește buffer overrun). Cel care a transmis pachetul inițial va trebui să trimită o copie.
Alocatoarele se mai confruntă cu o problemă neplăcută: aproape niciodată nu pot folosi întreaga memorie disponibilă, pentru că mici fragmente ``se pierd'' fără a putea fi folosite.
Aceste pierderi apar din cauză că consumatorii de memorie doresc bucăți de memorie de mărimi variate, care sunt greu de pus cap la cap în memoria disponibilă. În funcție de interfața alocatorului, există două tipuri de pierderi. Pentru că pierderile apar din cauza împărțirii spațiului disponibil în fragmente, această problemă se numește fragmentare. Există două feluri de fragmentare: internă și externă.
Tabela 1 arată un posibil scenariu de cereri de alocare/dealocare și evoluția memoriei în timp.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Fenomenul se petrece la momentul 4: dealocăm un bloc de memorie de 5 octeți cuprins între alte două blocuri. După aceea alocăm unul de zece; cei cinci octeți nu sunt suficienți, așa că în acel loc rămîne o ``gaură''. Astfel de găuri apar din ce în ce mai multe, și scad în dimensiune (de exemplu dacă am aloca apoi 3 octeți în gaura de 5 am rămîne cu o gaură de 2 octeți). După o vreme găurile practic nu mai pot fi folosite, dar consumă în total o sumedenie de spațiu. Acest gen de fragmentare se numește ``extern'' pentru că risipa apare între blocurile alocate.
Se demonstrează că atunci cînd avem de-a face cu alocări de blocuri de mărimi diferite, fragmentarea externă este inevitabilă. Singurul mod în care putem repara ceva este de a muta blocuri dintr-o parte într-alta, compactînd spațiul liber. Dar aceasta este o operație extrem de costisitoare ca timp, care în anumite condiții este imposibilă (de exemplu atunci cînd muți ceva din memorie trebuie să corectezi valorile tuturor pointerilor din program care punctează la acel obiect; pentru un limbaj ca C acest lucru este imposibil). LISP și Java folosesc uneori compactarea spațiului ocupat.
Tot compactare fac și programele care defragmentează discurile pentru a crește performanța accesului la fișiere.
Acest tip de alocare este folosit adesea pentru alocarea spațiului pe discurile magnetice, și pentru alocarea memoriei virtuale pentru procese.
Singurul mod în care putem evita fragmentarea externă este de a aloca toate obiectele de exact aceeași mărime. În acest caz orice ``gaură'' între două obiecte poate fi folosită pentru un alt obiect. Cînd consumatorul vrea 10 sau 50 de octeți, tot 100 îi dai (de exemplu). Asta duce la risipă în interiorul fiecărui ``bloc'' alocat; aceasta este fragmentarea internă.
Structurile de date și algoritmii pentru alocarea blocurilor de mărimi egale sunt mult mai simple și omogene (se pot chiar implementa parțial în hardware). Din cauza asta practic toate sistemele de operare moderne alocă memoria virtuală în termeni de pagini, care au în jur de 4 kiloocteți fiecare.
Pe lîngă faptul că spațiul se fragmentează, alocatorul însuși menține propriile structuri de date pentru gestiune. Aceste structuri ocupă loc adițional, reducînd utilizarea efectivă a memoriei. De pildă, nucleele au o tabelă a paginilor din RAM, în care memorează cum este utilizată fiecare pagină. Pentru fiecare pagină din RAM nucleul menține la Pentium 4 octeți suplimentari; asta înseamnă o risipă de 1 la mie.
Interfața malloc/free este foarte simplă; aproape că nu se poate concepe ceva mai simplu. Alte alocatoare pot avea interacțiuni mai complicate: de exemplu ar putea permite dealocarea doar a unui fragment dintr-o zonă alocată anterior, ar putea cere ca free să indice explicit cîtă memorie trebuie dealocată, ar putea avea tot felul de argumente suplimentare referitoare la urgența alocării, etc.
În fine, o ultimă dimensiune după care putem compara alocatoarele de memorie este gradul de acces concurent pe care îl permit. Pe un calculator cu mai multe procesoare este imaginabil că două procesoare vor simultan să aloce/dealoce memorie. Pentru a preveni haosul, trebuie puse anumite restricții asupra ordinii de execuție. Zona de cod care alocă/dealocă este de obicei o regiune critică, în sensul că nu poate fi executată de mai multe procesoare simultan3. Un alocator bine scris va permite un grad mai ridicat de concurență, pentru a exploata mai bine resursele computaționale.
Începînd cu această secțiune, voi trece în revistă felurite tipuri de alocatoare folosite în practică. În mijlocul acestei discuții voi insera o secțiune despre constrîngerile puse asupra alocatoarelor. Discuția este departe de a fi exhaustivă; este mai curînd ilustrativă.
Să începem cu cel mai simplu tip de alocator, cel care...nu există. În acest caz trebuie să alocăm toate zonele de la scrierea programului. Metoda aceasta era folosită în versiunile vechi de Unix, și este în continuare folosită pentru anumite sisteme de fișiere (sistemul de fișiere din Unix, UFS, prealocă pentru fiecare fișier cîte un inod pe disc la momentul formatării discului; numărul acesta nu se poate apoi schimba). În Pascal matricile pot fi alocate numai static (adică dimensiunile lor trebuie să fie cunoscute la compilare).
Marele avantaj al metodei este simplitatea. Există însă două mari dezavantaje:
Fiecare consumator de memorie are idiosincraziile lui; contextul în care memoria este folosită impune anumite constrîngeri asupra implementării alocatorului.
Cel mai comun consumator de memorie sunt programele utilizatorilor. Acestea pun și cele mai puține restricții asupra alocatorului; cele mai multe programe ale utilizatorilor nu au constrîngeri severe de viteză sau spațiu, și ca atare pot implementa scheme foarte complicate, cu cost mediu mai ridicat dar care au alte trăsături dezirabile.
Înainte de a trece la celelalte tipuri de alocatoare, permiteți-mi să fac niște recomandări de stil în ceea ce privește alocarea memoriei. Recomandările sunt inspirate de indicațiile proiectului GNU, care produce software de foarte bună calitate (despre proiectul GNU am scris pe larg într-un articol din PC Report consacrat fenomenului Free Software).
/* 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;
}
Funcția de bibliotecă realloc face chiar acest lucru: are ca argument un pointer și o nouă dimensiune. Rezultatul este un nou buffer, care are dimensiunea indicată, și care conține tot vechiul conținut al buffer-ului inițial.
/* Folosirea lui `realloc' pentru a mari un buffer pe masura
datelor pe care trebuie sa le contina */
#include <stdlib.h>
#define DUBLEAZA 1
char *buf = 0; /* bufferul */
int marime = 0; /* marimea curenta */
int ramas = 0; /* spatiu liber ramas in buffer */
FILE *f = blabla; /* un fisier oarecare */
while (1) {
int c = fgetc(f); /* citim date dintr-un fisier intr-un buffer */
if (c == EOF) break;
if (!ramas) { /* buffer-ul e plin: trebuie realocat */
/* avem doua variante de realocare */
#if DUBLEAZA
int marimenoua = marime ? (marime * 2) : 1;
#else
int marimenoua = marime + 1;
#endif
buf = realloc(buf, marimenoua);
if (!buf) exit(1); /* eroare fatala */
ramas = marimenoua - marime;
marime = marimenoua;
}
buf[marime - ramas] = c;
ramas--;
}
O simplă analiză arată că dacă dublăm lungimea buffer-ului,
costul plătit pentru a stoca k caractere este 1 + 2 + 4 + ...+
2lk, unde
. (Plătim un cost de 1
pentru realloc(2), 2 pentru realloc(4), etc.). Asta este o serie
geometrică, a cărei sumă este < 2k.
Pe de altă parte, dacă mărim buffer-ul cu o unitate la fiecare pas, plătim 1+2+3+...+(k-1) = k2.
Un alt alocator se află în nucleul sistemului de operare. Așa cum am spus deja, acest alocator gestionează atît spațiul folosit în structurile de date interne nucleului, cît și spațiu necesar proceselor care se execută. Interacțiunea dintre variatele alocatoare este înfățișată în figura 2.
 |
Subiectul acestui articol este cutiuța etichetată ``alocatorul intern al nucleului'', deși multe din principiile indicate se aplică și celorlalte entități. Aceste alocatoare sunt mult mai constrînse decît alocatoarele din spațiul utilizatorului; în particular trebuie să aibă timpi de răspuns foarte mici, pentru că pot fi chemate de părți critice din nucleu.
Cele trei alocatoare interacționează permanent: cînd nucleul nu mai are destule zone pentru propriile lui date cere noi pagini de la alocatorul de pagini. Cînd procesele utilizatorilor mor, paginile lor sunt preluate de alocatorul de pagini. Cînd alocatorul de pagini are puține resurse disponibile, el poate cere alocatorului intern să returneze din memoria pe care nu o folosește în acel moment, etc..
Un ultim mare subsistem al nucleului care se ocupă de alocarea spațiului este sistemul care alocă spațiu pe disc, atît pentru fișiere, cît și pentru memoria virtuală (memoria proceselor care sunt oprite din execuție este uneori salvată pe disc pentru a permite executarea altora; această tehnologie se numește ``memorie virtuală'').
Alocatoarele de spațiu pe disc au alte atribute foarte specifice; de pildă alocatoarele care trebuie să parcurgă o listă întreagă pentru a găsi spațiul necesar sunt complet nepractice, pentru că accesele la disc durează extrem de mult (milisecunde, ceea ce înseamnă milioane de cicli de procesor). Despre funcționarea acestor alocatoare am vorbit pe scurt în alte articole din PC Report, consacrate sistemelor de fișiere.
Voi ilustra aici în scop pur didactic implementarea unui alocator extrem de ineficient și risipitor, dar totodată complet. Aceasta este schema de bază de funcționare a tuturor alocatoarelor din nucleu; variațiunile constau în îmbunătățiri. Acest alocator implementează funcția free() fără a face nimic! Memoria eliberată este pur și simplu pierdută. Alocatorul extrage zonele de memorie dintr-o memorie mare alocată static inițial, care are 16 megaocteți. Puteți folosi acest alocator în programele dumneavoastră!
/* implementarea unui alocator dinamic foarte simplu; functia
free() nu face absolut nimic. */
typedef unsigned int size_t;
#define MARIME_MEMORIE 16 * 1024 * 1024
char memorie[MARIME_MEMORIE];
int memorie_consumata = 0;
void * malloc(size_t marime)
{
if (MARIME_MEMORIE < marime + memorie_consumata)
return 0;
memorie_consumata += marime;
return (void*) &memorie[memorie_consumata - marime];
}
void free(void *)
{}
Acest alocator este extrem de rapid; probabil că nici nu poate fi scris un alocator mai rapid. Prețul plătit este o enormă risipă de memorie: tot ce este dealocat se pierde complet.
Oricum, aceste funcții ilustrează cărămizile de bază cu care un alocator din nucleu trebuie să opereze. Alocatorul de pagini manipulează memoria fizică a mașinii ca un vector enorm de octeți, din care extrage porțiuni așa cum facem noi cu vectorul numit memorie.
Acesta este probabil cel mai simplu tip de alocator care implementează și funcția free. Acest alocator menține un vector de structuri care descriu fiecare bloc liber. Figura 3 arată o posibilă reprezentare a situației la un moment dat:
 |
Avem o mică problemă, pentru că alocatorul are nevoie el însuși de spațiu pentru a reprezenta tabela cu resurse. Putem face însă niște mici trucuri pentru a compacta reprezentarea:
Forma unui bloc de memorie ocupat: fiecare bloc este
precedat de 4 octe'ti care con'tin lungimea blocului.
--------------------------------------------
| lungimea | |
--------------------------------------------
^
\ adresa returnat'a de malloc
 |
Cînd alocatorul vrea să găsească un bloc liber pleacă de la adresa primului bloc liber și parcurge lista de blocuri libere pînă găsește unul de dimensiune corespunzătoare.
Acest alocator este relativ simplu, dar foarte ineficient. Din cauza fragmentării complexitatea operațiilor este mare (după o vreme lista de blocuri libere devine populată cu o sumedenie de blocuri mici, a căror traversare este costisitoare și inutilă). Schema este de asemenea ușor risipitoare: 4 octeți sunt memorați în plus pentru fiecare bloc ocupat, iar faptul că un bloc liber trebuie să conțină două valori impune o lungime minimă de 8 octeți pentru un bloc.
Eliberarea unui bloc îl inserează la începutul listei de blocuri libere. Dacă vrem să reducem fragmentarea, la eliberare putem să comasăm un bloc cu vecinul următor, în caz că acesta este liber și el. Dacă vrem să putem comasa și cu vecinul anterior, atunci în fiecare bloc memorăm și în ultimii 4 octeți lungimea sa; în acest fel, atunci cînd eliberăm un bloc, putem ști exact unde începe cel de dinainte. În orice caz, eliberarea cere un număr constant de instrucțiuni (care nu depinde de numărul de zone deja alocate).
Problema alocatorului de mai sus constă în faptul că trebuie să caute un bloc de dimensiune potrivită. Pentru a remedia acest lucru putem folosi o altă reprezentare: păstrăm o serie de liste de blocuri, toate blocurile de pe fiecare listă avînd o anumită dimensiune. Atunci cînd vrem un anumit bloc, returnăm un bloc de dimensiunea imediat superioară. Cele mai folosite dimensiuni sunt puteri ale lui 2, ca în figura 5.
 |
Acest alocator suferă de fragmentare internă, pentru că alocă întotdeauna mai mult decît i se cere.
Alocarea și dealocarea cer timp constant pe operațiune (calculul listei plus extragerea primului bloc din listă). Putem reprezenta listele de blocuri libere exact ca în schema cu harta de resurse; comasarea este practic imposibil a (am putea comasa numai vecini de dimensiuni egale, ca să obținem rezultate de mărime tot puteri ale lui doi). Pentru toate blocurile mai mici de o anumită limită și mai mari de o alta, putem avea niște liste separate, în care facem căutare exhaustivă. Dacă vrem să avem liste cu toate dimensiunile posibile de blocuri sunt suficiente 32 de liste, ceea ce e o valoare rezonabilă.
În momentul în care o listă dorită este complet depopulată, putem scoate un bloc mai mare de pe lista imediat superioară, pe care îl putem sparge în două bucăți mai mici.
În interiorul nucleului există multe structuri de date care au ca dimensiuni exact puteri ale lui 2; pentru astfel de cereri se irosește o cantitate enormă de memorie, pentru că fiecare bloc alocat trebuie să conțină și cei 4 octeți suplimentari. Astfel, dacă vrem să alocam 256 de octeți, trebuie de fapt 260, care înseamnă ca folosim un bloc de 512; risipa este de aproape 100%!
Alte dezavantaje ale metodei: în general blocurile mici nu se pot grupa laolaltă pentru a forma blocuri mari, și sistemul de paginare nu poate obține pagini nefolosite înapoi în caz de nevoie.
În 1988 Kirk McKusick și Michael Karels au construit o variantă îmbunătățită a alocatorului cu puteri ale lui 2, cere este folosită acum în 4.4BSD Unix și Digital Unix. Metoda lor elimină risipa pentru cazul blocurilor care au dimensiuni exact puteri ale lui 2.
Listele de blocuri libere sunt înlănțuite exact ca în alocatorul cu puteri ale lui 2. Diferența principală constă în modul în care blocurile ocupate își reprezintă lungimea; trucul folosit este foarte ingenios: alocatorul menține un vector mare de numere, cîte unul pentru fiecare pagină. Elementul 5 din vector reprezintă mărimea blocurilor din pagina 5. Figura 6 arată un exemplu de structuri de date ale alocatorului.
 |
O altă optimizare făcută de alocatorul acesta este modul în care se calculează rotunjirea în sus a unei valori la cea mai mică putere a lui 2; calculul este făcut cu un macro care conține o expresie de genul:
#define LISTA(marime) \
(marime) > 128 \
? (marime) > 256 ? 4 : 3 \
: (marime) > 64 \
? 2 \
: (marime) > 32 ? 1 : 0
Avantajul unei astfel de expresii în locul unei bucle este că, atunci cînd mărimea este cunoscută la compilare, întreaga expresie devine o constantă care poate fi calculată de compilator, deci codul executat devine mult mai rapid.
Acest alocator este mai eficient decît cel cu puteri ale lui 2, și risipește mult mai puțină memorie, pentru că toate cererile egale cu o putere a lui doi sunt satisfăcute cu un buffer de mărime potrivită. Celelalte dezavantaje rămîn însă prezente.
O schemă mult mai sofisticată de alocare, inspirată din limbajele orientate pe obiecte a fost introdusă de Sun în sistemul de operare Solaris 2.4 și este acum implementată și în Linux. ``Slab'' înseamnă în engleză ``lespede''; acest alocator are zone de memorie diferite pentru obiecte diferite, pe care le putem vedea ca niște mozaicuri de forme diferite; de aici și numele. Acest alocator tratează cu multă atenție o serie de aspecte importante pentru performanță care sunt complet ignorate de alte alocatoare:
Alocatorul slab constă de fapt într-o rutină centrală (numită kmem_cache_create) care crează alocatoare pentru fiecare obiect. Rutina asta primește ca parametri numele obiectului, mărimea unui obiect, constrîngerile de aliniere (de ex. toate obiectele trebuie să fie la o adresă multiplu de 16) și pointeri spre o funcție constructor și o funcție destructor.
Iată un exemplu de utilizare:
alocator_de_fisiere = kmem_cache_create("fisier", sizeof(struct fisier),
8, constructor_fisier,
destructor_fisier);
alocator_de_inoduri = kmem_cache_create("inod", sizeof(struct inod),
4, constructor_inod,
destructor_inod);
struct fisier * fs = kmem_cache_alloc(alocator_de_fisiere, FLAGS);
struct inod * in = kmem_cache_alloc(alocator_de_inoduri, FLAGS);
Funcția kmem_cache_create crează deci alocatoare pentru felurite obiecte. Fiecare alocator este apoi folosit pentru a construi obiecte de acel tip.
Fiecare alocator are propria lui zonă de memorie, în care menține numai obiecte de acel tip; va exista astfel o zonă de pagini în care se alocă numai fișiere, o zonă în care se alocă numai inoduri, etc. În acest fel toate obiectele dintr-o zonă au aceeași dimensiune!
Fiecare alocator menține de asemenea o listă cu obiectele care au fost de curînd dealocate, și le refolosește atunci cînd i se cer noi obiecte. Pentru că obiectele au fost dealocate, ele nu mai trebuie sa fie inițializate din nou.
Atunci cînd un alocator epuizează toată memoria pe care o are la dispoziție, el cere de la alocatorul de pagini o nouă pagină pe care o umple cu obiecte noi. Pentru că aceste obiecte nu au fost niciodată inițializate, alocatorul cheamă funcția constructor care a fost indicată pentru fiecare nou obiect. Observați că acest constructor este chemat numai prima oară cînd pagina este obținută; după ce un obiect a fost dealocat constructorul nu mai este chemat din nou.
 |
Fiecare alocator folosește propriile lui pagini într-un mod similar cu alocatorul cu puteri ale lui doi. La sfîrșitul fiecărei pagini alocatorul rezervă o zonă pentru o structură de date care descrie ocupația acelei pagini. Primul obiect în pagină este plasat la o distanță aleatoare de marginea pagini; acest plasament are efectul de a pune obiecte din pagini diferite la adrese diferite în cache, exact cum am indicat mai sus.
Alocatorul slab poate returna sistemului de paginare paginile în care toate obiectele sunt nefolosite. Alocatorul are o ``urmă'' mică, pentru că majoritatea cererilor accesează o singură pagină. Acest tip de alocator risipește ceva resurse datorită modului de plasare în pagină și pentru că are o zonă diferită pentru fiecare tip de obiect. Performanța lui este însă excelentă, și rămîne unul din cele mai puternice alocatoare implementate.
Alocarea memoriei este un subiect foarte generos, care suscită în continuare interes cercetătorilor. Gestiunea memoriei este un din funcțiile principale ale unui sistem de operare. Nucleul unui sistem de operare gestionează întreaga memorie fizică a unui calculator; el oferă memorie atît sieși (nucleului), pentru funcționarea sa, cît și proceselor executate de utilizatori. Procesele utilizatorilor gestionează la rîndul lor bucățelele primite de la nucleu.
Dacă subiectul vă interesează mai aveți multe de aflat în domeniu. Dacă nu, sper să-i alocați măcar 2-3 neuroni în memoria dumneavoastră. Alegeți un algoritm în acest scop.