GESTIUNEA MEMORIEI PRIN PAGINARE LA CERERE

GESTIUNEA MEMORIEI PRIN PAGINARE LA CERERE

Masinile a caror arhitectura a memoriei este bazata pe pagini si al caror UCP are instructiuni restartabile (daca un calculator executa o parte a unei instructiuni si genereaza o intrerupere de pagina, UCP trebuie sa reia instructiunea dupa tratarea intreruperii deoarece calculele intermediare facute inainte de intreruperea de pagina pot fi pierdute) pot admite un nucleu care implementeaza un algoritm de paginare la cerere pentru realizarea transferului intre memoria principala si un dispozitiv de swap. Sistemele cu paginare la cerere elimina limitarea marimii proceselor impusa de marimea memoriei fizice disponibile in sistem. De exemplu, masinile care contin 1 sau 2 Mo de memorie fizica pot executa procese ale caror dimensiuni pot fi de 4 sau 5 Mo. Nucleul impune insa o limitare a marimii virtuale a unui proces, dependenta de marimea memoriei virtuale pe care o poate adresa masina. Deoarece un proces poate sa nu incapa in memoria fizica, nucleul trebuie sa incarce dinamic partile sale relevante in memorie si sa le execute chiar daca alte parti ale acestuia nu sunt incarcate. Paginarea la cerere este transparenta pentru programele utilizator, exceptie facand marimea virtuala permisa pentru un proces.

Procesele au tendinta sa execute instructiuni din portiuni mici ale regiunii de text, astfel incat programul cicleaza si apeleaza subrutine in mod frecvent. Acest principiu este cunoscut sub denumirea de proncipiul 'localitatii'. Denning a formalizat notiunea de set de lucru al unui proces, care reprezinta setul de pagini pe care procesul le-a accesat in ultimele sale n referiri de memorie; numarul n este denumit fereastra setului de lucru. Deoarece setul de lucru este o fractiune a procesului, in memoria principala se pot gasi simultan mai multe procese decat intr-un sistem bazat pe swapping. Cand un proces adreseaza o pagina care nu este in setul de lucru se produce o intrerupere de pagina; pentru tratarea intreruperii, nucleul actualizeaza setul de lucru, incarcand in acesta alte pagini de pe un dispozitiv secundar daca este necesar.

Figura 12.1 descrie o secventa de referiri de pagina pe care o poate face procesul, ilustrand setul de lucru pentru diferite marimi ale ferestrei si urmand politica de inlocuire a paginii celei mai putin folosite recent. Pe timpul executiei procesului, setul sau de lucru se schimba, in functie de secventa de referinte de memorie pe care acesta o executa; o dimensiune mai mare a ferestrei presupune un set de lucru mai mare, implicand faptul ca procesul nu se va mai intrerupe asa des. Nu este practic sa se implementeze un model de set de lucru pur, deoarece este foarte greu sa se retina ordinea referirilor de pagina.

Totusi, sistemele aproximeaza un model de set de lucru prin setarea bitului referinta ori de cate ori un proces acceseaza o pagina si prin esantionarea periodica a referintelor la memorie: daca o pagina a fost referita recent, ea face parte din setul de lucru; altfel, ea sta in memorie pana cand devine eligibila pentru incarcare.

Figura 12.1 Setul de lucru al unui proces

Cand un proces acceseaza o pagina care nu este in setul de lucru, se produce o intrerupere de pagina (intrerupere de validitate). Nucleul suspenda executia procesului pana cand citeste pagina in memorie si o face accesibila pentru proces. Dupa incarcarea paginii in memorie, procesul restarteaza instructiunea pe care o executa atunci cand a aparut intreruperea de pagina. Astfel, implementarea unui subsistem de paginare are doua parti: evacuarea paginilor folosite mai putin pe un dispozitiv de swap si tratarea intreruperilor de pagina. Aceasta descriere generala a schemelor de paginare se extinde si la sistemele non-UNIX.

12.1 Structuri de date pentru paginare la cerere

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 numerul 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

12.2 Fork intr-un sistem de paginare

