Pagina documente » Informatica, Matematica » Sisteme de operare si metode de alocare a memoriei principale

Despre lucrare

lucrare-licenta-sisteme-de-operare-si-metode-de-alocare-a-memoriei-principale
Aceasta lucrare poate fi descarcata doar daca ai statut PREMIUM si are scop consultativ. Pentru a descarca aceasta lucrare trebuie sa fii utilizator inregistrat.
lucrare-licenta-sisteme-de-operare-si-metode-de-alocare-a-memoriei-principale


Cuprins

Cuprins:
Introducere 3
Capitolul I Alocarea memoriei principale 5
I.1 Algoritmi pentru gestionarea memoriei 6
I.3 Compactarea si colectarea gunoaielor 9
I.4 Suprapunere 11
I.5 incarcarea dinamica 13
I.6 Swapping 13
Capitolul II Memoria virtuala 15
II. 1 Paginare 15
II.1.1 Tabelele de pagina 17
II.1.2 inlocuirea paginii 22
II.1.3 Alocare de cadre pentru un singur proces 22
II.1.4 A doua sansa 25
II.1.5 Alocarea cadrelor pentru procese multiple 26
II.1.6 Alocarea cu partitii fixate 30
II.1.7 Frecventa erorii de pagina (PFF) 30
II.1.8 Multime de lucru 31
II.2 Segmentare 31
II.2.1 Segmentarea in sistemul de operare MULTICS 33
II.2.2 Intel x86 35
Capitolul III. Organizarea memoriei in sistemul de operare UNIX 36
III.1 Swapping (transfer) 36
III.1.1 Alocarea spatiului de swap 37
III.1.2 Transferarea proceselor din memoria principala 40
III.1.3 Transferul proceselor in memoria principala 41
III.2 Pagina la cerere 45
III.2.1 Structuri de date pentru paginarea la cerere 46
III.2.2 Procesul care fura pagini (pfp) 51
III.2.3 Erorile de pagina 55
III.2.4 Paginare la cerere pe hardware mai putin sofisticat 59
III.3 Un sistem hibrid cu swap si paginare la cerere 59
Capitolul IV Alocarea memoriei in sistemul de operare Windows 61
IV.1 Modelul de memorie segmentata de la Windows 3.1 61
IV. 2 Modelul de memorie nediferentiata de la Windows NT 63
IV.3 Tipuri de memorie Windows 66
Capitolul V. Alocatoare de memorie 68
V.1 Un alocator dinamic foarte simplu 68
V.2 Alocatorul cu harta de resurse 68
V.3 Alocatorul cu puteri ale lui 2 70
V.4 Alocatorul Karels-McKusick 71
V.5 Alocatorul slab 72
Bibliografie 75

EXTRAS DIN DOCUMENT

?{p}

{p}

?Introducere

Una din cele mai faimoase gafe ale lui Bill Gates, patronul firmei Microsoft, pronuntata candva pe la inceputul anilor ’80 suna cam asa: “640 de kiloocteti trebuie sa fie indeajuns pentru oricine“. Enuntul este cu atat mai amuzant cu cat compania Microsoft produce niste programe uriase, pentru care resursele calculatoarelor contemporane, care au evoluat intr-o rata greu de imaginat, nu sunt suficiente.

Daca lucrurile ar fi stat asa cum prevedea Gates, atunci sistemele de operare insele ar fi disparut, sau ar fi aratat substantial diferit de cele din ziua de azi. De ce spun ca sistemele de operare ar fi disparut ? Pentru ca rolul principal al unui sistem de operare este cel de management al resurselor unui calculator, in particular de management al memoriei. Daca resursele ar fi prezente din abundenta, atunci necesitatea unui manager ar fi mai putin stringenta.

Lucrarea de fata prezinta si analizeaza mecanismele de alocare a memoriei de catre sistemele de operare.

Lucrarea poate fi impartita in trei parti. Prima parte (capitolele I si II) prezinta mecanismele generale de alocare a memoriei. Aceasta parte este organizata evolutiv incepand cu tehnicile de gestionare a suprapunerilor si incarcare dinamica a modulelor, tehnici aplicabile de catre programator explicit. Apoi sunt prezentate pe larg tehnicile moderne de organizare a memoriei: paginarea si segmentarea cu exemple si scurte studii de caz.

