Paginarea memoriei

PAGINAREA MEMORIEI

Paginarea este un tip de alocare necontiguu, aceasta insemnand ca unui proces ii poate fi alocata memorie oriunde, atat in memoria interna cat si in cea externa, iar memoria alocata poate fi formata din bucati de memorie.

Suportul hardware

Memoria fizica este impartita in blocuri de lungime fixa, numite cadre de pagina (frames) sau pagini fizice. Lungimea unui cadru este o putere a lui doi si este constanta pentru fiecare arhitectura de sistem in parte. Pentru Intel lungimea unui cadru este 4KO.

Memoria logica a unui proces este impartita in pagini logice sau pagini virtuale care sunt plasate in memoria secundara, pe harddisc.

Pentru executia unui proces, paginile sale logice trebuie incarcate in cadrele libere ale memoriei fizice, intr-un mod necontiguu. Evidenta cadrelor libere este tinuta de sistemul de operare. Bineinteles, daca procesul are nevoie de n pagini logice, trebuie sa se gaseasca n cadre libere.

Atat adresele fizice cat si cele logice sunt implementate in hard si ele contin:

-adresa fizica=numar de cadru(f)+deplasament in cadru(d)

-adresa logica=numar de pagini logice(l)+deplasament in

pagina logica

Prin mapare se intelege translatarea adresei logice in adresa fizica. Aceasta sarcina ii revine sistemului de operare prin utilizarea tabelei de pagini.

Fiecare proces are o tabela de pagini in care in care fiecare pagina logica are adresa de baza a cadrului asociat ei. Pentru translatare se foloseste numarul de pagina drept index in tabela de pagini.

In schema din figura 5.3. se vede corespondenta intre adresa logica si cea fizica prin intermediul tabelei de pagini.

Adresa logica Adresa fizica

lf

Tabela de paginiMemoria fizica

Fig.5.3. Corespondenta dintre adresa logica si cea fizica.

Implementarea tabelei de pagini

Pastrarea tabelelor de pagini se face in :

a)-registrele hard;

b)-memoria principala;

c)-memoria hard speciala, de tip asociata.

a) Solutia de implementare a tabelelor de pagini in registrele unitatii centrale este , desigur , foarte rapida dar si foarte scumpa, mai ales pentru un numar foarte mare de tabele. In plus accesul la registre se face in mod privilegiat ceea ce, la un moment dat, poate constitui un impediment.

b) Solutia de implementare a tabelei de pagini in memoria principala presupune un cost mult mai scazut si de aceea este solutia cea mai des intalnita. Ea impune accese multiple la memorie; mai intai trebuie accesata tabela de pagini pentru aflarea adresei fizice asociata adresei logice dorite; apoi se acceseaza memoria fizica la adresa aflata pe baza translatarii. In acest tip de translatare se foloseste un Registru de Baza al Tabelei de Pagina (RBTP). Atunci cand se doreste sa se lucreze cu alta tabela de pagina decat cea curenta, se incarca RBTP cu noua valoare de pagina, reducandu-s in acest fel timpul de comutare.

c) O alta solutie de implementare este aceea in care se utilizeaza o memorie asociativa hardware, de mica dimensiune. Aceasta foloseste un set de registre asociative. Fiecare registru are doua componente:

-cheie, in care se memoreaza numarul paginii logice;

-valoare, in care se memoreaza numarul cadrului asociat.

Cautarea intr-o astfel de memorie asociativa se face in felul urmator: un element care trebuie gasit este comparat simultan cu toate cheile si unde se gaseste coincidenta se extrage campul valoare corespunzator.

In scopul utilizarii unei astfel de memorii asociative pentru tabela de pagina, se face urmatoarea corespondenta:

-in cheie se memoreaza numarul paginii logice;

-in valoare se memoreaza numarul cadrului asociat.

