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 întrerupere de pagina, UCP trebuie sa reia instructiunea dupa tratarea întreruperii deoarece calculele intermediare facute înainte de întreruperea 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 încapa in memoria fizica, nucleul trebuie sa încarce dinamic pârtile sale relevante in memorie si sa le execute chiar daca alte parti ale acestuia nu sunt încarcate. Paginarea la cerere este transparenta pentru programele utilizator, exceptie facând marimea virtuala permisa pentru un proces.

Procesele au tendinta sa execute instructiuni din portiuni mici ale regiunii de text, astfel încât programul cicleaza si apeleaza subrutine in mod frecvent. Acest principiu este cunoscut sub denumirea de principiul "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 decât intr-un sistem bazat pe swapping. Când un proces adreseaza o pagina care nu este in setul de lucru se produce o întrerupere de pagina; pentru tratarea întreruperii, nucleul actualizeaza setul de lucru, încarcând 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, ilustrând setul de lucru pentru diferite marimi ale ferestrei si urmând politica de înlocuire 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, implicând faptul ca procesul nu se va mai întrerupe 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 câte 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 pâna când devine eligibila pentru încarcare.

Figura 12.1 Setul de lucru al unui proces

Când un proces acceseaza o pagina care nu este in setul de lucru, se produce o întrerupere de pagina (întrerupere de validitate). Nucleul suspenda executia procesului pâna când citeste pagina in memorie si o face accesibi 555b19f la pentru proces. Dupa încarcarea paginii in memorie, procesul restarteaza instructiunea pe care o executa atunci când a aparut întreruperea de pagina. Astfel, implementarea unui subsistem de paginare are doua parti: evacuarea paginilor folosite mai putin pe un dispozitiv de swap si tratarea întreruperilor 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 câmpuri de biti pentru asigurarea paginarii la cerere:

validare;

referinta ;

modificare

copiere la cerere;

vârsta.

Nucleul seteaza bitul validare pentru a indica legalitatea continutului unei pagini, dar aceasta nu înseamna 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 când un proces ii modifica continutul. In sfârsit, nucleul manipuleaza bitii vârsta pentru a indica cât 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 vârsta, 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 "încarcare 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. Câmpurile 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 tinând 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 câte o intrare pentru fiecare pagina de pe dispozitivul de swap. Aceasta intrare contine un contor de referinta care indica câte 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, însemnând 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, indicând 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 pâna când un proces scrie in ea. Nucleul copiaza apoi pagina astfel încât 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 întrerupere de protectie, iar in tratarea acesteia, nucleul face o noua copie a paginii pentru procesul care a generat întreruperea. Copierea fizica a paginii este in acest fel amânata pâna când un proces are intr-adevar nevoie de ea.

Figura 12.4 prezinta structurile de date atunci când un proces executa apelul sistem fork. Procesele isi împart accesul la tabela de pagini a regiunii de text T folosita in comun, astfel încât 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, indicând 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.

Admitând inbunatatirea 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 decât 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 pâna când procesul fiu apeleaza exec sau se termina. Când procesul parinte reia in sfârsit 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

11.3 Exec intr-un sistem cu paginare

Când 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 încapa in memoria principala.

De aceea, nucleul nu preasigneaza memorie pentru fisierul executabil, dar genereaza o întrerupere, asignându-i câta memorie are nevoie. Acesta asigneaza mai întâi tabele de pagini si descriptori de bloc disc pentru fisierul executabil, marcând intrarile in tabela de pagina "încarcare la cerere" (pentru date non-BSS) sau "initializare cu zero" (pentru date BSS ). Urmând o varianta a algoritmului read pentru citirea fisierului in memorie, procesul produce o întrerupere de validitate (Paragraful 12.5.1) la citirea fiecarei pagini.  