A doua parte este o privire comparativa a modului in care cel mai cunoscute sisteme de operare isi organizeaza memoria. Pentru capitolul dedicat sistemului de operare UNIX am consultat o lucrare de marca editata sub patronajul firmei AT&T firma cu o mare contributie la dezvoltarea acestui sistem de operare. Aici sunt analizate detaliat atat aspecte general intalnite la alocarea memoriei cat si particularitati ale sistemului UNIX in acest domeniu. Este analizat apoi sistemul de operare Windows cu variantele sale de la Windows 3.1 la Windows NT.

În incheiere intr-un capitol mai practic sunt prezentate cateva implementari ale alocatorului de memorie din nucleul sistemelor de tip UNIX si nu numai.

Caracteristicile si performantele memoriei si procesului de memorare influenteaza in mare masura functionarea si performantele sistemului de calcul respectiv.

Activitatea de gestiune a memoriei are in vedere fie memoria organizata pe doua nivele, memoria principala si memoria auxiliara, fie memoria privita sub forma unui singur nivel in conceptul de memorie virtuala. Obiectivul principal al activitatii de gestiune a memoriei este de a furniza o viteza de executie foarte mare a unui program prin mentinerea in memoria principala a acelor parti din program care sunt referite cu o frecventa mare de catre procesor, restul partilor din program putand fi memorate in memoria auxiliara si incarcate in momentul solicitarii de catre procesor.

Capitolul I

Alocarea memoriei principale

Vom analiza cum putem organiza memoria principala (numita si random-access-memory (RAM)). În general organizarea memoriei presupune doua operatii:

Address allocate(int size);

void deallocate(Address block);

Procedura allocate primeste o cerere pentru un bloc alocat contiguu de dimensiunea size octeti de memorie si intoarce un pointer la un astfel de bloc. Procedura dealocate elibereaza blocul indicat el putand fi refolosit. Cateodata avem la dispozitie si o a treia procedura

Address reallocate(Address block, int new_size);

care ia un bloc alocat si ii modifica dimensiunea fie intorcand o parte din el memoriei disponibile fie extinzandu-l la un bloc mai mare. Nu intotdeauna este posibil sa se mareasca dimensiunea blocului fara a il copia la o noua locatie.

Alocatoarele de memorie sunt folosite in diferite situatii. În UNIX fiecare proces are un segment de date. Exista un apel sistem pentru a mari dimensiunea segmentului de date dar nu exista nici unul care sa il faca mai mic. De asemenea apelul sistem este destul de costisitor. Prin urmare exista biblioteci cu proceduri pentru a gestiona acest spatiu (functiile malloc, free si realloc). Doar cand malloc sau realloc nu mai au spatiu este necesar sa se faca un apel sistem. Operatorii C++ new si delete sunt variante mai noi ale functiilor malloc si free. Operatorul Java new foloseste de asemenea malloc, si impreuna cu rutina java free cand un obiect este gasit ca inaccesibil la colectarea gunoaielor.

Sistemul de operare foloseste de asemenea un alocator de memorie pentru a gestiona spatiul folosit de structurile de date ale sistemului de operare si procesele utilizator. Dupa cum am vazut mai devreme sunt cateva motive pentru care am putea dori mai multe procese cum ar fi satisfacerea mai multor utilizatori sau pentru a controla mai multe periferice. Mai este si un motiv mai “egoist” pentru care SO vrea sa aiba mai multe procese in memorie in acelasi timp: pentru a tine ocupat CPU ocupat. Presupunand ca sunt n procese in memorie (ceea ce se numeste nivelul de multiprogramare) si fiecare proces este blocat asteptand (pentru I/O) o fractiune de timp p. În cel mai bun caz CPU ar putea fi 100% ocupat .

