Optimizari ale Memoriei Loa la Nivelul Memoriei Virtuale

În orice moment al timpului, în computer execută mai multe procese, fiecare cu propria adresă spațiu. Ar fi prea costisitor să se aloce o valoare de full-adresa-spațiu de memorie pentru fiecare

proces, în special deoarece multe procese utilizează numai o mică parte a adresei-spațiu. Prin urmare, trebuie să existe un mijloc de a împărtăși o cantitate mai mică de memorie fizică în rândul mai multor procese. O modalitate de a face acest lucru, memoria virtuală, împarte memoria fizică în blocuri și le alocă in procese diferite. Inerente într-o astfel de abordare trebuie să fie un system de protecție care restrânge un proces de blocuri aparținând numai la acest proces. Cele mai multe forme de memorie virtuală reduc, de asemenea, timpul pentru pornirea unui program, deoarece nu tot codul și datele trebuie să fie în memoria fizică înainte ca programul sapoata incepe.

Programatorii impart programele in bucăți, apoi trebuie identificate piesele care se exclude reciporc, și timpul executării, trebuie încărcate sau descărcate suprapunerile din cadrul programului. Programatorul asigura că niciodată nu a încercat programul pentru a accesa mai multă memorie fizică principală decât a fost în calculator, și că suprapunerea corectă a fost încărcat la timpul cuvenit. După cum bine ne putem imagina, această responsabilitate erodateaza productivitatea programatorului. Memoria virtuala a fost inventata pentru a facilita sarcinile programatorilor si pentru a-i scapa de aceasta povara; în mod automat gestionează cele două niveluri ierarhice ale memoriei, reprezentata de memoria principala și de stocarea secundara. Memoria virtuală este o interacțiune eleganta de excepții de hardware, translatare a adreselor hardware, a memoriei principale, a fișierelor de pe disc si software-ul de kernel, care oferă fiecărui proces un spatiu mare, uniform si privat de adrese. Folosindu-se de un mecanism curat, memoria virtuală oferă trei capacități importante:

1. Folosește eficient memoria principală prin tratarea ei ca un cache pentru un spațiu de adrese stocate pe disc, păstrând numai zonele active în memoria principală, și transferarea datelor înainte și înapoi între disc și memorie, după cum este necesar.

2. Simplifică gestionarea memoriei prin furnizarea unui spatiu de adresare uniform catre fiecare proces.

3. Protejează spațiul de adresare al fiecărui proces de corupție prin alte procedee/procese.

In poza de mai jos se poate vedea cum arată un spatiu de adresare virtual cu 4 pagini in care 3 pagini se gasesc in memoria principală și una este pe discul fizic.

Memoria virtuală reprezinta una dintre ideile excelente dintr-un sistem de calcul. Un motiv important pentru succesul său este că funcționează tăcere și în mod automat, fară a fi nevoie de intervenția programatorului. De ce ar trebui un programator sa o ințeleagă, dacă funcționează atât de bine în spatele scenei? Există mai multe motive.

•Memoria virtulă este esențială. Pătrunde în toate nivelurile unui sistem informatic, unde joacă roluri cheie în proiectarea unor excepții, asamblori, linker-e, încărcătoare, obiecte partajate, fișiere și procese. Înțelegerea memoriei virtuale va ajuta la o mai bună intelegere a modului în care funcționează un sistem.

•Memoria virtuală este puternică. Oferă aplicațiilor capabilități puternice de a creea și a ”distruge” bucăți de memorie, mapa bucăți de memorie pentru a porționa fișierele pe disc și pentru a impărți memoria cu alte procese. De exemplu, știați că puteți încărca continutul unui fișier în memorie fară a face orice copiere explicită? Înțelegerea memoriei va ajuta la valorificarea puternicelor capabilități în aplicațiile pe care le puteți crea.

•Memoria virtulă este periculoasă. Aplicațiile interacționează cu memoria virtulă de ficare dată când se face o referință către o variabilă, se face un apel către un pachet de alocare dinamică cum este funcția malloc. Dacă memoria virtuală este folosită într-un mod necorespunzător, aplicațiile pot suferi de erori legate de memorie. De exemplu, dacă într-un program este un pointer eronat, acesta poate da o eroare de tipul ” Segmentation fault” sau ”Protection fault”, poate rula ore întregi până sa dea o eroare sau în cel mai rău caz poate să ruleze până la sfârșit și să dea rezultate incorecte. Înțelegerea memoriei virtule și pachetele de alocare, cum este malloc, poate ajuta prin a împiedica să se producă astfel de erori. [HaBr 01] Adresearea fizică și cea virtuală a memoria principală a unui sistem informatic se face după considerentul că memoria este organizată sub forma unui vector de M celule învecinate, fiecare având mărimea unui byte.Fiecare octet are o adresă fizică unică. Primul octet are adresa 0, următorul octet adresa 1, al treilea octet are adresa 2, și așa mai departe. Având în vedere această organizare simplă, cel mai firesc mod pentru procesor de a utiliza memoria este de a folosi adresele fizice. Această abordare se numește adresare fizică

Figura de mai sus prezinta un exemplu de adresare fizică în contextul în care o instrucțiune de încărcare care citește cuvântul incepand de la adresa fizică. Atunci când procesorul CPU execută instrucțiunea de încărcare, acesta generează efectiv o adresă fizică și o transfera catre memoria principala peste magistrala de memorie. Memoria principală preia cuvântul de patru octeți, începând de la adresă fizică 4 și revine la procesorul CPU, pe care il stochează într-un registru. O altă problematică a memoriei virtuale este legată de spațiile de adresare. Calculatoarele timpurii utilizau adresarea fizică si sisteme precum: procesoare de semnal digital, micorprocesoarele încorporate si supercalculatoarele Cray continuă sa facă acest lucru si in prezent. Cu toate acestea, procesoarele moderne concepute pentru uz general, folosesc o formă de adresare cunoscută sub numele de adresare virtuală. Cu adresarea virtuală, procesorul CPU accesează memoria principală prin generarea unei adrese virtuale (AV) care, înainte de a fi trimisa la memorie, este convertita la adresa fizică corespunzătoare. Sarcina de a converti o adresa virtuală intr-una fizică, este numita translatarea adresei(address translation). Aceasta necesita o colaborare strânsa intre hardware-ul procesorului CPU si sistemul de operare. Hardware-ul din cadrul chip-ului CPU, numit Unitatea de Management a Memoriei (UMM), transpune adrese virtuale foarte rapid folosind un tabel de cautare, stocat in memoria principale si al carui continut este gestionat de sistemul de operare. În figura de mai jos putem observa un sistem care folosește adresarea virtuală.

Un spațiu de adresare este un set ordonat de adrese nenegative intregi. {0,1,2,… } Daca numerele intregi din spatiul de adrese sunt consecutive, atunci putem spune ca este un spatiu de adrese lineare. Pentru a simplifica discuția, vom presupune întotdeauna spații de adrese liniare. Într-un sistem cu o memorie virtuală, procesorul CPU generează adrese virtuale dintr-un spațiu adresa N = 2n adrese, numit spațiu de adrese virtuale: {0,1,2,…, N-1}

Dimensiunea unui spațiu de adresă este caracterizată prin numărul de biți care sunt necesari pentru a reprezenta cea mai mare adresa. De exemplu, un spațiu de adrese virtuale cu N = 2 n adrese se numește un spațiu de adrese de n-biți. Sistemele moderne de regulă aloca fie 32 de biți sau 64-bit spatii de adrese virtuale.Un sistem are de asemenea un spațiu de adrese fizice care corespunde bitului M/bytes M de memorie fizică în sistem: {0,1,2,…, M-1} M nu trebuie sa fie la puterea a 2-a, dar pentru a simplifica discutia, vom preupune ca M = 2 m Conceptul unui spațiu de adresă este important deoarece aceasta face o distincție clara între obiecte de date (bytes) și atributele lor (adrese). După ce vom recunoaște această distincție, atunci putem generaliza și să permită fiecărui obiect de date sa aiba mai multe adrese independente, fiecare aleasa dintr-o altă adresă spatiu. Aceasta este ideea de bază a memoriei virtuale. Fiecare octet de memorie principală are o adresa virtuală aleasa din spatiul de adrese virtuale, precum și o adresă fizică aleasa din spațiul de adresă fizică. Memoria virtulă poate să fie folosită în mai multe scopuri: de exemplu se poate folosi ca un instrument în folosirea cache-urilor, ca un instrument in managementul memorie sau ca un instrument pentru protecția memorie. În continuare se va prezenta pe rând fiecare din aceate variante pentru a se putea observa cum functionează și ce aport are fiecare in optimizarea ierarhiei de memorie.