Asa cum s-a explicat in paragraful 8.1, nucleul duplica fiecare regiune a procesului parinte pe timpul apelului sistem fork si le ataseaza procesului fiu. De obicei, nucleul unui sistem cu swapping face o copie fizica a spatiului de adresa al parintelui, ceea ce reprezinta o operatie greoaie in majoritatea cazurilor, deoarece procesele apeleaza adesea exec imediat dupa apelul sistem fork si elibereaza imediat memoria pe care tocmai au copiat-o. La sistemul de paginare al System V, nucleul evita copierea paginii prin manipularea tabelelor de regiuni, intrarilor din tabelele de pagini si intrarilor din pfdata: pur si simplu este incrementat contorul de referinta al regiunilor folosite in comun.

Pentru regiunile private, ca cele de date si stiva, acesta aloca totusi o noua intrare in tabela de regiuni si o noua tabela de pagini iar apoi examineaza fiecare intrare din tabela de pagini a procesului parinte: daca o pagina este valida, incrementeaza contorul de referinte in intrarea din tabela pfdata, indicand numarul de procese care folosesc in comun pagina prin intermediul unor regiuni diferite (in opozitie cu numarul care indica folosirea in comun a paginii prin partajarea regiunii). Daca pagina exista pe dispozitivul de swap, nucleul incrementeaza contorul de referinte al tabelei de folosire a dispozitivului de swap pentru pagina respectiva.

Pagina poate fi acum referita din ambele regiuni care o folosesc in comun pana cand un proces scrie in ea. Nucleul copiaza apoi pagina astfel incat fiecare regiune are propria versiune. Pentru aceasta, nucleul seteaza bitul 'copiere la scriere' pentru fiecare intrare a tabelei de pagini din regiunile private ale procesului parinte si procesului fiu in timpul apelului sistem fork. Daca oricare dintre procese scrie in pagina, se produce o intrerupere de protectie, iar in tratarea acesteia, nucleul face o noua copie a paginii pentru procesul care a generat intreruperea. Copierea fizica a paginii este in acest fel amanata pana cand un proces are intr-adevar nevoie de ea.

Figura 12.4 prezinta structurile de date atunci cand un proces executa apelul sistem fork. Procesele isi impart accesul la tabela de pagini a regiunii de text T folosita in comun, astfel incat contorul de referinte al regiunii este 2 si contorul de referinte al tabelei pfdata pentru paginile din regiunea de text este 1. Nucleul aloca o noua regiune de date pentru procesul fiu, C1, copie a regiunii P1 din procesul parinte. Intrarile din tabela de pagini ale celor doua regiuni sunt identice, asa cum este ilustrat de intrarea pentru adresa virtuala 97.

Intrarile din tabela de pagini pointeaza catre intrarea 613 din tabela pfdata, al carei contor de referinte este 2, indicand faptul ca doua regiuni refera pagina.

Figura 12.4 Structurile de date la executarea apelului sistem fork

Implementarea apelului sistem fork in sistemul BSD face o copie fizica a paginilor procesului parinte.

Admitand imbunatatirea performantelor prin faptul ca nu trebuie sa se faca o copie, totusi, sistemul BSD contine si apelul sistem vfork, care presupune ca orice proces fiu va invoca imediat apelul sistem exec la revenirea din apelul sistem. Acesta vfork nu copiaza tabele de pagini, deci este mai rapid decat apelul sistem fork din implementarea System V.

Vom considera exemplul din figura 12.5 pentru a prezenta unele situatii periculoase care pot aparea la folosirea necorespunzatoare a apelului sistem vfork:

Dupa apelul sistem vfork, procesul-fiu nu apeleaza exec, dar reseteaza variabilele global si local dupa care se termina. Sistemul garanteaza ca procesul parinte este suspendat pana cand procesul fiu apeleaza exec sau se termina. Cand procesul parinte reia in sfarsit executia, gaseste valorile celor doua variabile diferite de cele dinainte de apelul sistem vfork. Pot aparea efecte mai spectaculoase daca procesul fiu revine din functia care a apelat vfork.   

Figura 12.5 Apelul sistem vfork si alterarea memoriei alocate procesului

12.3 Exec intr-un sistem cu paginare

Cand un proces invoca apelul sistem exec, nucleul citeste fisierul executabil in memorie din sistemul de fisiere, asa cum s-a aratat in capitolul 8. Intr-un sistem cu paginare la cerere, fisierul executabil poate fi totusi prea mare ca sa incapa in memoria principala.

