Algoritmi de Gestiune a Memoriei

Algoritmi de gestiune a memoriei

In continuare vom detalia cativa algoritmi care furnizeaza un nou page frame atunci cand este nevoie. Notam cu “N” numarul de pagini de memorat.

Bitmap

Bitmap-ul reprezinta o matrice de N/8 bytes avand rolul unei harti pentru indicarea folosirii memoriei. Intrarile in Bitmap contin o valoare pe minim un bit ce reprezinta starea de alocare a blocului de memorie corespunzator acelei intrari.

O forma simpla este intrarea este pe un bit cu valoarea 0, daca blocul de memorie este liber si 1 daca blocul de memorie este folosit de un proces. De exemplu, la un sistem u memorie de 256 MB avem nevoie de un Bitmap de dimensiune 8 192 Bytes pentru a gestiona toate cele 65 536 de pagini.

O forma mai avansata este intrarea pe doi biti, reprezentand una din cele 3 stari posibile:

– „liber” – starea corespunzatoare blocului de memorie nealocat (nefolosit);

– „sub-alocat” – starea corespunzatoare blocului de memorie care este el insusi un set alocat de mai multe blocuri;

– „alocat” – starea corespunzand blocului de memorie folosit de un proces.

Avantajul folosirii Bitmap-ului este reprezentat de implementarea sa simpla (alocarea spatiului pentru o intrare , parcurgerea si modificarea usoara a valorii starii blocului de memorie, de ex. : “aaaaaaaabbbbbbbb” = „a8b8” ).

Dezavantajele sunt urmatoarele:

– pentru a aduce spre folosinta un numar K de blocuri alaturate de memorie, manager-ul de memorie, trebuie sa gaseasca o sectiune continua de K intrari in Bitmap. Pentru a imbunatati performantele se foloseste un pointer care sa indice ultma intrare a unui bloc alocat, astfel cunoastem faptul ca intrarile anterioare au fost deja cautate si alocate.

– La fiecare alocare a unui bloctrebuie parcurs intreg Bitmap-ul

Stack/List of pages

Folosirea stivei (o structura de tip last in – first out) reprezinta o alternativa la Bitmap.

Stiva este o regiune dinamică în cadrul unui proces. Aceasta este folosită pentru a stoca “stack frame-urile” în cazul apelurilor de funcții și variabilele locale.

Stiva este gestionată automat de compilator. La fiecare revenire din funcție stiva este golită.

Pe marea majoritate a arhitecturilor moderne stiva crește în jos și heap-ul crește în sus. Adresele (fizice) ale paginilor libere sunt puse in stiva, iar cand o pagina trebuie alocata adresa urmatoare este scoasa din stiva si folosita. Cand o pagina este eliberata, adresa sa este pusa inapoi in stiva, si tot asa. Astfel, o alocare (sau dealocare) devine o problema de incrementare (sau decrementare) a unui pointer. Desi multe alocari nu necesita ca adresele fizice sa fie alaturate, exista si astfel de cazuri cum ar fi DMA. Daca este nevoie ca adresele sa fie alaturate, atunci managerul de memorie trebuie sa scoata adresele din mijlocul stivei, operatie ceva mai complicata. Avantajul acestei metode este ca alocarea si de-alocarea sunt rapide, in schimb verificarea starii unei pagini nu este deloc practica.

In plus, daca toata memoria ar fi libera ar fi nevoie de N x 4 bytes pentru a stoca toate starile.

Scheme hibride

O alta alternativa ar fi folosirea unor scheme hibride dupa cum urmeaza:

1. Alocatorii (cei care aloca memoria) pot fi inlaintuiti astfel incat in stiva sa fie retinute doar ultimele operatii, iar sfarsitul ei sa fie legat de Bitmap, pentru o buna compacitate. Daca stivei ii lipsesc pagini, se poate scana Bitmap-ul pentru a le gasi.