Pornim de la primul punct de mai sus, adică cel care specifică faptul ca memoria virtuală poate să fie folosită ca un instrument în folosirea cache-urilor. Conceptual, o memorie virtuală este organizata ca o serie de N celule învecinate byte-sized cell stocate pe disc. Fiecare octet are o adresă virtuala unica care servește ca un index în matrice. Conținutul de matricea de pe disc sunt cache în memoria principală. Ca și în orice alte cache în ierarhia de memorie, datele de pe disc (nivelul inferior) este împărțit în blocuri care servesc drept unități de transfer între discul și memoria principală (nivelul superior). Sistemele de memorie virtuală rezolva această problema prin partiționarea memoriei virtuală în blocuri de dimensiuni fixe numite pagini virtuale (PVs). Fiecare pagină virtuală este P = 2p biti în dimensiune. În mod similar, memoria fizică este împărțită în pagini fizice (PFS), de asemenea, P octeți în dimensiune. (Paginile fizice sunt, de asemenea, menționate în continuare ca și cadre pagină).

În orice moment, un set de pagini virtuale este împărțit în trei subgrupuri disjuncte:

•Unallocated (Nealocate): Pagini care nu au fost încă alocate (sau create) de către sistemul de memorie virtulă. Blocurile nealocate nu au niciun fel de date asociate cu ele, și astfel, nu ocupă nici un spațiu pe disc.

•Cached (In cache): pagini alocate care sunt în prezent cuprinse în memoria fizică.

•Uncached: pagini alocate care nu sunt în prezent cuprinse în memoria fizic

Exemplul din figura arată o memorie virtuală mica cu 8 pagini virtuale. Pagini virtuale 0 și 3 nu au fost inca alocate, astfel, nu există încă pe disc. Pagini virtuale 1, 4, și 6 sunt în cache/cuprinse în memoria fizică. Paginile 2, 3, 5 și 7 sunt alocate, dar nu sunt cuprinse inca/dar nu sunt inca cache in memoria principala.

Pentru putea păstra cache-uri diferite în ierarhia de memorie, vom folosi termenul de cache SRAM pentru a aminti cache-ul L1 si L2 între procesorul CPU și memoria principală, și termenul de cache DRAM , care denotă cache-ul sistemului de memorie virtuală care cuprinde pagini virtuale in memoria principala. Poziția cache-ului DRAM în ierarhia de memorie are un impact mare asupra modului în care este organizată. Sa ne reamintim faptul că un DRAM este de aproximativ 10 ori mai lent decât un SRAM și acel disc este de aproximativ 100.000 ori mai lent decât un DRAM. Astfel, miss-urile din cache-ul DRAM sunt foarte scumpe în comparație cu cele ale în cache-ului SRAM. Acest lucru se intampla, deoarece miss-urile cache-ului DRAM sunt de pe disc, in timp ce miss-urile cache-ului SRAM sunt servite de la DRAM bazate pe memoria principala. În plus, costul de a citi primul octet de pe un sector de disc este de aproximativ 100.000 ori mai lent decât daca citim in mod succesiv octeti din acest sector. octeți succesive în acest sector. Concluzia este că organizarea cache-ului DRAM este condusă în totalitate de costurile enorme de miss-uri/

Datorită gradului ridicat al penalizarii in cazul miss-ului si greutatii accesarii primului octet, paginile virtuale au tendinta de a avea dimensiuni mari, plecand de la 4 pana la 8 Kb. Datorită gradului ridicat al penalizarii in cazul miss-ului, cache-urile DRAM sunt complet asociative, astfel, orice pagina virtuală poate fi plasata în orice pagină fizică. Politica de înlocuire a miss- urilor presupune de asemenea o deosebita importanta, deoarece pedeapsa asociata cu inlocuirea paginii virtual gresss-uri/

Datorită gradului ridicat al penalizarii in cazul miss-ului si greutatii accesarii primului octet, paginile virtuale au tendinta de a avea dimensiuni mari, plecand de la 4 pana la 8 Kb. Datorită gradului ridicat al penalizarii in cazul miss-ului, cache-urile DRAM sunt complet asociative, astfel, orice pagina virtuală poate fi plasata în orice pagină fizică. Politica de înlocuire a miss- urilor presupune de asemenea o deosebita importanta, deoarece pedeapsa asociata cu inlocuirea paginii virtual gresite este ridicata. Astfel, sistemele de operare utilizeaza algoritmi de inlocuire mai sofisticati pentru cache-ul DRAM, decat foloseste hardware-ul pentru cache-ul SRAM. (Acesti algoritmi de în locuire sunt dincolo de domeniul nostru de aplicare) În cele din urmă, din cauza timpului mare de accesare al discului, cache-urile DRAM folosesc intotdeauna write-back in loc write-through.

Ca în cazul oricărui cache, sistemul de memorie virtuală trebuie să aibă un mod de a determina dacă o pagină virtuală este stocată undeva în cache DRAM. Dacă da, sistemul trebuie să determine ce pagină fizica este în cache. Dacă există un miss, sistemul trebuie să se determine unde este stocata pe disc pagina virtuala, selectați o pagină de victimă în memorie fizică, și copiati pagina virtuala de pe disc pe DRAM, înlocuind pagina victima.

Aceste capacități sunt furnizate printr-o combinație a sistemului software, a tranzitarii sdresei hardware in MMU (Unitatea de Management a Memorie), si o structura de date stocata in memoria fizica, cunoscuta sun numele de page tabel care mapeaza paginile virtuale in pagini fizice. Translatarea adresei hardware citeste page tabel(pagină de tabel) de fiecare data cand il convertste o adresa virtuala intr-o adresa fizica. [HaBr 01]

Figura prezinta organizarea de bază a unui tabel de paginare. Un tabel pagină este o serie de intrări în tabelul de paginare (IPT). Fiecare pagină din spațiul de adrese virtuale are o IPT la un offset fix în tabelul pagină. Pentru scopurile noastre, vom presupune că fiecare IPT este alcatuit dintr-un octet valid și un câmp adresă de n biți.

Octetul valid indica indică dacă pagina virtuala este stocata în memoria cache-ului DRAM. Daca bitul valid este setat, address field indică începutul paginii fizice corespunzătoare din cadrul DRAM, unde este cuprinsa pagina virtuala. În cazul în care octetul valid nu este setat, o adresă nulă indică faptul că pagina virtuală nu a fost încă alocata. În caz contrar, adresa indica spre inceputul paginii virtuale de pe disc. Luând în considerare ceea ce se întâmplă când procesorul citește un cuvânt de memorie virtuală conținut în PV 2, care este stocată în cache-ul DRAM( pentru acest exemplu vom folosi figura de mai jos) . Folosind o anumită tehnica vom descrie în detaliu într-un paragraf ulterior, translatarea de adresare, hardware-ul care utilizează adresa virtuala ca un index pentru a localiza ITP 2 și să o citeasca din memorie. Din moment ce octetul valid este stabilit, adresa de translatare hardware stie ca PV2 este cuprins in memorie. Deci, foloseste adresa memoriei fizice in ITP (care arata inspre inceputul paginii cache in PF0) pentru a realiza adresa fizica a cuvantului.

Exceptia page fault invocă o excepție in kernel, care selectează o pagină victimă, în cazul acesta PV 4 stocat în PF 3. Dacă PV 4 a fost modificată, kernel-ul le copiaza inapoi pe disc. În oricare dintre cazuri, kernel-ul modifică intrarea tabel pagina pentru PV 4, pentru evidentia faptul ca PV 4 nu mai este în cuprins in memoria principala.

In continuare, kernel-ul copiaza PV # de pe disc pe PF 3 in memorie, si apoi se intoaece. În cazul în care excepția se întoarce, acesta restartează instructiunea faulting, care retransmite adresa virtuala faulting la adresa hardware de tranzitare. Dar acum, PV3 este cuprins în memoria principală, și pagina readusa este tratată normal de către hardware-ul de translatare a adreselor, dupa cum se vede in figura se prezinta starea exemplului de tabel de paginare dupa page fault; excepția de page fault selectează PV 4 ca victimă și o înlocuiește cu o copie a PV 3 de pe disc.

După ce excepția de page fault repornește instrucțiunea faulting, acesta va citi în mod normal cuvântul din memorie, fără a genera o excepție. Memoria virtuala a fost inventata la începutul anilor 1960, cu mult înainte de lărgirea decalajului CPU- și cache-urilor pe bază de SRAM. Ca urmare, sistemele virtuale de memorie utilizează o terminologie diferită de pe cache-ul SRAM, chiar daca multe dintre ideile sunt similare. În limbajul memorie virtuală, în care blocurile sunt cunoscute ca pagini.

Activitatea de a transfera o pagină între disc și memorie este cunoscuta sub numele de swaPFing sau de paginare. Paginile sunt schimbate( paged in) de pe disc la DRAM, și interschimbate afară (paged out) de pe DRAM pe disc. Strategia de așteptare până în ultimul moment pentru a schimba într-o pagină, atunci când apare un miss, fiind cunoscut ca cererea de paginare. Alte abordări, cum ar fi încercarea de a prezice miss-uri și în paginile de swap înainte sa se faca referire la acestea, sunt posibile. Cu toate acestea, toate sistemele moderne utilizeaza paginarea.

Atunci când se învață despre ideea de memorie virtuală, prima impresie este de multe ori că aceasta trebuie să se fie foarte eficienta. Având în vedere miss-urile mari, ne facem griji ca paginarea va reduce din performanta programului. În practică, memoria virtuală funcționează destul de bine din cauza localizării. [HaBr 01]