Rutina de tratare a întreruperii retine daca pagina este marcata"încarcare la cerere", însemnând ca imediat va fi rescris continutul sau cu continutul fisierului executabil, astfel încât 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 deficiente. In primul rând, un proces produce o întrerupere de pagina când citeste fiecare pagina a fisierului executabil, chiar daca nu va trebui sa acceseze niciodata pagina respectiva. In al doilea rând, procesul "page-stealer" poate sa evacueze pagini din memorie înainte de terminarea apelului sistem exec, rezultând in plus doua operatii de transfer pentru fiecare pagina daca procesul solicita pagina respectiva curând. 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 întrerupere de pagina pe timpul unui apel sistem read când încearca sa copieze datele in spatiul utilizator, acesta trebuie sa rescrie aceste câmpuri in zona u area pentru a citi pagina din sistemul de fisiere. De aceea, nucleul nu poate folosi algoritmii obisnuiti pentru întreruperile 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 încarca o pagina direct din fisierul executabil, nucleul gaseste toate numerele blocurilor disc ale fisierului executabil când apeleaza exec si ataseaza lista lor la inodul fisierului.

Când 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 întreruperii de validitate foloseste aceasta informatie mai târziu pentru a încarca 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).

11.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 creeaza 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, lasând regiunile blocate in expectativa pentru a le examina la urmatoarea parcurgere a listei de regiuni, si incrementeaza apoi câmpul vârsta al tuturor paginilor valide.

Nucleul blocheaza o regiune când un proces produce o întrerupere pentru o pagina din regiune, astfel încât procesul page stealer nu poate evacua pagina care a generat întreruperea.

Pentru o pagina din memorie exista doua stari: pagina a fost încarcata 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 când 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 câte examinari au fost facute de la ultima referire a paginii. Deci prima stare consta in câteva substari corespunzatoare numarului de examinari pe care le face procesul page stealer pâna când pagina devine eligibila pentru evacuare (Figura 12.7). Când acest numar depaseste o valoare de prag, nucleul trece pagina in cea de-a doua stare, gata pentru evacuare. Perioada maxima care poate trece pâna când 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 procesele care acceseaza o pagina de catre procese si examinarile facute de procesul page stealer. Se pleaca de la pagina încarcata in memorie, figura ilustrând numarul de examinari ale procesului page stealer intre referirile la memorie. Un proces a referit pagina dupa a doua examinare, scazând astfel vârsta 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 îmbatrânire 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 ramâne in memorie; astfel pagina este eligebila pentru evacuare. Nu are importanta daca o regiune are mai multe pagini in memorie decât alta; procesul page stealer nu încearca sa evacueze un numar egal de pagina din toate regiunile active.

Nucleul trezeste procesul page stealer atunci când memoria libera disponibila in sistem ajunge la un nivel minim, iar acesta evacueaza pagini pâna când 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.

Când 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. Când 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 îl 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 încarcata in memoria principala dupa ce un proces genereaza o întrerupere 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 când aceasta a fost încarcata, 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 listă cu pagini de evacuat, posibil din regiuni diferite, si apoi, când 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 încarcate. Aceasta difera functie de politica procesului de evacuare/încarcare, 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 câte o pagina, consumând 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 decât in cazul swapping-ului deoarece nucleul evacueaza blocuri de pagini dar încarca numai câte o pagina.

Când 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 sfârsitul listei inlantuite de intrari libere in vederea reasignarii ei. Daca contorul nu este zero, atunci câteva procese folosesc in comun pagina ca rezultat al unui apel sistem fork anterior, dar nucleul evacueaza totusi pagina.

In sfârsit, 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 întrerupere 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 pâna când 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 intrarea din tabela de pagini, decrementeaza contorul de referinte al intrarii din tabela pfdata si plaseaza aceasta intrare la sfârsitul listei de intrari libere daca contorul sau de referinte este zero. Continutul paginii libere este valid in memorie pâna când pagina este reasignata.

12.5. Întreruperi de pagina

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

Întreruperi de validitate

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

algoritm vfault /*rutina de tratare a întreruperii de validitate*/

intrare: adresa unde este întrerupt procesul;

iesire: nici una;

if ( adresa este valida acum)

/*este posibil ca procesul sa fi fost în asteptare mai înainte*/

goto la iesire;

if ( pagina este în memoria cache )

else /* pagina nu este în memoria cache */