Atunci cand procesorul genereaza o adresa logica, daca numarul de pagina logica coincide cu una din chei, numarul de cadru devine imediat disponibil si este utilizat pentru a accesa memoria. Daca numarul de pagina nu coincide cu nici una dintre chei, atunci, pentru aflarea numarului cadrului asociat, se face un acces la tabela de pagini din memoria interna. Informatia astfel obtinuta este utilizata pentru accesarea memoriei utilizator, cat si pentru a fi adaugata in cadrul registrelor asociative, impreuna cu numarul de pagini asociat, ca sa poata fi regasita rapid in cadrul unei referiri ulterioare.

Alte imbunatatiri ale implementarii tabelei de pagini folosesc:

a)-tabele de pagini pe nivele multiple;

b)-tabele de pagini inverse.

a) Pentru un spatiu de adresare foarte mare, tabelele de pagini pot avea dimensiuni mari. De exemplu, pentru o memorie principala de 4 GO (2³²octeti), daca pagina are 4KO, atunci o tabela de pagini are 1 milion de intrari. Una din tehnicile de reducere a dimensiunilor tabelei de pagini este utilizarea unei tabele de pagini pe nivele multiple. Aceasta echivaleaza cu impartirea tabelei de pagina in altele care sa aiba dimensiuni mai mici si unde cautarea sa se faca intr-un timp mai scurt.

Pornind de la exemplul precedent, cu memoria principala de 2³² octeti, o adresa logica arata astfel:

Fiecare tabela de pagina are un milion de intrari. Daca partitonam tabelul de pagina in 4 sectiuni, fiecare sectiune are 256 K intrari iar o adresa logica pentru o sectiune arata astfel:

b) O alta modalitate de reducere a dimensiunii tabelelor de pagini este folosirea tabelei de pagini inversa. In loc de a avea o intrare in tabela pentru fiecare pagina virtuala, avem cate o intrare pentru fiecare cadru fizic. Deci in loc sa se faca corespondenta:

-pagina virtuala → cadru fizic

se face o corespondenta inversa:

-cadru fizic → pagina virtuala.

Cand se translateaza o adresa logica, se cauta in tabela de pagini inversa numarul paginii logice si se returneaza cadrul fizic corespunzator. In acest mod se face o reducere a numarului de intrari in pagina dar cautarea are o viteza mai mica, deoarece trebuie cautata intreaga tabela.

Concluzii privind paginarea

Principalul avantaj al paginarii este eliminarea completa a fragmentarii externe. Nu dispare insa si fragmentarea interna, deoarece poate ramane un spatiu nefolosit dar alocat proceselor, fiindca dimensiunea proceselor nu este un multiplu exact al lungimii paginilor.

Un alt avantaj al paginarii este posibilitatea de partajare a memoriei. Doua sau mai multe pagini pot vedea aceeasi zona de memorie incarcand paginile logice in acelasi cadru fizic. Singura solutie este ca in acel cadru fizic sa fie memorat cod reentrant, adica un cod care nu se mai poate automodifica in timpul executiei. Datorita proprietatii de reentranta , este posibil ca doua sau mai multe procese sa execute simultan acelasi cod, fiecare proces pastrand o copie a registrelor si a datelor proprii. In memoria fizica este necesar sa se pastreze o singura copie a codului comun, fiecare tabela de pagina indica spre acelasi cadru, in timp ce paginile corespunzatoare datelor proceselor sunt memorate in cadre diferite.

Un dezavantaj al paginarii este faptul ca fiecare acces la memorie presupune un acces suplimentar la tabela de pagini pentru calculul de adresa.

Segmentarea memoriei

Segmentarea reprezinta o vedere a memoriei din punctul de vedere al utilizatorului care percepe memoria nu ca pe o succesiune de cuvinte, asa cum este in realitate, ci ca pe o multime de bucati de memorie de diverse dimensiuni. Aceste segmente pot cuprinde: programul principal, proceduri, functii, stive, vectori, matrici etc.

Segmentarea este o schema de administrare a memoriei in care programul este divizat in mai multe parti functionale. Spatiul logic de adresare al programului este si el impartit in segmente. Fiecarui segment de memorie ii corespunde o unitate functionala a programului.

ProgramMemorie

Fig. Principiul segmentarii.

Fiecare segment are un nume si o dimensiune, deci:

-un nume

-un deplasament.

Programatorul vede spatiul virtual de adresare al programului ca un spatiu bidimensional, nu un spatiu unidimensional ca la programare.

