Algoritmi de înlocuire a paginilor

Notiuni generale despre algoritmii de inlocuire a paginilor

Operatia de inlocuire a paginilor este necesara atunci cand apare o asa-numita “eroare de pagina” (page fault). Trebuie mentionat ca aceasta se intampla in cazul memoriei virtuale, cand este utilizata paginarea. In acest context are loc operatia de translatare a adresei virtuale oferite de procesor intr-o adresa fizica.

Eroarea de pagina apare cand programul incearca sa acceseze o pagina virtuala care nu este prezenta in memoria fizica. Orice intrare in tabela de pagini are in componenta sa un bit de absent/prezent(valid/invalid). El tine evidenta paginilor din spatiul adreselor virtuale care sunt prezente in memoria fizica. Astfel, daca acest bit are valoarea 0, inseamna ca pagina virtuala careia ii corespunde intrarea in tabela nu se afla in memoria fizica; o referinta la aceasta pagina va avea ca rezultat o capcana- eraorea de pagina.

Cand o asemenea eroare are loc, este important rolul jucat de bitii Referit, Modificat (si ei facand parte din structura unei intrari intabela de pagini). Bitul Modificat este actualizat (setat) atunci cand datele dintr-o pagina incarcata in memorie se schimba.Necesitatea lui este evidenta cand sistemul de operare are nevoie de cadrul de pagina din memorie. Astfel, pentru M=1, continutul paginii trebuie rescris pe disc, pentru a salva schimbarile survenite. Daca M=0, inseamna ca nu au aparut modificari, iar cadrul poate fi evacuat direct, fara a salva informatia pe disc.

Bitul R (Referit) va fi setat atunci cand pagina este referita pentru scriere sau citire. Utilitatea sa : situatia in care sistemul de operare trebuie sa decida care cadru de pagina urmeaza a fi sacrificat, pentru a incarca de pe disc pagina dorita. Astfel, este de preferat sa se aleaga un cadru nereferit in locul unuia care a fost folosit, dupa cum se va vedea in continuare.

Atunci cand apare o eroare de pagina, sunt posibile 2 cazuri: fie avem cadre de pagina libere, fie nu. In cea de-a doua situatie, sistemul de operare trebuie sa elimine pagina cea mai putin probabil sa fie folosita in curand, realizand procesul de inlocuire. Acest schimb de pagini intre memoria principala si disc, realizat doar la aparitie unei erori de pagina, poarta numele de paginare la cerere.

Pasii unui algoritm PRA:

1. Se alege un cadru de pagina care este determinat , conform unui algoritm, ca fiind cel mai putin necesar in viitor;

2. Daca a fost modificat (M=1), se scrie pe disc, daca nu, pur si simplu se evacueaza

3. Se incarca noua pagina de pe disc

4. Se actualizeaza tabelele de pagini, bitul Prezent(invalid inlocuit cu valid) este setat

5. Se restarteaza instructiunea care a cauzat eroarea de pagina

Tipuri de algoritmi PRU

Din punct de vedere al politicii de inlocuire se remarca doua tipuri de algoritmi de inlocuire a paginilor, si anume:

- Algoritmi de inlocuire statici / ficsi

- Algoritmi de inlocuire dinamici / variabili

I. Algoritmii de inlocuire statici

Pentru acesti algoritmi, fiecarui proces i se aloca un numar fix de pagini de memorie la inceperea executiei, el nesolicitand spatiu de memorie suplimentar mai tarziu.

1.1 Algoritmul optimal de înlocuire a paginilor

Fiecare pagină se etichetează cu numărul de instrucţiuni ce se vor executa până când

este referită pagina pentru prima dată. Atunci când trebuie eliminată o pagină din memorie,

se selectează pagina cu cea mai mare valoare a etichetei.

Deşi acest algoritm generează cea mai mică rată de pagini invalidate, el nu poate fi

implementat, deoarece sistemul de operare nu poate determina când urmează să fie referită o

pagină. Acest algoritm este utilizat doar pentru studii comparative. De exemplu, pentru un

algoritm care nu este optimal, este util de ştiut că are performanţe cu 12% mai slabe decât cele

optimale.