De aceea, nucleul nu preasigneaza memorie pentru fisierul executabil, dar genereaza o intrerupere, asignandu-i cata memorie are nevoie. Acesta asigneaza mai intai tabele de pagini si descriptori de bloc disc pentru fisierul executabil, marcand intrarile in tabela de pagina "incarcare la cerere" (pentru date non-BSS) sau "initializare cu zero" (pentru date BSS ). Urmand o varianta a algoritmului read pentru citirea fisierului in memorie, procesul produce o intrerupere de validitate (Paragraful 12.5.1) la citirea fiecarei pagini.    

Rutina de tratare a intreruperii retine daca pagina este marcata"incarcare la cerere", insemnand ca imediat va fi rescris continutul sau cu continutul fisierului executabil, astfel incat nu este necesara stergerea sa, sau daca este marcata " initializare cu zero", situatie in care continutul sau trebuie sa fie sters.

Aceasta schema prezinta si unele dificiente. In primul rand, un proces produce o intrerupere de pagina cand citeste fiecare pagina a fisierului executabil, chiar daca nu va trebui sa acceseze niciodata pagina respectiva. In al doilea rand, procesul "page-stealer" poate sa evacueze pagini din memorie inainte de terminarea apelului sistem exec, rezultand in plus doua operatii de transfer pentru fiecare pagina daca procesul solicita pagina respectiva curand. Pentru a face apelul sistem exec mai eficient, nucleul poate solicita pagini direct din fisierul executabil daca datele sunt aliniate corespunzator dupa cum indica numarul magic. Totusi, folosirea algoritmilor standard pentru accesarea unui fisier (ca,de exemplu, bmap), ar face prea costisitoare paginarea la cerere prin blocurile de indirectare din cauza acceselor multiple la buffere-le cache necesare pentru citirea unui bloc. Nucleul seteaza diferitii parametri I/O in zona u area pe timpul apelului sistem read. Daca un proces provoaca o intrerupere de pagina pe timpul unui apel sistem read cand incearca sa copieze datele in spatiul utilizator, acesta trebuie sa rescrie aceste campuri in zona u area pentru a citi pagina din sistemul de fisiere. De aceea, nucleul nu poate folosi algoritmii obisnuiti pentru intreruperile de pagina. Algoritmii sunt reentranti in cazurile obisnuite deoarece fiecare proces are o zona u area proprie iar procesul nu poate executa simultan mai multe apeluri sistem.

Figura 12.6 Maparea unui fisier intr-o regiune

Pentru a incarca o pagina direct din fisierul excutabil, nucleul gaseste toate numerele blocurilor disc ale fisierului executabil cand apeleaza exec si ataseaza lista lor la inodul fisierului.

Cand seteaza tabelele de pagini pentru un astfel de fisier executabil, nucleul marcheaza descriptorul de bloc disc cu numarul blocului logic (pornind de la blocul 0 din fisier ) care contine pagina; rutina de tratare a intreruperii de validitate foloseste aceasta informatie mai tarziu pentru a incarca pagina din fisier. Figura 12.6 prezinta un aranjament tipic, in care descriptorul de bloc disc indica faptul ca pagina se gaseste la deplasamentul de bloc logic 84 in fisier. Nucleul urmareste pointerul de la regiune catre inod si gaseste numarul blocului disc corespunzator (279).

12.4. Procesul page stealer

Procesul page stealer este un proces al nucleului care evacueaza din memorie paginile care nu fac parte mult timp din setul de lucru al unui proces. Nucleul creaza procesul page stealer pe timpul initializarii sistemului si-l apeleaza pe toata durata de viata a sistemului, la nevoie. El examineaza fiecare regiune activa, care nu este blocata, lasand regiunile blocate in expectativa pentru a le examina la urmatoarea parcurgere a listei de regiuni, si incrementeaza apoi campul varsta al tuturor paginilor valide.

Nucleul blocheaza o regiune cand un proces produce o intrerupere pentru o pagina din regiune, astfel incat procesul page stealer nu poate evacua pagina care a generat intreruperea.