De exemplu daca fiecare proces este gata de rulare 20% din timp p=0,8 si CPU poate fi tinut complet ocupat cu 5 procese. Bineinteles procesele reale nu sunt asa de cooperative. În cel mai rau caz ele pot toate sa blocheze in acelasi timp (fractia de timp in care CPU este ocupat va fi doar de 1-p (20% in exemplul nostru). Daca fiecare proces se decide la intamplare si independent cand sa se blocheze sansa ca toate procesele sa fie blocate in acelasi timp este doar pn, asa ca utilizarea CPU este doar de 1-pn. Continuand exemplul pentru cazul n=5 si p=0.8, rata de utilizare asteptata este de 1-0.85=1-0.32768=0.67232. Cu alte cuvinte CPU va fi ocupat in medie 67%.

I.1 Algoritmi pentru gestionarea memoriei

Clientii gestionarului de memorie (procesele care cer memorie) pastreaza informatii despre blocurile alocate. Gestionarul de memorie trebuie sa tina minte golurile dintre blocurile alocate de obicei intr-o lista dublu inlantuita. Aceasta structura este numita lista blocurilor libere. Aceasta lista nu ocupa spatiu decat pentru pointerii cap si coada deoarece legaturile dintre goluri pot fi pastrate chiar in aceste goluri (presupunand ca fiecare gol are dimensiunea de cel putin de doua ori mai mare decat a spatiului necesar pentru un pionter).Pentru a satisface o cerere allocate(n) gestionarul de memorie gaseste un gol de dimensiune cel putin n si il inlatura din lista blocurilor libere. Daca golul este mai mare de n byti poate sa desparta blocul in doua parti si returnand partea ramasa in lista. Pentru a satisface o cere deallocate gestionarul de memorie transforma blocul intr-o structura de “gol” si il insereaza in lista blocurilor libere. Daca noul gol este urmat sau precedat de alt gol cele doua blocuri pot fi comasate in unul singur cum se va explica mai jos.

Cum stie gestionarul de memorie cat de mare este un bloc? Metoda uzuala este sa puna un header mai mic in blocul alocat care sa contina dimensiunea blocului si eventual alte informatii despre bloc. Procedura allocate intoarce un pointer spre corpul blocului nu spre nu spre header astfel clientul nu trebuie sa stie nimic despre aceasta. Procedura deallocate extrage dimensiunea headerului din argumentul sau(adresa blocului de eliberat) pentru a afla adresa headerului. Clientul crede ca dimensiunea blocului este putin mai mica decat este in realitate. Atat timp cat clientul nu modifica headerul blocului alocat este totul in ordine dar daca aceasta se intampla gestionarul de memorie va fi derutat. Aceasta este o problema intalnita frecvent la malloc in programele scrise in C sau C++ sub UNIX. Sistemul Java foloseste o serie de rutine pentru a verifica si preveni aceasta eroare. Pentru a fi mai usor de comasat golurile adiacente gestionarul de memorie adauga o eticheta la inceputul si la sfarsitul fiecarui gol sau bloc alocat si inregistreaza dimensiunea blocului la ambele capete ale sale.

Figura 1. Lista de blocuri

Cand blocul este dealocat gestionarul de memorie adauga dimensiunea blocului (care este pastrata in headerul sau) la adresa inceputului blocului pentru a afla adresa primului cuvant de dupa sfarsitul blocului. Se uita la eticheta pentru a vedea daca spatiul ce urmeaza este un gol sau este un bloc alocat. Daca este un gol atunci este eliminat din lista blocurilor libere si unit cu blocul care va fi eliberat pentru a face un gol mai mare. De asemenea daca eticheta de la sfarsitul blocului precedent arata ca spatiul urmator este un gol putem afla adresa de inceput a golului scazand dimensiunea sa din adresa blocului ce va fi eliberat (de aceea dimensiunea este pastrata la ambele capete), il elimina din lista blocurilor libere si il uneste cu blocul ce va fi eliminat. În final adaugam noul gol in lista blocurilor libere. Golurile sunt retinute in lista dublu inlantuita pentru a fi mai usor de eliminat din lista cand trebuiesc comasate cu blocurile care sunt eliberate.

Cum alege gestionarul de memorie un bloc liber pentru a satisface o cerere allocate ? La inceput poate parea ca ar trebui aleasa cel mai mic gol destul de mare pentru a satisface cererea. Aceasta strategie se cheama best fit. Aceasta are doua inconveniente. Primul este ca presupune o cautare costisitoare a intregii liste de blocuri libere pentru a o gasi pe cea mai potrivita (pot fi folosite alte structuri de date mai sofisticate pentru a face cautarea mai rapida). Dezavantajul mai important este ca duce la crearea a mai multe goluri de dimensiune prea redusa pentru a mai putea satisface vreo cerere. Aceasta situatie este numita fragmentare, si este o problema care apare la toate strategiile de alocare a memoriei cu toate ca nu este de dorit. O modalitate de a evita aparitia acestor goluri mici este sa se dea clientului un bloc mai mare decat cel cerut. De exemplu putem aproxima toate cererile prin primul multiplu de 64 octeti mai mare decat cel cerut. Aceasta nu elimina fragmentarea ci doar o ascunde. Spatiul nefolosit ce se gaseste sub forma de goluri se numeste fragmentare externa in timp ce spatiul nefolosit din interiorul blocurilor alocate se numeste fragmentare interna.

Alta metoda de alocare este prima potrivire (first fit) care parcurge pur si simplu lista blocurilor libere pana cand gaseste un bloc suficient de mare. În ciuda denumirii first fit este in general mai buna decat best fit deoarece reduce fragmentarea. Mai apare insa o alta problema: golurile mici tind sa se adune la inceputul listei iar alocatorul trebuie sa caute de fiecare data mai mult in lista. Aceasta problema este rezolvata cu metoda urmatoarei potriviri (next fit) care incepe fiecare cautare de acolo de unde s-a terminat ultima luand-o de fiecare data de la capat cand se ajunge la sfarsit.

O alta strategie este sa se mentina liste separate fiecare continand blocuri libere de dimensiuni diferite. Aceasta abordare lucreaza bine la nivel de aplicatii cand sunt doar cateva tipuri de obiecte (altfel ar putea fi multe instante de fiecare tip). Aceasta metoda poate fi folosita intr-un cadru mai general aproximand toate cererile prin adaos la cateva valori predeterminate. De exemplu gestionarul de memorie poate aproxima toate cererile prin urmatoarea putere de 2 octeti (cu un minim de 64) si memoreaza liste pentru golurile de 64, 128, 256,...,etc. Presupunand ca cea mai mare cerere poate fi de 1Mb aceasta cere doar 14 liste. Aceasta abordare este folosita de cele mai multe implementari ale functiei malloc. Astfel se elimina complet fragmentarea externa dar fragmentarea interna poate fi chiar de 50% in cel mai rau caz (acesta apare cand toate cererile sunt cu un octet mai mari de o putere a lui 2). O alta problema a acestei metode este gruparea spatiilor libere adiacente. O posibilitate ar fi sa nu facem aceasta compactare. La initializarea sistemului memoria este impartita in blocuri libere de dimensiune fixa (de aceeasi dimensiune sau de dimensiune variabila). Fiecare cerere este satisfacuta cu un bloc potrivit astfel: daca cererea este mai mica decat dimensiunea blocului liber este alocat intregul bloc. Cand blocul este eliberat este pur si simplu intors in lista potrivita. Cele mai multe implementari ale functiei malloc folosesc o varianta a acestei metode (in unele implementari golurile sunt sparte dar nu mai sunt comasate la loc).

O metoda interesanta de a comasa blocurile libere cand sunt mai multe liste de goluri este sistemul de camarazi (buddy system). Sa presupunem ca toate blocurile libere sau alocate au dimensiuni puteri ale lui 2 (deci cererile sunt intotdeauna aproximate cu urmatoarea putere a lui 2) si fiecare bloc liber sau ocupat incepe la o adresa care este multiplu al dimensiunii sale. Atunci fiecare bloc are un “camarad” de aceeasi dimensiune adiacent lui si astfel comasand un bloc de dimensiune 2n cu camaradul sau se obtine un bloc de dimensiune 2n+1 aliniat corespunzator. De exemplu blocurile de dimensiune 4 pot incepe la adresele 0, 4, 8, 12, 16, 20 etc. Blocurile de la adresele 0 si 4 sunt camarazi; unindu-le vom obtine un bloc incepand la adresa 0 si de dimensiune 8. La fel blocurile de la adresele 8 si 12 si cele de la adresele 16 si 20 sunt camarazi. Blocurile de la adresele 4 si 8 nu sunt camarazi chiar daca sunt vecine deoarece unindu-le obtinem un bloc de dimensiune 8 incepand la adresa 4, care nu este multiplu de 8. Adresa camaradului unui bloc poate fi calculata usor facand 1 al n–lea bit din dreapta din reprezentarea binara a adresei blocului (numaratoarea bitilor incepe de la 0). De exemplu perechile de camarazi: (0,4), (8,12), (16,20) se reprezinta in binar (00000, 00100), (01000,01100), (10000,10100). În fiecare caz cele doua adrese pereche difera doar prin bitul de pe a treia pozitie din dreapta (4=22). Pe scurt se poate gasi adresa camaradului unui bloc facand XOR intre adresa blocului si dimensiunea sa. Pentru a aloca un bloc de dimensiune data intai se aproximeaza dimensiunea cu urmatoarea putere a lui 2 si se cauta in lista blocurilor de aceasta dimensiune. Daca lista este vida se sparge un bloc din lista cu blocurile de dimensiune imediat urmatoare (daca si aceasta lista este vida i se adauga intai doua blocuri obtinute din spargerea unui bloc din lista imediat urmatoare si tot asa). Cand se elibereaza un bloc, se verifica mai intai daca este liber camaradul sau. Daca da comaseaza blocul cu camaradul sau si rezulta un bloc care va fi trecut in lista celor de dimensiune mai mare. La fel ca alocarea si dealocarea poate trece la liste cu blocuri de dimensiuni din ce in ce mai mari.

I.3 Compactarea si colectarea gunoaielor

Ce se intampla cand nu este suficienta memorie? Toate aceste metode pot esua deoarece toata memoria este alocata sau deoarece este prea mare fragmentarea. Malloc, care este folosit pentru a aloca segmentul de date al unui proces UNIX, renunta si face un apel de sistem (costisitor) pentru a mari segmentul de date. Un manager de memorie care aloca memorie fizica reala nu poate face acest lucru si alocarea esueaza. Sunt doua metode de a evita acest pericol: compactarea si colectarea gunoaielor.

Compactarea incearca sa rezolve problema fragmentarii mutand toate blocurile alocare la sfarsitul memoriei combinand astfel golurile din memorie. Pe langa costul evident mare al tuturor acestor copieri mai exista o limitare a compactarii: orice pointer la un bloc trebuie sa fie actualizat cand un bloc este mutat. Daca nu se pot gasi toti acesti pointeri compactarea este imposibila. Pointeri pot fi pastrati chiar in blocurile alocate, dar la fel de bine pot fi retinuti de clientul managerului de memorie. În unele situati pointerii pot indica nu numai spre inceputul blocului ci si spre corpul lor. De exemplu daca un bloc contine cod executabil o instructiune poate fi pointer spre alta locatie din acelasi bloc. Compactarea se face in trei faze. În prima se va calcula noua locatie a fiecarui bloc pentru a determina distanta cu care va fi mutat blocul. Apoi fiecare pointer este actualizat adagandu-i-se distanta cu care este mutat blocul spre care pointeaza. În final blocul este efectiv mutat. Sunt mai multe posibilitati de a combina aceste operatii.

Prin colectarea gunoaielor se cauta blocurile inaccesibile si sunt adaugate in lista blocurilor libere. La fel ac si compactare si colectarea gunoaielor presupune gasirea tuturor pointerilor la blocuri si din blocul insusi si din alte blocuri. Daca acest lucru nu este posibil putem face totusi o colectare mai conservativa a gunoaielor in care fiecare cuvant din memorie care contine o valoare ce pare a fi pointer este tratat drept pointer. Abordarea conservatoare poate da gres in colectare blocurilor “gunoaie” dar nu va colecta niciodata din greseala blocuri accesibile. Sunt trei metode principale pentru colectarea gunoaielor: numararea referintelor (reference count), marcare si stergere (mark-and-sweep) si algoritmi pe generatii.

Oferta anului

Reducere 2020