Deși numărul total de pagini la care fac referire programele în timpul unei intregi rulari ar putea depăși mărimea totală de memorie fizică, principiul de localitate promite că, în orice punct dintr-un momentul vor avea tendința de a lucra la un set mai mic de pagini active, cunoscute sub numele de setul de lucru sau un set de rezident. După un overhead inițial, unde setul de lucru este paginat în memorie, trimiterile ulterioare la setul de rezultate de lucru in hit-uri, fără suplimentare disc de trafic.

Atâta timp cât programele noastre au localizare temporală, sistemele virtuale de memorie funcționează destul de bine. Dar desigur, nu toate programele prezintă o bună localizare temporală. Dacă mărimea de lucru stabilită depășește mărimea fizică de memorie, atunci programul poate produce o situație nefericită cunoscută sub numele de thrashing, caz în care paginile sunt transferate in mod continuu. Deși, deobicei, memoriea virtuală este eficientă, dacă performanța unui program încetinește până în punctul de a se opri , programatorul va lua în considerare posibilitatea că este vorba de thrashing. [HaBr 01]

În continuare ne vom referi la memoria virtuală ca la o modalitate de management al memoriei. Interesant,cum unele sisteme timpurii de alertă, cum ar fi DEC PDP-11/70 au susținut un spațiu de adrese virtuale mai mic decât cel al memoriei fizice. Totuși, memorie virtuală era încă un mecanism util, deoarece simplificata foarte mult de gestionarea memoriei și a oferit un mod natural de a proteja memoria. Pentru acest punct am asumat un singur tabel de paginare care mapează un singur spațiu virtual de adrese pentru cea fizică. De fapt, sistemele de operare furnizează un tabel de pagină separat, și, astfel, un spațiu de adresă virtuală pentru fiecare proces. Figura prezintă ideea de bază. Tabelul de paginare pentru proces mapează PV la 1 la PF 2 și PV 2 la PF 7. În mod similar, tabelul pagină pentru proces mapează PV 1 la PF 7 și PV 2 la PF 10.

Se observă că mai multe pagini virtuale pot fi mapate la aceeași pagina fizică partajată.

Modul în care memoria virtuală furnizează spați de sdresă separate proceselor. Operația păstrează o pagină tabel separată pentru fiecare proces din cadrul sistemului. Combinațiea mapării cerute și spații de adresă virtuală separate au un impact profund asupra modului în care este utilizată și gestionată memoria într-un sistem. În special, memoria virtuală simplifica linking-ul și loading-ul schimbul de cod și date și alocă memorie aplicațiilor.

Un spațiu de adrese separate permite fiecărui proces să utilizeze același format de bază pentru propria imagine de memorie, indiferent de locul în care codul și datele sunt alocate efectiv în cadrul memoriei fizice. Ca un exemplu, fiecare proces Linux folosește formatul prezentat în figura de mai jos.

Secțiunea de text începe întotdeauna la adresa virtuală 0x08048000, stiva crește mereu în jos de la adresa 0xbfffffff, codul unei librarii partajeye începe întotdeauna la adresa 0x40000000, și codul sistemului de operare și a datelor începe întotdeauna la adresa 0xc0000000.

Astfel de uniformitate simplifică in mod considerabil proiectarea și implementarea linkere-lor, permițându-le să producă executabile link-ubile complet care sunt independente față de locația finală a codului și datelor în memoria fizică.

Imaginea memoriei a unui proces Linux. Programele întotdeauna încep la adresa virtuală 0x08048000. Stiva utilicator întotdeauna începe la adresa virtuală 0xbfffffff. Obiectele partajate sunt întotdeauna încărcate în regiune începând de la adresa virtuală 0x40000000. Cu toate acestea, în unele cazuri este de dorit ca procesele să împartă cod și date. De exemplu, fiecare proces trebuie să apeleze același sistem de operare cod kernel și fiecare program C apelează la rutine în librării C standard cum ar fi printf. Decât să includă copii separate ale kerne-lului și librăriile C standard în fiecare proces, sistemul de operare poate face astfel încât mai multe procese să poată împărții o singură copie a acestui cod prin faptul că mapează paginile virtuale corespunzătoare în procese diferite la aceleași pagini fizice.

Memoria virtuală oferă un mecanism simplu pentru alocarea de memorie suplimentară pentru procesele de utilizator. Atunci când un program care rulează într-un proces utilizator este nevoie de spațiu suplimentar (de exemplu, ca urmare a apelării malloc), sistemul de operare alocă un număr corespunzător, k, de paginile virtuale de memorie și le mapează în pagini fizice arbitrare situate oriunde în memoria fizică. Din cauza modului în care tabele pagina funcționează, sistemul de operare nu trebuie să localizeze paginile invecinate de memorie fizică. Paginile pot fi răspândite aleatoriu în memoria fizică. [HaBr 01]

De asemenea, memoria virtuală facilitează încărcarea fișierelor executabile și partajarea obiectelor în cadrul memoriei. Să ne reamintim că secțiunile .text și .data în executabilele ELF sunt învecinate. Pentru a încărca aceste secțiuni într-un proces nou creat, Loader-ul de Linux alocă o bucată învecinată de pagină virtuală la adresa 0x08048000, marcându-le ca fiind invalide (adica, nu sunt cachate), și îndreaptă intrările tabel pagina la locația corespunzătoare, în fișierul obiect. Faptul interesant este că loader-ul nu copiază niciodată toate datele de pe disc în memorie. Datele sunt mapate în mod automat și la cererea sistemului memoriei virtuale prima dată când se face referire la o pagină, fie din partea CPU atunci când preia p instrucțiune, sau de către o instrucțiune de executare atunci când face referire la o memorie locație.

Noțiunea de mapare a unui set de pagini virtuale învecinate într-o locație arbitrară într-un fișier arbitrar, este cunoscută ca maparea memoriei. Pe lângă faptul că memoria virtuală poate să ajute cache-ul să fie mai rapid sau poate să fie folosită pentru managementul memorie, ea mai poate sa fie folosită și ca mod de protecție a memoriei. Orice sistem informatic trebuie să furnizeze mijloacele pentru ca sistemul de operare să poată controla accesul la sistemul de memorie. Un proces de utilizator nu ar trebui să poată să modifice secțiunea de read-only. Acesta nu ar trebui să aibă permisiunea de a citi sau a modifica oricare dintre coduri și structurile de date în kernel. Acesta nu ar trebui să aibă accesul de a citi sau a scrie memoria privată a altor procese. Și nu ar trebui să aibă accesul să modifice orice pagină virtuală care este partajată cu alte procese, decât dacă toate părțile permit în mod explicit acest lucru (prin apeluri explicite inter-procese prin apelarea sistemului de comunicare).

Așa cum s-a văzut, oferind spatii virtuale separate este ușor să se izoleze amintirile private ale diferitelor procese. Dar mecanismului de translatare a adreselor poate fi extins într-un mod natural pentru a furniza un control al accesului mai fin. Având în vedere că hardware-ul de translatare a adreselor citește un IPT, procesorul CPU generează o adresă, de fiecare dată, este simplu să controleze accesul la conținutul unei pagini virtuale prin adăugarea unor biți suplimentari de permisiune la IPT. Figura arată idea generală. [HaBr 01] A

cest exemplu, s-au adăugat trei biți de permisiune pentru fiecare IPT. Bit-ul SUP indică dacă procesele trebuie să ruleze în modul kernel (supervizor) de accesare a paginii. Procesele care rulează în mod kernel pot accesa orice pagină, dar procesele care rulează în modul utilizare pot accesa doar pagini pentru care SUP este 0. Bitii READ și WRITE controlează cititul și scrisul asupra paginii. De exemplu, dacă procesul i rulează în modul utilizator, atunci acre permisiunea sa citească PV 0 și să citească sau să scrie PV

1. Cu toate acestea, nu este permis să acceseze PV

2. În cazul în care o instrucțiune încalcă aceste permisiuni, atunci procesorul CPU declanșează o excepție generală de tipul protection fault care transferă controlul la o excepție în kernel.

2. În cazul în care o instrucțiune încalcă aceste permisiuni, atunci procesorul CPU declanșează o excepție generală de tipul protection fault care transferă controlul la o excepție în kernel.

Celulele Unix raportează această excepție ca ”segmentation fault ". Aceasta sectiune cuprinde bazele translatarii adresei. In mod formal, tranzlatarea adresei reprezinta maparea dintre elementele unui spatiu de adresa virtuala cu N-elemente (VAS) si a unui spariu de adresa fizica cu M-elemente (PAS), MAP: VAS → PAS Ụ Ø