Segmentare paginata

A fost introdusa de sistemul de operare MULTICS al lui Tannenbaum si incearca sa imbine avantajele celor doua metode, de paginare si de segmentare.

Fiecare segment este impartit in pagini. Fiecare proces are o tabla de segmente, iar fiecare segment are o tabela de mapare a paginilor.

Adresa virtuala se formeaza din: segment, pagina si deplasament.

Adresa fizica se formeaza din cadru de pagina si deplasament.

In segmentarea paginata se elimina doua dezavantaje ale segmentarii pure: alocarea contigua a segmentului si fragmentarea externa.

Memorie virtuala

Alocarea prin memorie virtuala are capacitatea de a aloca un spatiu de memorie mai mare decat memoria interna disponibila. Pentru aceasta se utilizeaza paginarea sau segmentarea combinate cu swappingul. Memoria virtuala este o tehnica ce permite executia proceselor chiar daca acestea nu se afla integral in memorie. Metoda functioneaza datorita "localitatii" referintelor la memorie. Numai un subset din codul, respectiv datele, unui program sunt necesare la un moment arbitrar de timp. Problema consta in faptul ca sistemul de operare trebuie sa prevada care este subsetul dintr-un moment urmator. Pentru aceasta se apeleaza la principiul localitatii (vecinatatii), enuntat de J.P.Denning in 1968. Acest principiu are doua componente:

-localitate temporara - tendinta de a accesa in viitor locatii accesate deja in timp;

-localitate spatiala - tendinta de a accesa in viitor locatii cu adrese apropiate de cele accesate deja.

Alocarile cele mai des utilizate in memoria virtuala sunt:

-alocarea de tip paginare la cerere;

-alocarea de tip segmentare la cerere.

Paginare la cerere

Paginarea la cerere imbina tehnica de paginare cu tehnica swapping. In acest fel, paginile de pe harddisc sunt aduse in memorie numai cand sunt referite, cand este nevoie de ele. In acest mod se elimina restrictia ca programul sa fie in intregime in memorie. In fig. 5.5. se da o organigrama a paginarii la cerere.

NU DA

NU (BITVALID=0) DA

Fig. 5.6. Organigrama paginarii la cerere.

Asa cum se observa din organigrama, daca referirea unei pagini este valida, adica daca adresa ei este corecta, atunci primul lucru care se testeaza este bitul valid/nevalid. Acesta este implementat in tabelul de mapare a paginilor si daca este 1 inseamna ca pagina se afla in memorie, daca este 0 pagina este pe harddisc si trebuie adusa in memorie. Daca este zero, se declanseaza eroare de pagina, se genereaza o intrerupere de pagina ( PFI = Page Fault Interrupt), de tip sincron, transparenta pentru utilizator, cu o prioritate superioara. In acest moment se va intrerupe executia programului in curs iar sistemul de operare va lansa rutina de tratare a intreruperii de pagina. Aceasta va cauta un spatiu liber si, daca exista, va plasa pagina in el. Daca nu, va trebui sa aleaga o rutina, adica un cadru ce va fi inlocuit.

NU DA

NU DA

DANU(bit dirty =0)

Pagina nu a fost modificata si nu trebuie salvata pe harddisc

Fig.5.7. Rutina de tratare a intreruperii de pagina.

Se testeaza, in continuare, bitul de tranzit al paginii rutina si daca este 1 se abandoneaza aceasta pagina victima si se trece la alta victima. Regula este ca in alegerea victimei sa se evite o pagina in curs de incarcare. Apoi se testeaza bitul dirty. Acesta este pus la 0 initial la incarcare si este setat la 1 ori de cate ori se face o modificare in pagina. Deci acest bit arata daca pagina a fost modificata sau nu la nivel de memorie. Daca nu a fost modificata, atunci nu are rost salvarea ei pe harddisc, unde exista deja aceasta pagina. Daca a fost modificata, atunci ea trebuie salvata pe harddisc.

Alegerea victimei se face conform unui algoritm de inlocuire iar plasarea in memorie conform unei anumite politici de plasare .

