Structuri de date pentru paginare la cerere - UNIX

Structuri de date pentru paginare la cerere - UNIX

Nucleul contine 4 structuri de date majore pentru a asigura functiile de nivel scazut pentru gestiunea memoriei si paginarea la cerere: intrarile din tabela de pagini (page table entries), descriptorii de bloc disc, tabela pfdata (page frame data table) si tabela de folosire a dispozitivului de swap (swap use table). Nucleul aloca spatiu pentru tabela pfdata o singura data pe durata de viata a sistemului iar pentru celelalte structuri aloca pagini de memorie dinamic.

Asa cum s-a aratat in capitolul 7 o regiune contine tabele de pagini pentru a accesa memoria fizica. Fiecare intrare a unei tabele de pagini (Figura 12.2)contine adresa fizica a paginii, bitii de protectie care indica daca procesul poate citi, scrie sau executa pagina si urmatoarele campuri de biti pentru asigurarea paginarii la cerere:

validare;

referinta ;

modificare

copiere la cerere;

varsta.

Nucleul seteaza bitul validare pentru a indica legalitatea continutului unei pagini, dar aceasta nu inseamna ca referirea paginii este ilegala daca bitul validare este resetat.

Bitul referinta indica daca un proces a referit recent o pagina, iar bitul modificare indica daca un proces a modificat recent continutul unei pagini. Bitul copiere la scriere, utilizat in apelul sistem fork, indica faptul ca nucleul trebuie sa creeze o noua copie a paginii atunci cand un proces ii modifica continutul. In sfarsit, nucleul manipuleaza bitii varsta pentru a indica cat timp a facut parte o pagina din setul de lucru al unui proces.

Figura 12.2 Intrari in tabela de pagini si descriptori de bloc disc

De retinut ca nucleul manipuleaza bitii validare, copiere la scriere si varsta, iar bitii referinta si modificare sunt setati de hardware. Fiecare intrare in tabela de pagini este asociata cu un descriptor de bloc disc, care descrie copia de pe disc a paginii virtuale (Figura 12.2). Procesele care partajeaza o regiune acceseaza de aceea intrari comune in tabela de pagini si descriptori comuni de bloc disc. Continutul unei pagini virtuale se poate gasi intr-un anumit bloc din zona de swap, intr-un fisier executabil sau poate sa nu fie pe un dispozitiv de swap. Daca pagina se gaseste pe un dispozitiv de swap, descriptorul de bloc disc contine numarul dispozitivului logic si numarul blocului care contine pagina respectiva. Daca pagina este continuta intr-un fisier executabil, descriptorul de bloc disc contine numarul blocului logic din fisier care contine pagina; nucleul poate translata rapid acest numar in adresa disc a acestuia. Descriptorul de bloc disc indica doua conditii speciale setate pe parcursul apelului sistem exec: daca o pagina este marcata "incarcare la cerere" (demand fill) sau "initializare la cerere" (demand zero). Aceste conditii vor fi explicate in paragraful 12.3.

Tabela pfdata descrie fiecare pagina de memorie fizica si este indexata prin numarul paginii. Campurile unei intrari in tabela pfdata sunt:

Starea paginii, care indica daca pagina este pe dispozitivul de swap sau intr-un fisier executabil, daca DMA citeste datele de pe dispozitivul de swap sau daca pagina poate fi reasignata;

Numarul de procese care refera pagina. Contorul de referinte indica numarul intrarilor valide din tabela de pagini care refera o anumita pagina. Acesta poate diferi de numarul de procese care folosesc in comun regiunile care contin pagina.

Numarul dispozitivului logic (de swap sau sistem de fisiere) si numarul blocului care contine o copie a paginii.

Pointeri catre alte intrari in tabela pfdata ,intrari care sunt inlantuite intr-o lista de pagini libere si intr-o coada hash (de dispersie), asemanatoare celor pentru buffer-le cache.

Lista intrarilor libere este o memorie cache de pagini care sunt disponibile pentru reasignare. Aceasta lista permite nucleului sa evite operatiile de citire a dispozitivului de swap care nu sunt necesare. Nucleul aloca noi pagini din lista in ordinea paginilor cel mai putin folosite recent. Nucleul inlantuie intrarile in tabela pfdata in coada hash tinand cont de numarul dispozitivului de swap si numarul blocului.

In acest fel nucleul poate localiza rapid o pagina daca aceasta se afla in memorie. Pentru a asigna o pagina fizica unei regiuni, nucleul sterge o intrare libera din capul listei inlantuite, actualizeaza numarul dispozitivului de swap si numarul blocului si o pune in lista hash corespunzatoare.

Tabela de folosire a dispozitivului de swap contine cate o intrare pentru fiecare pagina de pe dispozitivul de swap. Aceasta intrare contine un contor de referinta care indica cate intrari din tabela de pagini pointeaza catre o pagina de pe dispozitivul de swap.

Figura 12.3 ilustreaza relatiile existente intre intrarile in tabela de pagini, descriptorii de bloc disc, intrarile din tabela pfdata si tabela de folosire a dispozitivului de swap. Adresa virtuala 1493k a procesului este mapata intr-o intrare din tabela de pagini care pointeaza catre pagina fizica 794; descriptorul de bloc disc pentru intrarea din tabela de pagini arata ca exista o copie a paginii pe blocul disc 2743 de pe dispozitivul de swap 1. Intrarea in tabela pfdata pentru pagina fizica 794 arata, de asemenea, ca o copie a paginii exista pe blocul disc 2743 de pe dispozitivul de swap 1 iar contorul sau de referinte din memoria interna este 1. Contorul tabelei de folosire a dispozitivului de swap pentru pagina virtuala este 1, insemnand ca o singura intrare din tabela de pagini printeaza catre copia de pe dispozitivul de swap.

Figura 12.3 Relatii intre structurile de date pentru paginarea la cerere