Gestiunea memoriei - memoria virtuala, algoritmi de inlocuire a paginilor, aspecte de implementare

Gestiunea memoriei - memoria virtuala, algoritmi de inlocuire a paginilor, aspecte de implementare.

Memoria virtuala

Unele programe pot fi mai mari decat memoria fizica

Sistemul de operare pastreaza in memorie acele parTi de program care sunt folosite iar restul este pastrat pe disc.

Paginarea

Exista un set de adrese de memorie pe care programele le pot genera. Aceste adrese se numesc adrese virtuale si formeaza spaTiul virtual de adrese.

Unitatea de gestiune a memoriei MMU (Memory Management Unit) asociaza adresele virtuale cu adresele din memoria fizica.

SpaTiul virtual de adrese este imparTit in unitaTi numite pagini.

Memoria fizica este imparTita in unitaTi numite cadre de pagina

Un bit de prezenTa/absenTa este folosit pentru a urmari care pagini sunt fizic prezente in memorie.

Daca pagina solicitata nu este in memorie ci pe hard disc, are loc un defect de pagina:

Sistemul alege o pagina din memorie si o transfera pe disc apoi aduce pagina solicitata in memorie.

Tabelele de pagini

Tabelele de pagini asociaza paginile virtuale unor cadre de pagini.

Fiecare proces are cate o tabela de pagini.

Trebuie rezolvate doua probleme:

tabelele de pagini pot fi foarte mari;

asocierea trebuie sa se faca foarte rapid.

Implementarea tabelelor

o singura tabela constand dintr-un vector de registre fizice rapide cu un element pentru fiecare pagina virtuala. Are ca dezavantaj reducerea

performanTelor daca tabela este mare.

tabele de pagini pe mai multe nivele. Se evita pastrarea tuturor tabelelor de pagina in memorie

Algoritmi de inlocuire a paginilor

Algoritmul optim de inlocuire a paginilor

Este imposibil de implementat.

Fiecarei pagini i se pune o eticheta cu numarul de instrucTiuni care vor fi executate inainte ca pagina respectiva sa fie accesata.

Este scoasa pagina cu eticheta cea mai mare.

Se amana defectul de pagina.

Nu se poate implementa pentru ca nu se stie cand va fi accesata fiecare pagina din memorie.

Este util pentru compararea performanTelor celorlalTi algoritmi.

Algoritmul inlocuirii paginilor care nu au fost accesate recent foloseste doi biTi: A si M

A are valoarea 1 atunci cand pagina este accesata.

M are valoarea 1 atunci cand s-a scris in pagina

Cand este generat un defect de pagina sistemul de operare analizeaza toate paginile si le imparte in patru categorii in funcTie de valorile biTilor A si M:

. Clasa 0 - nu a fost nici accesata, nici modificata;

. Clasa 1 - nu a fost accesata, dar a fost modificata

. Clasa 2 - a fost accesata, dar nu a fost modificata

. Clasa 3 - a fost accesata si a fost modificata.

Clasa 1 este posibila cand unei pagini din clasa 3 ii este modificat bitul A in urma unei intreruperi generate de ceas.

Acest algoritm elimina aleator o pagina din cele din clasa cu numar minim care nu este vida.

Are o performanTa destul de buna.

Algoritmul primul intrat - primul iesit

Sistemul de operare Tine o lista cu paginile care se gasesc in memorie avand ca element de inceput al listei cea mai veche pagina introdusa.

Este scoasa prima pagina din lista, iar noua pagina este adaugata la sfarsit.

Poate scoate pagini care sunt utilizate in continuare.

Este rareori aplicat.

Algoritmul celei de-a doua sanse

Modificare a algoritmului FIFO.

Se verifica bitul A al celei mai vechi pagini.

Daca A este 0, atunci pagina este si veche si nefolosita si poate fi imediat inlocuita.

Daca A este 1 atunci este modificat in 0 si este trecuta la sfarsitul listei.