Algoritmi de inlocuire a paginii

Algoritmii de inlocuire a paginii au drept scop alegerea celei mai "bune" victime. Criteriul dupa care se face aceasta alegere este minimizarea ratei erorilor de pagina.

Teoretic, cel mai bun algoritm ar fi acela care alege victime dintre paginile care vor fi solicitate cel mai tarziu. Acest lucru este greu de realizat deoarece evolutia unui program nu este previzibila si de aceea raspunsul nu poate fi prevazut usor. Au existat incercari de determinare a paginilor care vor fi utilizate cel mai tarziu, In 1966, L.A.Belady a creeat un algoritm statistic care incerca, pe baze probabilistice, sa rezolve aceasta problema, dar rezultatul algoritmului nu a fost din cele mai bune. In continuare vom prezenta cei mai cunoscuti astfel de algoritmi practici.

Algoritmul FIFO

Este unul dintre cei mai simpli algoritmi, atat ca idee cat si ca implementare. Fiecarei pagini i se asociaza momentul de timp cand a fost adusa in memorie. Se realizeaza o structura de coada la care printr-un capat vor fi aduse noile pagini in memorie, in ordinea stricta a sosirii lor, iar celalalt capat va fi pentru paginile victima.

Sa luam un exemplu. Fie o situatie cu numarul de pagini virtuale 5.

Secventa de alocare a paginilor 543254154321

Rata erorilor de pagina este, pentru folosirea a trei cadre, de:

r₃=

iar pentru folosirea a patru cadre :

r₄ =

In aceste doua cazuri se observa ca pentru utilizarea a 3 cadre rata erorilor de pagina este 75% iar cand sunt 4 cadre rata erorilor creste, fiind 83%. Ne-am fi asteptat ca, odata cu cresterea numarului de cadre rata erorilor de pagina sa scada nu sa creasca. Acest fapt este cunoscut ca anomalia lui Belady si constituie unul din dezavantajele algoritmului FIFO.

Un alt dezavantaj al acestui algoritm este faptul ca o pagina frecvent utilizata va fi foarte des evacuata pe disc si reincarcata in memorie.

Algoritmul LRU (Least Recently Used)

Algoritmul LRU alege victima dintre paginile cele mai putin utilizate in ultimul timp. Algoritmul se bazeaza pe presupunerea ca pagina care a fost accesata mai putin intr-un interval de timp va fi la fel de accesata si in continuare. Ideea este de a folosi localitatea temporara a programului.

Pentru implementare este necesar sa se tina evidenta utilizatorilor paginilor si sa se ordoneze paginile dupa timpul celei mai recente referinte la ele.

Teoretic, implementarea s-ar putea face cu o coada FIFO in care o pagina accesata este scoasa din coada si mutata la inceputul ei. Totusi aceasta implementare este destul de costisitoare.

Principalul avantaj al algoritmului LRU este faptul ca el nu mai prezinta anomalia lui Belady.

Sa luam exemplul anterior, folosit la algoritmul FIFO.

Se observa ca odata cu cresterea numarului de cadre scade rata erorilor de pagina, deci anomalia Belady nu mai apare. Se asemenea este corectat si celalalt dezavantaj al algoritmului FIFO si anume la LRU sunt avantajate paginile frecvent utilizate, care sunt pastrate in memorie, ne mai fiind necesara evacuarea pe disc.

Exista mai multe feluri de implementare ale algoritmului LRU:

LRU cu contor de accese

LRU cu stiva

LRU cu matrice de referinte.

a) LRU cu contor de accese se implementeaza hard. Se utilizeaza un registru general al unitatii centrale pe post de contor. La fiecare acces la memorie, contorul va fi incrementat. La fiecare acces la o pagina, contorul este memorat in spatiul corespunzator acelei pagini in tabela de pagini. Alegerea "victimei" consta in cautarea in tabela de pagini o pagina cu cea mai mica valoare a contorului.

b) LRU cu stiva utilizeaza o stiva in care sunt pastrate numerele paginilor virtuale. Cand este referita o pagina, este trecuta in varful stivei. In felul acesta vom gasi "victima" la baza stivei.

