8

Gestiunea memoriei

​

Gestiunea memoriei (II)

• Gestiunea memoriei fizice în Linux
• Gestiunea memoriei virtuale în Linux
• Bibliografie
• UTLK: capitolele 8, 9

Gestiunea memoriei fizice în Linux

• Algoritmi și structuri de date ce mențin starea memoriei fizice
• Se face la nivel de pagină
• (Relativ) independentă de gestiunea memoriei virtuale
• Fiecare pagina fizică are asociat un descriptor: struct page
• În zona lowmem se ţine un vector de astfel de descriptori (mem_map)
• (descritorul de pagină conţine: un contor de utilizare al paginii, flag-uri, poziţia în swap sau în fișier, buferele conţinute de pagină, poziţia în "page cache", etc.)

Zone (fizice) de memorie

• Zona DMA: 0 - 16Mb
• Zona Normal (LowMem): 16Mb - 896Mb
• Zona HighMem: 896Mb – 4Gb/64Gb
• Non-Uniform Memory Access
• Memoria fizică este împarțită între mai multe noduri
• există un spaţiu comun de adrese fizice
• accesul la memoria locală este mai rapidă
• Fiecare nod
• are procesorul propriu
• are zone de memorie proprii: DMA, NORMAL, HIGHMEM

Alocarea de pagini

• alloc_pages(gfp_mask, order)
• Alocă 2^order PAGINI contigue şi întoarce un descriptor de pagină pentru prima pagină alocată
• alloc_page(gfp_mask)
• Funcții mai folositoare (întorc adresa liniară a paginii/primei pagini)
• __get_free_pages(gfp_mask, order)
• __get_free_page(gfp_mask)
• __get_zero_page(gfp_mask)
• __get_dma_pages(gfp_mask, order)

​

De ce alocare în puteri ale lui 2?

• Algoritmii de alocare obișnuiți sunt liniari
• O posibilă soluţie: paging
• Uneori kernelul chiar are nevoie de memorie fizică contiguă (pentru DMA)
• Dacă s-ar folosi paging, tabela de pagini s-ar modifica => penalizări la accesul la memorie
• Dacă s-ar folosi paging nu s-ar mai putea folosi paginare extinsă (pagini de 4Mb/2Mb)
• Anumite arhitecturi (MIPS) mapează o parte din spaţiul liniar de adresă kernel în memoria fizică (i.e. pe acea zonă nu se foloseşte paginare)

Algoritmul buddy

• Blocurile sunt grupate în liste de dimensiune fixă
• Blocurile au ca dimensiune puterile lui 2, aliniate corespunzător cu dimensiunea
• Alocarea se face numai în blocuri de puteri ale lui 2
• La alocarea unui bloc (dimensiune N)
• Dacă există un bloc de dimensiune N se alocă
• Dacă nu, se sparge un bloc de dimensiune 2N în două blocuri de dimensiune N, unul se alocă, altul se pune în lista cu blocuri de dimensiune N
• La dealocarea unui bloc (dimensiune N)
• Dacă există blocuri adiacente în memoria fizică de aceeași dimensiune N, iar primul este aliniat la 2N, cele două blocuri se “coagulează” într-un bloc de dimensiune 2N
• Se încearcă iterativ să se coaguleze cât mai multe blocuri

Implementarea algorimului buddy în Linux

• Sunt folosite 11 liste pentru blocuri de 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 PAGINI
• Fiecare zonă de memorie are alocatorul buddy propriu
• Fiecare zona are asociată un vector de descriptori de blocuri libere, câte o intrare pentru fiecare dimensiune de bloc
• Descriptorul de blocuri libere conţine numărul de pagini libere şi capul listei de blocuri libere
• Blocurile sunt înlănţuite cu ajutorul câmpului lru din descriptorul de pagini
• Paginile libere folosite de buddy au flagul PG_buddy setat
• Descriptorul de pagina menţine dimensiunea blocului în câmpul private pentru a putea face uşor verificările necesare pentru coagularea a două blocuri libere ce sunt adiacente

Alocarea de blocuri cu dimensiune mică

• Sistemul buddy este folosit în kernel pentru a aloca pagini
• Multe componente din kernel au nevoie de blocuri de dimensiune mult mai mică decât dimensiunea unei pagini
• Soluţie: folosirea de blocuri mai mici cu dimensiune variabilă
• Probleme: fragmentare externă
• Soluţie: folosirea unor blocuri de dimensiune fixă, dar mai mici
• Probleme: cât de mică/mare să fie dimensiunea ?
• Soluţie: crearea mai multor zone cu blocuri de mai multe dimensiuni, distribuite geometric: 32, 64, ..., 131 056

Alocatorul slab

• Zonele de memorie alocate/dezalocate sunt văzute ca "obiecte"
• Fiecare tip de "obiect" are un constructor și un destructor
• Obiectele dealocate sunt păstrate într-un cache, astfel că la urmatoarea folosire a lor nu mai trebuie reiniţializate și nu mai trebuie apelat algoritmul buddy
• În Linux nu (prea) se folosesc constructori/destructori din motive de eficienţă

De ce slab?