Unde MAP(A) = A` dacă data din spatiul virtual se gasește si in spatiul fizic = Ø dacă data din spatiul virtual nu se gasește in cel fizic

Figura prezinta modul in care MMU utilizează tabelul de paginare pentru a realiza aceasta mapare. Un registru de control in cadrul COU, registrul page table base register (PTBR) arata spre actuala pagina din tabel. Octetul- n al adresei virtule are doua componente: un bit- p virtual page offset (DPV) si un (n-p)-bit virtual page number (NPV). MMU-ul utilizeaza NPV-ul pentru a selecta IPT-ul corespunzator. De exemplu, NPV 0 selecteaza IPT 0, NPV 1 selecteaza NPV 1, asa mai departe. Adresa fizica corespunzatoare reprezinta concatenarea numarului pagina fizice (NPF) de la intrarea pagina tabel si DPV de la adresa virtuala. Observati ca, din momentul in care paginile fizice si virtuale au amandoua P biti, physical page offset (PPO) este identica cu DPV. [HaBr 01]

În figura de mai sus,(a) se prezinta pașii pe care ii percurge hardware-ul CPU in momentul unei page hit.

•Pasul 1: Procesorul generează o adresa virtuala pe care o trimite MMU-ului.

•Pasul 2: MMU-ul genereaza adresa IPT si o solicita de la cache/de la memoria principala.

•Pasul 3: Cache-ul/memoria principala returneaza IPT-ul la MMU.

•Pasul 4: Cache-ul/memoria principala returneaza procesorului datele solicitate.

Spre deosebire de un page hit care esre folosit de catre hardware, utilizarea unei page fault, necesita cooperarea dintre hardware si sistemul de operare kernel(figura b).

•Pasii 1-3: Sunt la fel ca si pasii 1-3 din figura(a).

•Pasul 4: Bitul valid din IPT este 0, astfel MMU-ul declanseaza o exceptie care transfera controlul din CPU la o excepție de tipul in sistemul de operare kernel.

•Pasul 5: Excepția de fault identifica o pagina victima in memoria fizica, si, in cazul in care pagina a fost modificata, o pagineaza pe disc.

•Pasul 6: Excepția de fault pagineaza noua pagina si actualizeaza IPT-ul in memorie.

•Pasul 7: Excepția de fault revine la procesul original, provocand repornirea instrucțiunii de fault. CPU retransmite adresa virtuala ofensatoare la MMU.

Deoarece pagina virtuală este acum cuprinsa în memoria fizică, există un rezultat pozitiv, și după ce MMU efectuează pașii din figura (b), memoria principala returneaza procesorului cuvantul solicitat.

În orice sistem care utilizează atât memoria virtuala, cat și cache-ul SRAM, există problema dacă sa se utilizeze adresele virtuale sau cele fizice pentru a accesa memoria cache. Deși o discuție detaliată a tradeoffs este dincolo de sfera noastra, cele mai multe sisteme oIPTaza pentru abordarea fizica. Abordarea fizica este o abordare simpla pentru ca mai multe procese sa aiba in acelasi timp blocuri in cache si sa partajeze blocuri care apartin aceleiasi pagini virtuale. În plus, cache-ul nu trebuie sa cuprinda aspecte pegate de protectie, deoarece drepturile de acces sunt cuprinse ca fiind parte a procesului de tranzlatarea a adresei.

Figura de mai jos prezinta modul in care un cache adresat in mod fizic poate fi integrat in memoria virtuala.

Ideea pricipala este aceea ca. Translatarea adresei are loc inainte de cache lookup. Se observați că intrările în tabelul de paginare pot fi memorate în cache, la fel ca orice alte date de cuvinte.

Așa cum am văzut si anterior, de fiecare dată când procesorul CPU generează o adresă virtuală, MMU-ul trebuie să se refere la o IPT, pentru a putea translata adresa virtuală intr-o adresa fizică.

În cel mai rău caz, acest lucru necesită o descărcare suplimentara din memorie, la un cost de la zeci la sute de cicluri. În cazul în care IPT este memorat în cache-ul L1, costul se reduce la unul sau două cicluri. Cu toate acestea, multe sisteme încearca să elimine chiar si acest cost, prin faptul ca includ un mic cache de IPTs în MMU, numit translation lookaside buffer (TLB).

Un TLB este un cache mic, adresat virtual, unde fiecare linie deține un bloc format dintr-un singur IPT

Un TLB are de obicei un grad ridicat de asociativitate. Așa cum se arată si figura care urmează, indicele si campurile etichetate care sunt utilizate pentru selecțiea stabilita și potrivirea liniei sunt extrase din numărul paginii virtuale în adresa virtuală

În cazul în care TLB are T=2t seturi, atunci indicele TLB (TLBI) este format din cel putin t biți semnificativi ai NPV, și tag-ul TLB (TLBT) este format din biții rămasi în NPV. [HaBr 01]

Figura de mai sus(a), prezinta pașii implicați atunci când există un rezultat pozitiv TLB (cazul obișnuit). In acest caz, punctul cheie este acela ca toate măsurile de translatare a adreselor sunt efectuate în interiorul on-chip-ul MMU și, prin urmare sunt rapide.

•Pasul 1: CPU generează o adresă virtuale.

•Pasii 2 și 3: MMU preia PTE corespunzătoare din TLB.

•Pasul 4: MMU traanslateaza adresa virtuală la o adresă fizică și o trimite la cache/memoria principală.

•Pasul 5: cache / memoria principala returnează procesorului CPU datele de cuvinte solicitate.

Atunci când există un miss TLB, atunci MMU trebuie să aducă PTE-ul din cache-ul L1, așa cum se arată în figura (b). PTE-ul adus recent este stocat în TLB, eventual suprascriind o intrare deja existenta.

Pentru în acest punct s-a presupus că sistemul utilizează un singur tabel paginare pentru a translata adrese. Dar dacă am avut un spațiu de adrese pe 32 de biți, pagini de 4-KB și un PTE de 4 octeti, atunci am avea nevoie de un page tabel de 4 MB, deja existent in memorie, in orice moment, chiar dacă cererea face referire la doar o mica parte a spatiului adresei virtuale.

Problema este agravată pentru sistemele cu spații de adrese pe 64 de biți. Abordare comună pentru compactarea pagină tabel, este utilizare unei ierarhii de tabeluri de paginare. Ideea este mai ușor de înțeles, cu un exemplu concret. Să presupunem că spațiul de adresa virtuala pe 32 de biți este împărțit în pagini de patru KB, și ca intrările pagina tabel sunt fiecare de patru octeți. Să presupunem, de asemenea, că, în acest moment al timpului, spațiu de adresa virtuala are următoarea formă: primele pagini de memorie de 2K sunt alocate pentru cod și de date, următorii 6K de pagini sunt nealocati, următoarele 1023 de pagini sunt, de asemenea nealocate, și pagina următoare este alocata pentru stiva utilizator. Figura urmataoare arată cum se poate construi o ierarhie de tabele de paginare pe două niveluri pentru acest spațiu de adresa virtuală.

Fiecare PTE la nivelul-1 tabel este responsabil pentru maparea unei sectiuni de 4MB a spatiului de adresa virtuala, unde, fiecare sectiune este alcatuita din 1024 pagini invecinate. De exemplu,PTE 0 mapeaza prima parte, PTE 1 urmatoarea sectiune și așa mai departe. Având în vedere că

spațiul de adrese este de patru GB, 1024 PTEs sunt suficiente pentru a acoperi întregul spațiu.

Dacă fiecare pagină din sectiunea i este nealocată, apoi nivel-1 PTE i este nulă. De exemplu, în

figura de mai sus, sectiunile 2-7 sunt nealocate. Cu toate acestea, dacă cel puțin o pagina din sectiunea i este alocată, apoi nivel-1 PTE I, arata inspre baza unei pagini tabel nivel-2. De exemplu, în figura de mai sus, toate sau porțiuni ale sectiunii 0, 1 și 8 sunt alocate, astfel încât nivelul lor PTEs-1 arata inspre nivelul-2 pagina tabele. Fiecare PTE la un nivel-2 pagina tabel este responsabila pentru maparea unei pagini a memoriei virtuale de 4-KB, la fel ca înainte cand

ne-am uitat la pagina tabele cu un singur nivel. Observați că, cu PTEs de 4-octeti, fiecare nivel-1

și nivel-2 pagina tabel este de 4K octeți, care este de aceeași dimensiune ca o pagină.

Acest sistem reduce cerințele de memorie în două moduri. În primul rând, dacă un PTE în

nivelul-1 tabel, atunci nivelul-2 pagina tabel corespunzător, nici măcar nu trebuie să existe. Acest

lucru reprezintă un potențial semnificativ de economii, deoarece cel mai mult din spatiul de

adresa vitruala de 4-GB pentru un program tipic, este nealocat. În al doilea rând, numai nivelul-1

tabel trebuie să fie în memoria principală, în orice moment. Nivelul-2 pagina tabel, poate fi creat

și mapat in interior si exterior, de catre sistemul MV, deoarece acestea sunt necesare, fapt care

reduce presiunea asupra memoria principală. Numai pentru cele mai utilizate tabele pagina din

nievelul-2, trebuie cuprinse in memoria principala. În figura de mai jos prezinta translatarea

adresei cu o ierarhie nivel-k pagina tabel. Adresa virtuală este împărțit în k VPNs si o VPO.

Fiecare VPN I, 1 ≤ i ≤ K, este un indice într-o pagină tabel la nivel i.

Fiecare PTE într-un tabel nivel-j, 1 ≤ j ≤ K, arata inspre pagina tabrl la nivel j+1. Fiecare PTE într-un tabel de nivel-k conține, fie PPN a unei pagini fizice sau adresa unui bloc de disc. Pentru a construi adresa fizică, MMU trebuie să acceseze PTEs k înainte de a putea determina PPN. Ca și o ierarhie cu un singur nivel, PPO este identic cu VPO.

În continuare vom prezenta un studiu de caz în care avem un sistem din clasa Pentium care rulează în Linux. Figura de mai jos evidențiază sistemul de memorie Pentium. Pentium are o adresa spațiu de 32 de biți (4 GB). Pachetul procesor include cipul procesorului CPU, o memorie unificată cache L2 și un cache bus (backside bus), care le conectează. Cipul CPU conține patru cache-uri diferite: o instrucțiune TLB, date TLB, L1 i-cache și d-L1 cache. TLB-urile sunt adresate virtual. Cache-urile L1 și L2 sunt adresate fizic.

Cipul CPU conține patru cache-uri diferite: o instrucțiune TLB, date TLB, L1 i-cache și d-L1 cache. TLB-urile sunt adresate virtual. Cache-urile L1 și L2 sunt adresate fizic. Toate cache-urile cuprinse de Pentium(inclusiv TLB-urile) sunt seturi de patru căi asociative. Cache-ul TLB de 32-biți intrări pagină tabel. Instrucțiunea TLB cuprinde PTE-urile pentru adresele virtuale generate de unitatea de aducere a instrucțiune. Datele TLB cuprind PTE-urile pentru instrucțiunile virtuale generate de instrucțiuni. Instrucțiunea TLB are 32 de intrări. Datele TLB are 64 intrări. Dimensiunea paginii poate fi configurată in momentul pornirii, fie ca 4 KB sau 4 MB. Linux care rulează pe un Pentium utilizează pagini de 4 KB. Cache-urile L1 și L2 au blocuri de 32-biți. Fiecare cache L1 are o dimensiune de 16 KB și 128 de seturi, fiecare dintre acestea conținând patru linii. Dimensiunea cache-ului L2 poate varia de la un minimum de 128 KB la un maximum de 2 MB. O dimensiune tipică este de 512 KB.

În discuție v-om vorbi și despre optimizari privind translatarea adresei. Am descris un process secvențial în două etape, caz în care MMU (1) transpune adresa virtuală la o adresă fizică, și apoi (2) trece adresa fizică la cache-ul L1. Cu toate acestea, implementări reale hardware folosesc un truc care permite acești pași să fie parțial suprapuși, astfel, accelerând accesul către cache-ul L1.

De exemplu, o adresă virtuală de pe un Pentium cu pagini de 4-KB, are 12 de biți de VPO, acești biți fiind identici cu cei 12 biți de PPO din adresa fizică corespunzătoare. Deoarece setul de patru căi asociative, care adresează fizic cache-ul L1 are 128 seturi și blocuri cache de 32-biți, fiecare adresă fizică are cinci (log2 32) biți de cache offset și șapte (log2 128) biți index. Acești 12 biți se potrivesc exact în VPO-ul unei adrese virtuale, care nu este un accident! Când CPU are nevoie de o adresă virtuală translatată, acesta trimite VPN către MMU și VPO la cache-ul L1. În timp ce MMU solicită o intrare în tabelul de paginare de la TLB, cache-ul L1 este ocupat folosind biți VPO pentru a găsi un set adecvat și pentru a citit cele patru tag-uri și cuvinte de date corespunzătoare din acel set. Când MMU primește PPN înapoi de la TLB, cache-ul este gata să încercea să potrivească PPN-ul la unul din aceste patru tag-uri.

Fiecare sistem Pentium folosește tabelul de paginare pe două niveluri. Nivelul-1 al tabelului, cunoscut sub numele de page directory, conține 1024 32-bit page directory entries (PDEs), fiecare dintre ele indicând la o 1024 level-2 pagina din tabel. Fiecare pagină tabel conține 1024 32-bit page table entries (PTEs), fiecare dintre acestea indicând către o pagină cuprinsă în memoria sau pe disc. Fiecare proces are un director pagină unic și un set de tabele de paginare. În momentul în care rulează un proces Linux, atât directorul de pagini, cât și tabelele de paginare asociate cu paginile alocate sunt rezidente in memorie, chiar dacă arhitectura Pentium permite ca tabelele de paginare să fie schimbate atât în interior, cât și în exterior. Registrul page directory base register (PDBR) arată spre începutul directorului de pagini.

În figura(a) de mai jos este prezintat formatul unui PDE. Când P = 1 (care este întotdeauna cazul cu Linux), câmpul de adresă conține un număr de pagină fizică de 20 biți, care arată înspre începutul tabelului de pagini corespunzător. Să se observe faptul că acest lucru impune o cerință de aliniere de 4 KB pe tabelul paginat.

Figura (b), prezintă formatul unui PTE. [HaBr 01]

Când P = 1, câmpul de adresă conține un număr de pagină fizică de 20 biți, care arată înspre baza unei pagini din cadrul memoriei fizice. Din nou, se impune o aliniere de 4-KB pe paginile fizice. PTE-ul are 2 biți de permisiune, care controlează accesul asupra paginii. Bit-ul R /W determină faptul dacă conținutul unei pagini este read/write sau read/only. Bit-ul U/S, care determină dacă pagina poate fi accesată din modul utilizator, protejează cod și date din cadrul unui sistem de operare kernel de către programele din modul utilizator.

La fel cum MMU translatează fiecare adresă virtuală, de asemenea actualizează alți biți care pot fi utilizați de excepția page fault din kernel. MMU-ul stabilește bitul A, care este cunoscut sub numele de bit dereferinta, de fiecare dată când este accesata o pagină. Kernel-ul poate utiliza bitul de referință pentru a implementa algoritmul de înlocuire al paginii sale. MMU setează bitul D, sau dirty bit, de fiecare dată când se scrie pe pagină. O pagina care a fost modificată, uneori este numită dirty page. The dirty bit spune kernel-ului dacă acesta trebuie sau nu trebuie să scrie-înapoi o pagină victimă, înainte de a o copia într-o pagină de înlocuire. Kernel-ul pot apela o instrucțiune într-un mod-kernel, lucru realizat pentru a goli referinta din dirty bits.

Figura de mai jos arată cum Pentium MMU folosește tabelul de paginare de două nivele pentru a translata o adresă virtuală într-o adresă fizică. Al 20 lea bit VPN este împărțit în două secținui a cîte 10 biți. VPN1 indexează o PDE în directorul care este indicat de PDBR. Adresa din PDE arată înspre baza unui tabel paginat care este indexat de VPN2. PPN din cadrul PTE, indexat de VPN2 este concatenat cu VPO pentru a forma adresa fizică.

În cazul în care PTE este memorat/cached în setul indexat de TLBI (un bit TLB), atunci PPN este extras din PTE memorat și concatenat cu VPO pentru a forma adresa fizică. În cazul în care PTE-ul nu este memorat, dar PDE este memorat (un bit TLB parțial), atunci MMU trebuie să aducă din memorie PTE-ul corespunzătr, înainte de a putea forma adresa fizică. Iar dacă nici

PDE-ul, nici PTE-ul nu este memorat (un miss TLB), în cazul acesta MMU-ul trebuie să aducă atât PDE-ul, cît și PTE-ul din memorie, pentru a forma adresa fizică. Un sistem de memorie virtuală necesită o colaborare strânsă între hardware și software-ul kernel. În timp ce o descriere completă este dincolo de domeniul nostru de aplicare, scopul nostru în această secțiune este de a descrie o cantitate suficientă a sistemului virtual de memorie Linux pentru a vă oferi o idee despre modul în care un sistem de operare real, organizează memoria virtuală si cum stăpânește page fault.

Linux menține un spațiu separat de adrese virtuale pentru fiecare proces al formei prezentată în fig. 10.28. Deja am văzut această imagine de mai multe ori , cu codul său familiar, date, heap, libraria partajată, și stivă de segmente. Acum, dupa ce s-a arătat translatarea adresei, se poate completa cu câteva detalii în plus depre kernel-ul de memorie virtuală care se află de mai sus adresa 0xc0000000.

Kernel-ul de memorie virtuală conține codul și structurilor de date în kernel. Unele regiuni ale kernel-ului de memorie virtuală sunt mapate la paginile fizice care sunt împărtășite de toate procesele. De exemplu, fiecare proces partajează codul kernel-ului si structurile de date globale.

În mod interesant, Linux mapează de asemenea, un set de pagini virtuale învecinate (egal, din punctul de vedere al dimensiunii, cu valoarea totală a DRAM din sistem) cu setul corespunzător de pagini virtuale învecinate. Aceasta oferă kernel-ului un mod convenabil de a accesa orice locație specifică din memoria fizică, de exemplu, atunci când are nevoie să efectueze operațiuni de mapare a memoriei I/O pe dispozitivele care sunt mapate în locații de memorie fizică specifice. Alte regiuni ale kernel-ului de memorie virtuală conține date care diferă pentru fiecare proces. Exemplele includ tabele paginate, stiva pe care o folosește kernel-ul atunci când este executat codul din contextul procesului, precum și diverse structuri de date care urmăresc organizarea actuală a spațiului de adrese virtuale.

Linux organizează memoria virtuală ca pe o colecție de domenii (de asemenea numite segmente). Un domeniu, reprezintă o parte din memoria virtuală existentă (alocată), ale cărei pagini sunt învecinate într-un fel sau altul. De exemplu, segmentul de cod, segmentul de date, heap, segmentul de librărie partajată, și stiva user, toate reprezintă zone distincte. Fiecare pagină virtuală existentă este cuprinsă în unele domenii, iar orice pagină virtuală, care nu face parte din cadrul unui domeniu, nu există, așa că procesul nu poate face referire la ea. Noțiunea de domeniu este importantă deoarece permite spațiului de adrese virtuale să conțină lacune. Kernel-ul nu urmărește paginile virtuale care nu există, și astfel de pagini nu consumă resurse suplimentare din memorie, de pe disc sau din kernel-ul în sine.

Kernel-ul menține o structură distinctă de activitate pentru fiecare proces din sistem. Elementele structurii de activitate, fie conțin sau arată înspre toate informațiile de care kernel-ul are nevoie pentru a rula procesul, (de exemplu, PID-ul, pointer catre stiva utilizator, numele fișierului obiectului executabil și program counter). Una dintre intrările în strucrura de sarcină arată înspre o structură mm, care caracterizează stadiul actual al memoriei virtuale. Cele două domenii de interes pentru noi sunt PGD, care arată înspre o listă de domenii vm, fiecare dintre ele caracterizând o zonă a spațiului actual de adrese virtuale.Când kernel-ul rulează acest proces, stochează pgd-ul în registrul de control PDBR. Domeniul struct al unei zone particulare cuprinde următoarele câmpuri:

1. vm_start: arată înspre începutul domeniului

2. vm_end: arată înspre sfârșitul domeniului

3. vm_prot: descrie permisiunea citire/scriere pentru toate paginile cuprinse în domeniu

4. vm_flags: descrie(printre alte lucruri)dacă pagnile dintr-un domeniu sunt partajate cu alte

procese sau sunt private pentru acest process

Următoarele 2 imagini ne arata cum arata memoria virtuală a unui process Linux și cum Linux-ul își organizează memoria virtuala.

Să presupunem că MMU declanșează page fault în timp ce încearcă să translateze anumite adrese virtuale A. Excepția rezultă într-un transfer al controlului excepțiilor page fault la kernel care efectuează apoi următorii pași:

1. Dacă instructiunea nu este legală se declanșează excepția segmentation fault și procesul este termintat.

2. Este accesul de memorie legal? Cu alte cuvinte, are procesul permisiunea să citească sau să scrie pagini în acest domeniu? De exemplu, page fault rezultatul unei instrucțiuni înmagazinate care încearcă să scrie pe o pagină read-only în segmentul de cod?

Reprezintă page fault rezultatul unui proces care rulează în modul user care încearcă să citească un cuvânt din memoria virtuală kernel? În cazul în care accesul nu este legal, atunci se declanșează o excepție de protecție, care pune capăt procesului.

3. În acest moment, kernel-ul știe că page fault-ul rezultat dintr-o operațiune legală-permisă pe o adresă virtuală legală. Eroarea este rezolvat prin faptul că este selectată o pagină victimă, se schimbă pagina victimă în cazul în care este murdară, se schimbă în pagina nouă se și actualizează tabelul paginat. Când page fault-ul se întoarce, procesorul

CPU repornește instrucțiunea Faulting, care trimite din nou A la MMU. De această dată, MMU translatează A într-un mod normal, fără să genereze page fault. [HaBr 01] Figura de mai jos reprezintă procesul descris mai sus

.

Capitolul 2. Specificațiile aplicației

2.1 Functiile sistemului

În ceea ce privește partea practică a lucrării ”Optimizări ale ierarhiei de memorii la nivelul memoriei virtuale”, ne vom axa asupra unui program care este un alocator de memorie. Un alocator este un program de alocare dinamică a memoriei pe care un alt program il folosește în timpul rulării lui. Crearea unui alocator de memorie nu este ușoară, deoarece pot să intervină o mulțime de factori cum ar fi: alegerea celui mai bun format pentru blocul de memorie, formatul listei pentru eliberarea lui, cum se face plasarea, împărțirea etc. O altă problemă ar fi că programatorii care sunt foarte familiarizați cu limbaje de nivel înalt precum C++ sau Java se lovesc de multe ori de un zid conceptual când se întâlnesc cu un aseamenea mod de programare. Acest tip de aplicații nu se vor găsi in practică rulând de undele singure. Ele sunt considerate sub-sisteme care îndeplinesc un scop precis, acela de a oferi programelor spatial necesar pe toatădurata de funcționare, ca să nu existe niciodată pericolul ca programele să ramână fară memorie sau să intre peste spațiul dedicat altor aplicații.

Cu acest program putem observa ușor cum se face această alocare a memoriei virtuale. Folosind niste fișiere predefinte de test alocatorul va putea face mai multe operații precum de a testa unul sau mai multe fișiere deoadată, oprirea testelor dupa un anumit timp dat de utilizator. La sfarșitul rulării programul returnează pentru fiecare fișier pe care l-a testat anumite informatii legate de timpii de execuție, cate operații s-au efectuat etc. Urmatorul exemplu evidențiaza modul de operare al acestuia.

Programul nostru poate aloca minim un bloc de marimea unui cuvant dublu( 16 bytes), iar lista liberă este organizată sub forma unui liste libere implicite dupa cum se poate observa în imaginea de mai jos:

2.2 Interfata cu utilizatorul

Programul dispune de o interfață intuitivă și destul de ușor de uitilizat. Aceasta este formată dintr-o fereastră în care sunt plasate toate butoanele de care utilizatorul are nevoie. Pe lângă aceastea semai găsește și fereastra în care sunt returnate rezultatele din urma utilizării programului în diferitemoduri.În imaginea de mai jos se poate observa fereastra principală cu toate componentele ei: butoane detipul check box, fiindcă se pot alege mai multe operații pentru o singură rulare; casetele unde sepot introduce opțiunile pentru operațiile care beneficiază de ele; fereastra unde se vor afișarezultatele și butoanele de run, pentru rularea aplicație și cel de help.

În momentul apăsării butonului de help se va deschide o nouă fereastră în care sunt explicitate operațiile și opțiunile aferente acestora. Figura de mai sus prezintă fereastra pricipală a programului după rularea acestuia cu una din operațiile posibile. În aceasta se poate observa rezultatul dat de program în urma folosirii de către acesta a fișierelor de test. Asupra rezultatului se va reveni într-un capitol următor unde va fi analizată componeta acestuia și se va explica fiecare informație relevantă pentru utilizator.

Datorită faptul că interfața grafică prezintă un grad mai scăzut de complexitate, considerăm că o atenție mai riguroasă trebuie acordată unor anumite funcții ale sistemului.

Capitolul 3. Proiectarea aplicației

3.1 Descrierea aplicației

În acest capitol se va prezenta mai în detaliu aplicația, împreună cu câteva din funcțiile de bază ale acesteia. Alocatorul de memorie este un program care aloca memorie într-un mod dinamic altor aplicații.

Din imaginea următoare se poate vedea poziția acestuia într-o ierahie, unde cea mai înaltă poziție o reprezintă aplicația, iar la bază se afla memoria. Vom folosi această aplicație pentru a testa și vedea cum se aloca și eliberează memoria.

Aplicația este un alocator de memorie care este implementat într-o manieră mai simplă. El se bazează pe o listă liberă implicită. În acest caz ne interesează dacă pentru fiecare bloc aveam lungimea alocată deja. Dacă s-ar folosi două cuvinte ca să stocăm imformatia s-ar face risipă de spațiu. În mod normal dacă blocurile de memorie sunt aliniate biții mai puțini semnificativi din adrese sunt tot timpul 0. Când folosim o listă implicită în loc de a stoca tot timpul biți 0, aceștia se vor primi câte un flag pentru cazul în care sunt alocați sau liberi.

3.2 Descrierea componentelor

Alocatorul folosește un model al unui sistem de memorie astfel încât să poată fi rulat fară să interfereze cu pachetul malloc care există deja. Acesta exportă 3 funcții de bază care să poată să fie folosite de către programator: mm_init (void), mm_malloc (size_t size) și mm_free (void *bp).Funcția mem_init modelează memoria virtuală într-un heap, care este un vector aliniat de bytes de mărimea unui cuvânt dublu.

void mem_init(int size)

{

mem_start_brk = (void *)Malloc(size); /* modelează memoria virtuală liberă*/

mem_brk = mem_start_brk; /* heap –ul este inițial gol */

mem_max_addr = mem_start_brk + size; /* adresa maximă de memorie virtuală pentru

heap */

}

Bytes dintre mem_start_brk și mem_brk reprezintă memoria virtulă alocată, iar cei de după mem_brk reprezintă memoria liberă.

Funcția mm_init inițializează alocatorul și returnează 0 în caz de succes și -1 in caz de eșec. int mm_init(void)

{

/* creaza heap-ul initial gol */

if ((heap_listp = mem_sbrk(4*WSIZE)) == NULL)

return -1;

PUT(heap_listp, 0); /* alignment padding */

PUT(heap_listp+WSIZE, PACK(OVERHEAD, 1)); /* header-ul din prolog */

PUT(heap_listp+DSIZE, PACK(OVERHEAD, 1)); /* footer-ul din prolog*/

PUT(heap_listp+WSIZE+DSIZE, PACK(0, 1)); /* header-ul din epilog */

heap_listp += DSIZE;

/* Exstinde heap-ul gol cu un bloc de marimea CHUNKSIZE bytes*/

if (extend_heap(CHUNKSIZE/WSIZE) == NULL)

return -1;

return 0;

}

Funcția mm_init preia 4 cuvinte din memoria sistemului și le inițializează ca să creeze cu ele lista goală. După preluarea cuvintelor mm_init apelează funcția extended_heap care extinde heap-ul cu un număr de bytes dat de CHUNKSIZE creând astfel lista inițială liberă. În acest punct programul este inițializat și gata să aloce sau să elibereze spațiu pentru aplicații.

Funcția extende_heap este folosită în 2 circumstanțe: 1) când se face inițializarea heap-ului și 2) când funcția mm_malloc nu poate să găsească un spațiu bun.

Ca să mențină aliniamentul funcția extende_heap aduna spațial necesar din 2 cuvinte apropiate (8 bytes) și apoi cere spațiu suplimentar pentru heap de la memoria sistemului.

Un program care are nevoie de un bloc de memorie de o anumită mărime îl va cere apelând funcția mm_malloc din cadru alocatorului. De precizat că funcția mm_malloc folosește aceiași interfață și semantică ca și cea din pachetul de bază standard malloc. După ce au fost verificate cererile precedente, alocatorul ia un bloc de memorie și îl ajustează ca să facă loc pentru header și footer, și să satisfacă aliniamentul de cuvânt dublu cerut. Blocul minim cerut este de 16 bytes: 8 bytes care satisfac aliniamentul cerut (DSIZE) și ceilalți 8 pentru header și footer (OVERHEAD). Pentru cereri de peste 8 bytes regula este să se adune în OVERHEAD și după care să se mărească sau să se micșoreze la cel mai apropiat multiplu de 8(DSIZE). După ce alocatorul a făcut aceste operații va cauta în lista goală pentru un block care satisface cerințele. Dacă s-a găsit un loc, programul va plasa blocul și opțional va împărții excesul de spațiu, iar apoi va returna adresa noului bloc alocat. Pentru cazul în care nu s-a găsit un loc, se va extinde heap-ul cu un bloc nou, se va plasa blocul în zona nouă create, opțional se va împărți blocul. Se va returna adresa noului bloc alocat.

void *mm_malloc(size_t size)

{

size_t asize; /* ajusteaza marimea blocului */

size_t extendsize; /* marimea cu care trebuie extin heap-ul in cazul in care nu corespunde

*/

char *bp;

/* ignora cererile superioare */

if (size <= 0)

return NULL;

/* ajusteaza marimea blocului ca sa fie inclus overhead-ul si aliniamentul cerut */

if (size <= DSIZE)

asize = DSIZE + OVERHEAD;

else

asize = DSIZE * ((size + (OVERHEAD) + (DSIZE-1)) / DSIZE);

/* cauta in lista goala dupa un loc bun */

if ((bp = find_fit(asize)) != NULL) {

place(bp, asize);

return bp;

}

/* nu s-a gasit loc, se va mai cere memorie si dupa aceea se plaseaza */

extendsize = MAX(asize,CHUNKSIZE);

if ((bp = extend_heap(extendsize/WSIZE)) == NULL)

return NULL;

place(bp, asize);

return bp;

}

Pentru a elibera un spațiu ocupat de memorie se folosește funcția mm_free, care eliberează blocul respective și apoi unește spațiile adiacente libere folosindu-se de tag-urile de granițe. De precizat că funcția mm_free folosește aceiași interfața și semantică ca și cea din pachetul de bază standard malloc.

void mm_free(void *bp)

{

size_t size = GET_SIZE(HDRP(bp));

PUT(HDRP(bp), PACK(size, 0));

PUT(FTRP(bp), PACK(size, 0));

coalesce(bp);

}

static void *coalesce(void *bp)

{

size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));

size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));

size_t size = GET_SIZE(HDRP(bp));

if (prev_alloc && next_alloc) { /* Caz 1 */

return bp;

}

else if (prev_alloc && !next_alloc) { /* Caz 2 */

size += GET_SIZE(HDRP(NEXT_BLKP(bp)));

PUT(HDRP(bp), PACK(size, 0));

PUT(FTRP(bp), PACK(size,0));

return(bp);

}

else if (!prev_alloc && next_alloc) { /* Caz 3 */

size += GET_SIZE(HDRP(PREV_BLKP(bp)));

PUT(FTRP(bp), PACK(size, 0));

PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));

return(PREV_BLKP(bp));

}

else { /* Caz 4 */

size += GET_SIZE(HDRP(PREV_BLKP(bp))) +

GET_SIZE(FTRP(NEXT_BLKP(bp)));

PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));

PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));

return(PREV_BLKP(bp));

}

}

Capitolul 4. Implementarea aplicatiei

4.1 Mediul de lucru utilizat

În realizarea acestei aplicații au intrat 2 limbaje de programare diferite. Acestea sunt limbajul de nivel jos C și limbajul de nivel înalt JAVA. Limajul de nivel înalt JAVA a fost folosit pentru realizarea interfeței grafice a aplicației. În acest scop s-a folosit mediul de dezvoltare NetBeans. Acest mediu, de tipul open-source, este ușor de folosit pentru utilizator, având tot ce trebuie pentru că un dezvoltator să poate să creeze aplicații pentru platform java, C/C++, PHP, JavaScript etc. Următoarele poze (a, b) arata interfața programului NetBeans, prima fii cum meniul de selecție al programului, în care dezvoltatorul își alege ce tip de proiect vrea să creeze, iar în cea de a 2-a poză se poate vedea cum arată un proiect deschis pentru putea crea tipul de interfața pe care îl are și programul cuprins.

În imaginea (b) se pot observa deschise pentru design o fereastră în care s-au adaugat niște butoane și obiecte de tipul textbox. Acestea pot fi gasite cu usurintă în partea din dreapta, în secțiunea palette. Pe lângă se mai pot găsi si alte elemente constructive venite in ajutorul dezvoltatorului.

4.2 Descrierea generală a implementării

Atât codul de C cât și partea vizuală a programului au fost realizate sub sistemul de operare Linux UBUNTU 9.10. Acesta este rulat de pe o mașină virtuală. Pentru partea de programare în C s-au folosit un editor de text, bibliotecile standard de Linux și compilatorul gcc (oferit tot de sistemul de operare Linux). Bibliotecile de Linux folosite în acest program sunt:

Unistd.H; Sys/mman.H; Sys/time.H; Sys/types.H; Sys/socket. H, etc.

Implementarea în C nu a pus probleme foarte mari. Partea care nu a fost luată în considerare la începutul implementării a fost legată de interfață grafică. Pe parcusul dezvoltării proiectul s-a pus problema unei interfețe grafice și a nu lăsa programul să fie rulat din consola de Linux.

Pe lângă faptul că, acum în varianta finală programul dispune și de o interfață grafică el mai poate fi rulat și din consola de Linux.

În momentul deciderii asupra unei interfețe grafice s-a pus problema unei intervenții minore asupra programul gata termintat. Astfel s-a ales folosirea unei interfețe de tipul Java Application. După ce s-a creat un proiect nou, în fereastra de dialog au fost adăugate 7 butoane de tipul check box, 5 ferestre de tipul TextField, 2 butoane și un TextArea pentru a putea afișa rezultatele programului. Butoanele operațiilor de testare care se pot face au fost alese în mod special de tipul check box, deoarece la o singură rulare pot fi selectate mai operații (depinde doar de dorința utilizatorului). Operațiile care primesc și parametru au în dreptul lor ferestrele de tip TextField pentru a putea fi introduși parametrii corespunzători.

Cele 2 butoane simple au roluri foarte bine definite. Unul din ele deschide fereastra de help a aplicației, iar celălalt rulează aplicația după ce au fost selectate opțiunile. În final în fereastra de tip TextArea se tipărește rezultatul rulării programului.

O problemă interesantă a fost legarea interfeței de output-ul consolei de Linux. Deoarece nu se poate ca în timp ce rulează aplicația să se și afișeze rezultatul, acesta este salvat într-un fișier out.txt iar apoi la încheierea rulării, fișierul out.txt este copiat în TextArea pentru a se puteavedea pe interfață grafică.

Capitolul 5. Utilizarea sistemului

După cum s-a precizat și într-un capitol anterior acest program ne ajută să testăm mecanismul de memorie virtual.

Pentru a-l porni trebuie să fim într-un sistem de operare Linux și să avem jdk-ul instalat.

Următorul pas este să intrăm intrăm în terminal și să rulăm următoarea comandă:

. / java –jar „/home/clau/desktop/licFCT/malloc/licența.jar” pentru a putea porni interfață grafică a acestuia. În momentul când se mută programul pe alt calculator se face aceiași operație numai că se schimba calea dintre ghilimele cu noua cale unde se găsește programul licența.jar.

În momentul în care a pornit aplicația pentru a o folosi se poate intra în help de unde se afla informații despre sistem. În figură de mai jos se poate vedea fereastra de help.

In aceasta fereastra sunt date cateva explicatii legate de operatiile care se pot face acest program:

1) Pentru modul debug avem 3 parametrii:

-Parametru „0”. In acest mod nu se fac foarte multe teste de validari si este bun daca se cauta performanta.

-Parametru „1”. Fiecare vector alocat de aplicatie este umplut cu biti in mod aleator. Cand vectorii respectivi sunt eliberati sau realocati se verifica, ca bitii sa nu se fi schimbat. Acesta este modul standard\

-Parametru „2” . de cate ori se face o operatie, fiecare vector este verificat. Acest mod este foarte incet, dar bun pentru a se descoperii probleme cat mai repede.

2) In acest se testeaza un fisier dat ca parametru doar o singura data pentru a se verifica corectitudinea. Este folositor pentru a se vedea mesajele de debbing.

3) Se introduce directorul cu fișierele de test pentru a nu le lua pe cele care sunt deja în sistem.

4) Se rulează în paralel biblioteca standard malloc cu cea a programului putându-se observă diferența de viteză între cele 2. În mod normal pachet standard malloc este mai încet.

5) Pe lângă output-ul normal în acest mod se mai printează și informații de diagnostic de la fiecare fișier rulat în parte de program. Dacă cumva vrea un fișier cauzează defecte programului în acest mod se poate vedea care.

6) În acest mod se poate da o valoare de time out (aceasta bineînțeles este în secunde). Când s-a ajuns la această valoare programul se oprește. În mod standard programul rulează până la sfârșit.

7) Se folosește un singur fiser pentru teste în loc se se foloseaca toate fișierele din director.

După ce au fost selectate operațiile dorite, și introduși parametrii se poate da drumul la test prin apăsarea butonului RUN.

În momentul în care toate operațiile au fost efectuate rezultatul va fi tipărit în fereastra aplicației, de acolo putându-se interpreta rezultatele. În imaginea de mai jos se poate vedea cum arată fereasta pregătită pentru rulare.

Capitolul 6. Punerea în funcțiune și rezultate experimentale

În cadrul testelor s-a mers pe idea de a testa programul pe mai multe sisteme fizice, versiunea de Linux fiind aceaisi Ubuntu 9.1.

Platformele de test au fost atât cu procesoare Intel cât și cu procesoare AMD. Comparația se va face între sistemele cu același tip de procesor. Pentru primul test am folosit un processor Intel T7500 core 2 DUO cu o viteză de 2.2GHZ/nucleu cu un L2 cache de 4Mb.

După cum se poate observa avem rezultatele rulării care sunt împărțite pe mai multe coloane. Prima coloană verifica dacă fișierul de test a fost valid sau nu. Cea de-a 2 coloana arata gradul de ocupare al spațiului pentru alocat. Cea de a 3-a coloana indica câte operații (alocare/eliberare/realocare) s-au făcut. Cea de a 4-a indica timpul de execuție. Cea de a 5-a coloana indica numărul de kilo operații pe secundă, iar în final este indicat fișierul de test folosit.

La sfarsit se calculeaza performanta. Trebuie sa se țină cont de faptul că dacă testul nu este valid nu se vor calcula indicicele de utilitate si numarul de operatii.

Pentru cel de al 2-lea test am folosit tot un process Intel Pentium 4 cu o viteza de 3GHZ si un cache L2 de 2MB.

Se poate observa că deși gradul de utilizare și număr de operații făcute este același între cele două procesoare timpii de execuție și numărul de kilo operații pe secundă diferă, dar nu în favoarea unuia sau a altuia. Anumite fisere de test au fost verificate mai repede și au avut efectuate mai multe kops pe procesorul Pentium și alte pe Core 2 Duo. Deși primul procesor testat are 2 nuclee aplicația testează numai unul singur. În continuare se vor arăta testele pentru cele 2 procesoare de la Amd. Primul procesor este un Amd Turion 64 x2 cu o viteză de 1.90 Ghz/nucleu și un cache L2 de 1Mb.

Deși s-a precizat că nu se face comparația între sisteme cu procesoare diferite, nu putem să nu observăm cum în acest test performata a scăzut considerabil chiar dacă gradul de utilizare al spațiului și numărul de operații rămâne constat. Numărul kops a scăzut destul de mult față de celalalte 2 sisteme testate anterior.

În cele din urmă s-a mai testat un sistem cu procesor Amd Turion 64 x2 cu o viteză de 1.60Ghz/nucleu și cu un cache L2 de 1MB.

În figură următoare se va putea observa rezultatul. Se poate observa că acest ultim sistem este mai slab și decât celălalt sistem cu procesor Amd, văzându-se clar o diferență între numărul de kops de la cele 2 test.

În concluzie putem spune că deși gradul de utilizare al spațiului și numărul de operații făcute pe fiecare fișier a fost egal la toate cele 4 teste făcute, ele s-au diferențiat la număr de kops și timpul de lucru efectiv asupra fișierelor de test. Rezultatele mai slabe obținute de cele două procesoare de la Amd s-au datorat cache-ului L2 mai mic, asta pe lângă faptul că au avut și viteze de lucru mai scăzute.

Până la urma procesorul Intel Core 2Duo a avut rezultatele mai bune din cauză că a avut un cacheL2 mai mare, chiar dacă frecvența de lucru a fost mai mică decât cea a procesorul Intel Pentium 4.

Concluzii

Prezenta lucrare a dezvoltat tema potrivit căreia, în cadrul memoriei virtuale există o serie de procese care au rolul de a contribui la optimizarea acesteia. Pe parcursul elaborării temei am putut constata faptul că memoria virtuală reprezintă o componentă de bază a unui sistem de calcul. Astfel, succesul memoriei virtale se datorează faptului că funcționează în tăcere și în mod automat. De asemenea, am constatat faptul că, utilizând un mecanism curat, memoria virtuală utilizează într-un mod eficient memoria principală și cache-ul pentru un spațiu de adrese stocat pe disc, ajută la simplificarea gestionării memoriei prin oferirea unui spațiu de adresă uniform pentru fiecare proiect. Altă capacitate a acesteia este aceea de a proteja spațiul de adresare al fiecărui proces de corupție față de alte procese.

În ceea ce privește partea aplicativă a acestei lucrări, ea și-a propus să arate felul în care se pot face teste asupra memoriei, în acest scop folosindu-se un alocator de memorie. Prin utilizarea acestuia am realizat o serie de teste. Pentru a vedea dacă există diferențe în modul de alocare a memoriei a sistemelor fizice, am folosti același sistem de operare pe mai multe mai configurații hardware.

Din aceste teste s-a putut observa faptul că, în mare parte, departajarea intre sisteme a fost făcută de mărimea cache-ului de L2. Cu cât acesta era mai mare cu atât numărul kilo operațiilor pe secundă era mai mare, chiar dacă procesorul cu cache-ul cel mai mare nu avea și viteza de lucru cea mai ridicată.

Bibliografie

1. J. L. Hennessy, D. A. Patterson. Computer Architecture: A Quantitative Approach, Second Edition. Morgan-Kaufmann, 1996.

2. Randal E. Bryant, David R. O’Hallaron. Computer Systems: A Programmer’s Perspective. Pearson, 2001

3. T. Stricker and T. Gross. – Global address space, non-uniform bandwidth. A memory system performance characterization of parallel systems. In Proceedings of the Third International Symposium on High Performance Computer Architecture (HPCA), pages 168-179, San Antonio, TX, February 1997. IEEE.

4. Mel Gorman Understanding the Linux Virtual Memory Manager

5. Richard William Carr Virtual memory management

Bibliografie

1. J. L. Hennessy, D. A. Patterson. Computer Architecture: A Quantitative Approach, Second Edition. Morgan-Kaufmann, 1996.

2. Randal E. Bryant, David R. O’Hallaron. Computer Systems: A Programmer’s Perspective. Pearson, 2001

3. T. Stricker and T. Gross. – Global address space, non-uniform bandwidth. A memory system performance characterization of parallel systems. In Proceedings of the Third International Symposium on High Performance Computer Architecture (HPCA), pages 168-179, San Antonio, TX, February 1997. IEEE.

4. Mel Gorman Understanding the Linux Virtual Memory Manager

5. Richard William Carr Virtual memory management