Pentru o pagina din memorie exista doua stari: pagina a fost incarcata recent si nu este inca eligibila pentru swapping, sau pagina este eligibila pentru swapping si este disponibila pentru reasigurarea la alte pagini virtuale. Prima stare arata ca un proces a referit recent pagina, ea fiind deci in setul sau de lucru. Unele masini seteaza bitul referinta cand acceseaza o pagina, insa metodele software pot suplini lipsa acestei facilitati daca hardware-ul nu dispune de ea. Procesul page stealer pune pe 0 bitul referinta al paginilor referite si retine cate examinari au fost facute de la ultima referire a paginii. Deci prima stare consta in cateva substari corespunzatoare numarului de examinari pe care le face procesul page stealer pana cand pagina devine eligibila pentru evacuare (Figura 12.7). Cand acest numar depaseste o valoare de prag, nucleul trece pagina in cea de-a doua stare, gata pentru evacuare. Perioada maxima care poate trece pana cand pagina devine eligibila pentru evacuare este dependenta de implementare, si este limitata de numarul de biti disponibili in intrarea din tabela de pagini.

Figura 12.7 Diagrama starilor in functie de timpul de rezidenta

al paginilor

Figura 12.8 prezinta interactiunea dintre procesel care acceseaza o pagina de catre procese si examinarile facute de procesul page stealer. Se pleaca de la pagina incarcata in memorie, figura ilustrand numarul de examinari ale procesului page stealer intre referirile la memorie. Un proces a referit pagina dupa a doua examinare, scazand astfel varsta aceteia la 0. In mod similar, un proces a referit din nou pagina dupa inca o examinare. In sfarsit, procesul page stealer examineaza pagina de trei ori fara sa intervina vreo referire si evacueaza pagina.

Figura 12.8 Exemplu de imbatranire a unei pagini

Daca doua sau mai multe procese folosesc in comun o regiune, ele actualizeaza bitii referinta ai aceluiasi set de intrari din tabela de pagini. In acest fel, paginile pot fi parti ale seturilor de lucru ale mai multor procese, dar acest fapt nu are importanta pentru procesul page stealer. Daca o pagina face parte din setul de lucru al unui proces, ea ramane in memorie; astfel pagina este eligebila pentru evacuare. Nu are importanta daca o regiune are mai multe pagini in memorie decat alta; procesul page stealer nu incearca sa evacueze un numar egal de pagina din toate regiunile active.

Nucleul trezeste procesul page stealer atunci cand memoria libera disponibila in sistem ajunge la un nivel minim, iar acesta evacueaza pagini pana cand memoria libera disponibila in sistem ajunge la un nivel maxim. Valorile nivelelor descrise mai sus pot fi configurate de administrator in vederea cresterii performantelor sistemului.

Cand procesul page stealer decide sa evacueze o pagina, acesta verifica daca exista o copie a paginii pe dispozitivul de swap. Exista trei posibilitati:

Daca nu exista o copie a paginii pe dispozitivul de swap, nucleul planifica pagina pentru evacuare: procesul page stealer pune pagina intr-o lista a paginilor care trebuiesc evacuate si continua; din punct de vedere logic, evacuarea este terminata. Cand lista atinge o limita (dependenta de posibilitatile controlerului de disc), nucleul scrie paginile pe dispozitivul de swap.

Daca exista deja o copie a paginii pe dispozitivul de swap si nici un proces nu i-a modificat continutul in memorie (in intrarea din tabela de pagina bitul modificare este sters), nucleul sterge bitul validare al intrarii din tabela de pagini, decrementeaza contorul de referinte al intrarii din tabela pfdata si pune intrarea intr-o lista de intrari libere in vederea unei alocari viitoare.

Daca exista o copie a paginii pe dispozitivul de swap, dar un proces a modificat continutul paginii in memorie, nucleul planifica pagina pentru a fi evacuata, ca mai sus, si elibereaza spatiul pe care pagina il ocupa pe dispozitivul de swap.

Procesul page stealer copiaza pagina pe dispozitivul de swap in cazurile 1 si 3. Pentru a ilustra diferentele dintre ultimele doua cazuri, sa presupunem ca o pagina este pe dispozitivul de swap si este incarcata in memoria principala dupa ce un proces genereaza o intrerupere de validitate. Sa presupunem ca nucleul nu sterge automat copia de pe disc. Eventual, procesul page stealer decide sa evacueze din nou pagina.