c) LRU cu matrice de referinte utilizeaza o matrice patratica n-dimensionala, binara (cu elemente 0 si 1), unde n este numarul de pagini fizice. Initial matricea are toate elementele 0. In momentul in care se face o referinta la pagina k, se pune 1 peste tot in linia k, apoi 0 peste tot in coloana k. Numarul de unitati (de 1) de pe o linie arata ordinea de referire a paginii. Alegerea "victimei" se face in matrice linia cu cele mai putine cifre de 1, indicele acestei linii fiind numarul paginii fizice aleasa ca "victima".

7.3.Algoritmul LFU ( Least Frequently Used)

Victima va fi pagina cel mai putin utilizata.

Ca mod de implementare se foloseste un contor de accese care se incrementeaza la fiecare acces de pagina dar care nu este resetat periodic ca la LRU. "Victima" va fi pagina cu cel mai mic contor.

Principalul dezavantaj al acestei metode apare in situatia in care o pagina este utilizata des in faza initiala si apoi nu mai este utilizata de loc; ea ramane in memorie deoarece are un contor foarte mare.

7.4.Algoritmul real Paged Daemon

De obicei, sistemele de operare desemneaza un proces sistem responsabil cu implementarea si realizarea politicii de inlocuire a paginilor pentru memoria virtuala. Un astfel de proces autonom care sta in fundal si executa periodic o anumita sarcina se numeste demon (daemon). Demonul de paginare poarta numele de paged daemon. Acesta pregateste sistemul pentru evacuarea de pagini inainte ca evacuarea sa fie necesara. Obisnuit el este intr-o stare dormanta, fiind trezit de sistemul de operare atunci cand numarul cadrelor libere devine foarte mic. Dintre principalele sale sarcini amintim:

-salveaza pe disc paginile cu bitul dirty pe 1, efectuand asa numita operatie de "curatire" a paginilor;

-utilizand un algoritm sau o combinatie de algoritmi de inlocuire a paginilor, alcatuieste o lista ordonata pentru paginile ce vor fi "victime";

-decide cata memorie sa aloce pentru memoria virtuala.

7.5. Fenomenul de trashing

Atunci cand procesele folosesc mai mult timp pentru activitatea de paginare decat pentru executia propriu zisa se spune ca are loc fenomenul de trashing.

Un exemplu tipic este acela cand un proces are alocat un numar mai mic de cadre decat ii este necesar. Aceasta este o conditie necesara pentru aparitia trashingului. Deoarece toate paginile sunt necesare pentru rularea programului, procesul va incerca sa aduca din memoria externa si restul paginilor necesare. Daca nu sunt cadre libere, este posibil ca victimele sa fie chiar pagini ale procesului. Pentru acestea se vor genera din nou cereri de aduceri in memorie si astfel se poate intra la un moment dat intr-un cerc vicios, cand procesul va face numai cereri de paginare, si nu va mai executa nimic din programul sau. Acesta este, de fapt, trashingul.

Exista mai multe modalitati de a evita trashingul. Se alege un algoritm de paginare care poate fi global sau local.

Algoritmii globali permit procesului sa aleaga pentru inlocuire orice cadru, chiar daca acesta este alocat altui proces.

Algoritmii locali impun fiecarui proces sa foloseasca pentru selectie numai cadre din propriul set, numarul cadrelor asociate procesului ramanand acelasi.

Daca se utilizeaza un algoritm local, fenomenul de trashing dispare, deoarece setul de pagini asociat unui proces in memorie este influentat numai de activitatea de paginare a procesului respectiv.

7.6. Concluzii privind paginarea la cerere

Principalele avantaje ale paginarii la cerere sunt:

- programul este prezent doar partial in memorie;

se executa mai putine operatii de intrare iesire;

-la un moment dat, este necesara o cantitate mai mica de memorie;

-creste mult gradul de multiprogramare;

-in programarea la cerere nu mai este nevoie ca programatorul sa scrie overlayurile, sarcina aceasta revenind sistemului de operare.

Principalul dezavantaj este ca mecanismul de gestiune a memoriei, atat hard cat si soft, are o complexitate deosebita.