Inlocuirea paginilor dupa ceas

Pastrarea tuturor cadrelor de pagina intr-o lista circulara in forma de ceas. O sageata indica pagina cea mai veche.

Cand este generat un defect de pagina, SO verifica pagina indicata de sageata.

Daca bitul A este 0 atunci pagina este eliminata, noua pagina este pusa in locul ei si sageata avanseaza o poziTie.

Daca bitul A este 1, atunci este trecut pe 0 si sageata trece la urmatorul element.

Algoritmul de inlocuire a paginilor cel mai demult folosite

Atunci cand apare un defect de pagina, pagina eliminata va fi cea nefolosita de cel mai mult timp (LRU - Last Recently Used).

Trebuie pastrata o lista inlanTuita cu paginile din memorie - la inceputul listei sunt paginile cel mai recent folosite.

Algoritmul inlocuirii paginilor din setul de lucru

Nici una dintre paginile procesului nu este in memorie.

Cand se executa prima instrucTiune se genereaza un defect de pagina si SO aduce in memorie pagina care conTine prima instrucTiune.

Paginare la cerere - paginile sunt incarcate cand sunt cerute.

Setul de pagini cu care un proces lucreaza la un moment dat se numeste set de lucru.

Algoritmul ceasului si al setului de lucru

Este adesea intalnit in practica.

Lista circulara de cadre de pagina ca in algoritmul de inlocuire a paginilor dupa ceas.

IniTial lista este goala, atunci cand se incarca o pagina, aceasta este adaugata la lista.

Aspecte de implementare

Implicarea sistemului de operare in paginare are loc cand este creat un proces nou - SO trebuie sa creeze un tabel de pagini pentru acesta, trebuie sa aloce memorie in zona de transfer (swapping).

in momentul inceperii execuTiei procesului - SO trebuie sa reseteze MMU

cand apare un defect de pagina SO trebuie sa citeasca registrele hard pentru stabilirea adresei virtuale care a generat defectul de pagina SO trebuie sa determine pagina necesara, sa o localizeze pe disc, sa gaseasca un cadru de pagina disponibil si sa incarce noua pagina

cand un proces se termina SO trebuie sa elibereze tabelul de pagini si spaTiul de pe disc alocat paginilor procesului

Tratarea defectelor de pagina

Se salveaza contorul programului pe stiva.

Printr-o rutina de limbaj de asamblare se salveaza registrele generale si alte informaTiile volatile.

SO incearca sa determine pagina virtuala necesara

Odata cunoscuta adresa virtuala care a generat defectul de pagina, SO verifica daca aceasta adresa este valida si nu are loc o violare a protecTiei. Daca

nu, procesul este terminat, daca da, SO determina un cadru liber sau un cadru care poate fi eliberat.

Daca cadrul selectat este ocupat, pagina se transfera pe disc.

SO programeaza o operaTie pe disc pentru a o aduce in memorie. Procesul care a generat defectul de pagina este suspendat.

Cand pagina de pe disc este incarcata are loc o reactualizare a tabelelor paginii pentru a reflecta poziTia acesteia iar cadrul este marcat ca fiind in

stare normala.

InstrucTiunea care a generat defectul de pagina este readusa la starea in care era la inceputul execuTiei iar contorul programului este resetat la instrucTiunea respectiva.

Se programeaza procesul care a generat defectul de pagina.

Rutina in limbaj de asamblare reincarca registrele si alte informaTii de stare.

Se reia execuTia procesului.

Salvarea instrucTiunilor

Este dificila determinarea inceputului instrucTiunii.

Pe anumite calculatoare exista un registru in care se copiaza contorul programului chiar inainte de execuTia fiecarei instrucTiuni.

Blocarea paginilor in memorie apare la interacTiunea dintre memoria virtuala si operaTiile de I/E.

Se blocheaza in memorie paginile angajate de procese de I/E pentru a nu putea fi eliminate.