Daca nici un proces nu a scris in pagina de cand aceasta a fost incarcata, copia din memorie este identica cu cea de pe disc si nu este necesar ca pagina sa fie scrisa din nou pe dispozitivul de swap. Daca totusi un proces a scris in pagina, copia din memorie difera de cea de pe disc, astfel ca nucleul trebuie sa scrie pagina pe dispozitivul de swap, dupa ce in prealabil elibereaza spatiul ocupat de pagina pe dispozitivul de swap.

Procesul page stealer completeaza o lista cu pagini de evacuat, posibil din regiuni diferite, si apoi, cand lista este plina, le evacueaza pe dispozitivul de swap. Nu toate paginile unui proces trebuie sa fie evacuate: de exemplu, unele pagini s-ar putea sa nu fi stat suficient timp incarcate. Aceasta difera functie de politica procesului de evacuare/incarcare, care evacueaza din memorie fiecare pagina a procesului, dar metoda de scriere a datelor pe dispozitivul de swap este identica cu cea descrisa pentru sistemele cu swapping. Daca nici un dispozitiv de swap nu contine suficient spatiu contiguu, nucleul evacueaza cate o pagina, consumand astfel mai mult timp. Exista o mai mare fragmentare a spatiului pe un dispozitiv de swap in cazul unei scheme de evacuare prin paginare la cerere decat in cazul swapping-ului deoarece nucleul evacueaza blocuri de pagini dar incarca numai cate o pagina.

Cand nucleul scrie o pagina pe dispozitivul de swap, el pune pe zero bitul validare din intrarea in tabela de pagini si decrementeaza contorul de utilizare al intrarii din tabela pfdata. Daca contorul ajunge la zero, pune intrarea din tabela pfdata la sfarsitul listei inlantuite de intrari libere in vederea reasignarii ei. Daca contorul nu este zero, atunci cateva procese folosesc in comun pagina ca rezultat al unui apel sistem fork anterior, dar nucleul evacueaza totusi pagina.

In sfarsit, nucleul aloca spatiu pentru evacuare, salveaza adresa de evacuare in descriptorul de bloc disc si incrementeaza contorul tabelei de folosire a dispozitivului de swap pentru pagina respectiva. Daca un proces produce o intrerupere de pagina in timp ce pagina este in lista paginilor libere, nucleul poate totusi recupera pagina din memorie in loc sa o recupereze de pe dispozitivul de swap.

De exemplu, sa presupunem ca procesul page stealer evacueaza 30, 40, 50 si 20 de pagini din procesele A, B, C si respectiv D, si ca scrie 64 de pagini pe dispozitivul de swap intr-o operatie de scriere pe disc. Figura 12.9 prezinta secventa operatiilor de evacuare a paginilor care ar aparea daca programul page stealer ar examina paginile proceselor in ordinea A,B,C si D. Procesul page stealer aloca spatiu pentru 64 de pagini pe dispozitivul de swap si evacueaza 30 de pagini ale procesului A si 34 de pagini ale procesului B. Aloca apoi spatiu pe dispozitivul de swap pentru alte 64 de pagini si evacueaza cele 6 pagini ramase de la procesul B, 50 de pagini ale procesului C si 8 pagini ale procesului D. Cele doua zone de pe dispozitivul de swap pentru cele doua operatii de evacuare nu trebuie sa fie contigue. Procesul page stealer pastreaza cele 12 pagini ramase ale procesului D intr-o lista a paginilor ce trebuiesc evacuate, dar nu le va evacua pana cand lista nu se umple.

Figura 12.9 Alocarea spatiului de evacuare intr-o schema de paginare

In concluzie, exista doua faze in evacuarea unei pagini din memorie. In prima faza, procesul page stealer gaseste pagina eligibila pentru evacuare si plaseaza numarul paginii in lista de pagini care trebuiesc evacuate. In cea de-a doua faza, nucleul copiaza pagina pe dispozitivul de swap, pune pe zero bitul validare in intarea din tabela de pagini, decrementeaza contorul de referinte al intrarii din tabela pfdata si plaseaza aceasta intrare la sfarsitul listei de intrari libere daca contorul sau de referinte este zero. Continutul paginii libere este valid in memorie pana cand pagina este reasignata.

12.5. Intreruperi de pagina