2. A doua varianta ar fi ca in loc sa memoram biti reprezentand pagina, sau numere intr-o stiva, sa folosim o matrice de structuri pentru a reprezenta memoria. Aceste structuri de page frame-uri stocheaza o singura legatura catre o pagina urmatoare (de marimea unui pointer) si un block de informatie de 8-16 biti, care sa indice starea paginii. Algoritmul include, de asemenea, un pointer catre o pagina virtuala si TCB-ul fiecarui numar de pagina. Se pastreaza pointeri pentru fiecare tip de pagina, care sa indice atat inceputul cat si sfarsitul listelor. In acest fel se poate afisa cu usurinta informatia despre continutul lor, numarul de pagini pentru fiecare tip, tipuri mixe. De asemenea, se permite o curatare dinamica, se permite un „copy-on write” destul de usor si se pastreaza clar si concis overviewurile paginilor. Este la fel ca la un tabel de mapare invers, care listeaza si tipurile de pagina.

4.4.4 Flat List

Spatiul adreselor poate fi foarte bine gestionat prin folosirea unei liste inlantuite – „linked-list”. Fiecare regiune „libera” (nealocata) este asociata cu un descriptor ce indica marimea si adresa ei de baza (inceput). Cand un anumit spatiu trebuie alocat, lista este scanata dupa un algortim „first fit”sau „best fit” sau un alt algoritm corespunzator. Cand memoria este alocata, intrarea respectiva este ori inlaturata (daca intreaga regiune a fost alocata), ori redimensionata (numai o poritune din regiune a fost alocata). Un dezavantaj ar fi ca in cazul „linked-lists”,trebuie parcursa complet lista pentru a gasi cea mai potrivita locatie.

O alta problema o constituie situatia in care memoria este fragmentata, iar lista de dimensiune mare. In acest caz trebuiesc identificate doua zone libere care se unesc si formeaza o zona mai mare.

Exemplu de lista inlantuita :

O soluție este de a menține o listă a segmentelor alocate și libere, unde un segment este fie un proces fie un spațiu între procese. Fiecare element al listei conține un câmp care specifică dacă este un spațiu (S) sau un proces (P), adresa de unde începe segmentul, lungimea sa și un pointer spre următorul element. Lista se poate menține sortată după câmpul de adresă ceea ce determină ca actualizarea listei să se facă foarte ușor în cazul terminării unui proces sau mutării lui pe disc.

Un proces din interiorul memoriei (nu de la capete) are doi vecini. După terminarea lui, ne putem găsi în una din următoarele situații :

Cheltuielile de regie ar fi mai mici dacă s-ar folosi o listă dublu înlănțuită.

În cazul păstrării listei ordonate după adresă, avem următorii algoritmi de alocare a memoriei pentru un proces nou creat sau adus de pe disc :

4.4.5 Arborele

Din moment ce a devenit frecventa cautarea in lista a unei anumite adrese sau a unui spatiu de memorie de o anumita dimensiune, o solutie ar fi utilizarea unor structuri de date mai eficiente. Una din structuri care pastreaza inca parcurgerea intregii liste este „ Tree” („Arborele ”). Fiecare nod din acest arbore va descrie o regiune de memorie si are un pointer catre subarborii (subtrees) nodurilor inferioare si catre subarborii (subtrees) nodurilor superioare.

Un arbore binar (Adelson-Velskii si Landis) este un arbore binar ordonat avand proprietatea ca pentru fiecare nod al sau inaltimea subarborelui stang difera de inaltimea subarborelui drept cu cel mult 1.

Cu alte cuvinte, intr-un arbore pentru orice nod R avand subarborii Ss si Sd de inaltime hs, respectiv hd, |hs-hd| <= 1. Inaltimea unui arbore vid este 0, iar inaltimea unui arbore nevid este 1 plus maximul dintre inaltimea subarborelui stang si inaltimea subarborelui drept.

Operatia de cautare a unui nod cu cheia data in arbori echilibrati se face cu un efort de calcul de O(log n) unitati de timp, consecinta directa a teoremei demonstrate de Adelson-Velskii si Landis ce garanteaza ca un arbore echilibrat nu va fi niciodata cu mai mult de 45% mai inalt decat omologul sau perfect echilibrat, oricare ar fi numarul sau de noduri.

Desi inserarea sau stergerea intr-un astfel de arbore necesita operatii mai complexe decat o simpla manipulare a listei, parcurgerea arborelui se face cu log2(N) iteratii, in loc de N iteratii la liste inlantuite – asa ca daca avem 100 de intrari este nevoie doar de 10 iteratii, in loc de 100 pentru a gasi un interval cautat.

Observatie importanta : algoritmul se folosete pentru regiuni (ca acelea pe care le gasim

in /proc/xxx/maps) si nu pentru interfata de tip malloc.