trezeste procesele ( eveniment: continutul paginii este valid ); }

seteaza bitul validare pentru pagina respectiva;

reseteaza bitii modificare si vârsta;

recalculeaza prioritatea procesului;

iesire: deblocheaza regiunea; }

Figura 12.10 Algoritmul rutinei de tratare a întreruperii 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 întrerupere 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 încearca sa evacueze pagina. Daca descriptorul de bloc disc nu are nici o înregistrare referitoare la pagina care a cauzat întreruperea, încercarea 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 când 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 întreruperilor de validitate

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

in zona de swap si nu in memorie;

in lista de pagini libere in memorie;

intr-un fisier executabil;

marcata " încarcare la cerere ";

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 cândva 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 încât 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 întreruperii si apoi citeste pagina de pe dispozitivul de swap. Procesul care produce întreruperea se pune in asteptare pâna când 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 întrerupere de validitate atunci când acceseaza pagina, rutina de tratare a întreruperii 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 întreruperii 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 încarcarea paginii in memorie

Nucleul nu are de facut totdeauna o operatie I/O când apare o întrerupere 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 întrerupere pentru pagina virtuala, asignând pentru ea o alta pagina fizica; in fiecare caz, rutina de tratare a întreruperii 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 întrerupere când acceseaza adresa virtuala 64k din figura 12.11. Cautând 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 întreruperii nu trebuie sa citeasca pagina in memorie daca alt proces a generat o întrerupere pentru aceeasi pagina, dar nu a terminat inca încarcarea 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 întreruperii. De aceea, se pune in asteptare pâna 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 întrerupere 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 întreruperii 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. Cunoscând numarul blocului disc, nucleul citeste pagina in memorie. De exemplu, descriptorul de bloc disc pentru adresa virtuală 1k din figura 12.11 ilustreaza faptul ca pagina este continuta in blocul logic 3 din fisierul executabil.

Daca un proces genereaza o întrerupere de pagina pentru o pagina marcata "încarcare 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 "încarcare 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 întâmpla la accesarea adreselor virtuale 3k si 65k din figura 12.11: nici un proces nu a accesat paginile de când s-a executat apelul sistem exec.

Rutina de tratare a întreruperii de validare se încheie 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, obtinând 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 întreruperii de pagina.

Întreruperi de protectie

Al doilea fel de întrerupere pe care o poate produce un proces este întreruperea de protectie ceea ce înseamna 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 încearca sa scrie in spatiul sau de text). Un proces poate, de asemenea, produce o întrerupere de protectie atunci când încearca 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 întâmplat ceva ilegal.

Hardware-ul furnizeaza rutinei de tratare a întreruperii de protectie adresa virtuala la care a aparut întreruperea, iar aceasta gaseste regiunea si intrarea din tabela de pagini corespunzatoare (Figura 12.14). Rutina va bloca regiunea astfel încât procesul page stealer sa nu poata evacua pagina cât timp opereaza cu ea rutina de tratare. Daca aceasta determina ca întreruperea 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 tratare a întreruperii 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 întrerupere de protectie deoarece bitul " copiere la scriere " este setat.

Rutina de tratare a întreruperii 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 Întrerupere 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 întrerupere de protectie, sa presupunem ca sistemul trateaza mai întâi întreruperea de validitate când un proces acceseaza pagina. Cu toate acestea, rutina de tratare a întreruperii de protectie trebuie sa verifice daca pagina mai este valida, deoarece ea s-ar putea pune in asteptare cât 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 întrerupere de validitate.

Nucleul trateaza întreruperea de validitate, dar procesul va produce din nou o întrerupere de protectie. Mai mult ca sigur el va trata întreruperea de protectie fara nici o alta interferenta deoarece va tece destul timp pâna ce pagina va avea "vârsta" necesara pentru a fi evacuata. Aceasta secventa de evenimente este ilustrata in figura 12.16

Figura 9.27 Interactiunea dintre întreruperea de protectie si întreruperea

de validitate

Când rutina de tratare a întreruperii 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 sfârsitul rutinei de tratare a întreruperii de validitate.