Sistemul poate produce doua tipuri de intreruperi de pagina: de validitate si de protectie. Deoarece rutinele de tratare a intreruperilor de pagina trebuie sa citeasca pagina de pe disc in memorie si sa astepte pe parcursul operatiilor I/O, rutinele de tratare a intreruperilor reprezinta o exceptie de la regula generala potrivit careia rutinele de tratare a intreruperilor nu se pot pune in asteptare. Totusi, deoarece rutina se pune in asteptare in contextul procesului care a cauzat intreruperea, intreruperea este legata de procesul in executie; prin urmare, nu sunt puse in asteptare procese in mod arbitrar.

Intreruperi de validitate

Daca un proces incearca sa acceseze o pagina al carei bit validare nu este setat, apare o intrerupere de validitate si nucleul apeleaza rutina de tratare a intreruperii de validitate (Figura 12.10).

Figura 12.10 Algoritmul rutinei de tratare a intreruperii de validitate

Pentru paginile care sunt in afara spatiului de adrese virtuale al procesului bitul validare nu este setat, si nu este setat nici pentru acele pagini care sunt in spatiul de adrese virtuale al procesului dar nu au momentan asignate pagini fizice. Hardware-ul informeaza nucleul despre adresele virtuale accesate pentru ca aceasta sa produca o intrerupere de pagina, iar nucleul gaseste intrarea din tabela de pagini si descriptorul de bloc disc pentru pagina respectiva. Nucleul blocheaza regiunea care contine intrarea in tabela de pagini pentru a preveni conditiile de concurenta care ar putea sa apara daca procesul page stealer incearca sa evacueze pagina. Daca descriptorul de bloc disc nu are nici o inregistrare referitoare la pagina care a cauzat intreruperea, incercarea de a referi memoria este invalidata iar nucleul emite semnalul 'violare de segmentare' catre procesul respectiv. Este aceeasi procedura pe care o urmeaza un sistem cu swapping cand un proces refera o adresa invalida, cu diferenta ca acesta recunoaste imediat eroarea deoarece toate paginile legale sunt rezidente in memorie. Daca referinta la memorie a fost corecta, nucleul aloca o pagina de pe dispozitivul de swap sau din fisierul executabil.

Figura 12.11 Aparitia intreruperilor de validitate

Pagina care a cauzat intreruperea se poate gasi in una din urmatoarele stari:

1. in zona de swap si nu in memorie;

2. in lista de pagini libere in memorie;

3. intr-un fisier executabil;

4. marcata ' incarcare la cerere ';

5. marcata ' initializare cu zero '.

Sa consideram in continuare fiecare din aceste cazuri. Daca o pagina este pe dispozitivul de swap si nu in memorie (cazul 1), ea a fost candva in memoria principala insa a fost evacuata de procesul page stealer. In descriptorul de bloc disc, nucleul gaseste dispozitivul de swap si numarul blocului pe care se gaseste pagina si verifica daca pagina este in memoria cache. Nucleul actualizeaza intrarea din tabela de pagini astfel incat aceasta sa printeze catre pagina care urmeaza sa fie citita, pune intrarea din tabela pfdata in lista hash in vederea sporirii vitezei de executie a rutinei de tratare a intreruperii si apoi citeste pagina de pe dispozitivul de swap. Procesul care produce intreruperea se pune in asteptare pana cand se termina operatiile I/O, moment in care nucleul trezeste alte procese care asteptau sa fie citit continutul paginii.

De exemplu, sa consideram intrarea din tabela de pagini pentru adresa virtuala 66k din figura 12.11. Daca un proces genereaza o intrerupere de validitate atunci cand acceseaza pagina, rutina de tratare a intreruperii examineaza descriptorul de bloc disc si constata ca pagina este continuta in blocul 847 al dispozitivului de swap (presupunem ca exista doar un asemenea dispozitiv). De aici rezulta ca adresa virtuala este corecta. Rutina de tratare a intreruperii cauta apoi pagina in memoria cache, dar nu o gaseste. Deci, nu exista o copie a paginii virtuale in memorie si rutina va trebui sa o citeasca de pe dispozitivul de swap. Nucleul asigneaza pagina 1776 (Figura 12.12), citeste continutul paginii virtuale de pe dispozitivul de swap in noua pagina si actualizeaza intrarea din tabela de pagini pentru a referi pagina 1776. In final, actualizeaza descriptorul de bloc disc pentru a indica faptul ca pagina este inca evacuata, si intrarea din tabela pfdata pentru pagina 1776 pentru a indica faptul ca blocul 847 de pe dispozitivul de swap contine o copie identica a paginii virtuale.