• Kernelul tinde să aloce/dealoce succesiv acelaşi tip de structuri de date (de exemplu PCB-uri); folosirea cache-ului din slab reduce frecvenţa operatiilor (mai costisitoare) de alocare/dealocare
• Multe cereri de alocare frecvente folosesc aceeaşi dimensiune pentru fiecare alocare: pentru aceste tipuri se pot crea zone speciale, care să conţină blocuri de dimensiunea dorită => se reduce astfel fragmentarea interna
• Pentru cereri ce nu folosesc aceaşi dimensiune la alocare (mult mai puţin frecvente) se poate folosi în continuare abordarea geometrică (şi cache)
• Reduce foot-print-ul pentru alocare/dealocare pentru că nu se mai caută pagini libere ci sunt luate direct din cache-uri (cache-urile de obiecte sunt concentrate într-o zonă de memorie şi sunt mult mai mici decât structurile folosite de buddy)
• Distribuie obiectele în memorie astfel încât să acopere uniform liniile de cache

Arhitectura alocatorului slab

• Alocatorul slab este format din
• Mai multe cache-uri
• Fiecare cache are mai multe slab-uri
• Fiecare slab menţine mai multe obiecte alocate / libere

Descriptorii de cache

• Un nume folosit pentru informaţii către user-space
• Funcţii pentru iniţializarea / deiniţializarea obiectelor cache-ului
• Dimensiunea obiectelor
• Diverse flaguri statice / dinamice
• Dimensiunea slab-urilor (structurile care conţin efectiv obiectele) în pagini (puteri ale lui 2)
• Măsti GFP pentru alocarea dintr-o zonă specifică
• Mai multe slab-uri: pline, libere sau parţial pline

Descriptorii de slab

• Numărul de obiecte alocate
• Zona de memorie în care se ţin obiectele
• Zona de memorie către primul obiect liber
• Descriptorii de slab sunt ţinuti fie
• În cadrul slab-ului ce îl descriu (dacă dimensiunea obiectelor e mai mică de 512, sau dacă fragmentarea internă lasa loc pentru descriptorul de slab)
• În cadrul unor cache-uri generale folosite de către alocatorul slab

Arhitectura detaliată slab

Cache-urile generale / specifice

• Cache-urile generale sunt folosite de alocatorul slab pentru
• A aloca memorie pentru descriptorii de cache sau slab
• A menţine 26 de cache-uri generale cu dimensiunea obiectelor de 32, 64, 128, ..., 131 072 (câte unul pentru zona normală şi unul pentru zona DMA); kmalloc() alocă memorie din aceste cache-uri
• Cache-urile specifice sunt create de către restul kernelului la cerere

Descriptorii de obiecte

Descriptorii de obiecte

• Descriptorul de obiect este folosit doar atunci când obiectul este liber
• Este de fapt un întreg care indică următorul obiect liber
• Ultimul obiect liber are valoarea BUFCTL_END
• Descriptori de obiecte
• Interni - ţinuţi în slab
• Externi - ţinuţi în cache-urile generale

“Colorarea” slab-ului

Gestiunea memoriei virtuale

• Memoria virtuală este folosită
• în user-space
• în kernel-space
• Alocarea unei zone de memorie în spaţiul de adresă (kernel sau user) implică
• alocarea unei pagini fizice
• alocarea unei zone din spaţiul de adresă
• în tabelele de pagini
• în structuri interne, menţinute de sistemul de operare

Descrierea spaţiului de adresă

Descriptor

spaţiu de adresă

Descriptor

zonă

Descriptor

zonă

Descriptor

zonă

Descriptor

zonă

Descriptor

zonă

Descriptor

zonă

Tabela

de

pagini

Descrierea spaţiului de adresă (2)

• Tabela de pagini este folosită
• de procesor  (CISC)
• de nucleu - căutare pagină şi adaugare în TLB (RISC)
• Descriptorul spaţiului de adresă este folosit de sistemul de operare pentru a menţine informaţii mai high level
• Fiecare descriptor de zonă specifică dacă zona este mapată peste un fişier, este mapată read-only, este mapată copy-on-write, etc.

Alocarea de memorie virtuală

1. Căutarea unei zone libere în descriptorul spaţiului de adresă
2. Alocarea de pagini fizice pentru descriptorul zonei
3. Inserarea în descriptorul spaţiului de adresă a descriptorului zonei
4. Alocarea de pagini fizice pentru tabelele de pagini
5. Iniţializarea tabelei de pagini astfel încât să indice către zona alocată
6. Alocarea la cerere de pagini fizice pentru zona alocată (şi eventual pentru noi tabele de pagină)

Dezalocarea de memorie virtuală

1. Ştergerea descriptorului zonei din descriptorul spaţiului de adresă
2. Eliberarea paginii fizice asociată cu descriptorul zonei
3. Invalidarea tuturor întrarilor din tabelele de pagini asociate cu zona de dealocat
4. Invalidarea TLB-ului pentru zona delocată
5. Eliberarea paginilor asociate cu tabelele de pagini construite pentru zona dealocată

Gestiunea memorie virtuale în Linux

• În kernel-space
• pentru apeluri vmalloc
• descriptorul de zonă: struct vm_struct
• descriptorul spaţiului de adresă: listă simplu înlănţuită de descriptori de zonă
• În user-space
• descriptorul de zonă: struct vm_area_struct
• descriptorul spaţiului de adresă: arbore red-black

Tratarea page fault-urilor în Linux

Evacuarea paginilor în Linux

• Algoritm de tip LRU
• se menţin doua liste: cu paginile active şi cu paginile inactive
• atunci când sistemul are nevoie de pagini, se eliberează pagini, în ordine, din:
• diversele cache-uri: buffer cache, dcache, icache
• lista de pagini inactive
• lista de pagini active
• kswapd
• kernel thread care evacuează paginile
• este activat atunci când numărul de pagini libere scade sub o limită

Întrebări

?