Figura 12.12 Dupa incarcarea paginii in memorie

Nucleul nu are de facut totdeauna o operatie I/O cand apare o intrerupere de validitate, chiar daca descriptorul de bloc disc indica faptul ca pagina este evacuata (cazul 2 ).Este posibil ca nucleul sa nu fi reasignat niciodata pagina fizica dupa ce a evacuat-o sau ca alt proces sa fi produs o intrerupere pentru pagina virtuala, asignand pentru ea o alta pagina fizica; in fiecare caz, rutina de tratare a intreruperii gaseste pagina in memoria cache de pagini si pune numarul blocului in descriptorul de bloc disc. Rutina actualizeaza intrarea din tabela de pagini pentru a pointa catre pagina tocmai gasita, incrementeaza contorul de referinte al acesteia si sterge pagina din lista paginilor libere, daca este necesar. De exemplu, sa presupunem ca un proces genereaza o intrerupere cand acceseaza adresa virtuala 64k din figura 12.11. Cautand pagina in memoria cache, nucleul gaseste ca intrarea 1861 a tabelei pfdata este asociata cu blocul disc 1206. El seteaza intrarea din tabela de pagini pentru adresa virtuala 64k sa pointeze catre pagina 1861, si apoi seteaza bitul validare

. Numarul de bloc disc asociaza astfel intrarea in tabela de pagini unei intrari in tabela pfdata, ceea ce explica salvarea acestuia in ambele tabele.

In mod similar, rutina de tratare a intreruperii nu trebuie sa citeasca pagina in memorie daca alt proces a generat o intrerupere pentru aceeasi pagina, dar nu a terminat inca incarcarea acesteia in memorie. Rutina de tratare gaseste blocata regiunea care contine intrarea in tabela de pagini ca urmare a unei alte instante a rutinei de tratare a intreruperii. De aceea, se pune in asteptare pana la terminarea celelalte instante a rutinei, gaseste pagina valida si se termina. Un astfel de scenariu este ilustrat in figura 12.13.

Figura 12.13 Dubla intrerupere de pagina

Daca nu exista o copie a paginii pe dispozitivul de swap, dar aceasta exista in fisierul executabil ( cazul 3 ), nucleul citeste pagina din fisierul original. Rutina de tratare a intreruperii examineaza descriptorul de bloc disc, gaseste numarul blocului logic din fisier care contine pagina, si inodul asociat intrarii din tabela de regiuni. Numarul blocului logic este folosit ca deplasament intr-o lista de numere de blocuri disc atasata inodului pe timpul apelului sistem exec. Cunoscand numarul blocului disc, nucleul citeste pagina in memorie. De exemplu, descriptorul de bloc disc pentru adresa virtuala 1k din figura 12.11 ilustreaza faptul ca pagina este continuta in blocul logic 3 din fisierul executabil.

Daca un proces genereaza o intrerupere de pagina pentru o pagina marcata 'incarcare la cerere ' sau 'initializare cu zero' (cazurile 4 si 5), nucleul aloca o pagina libera in memorie si actualizeaza intrarea corespunzatoare din tabela de pagini. Pentru pagina marcata ' initializare cu zero ', nucleul umple toata pagina cu '0'. In final, sterge indicatoarele ' initializare cu zero' si 'incarcare la cerere ': pagina este acum valida in memorie iar continutul sau nu este duplicat pe dispozitivul de swap sau in sistemul de fisiere. Aceasta s-ar intampla la accesarea adreselor virtuale 3k si 65k din figura 12.11: nici un proces nu a accesat paginile de cand s-a executat apelul sistem exec.

Rutina de tratare a intreruperii de validare se incheie cu setarea bitului validare al paginii si cu stergerea bitului modificare. Aceasta recalculeaza apoi prioritatea procesului deoarece a trebuit sa se puna in asteptare la o prioritate de nivel nucleu, obtinand astfel un avantaj incorect de planificare la revenirea in modul utilizator. In final, daca se revine in modul utilizator, verifica daca s-au primit semnale pe timpul tratarii intreruperii de pagina.

Intreruperi de protectie

Al doilea fel de intrerupere pe care o poate produce un proces este intreruperea de protectie ceea ce inseamna ca procesul a accesat o pagina valida dar bitii de permisiune asociati paginii nu permit accesul la aceasta (sa ne amintim exemplul din figura 12.11, in care un proces incearca sa scrie in spatiul sau de text). Un proces poate, de asemenea, produce o intrerupere de protectie atunci cand incearca sa scrie o pagina al carei bit copiere la scriere a fost setat pe timpul apelului sistem fork. Nucleul trebuie sa determine daca permisiunea de acces a fost refuzata deoarece pagina are setat bitul copiere la scriere sau daca s-a intamplat ceva ilegal.

Hardware-ul furnuzeaza rutinei de tratare a intreruperii de protectie adresa virtuala la care a aparut intreruperea, iar aceasta gaseste regiunea si intrarea din tabela de pagini corespunzatoare (Figura 12.14). Rutina va bloca regiunea astfel incat procesul page stealer sa nu poata evacua pagina cat timp opereaza cu ea rutina de tratare. Daca aceasta determina ca intreruperea a fost cauzata de faptul ca a fost setat bitul copiere la scriere, si daca pagina este folosita in comun cu alte procese, nucleul aloca o pagina noua si copiaza in aceasta continutul vechii pagini; celelalte procese isi mentin referintele la pagina veche.

Figura 12.14 Algoritmul rutinei de tratere a intreruperii de protectie

Dupa copierea paginii si actualizarea intrarii din tabela de pagini, nucleul decrementeaza contorul de referinte al vechii intrari din tabela pfdata. Figura 12.15 ilustreaza urmatorul scenariu: trei procese folosesc in comun pagina fizica 828. Procesul B scrie pagina dar produce o intrerupere de protectie deoarece bitul ' copiere la scriere ' este setat.

Rutina de tratare a intreruperii de protectie aloca pagina 786, copiaza continutul paginii 828 in noua pagina, decrementeaza contorul de referinte al paginii 828 si actualizeaza intrarea din tabela de pagini accesata de procesul B sa pointeze catre pagina 786.

Figura 12.15 Intrerupere de protectie cu bitul copiere la scriere setat

Daca bitul 'copiere la scriere ' este setat dar nu sunt alte procese care folosesc in comun aceasta pagina, nucleul permite procesul sa scrie pagina fizica. El pune pe zero bitul ' copiere la scriere ' si elimina asocierea paginii cu copia sa de pe disc. Apoi sterge intrarea in tabela pfdata din coada de pagini pentru ca noua copie a paginii virtuale nu mai exista pe dispozitivul de swap. Apoi, nucleul decrementeaza contorul tabelei de folosire a dispozitivului de swap pentru pagina respectiva si daca aceasta ajunge la zero, elibereaza spatiul de pe dispozitivul de swap.

Daca intrarea din tabela de pagini este invalida si bitul sau ' copiere la scriere este setat pentru a produce o intrerupere de protectie, sa presupunem ca sistemul trateaza mai intai intreruperea de validitate cand un proces acceseaza pagina. Cu toate acestea, rutina de tratare a intreruperii de protectie trebuie sa verifice daca pagina mai este valida, deoarece ea s-ar putea pune in asteptare cat timp regiunea este blocata iar procesul page stealer ar putea evacua, intre timp, pagina din memorie. Daca pagina nu este valida, rutina de tratare se termina imediat, iar procesul va produce din nou o intrerupere de validitate.

Nucleul trateaza intreruperea de validitate, dar procesul va produce din nou o intrerupere de protectie. Mai mult ca sigur el va trata intreruperea de protectie fara nici o alta interferenta deoarece va tece destul timp pana ce pagina va avea "varsta" necesara pentru a fi evacuata. Aceasta secventa de evenimente este ilustrata in figura 12.16

Figura 9.27 Interactiunea dintre intreruperea de protectie si intreruperea

de validitate

Cand rutina de tratare a intreruperii de protectie isi termina executia, ea seteaza bitii protectie si modificare si sterge bitul 'copiere la scriere '.

Apoi recalculeaza prioritatea procesului si verifica daca au fost receptionate semnale, ca si la sfarsitul rutinei de tratare a intreruperii de validitate.