MEMORIA

MEMORIA

11. GESTIUNEA MEMORIEI PRIN SWAPPING

Algoritmul de planificare al U.C.P. descris mai înainte este puternic influentat de politicile de gestiune a memoriei. U.C.P. nu poate executa un proces care exista în întregime in memoria secundara; cel putin o parte a procesului trebuie sa fie continuta în memoria principala pentru ca procesul sa poata fi executat. Totusi, memoria principala este o resursa pretioasa care, de obicei, nu poate contine toate procesele active din sistem.

Subsistemul de gestiune a memoriei decide care dintre procese ar trebui sa ramâna (cel putin partial) în memoria principala si gestioneaza partile din spatiul de adrese virtuale ale procesului care nu sunt rezidente în memoria principala. El monitorizeaza memoria principala disponibila si poate, periodic, sa scrie procese pe un dispozitiv de memorie secundara numit dispozitiv de evacuare (swap device) pentru a asigura mai mult spatiu in memoria pri 222i86c ncipala. Dupa un anumit timp, nucleul citeste datele din zona de swap înapoi în memoria principala.

Din punct de vedere al evolutiei în timp, sistemele UNIX au transferat procese întregi între memoria principala si dispozitivul de swap, dar nu au transferat independent parti ale unui proces, cu exceptia zonelor de text folosite in comun. O astfel de de politica de gestiune a memoriei se numeste swapping.

A avut sens sa se implementeze o astfel de politica de gestiune a memoriei pe PDP-11, unde marimea maxima a unui proces era de 64 Ko. Pentru aceasta politica de gestiune a memoriei, marimea unui proces este limitata de marimea memoriei fizice disponibile în sistem.

Exista trei etape în descrierea algoritmului de swapping: gestiunea spatiului pe dispozitivul de swap, evacuarea proceselor din memoria principala si încarcarea proceselor în memoria principala.

11.1 Alocarea spatiului de evacuare

Dispozitivul de swap este un dispozitiv de tip bloc într-o sectiune configurabila a discului. În timp ce nucleul aloca spatiu pentru fisiere bloc cu bloc, în zona de swap spatiul este alocat în grupuri de blocuri contigue. Alocarea spatiului pe dispozitivul de swap este tranzitorie, depinzând de modul de planificare a proceselor. Un proces care rezida pe dispozitivul de swap va migra, în cele din urma, înapoi în memoria principala, eliberând spatiul pe care l-a ocupat în zona de swap. Deoarece viteza este critica iar sistemul poate face operatii de intrare/iesire mai rapid într-o singura operatie multibloc decât în câteva operatiuni cu câte un singur bloc, nucleul aloca spatiu contiguu în zona de swap.

Deoarece schema de alocare pentru dispozitivul de swap difera de schema de alocare pentru sistemele de fisiere, structurile de date folosite sunt deasemenea diferite. Nucleul pastreaza evidenta spatiului liber pentru sistemele de fisiere într-o lista înlantuita de blocuri libere, accesibila din superblocul sistemului de fisiere, iar spatiul liber pentru dispozitivul de swap este pastrat într-o tabela în memoria interna denumita map.Aceste tabele permit o alocare tip first-fit (prima potrivire) a blocurilor contigue de resursa.

O tabela map este o tabela în care fiecare intrare contine o adresa a unei resurse alocabile si numarul corespunzator de unitati de resursa disponibile; nucleul interpreteaza adresa si unitatile în concordanta cu tipul tabelei map. Initial, aceasta contine o intrare care indica adresa si numarul total de resurse. De exemplu, nucleul trateaza fiecare unitate a tabelei ca un grup de blocuri disc, iar adresa este tratata ca un deplasament fata de începutul zonei de swap.

Figura 11.1 ilustreaza o tabela initiala a zonei de swap care contine 10.000 de blocuri, începând de la adresa 1.

Figura 11.1 Tabela map initiala

Deoarece nucleul aloca si elibereaza resurse, acesta actualizeaza tabela astfel încât aceasta continua sa contina informatii corecte despre resursele libere.

Figura 11.2.Algoritmul pentru alocarea spatiului gestionat

în tabelele map

Nucleul cauta în tabela map prima intrare care contine spatiu suficient pentru a satisface cererea facuta. Daca cererea consuma toate resursele intrarii în tabela map, nucleul sterge intrarea din tabela si comprima tabela în mod corespunzator.Altfel, nucleul ajusteaza câmpurile de adresa si numar de unitati ale intrarii în concordanta cu cantitatea de resurse alocate. Figura 11.3 ilustreaza configuratia tabelei map dupa alocarea a 100 de unitati, apoi înca 50 de unitati, si înca 100 de unitati. Nucleul ajusteaza tabela map pentru a arata ca primele 250 de unitati au fost alocate, si ca aceasta contine acum numai 9750 unitati libere, începând cu adresa 251.

Figura 11.3 Alocarea spatiului pe dispozitivul de swap

Când elibereaza resursele, nucleul gaseste pozitia corecta in tabela prin intermediul adresei. Exista trei cazuri posibile :

Resursele eliberate acopera complet un gol în tabela: ele sunt contigue cu intrarile ale caror adrese le preced si le urmeaza imediat în tabela. În acest caz nucleul combina noile resurse eliberate si intrarile existente ( doua ) într-o singura intrare în tabela.Numarul de intrari scade cu una.

Resursele eliberate acopera partial un gol în tabela map. Daca adresele resurselor eliberate sunt contigue cu intrarea a carei adresa le precede sau cu intrarea a carei adresa le urmeaza imediat în tabela( dar nu cu amândoua), atunci nucleul ajusteaza câmpurile de adresa si numarul de unitati pentru intrarea respectiva, tinând cont de cantitatea de resurse eliberata.Numarul intrarilor din tabela map ramâne acelasi.

Resursele eliberate acopera partial un gol din tabela map dar nu sunt contigue cu nici o intrare din aceasta. Nucleul creaza o noua intrare si o insereaza în pozitia corespunzatoare.

Revenind la exemplul anterior, daca nucleul elibereaza 50 de unitati de resursa începând cu adresa 101, tabela map contine o noua intrare pentru resursele eliberate, întrucât resursele eliberate nu sunt contigue cu niciuna din intrarile existente. Daca nucleul elibereaza dupa aceea 100 de unitati de resursa începând cu adresa 1, acesta ajusteaza prima intrare în tabela map deoarece resursele eliberate sunt contigue cu acelea din prima intrare.

Figura 11.4 prezinta secventa configurarii tabelei map corespunzator acestor evenimente.

Figura 11.4 Eliberarea spatiului de swap

Sa presupunem ca nucleul solicita acum 200 de unitati. Deoarece prima intrare din tabela de swap contine numai 150 de unitati, nucleul satisface cererea de la cea de-a doua intrare (Figura 11.5). În sfârsit, sa presupunem ca nucleul elibereaza 350 de unitati din spatiul de swap, începând de la adresa 151. Cu toate ca cele 350 de unitati au fost alocate separat, nu exista nici un motiv pentru ca nucleul sa nu le poata elibera pe toate odata. Nucleul constata ca resursele eliberate se potrivesc perfect în golul dintre prima si a doua intrare din tabela map si creaza o singura intrare pentru amândoua (si pentru resursele eliberate).

Figura 11.5 Alocarea spatiului de swap gestionat în cea de-a doua

intrare din tabela map

Implementarile traditionale ale sistemului UNIX folosesc un singur dispozitiv de swap, dar ultimele implementari permit mai multe dispozitive de swap.

Administratorul poate crea sau sterge în mod dinamic dispozitive de swap. Daca un dispozitiv este în curs de stergere, nucleul nu mai poate evacua date din memorie pe acel dispozitiv.

11.2 Evacuarea proceselor

Nucleul evacueaza un proces daca are nevoie de spatiu în memorie, aceasta necesitate aparând în unul din urmatoarele cazuri :

1. Apelul sistem fork trebuie sa aloce spatiu pentru un proces fiu;

2. Apelul sistem brk mareste dimensiunea unui proces;

3. Un proces se mareste prin cresterea naturala a stivei sale;

4. Nucleul doreste sa elibereze spatiu în memorie pentru procesele care au fost evacuate anterior si acum trebuiesc reâncarcate.

Cazul apelului fork iese din discutie deoarece este singurul caz în care memoria interna ocupata anterior de catre proces nu este abandonata.

Când nucleul decide ca un proces poate fi ales pentru evacuarea din memoria principala, el decrementeaza contorul de referinta al fiecarei regiuni a procesului si evacueaza regiunea daca contorul a ajuns la 0. Nucleul aloca spatiu pe un dispozitiv de evacuare si blocheaza procesul în memorie(pentru cazurile 1-3), împiedicând procesul încarcator sa îl evacueze în timp ce se deruleaza operatia curenta de evacuare. Nucleul salveaza adresa de evacuare a regiunii în intrarea din tabela de regiuni.

Nucleul transfera maximum de date posibile în fiecare operatie I/O direct între zona de swap si spatiul de adrese al utilizatorului evitând buffer-le cache. Daca hardware-ul nu poate transfera mai multe pagini într-o operatie, software-ul nucleului trebuie sa transfere succesiv câte o pagina. Rata de transfer a datelor si mecanismul sau depind, printre alti factori, de posibilitatile controlerului de disc si de implementarea gestiunii memoriei. De exemplu, daca memoria este organizata pe pagini, datele care trebuiesc evacuate este posibil sa nu fie contigue în memoria fizica. Nucleul trebuie sa obtina adresele de pagina ale datelor de evacuat iar driverul de disc poate folosi multimea adreselor de pagina pentru a initializa operatii I/O. Procesul încarcator asteapta terminarea fiecarei operatii I/O înainte de a evacua alte date.

Nu este necesar ca nucleul sa scrie întreg spatiul virtual de adrese al unui proces pe dispozitivul de evacuare. În schimb, el copiaza memoria fizica asignata unui proces în spatiul alocat pe dispozitivul de swap, ignorând adresele virtuale neasignate. Când nucleul încarca înapoi în memorie procesul, el cunoaste tabela adreselor virtuale ale procesului, astfel încât reasigneaza procesul la adresele virtuale corespunzatoare.

Figura 11.6 ofera un exemplu de mapare a imaginii din memoria interna a unui proces în zona de evacuare.

Procesul contine 3 regiuni pentru text, date si stiva: regiunea de text se termina la adresa virtuala 2ko, iar regiunea de date începe la adresa virtuala 64ko, ramânând un spatiu de 62 ko în spatiul virtual de adresa. Când nucleul evacueaza procesul, el evacueaza paginile de la adresele virtuale 0, 1ko, 64ko, 65ko, 66ko, si 128ko; nu se aloca spatiu în zona de swap pentru golul de 62 ko dintre regiunile de date si text, sau pentru golul de 61 ko dintre regiunile de date si stiva, dar spatiul de pe dispozitivul de evacuare este umplut contiguu.

Figura 11.6 Maparea spatiului procesului pe dispozitivul de swap

Când nucleul încarca procesul în memorie, el stie ca acesta are un gol de 62 ko prin consultarea tabelei map a procesului din memorie si asigneaza memorie fizica în concordanta cu aceasta. Figura 11.7 prezinta acest caz.

Figura 11.7 Încarcarea unui proces în memorie

Teoretic, tot spatiul de memorie ocupat de un proces, inclusiv uarea si stiva nucleului, este elegibila pentru a fi evacuat, desi nucleul poate sa blocheze temporar o zona de memorie cât timp o operatie este în desfasurare. Totusi, în mod practic, implementarile nucleului nu evacueaza uarea daca aceasta contine tabelele de translatare a adreselor pentru proces. Implementarea stabileste de asemenea, daca un proces se poate autoevacua sau daca el trebuie sa ceara altui proces sa îl evacueze.

11.2.1 Evacuarea în cazul apelului sistem fork

Descrierea apelului sistem fork(Paragraful 8.1) a presupus ca procesul parinte a gasit suficienta memorie pentru a crea contextul procesului fiu. În alte conditii, nucleul evacueaza procesul fara eliberarea memoriei ocupate de copia parintelui din memoria interna. Când se termina evacuarea, procesul fiu exista pe dispozitivul de swap; procesul parinte pune procesul fiu in starea "gata de executie" (Figura 7.1) si revine în modul utilizator. Deoarece procesul fiu este în starea "gata de executie", procesul încarcator îl poate încarca în cele din urma în memorie, unde îl va planifica;procesul fiu îsi va termina partea de apel fork si va reveni în modul utilizator.

11.2.2 Evacuarea în cazul apelului sistem brk

Daca un proces necesita mai multa memorie fizica decât îi este alocata în mod curent, ca rezultat al cresterii stivei utilizatorului, sau ca rezultat al invocarii apelului sistem brk si daca are nevoie de mai multa memorie fizica decât este disponibila nucleul executa o evacuare extinsa a procesului.

El rezerva spatiu suficient pe dispozitivul de swap pentru a include spatiul de memorie al procesului, inclusiv noul spatiu solicitat. Apoi, nucleul actualizeaza modul de translatare a adreselor luând în calcul noua memorie virtuala, dar nu asigneaza memorie fizica(întrucât nu este disponibila). În final, nucleul evacueaza procesul printr-o operatie de evacuare normala, completând cu zero spatiul nou alocat în zona de swap (Figura 11.8).

Figura 11.8 Actualizarea tabelei map din memorie pentru

evacuarea extinsa

Când nucleul va încarca mai tîrziu procesul în memorie, acesta va aloca memorie fizica în concordanta cu noua tabela map. Când procesul îsi va relua executia, el va avea memorie suficienta.

10.3 Încarcarea proceselor

Procesul 0, încarcatorul, este singurul proces care încarca procese în memorie de pe dispozitivele de swap. La sfârsitul initializarii sistemului, procesul încarcator intra într-o bucla infinita, în care singura sa sarcina este sa faca încarcarea/evacuarea proceselor. El încearca sa încarce procese din zona de swap, si evacueaza procese daca este nevoie de spatiu în memoria principala.

Daca nu are nici o sarcina de rezolvat, procesul încarcator se pune în asteptare(de exemplu, daca nu exista procese de încarcat) sau daca este incapabil sa faca altceva (nu exista procese care pot fi alese pentru a fi evacuate); nucleul îl trezeste periodic, asa cum se va vedea în continuare.

Nucleul planifica procesul încarcator sa se execute asa cum planifica orice alt proces,dar acesta se executa numai în modul kernel.

Procesul încarcator nu face apeluri de functii sistem dar utilizeaza functii interne ale nucleului pentru a executa transferul.

Figura 11.9 Algoritmul swapper

Rutina de tratare a înterruperii de ceas masoara timpul cât fiecare proces a stat în memoria interna sau a fost evacuat. Când procesul încarcator este trezit pentru a încarca procese, el verifica toate procesele care sunt în starea "gata de executie" dar evacuate si îl selecteaza pe acela care a stat cel mai mult timp evacuat.

Daca exista suficienta memorie libera disponibila, procesul încarcator încarca procesul în memorie, executând operatiile inverse evacuarii: aloca memorie fizica, citeste procesul din zona de swap si elibereaza spatiul de swap.

Daca procesul încarcator a terminat cu succes încarcarea unui proces, el cauta un alt proces în starea "gata de executie" dar evacuat pentru a-l încarca în memorie si repeta procedura descrisa mai înainte. Poate aparea, în final, una din urmatoarele situatii:

Nu exista procese în starea "gata de executie" pe dispozitivul de swap : procesul încarcator trece în starea de asteptare pâna când îl trezeste un proces de pe dispozitivul de swap sau pâna când nucleul evacueaza un proces care este în starea "gata de executie " (a se revedea diagrama starilor din figura 7.1).

Procesul încarcator gaseste un proces potrivit pentru a fi încarcat, dar sistemul nu dispune de memorie suficienta: procesul încarcator încearca sa evacueze un alt proces, si, daca reuseste, reia algoritmul de încarcare, cautând un proces pentru a-l încarca în memorie.

Daca procesul încarcator trebuie sa evacueze un proces, el examineaza toate procesele din memorie. Procesele în starea "zombie" nu vor fi evacuate deoarece ele nu ocupa memorie fizica; procesele blocate în memorie pe timpul operatiilor cu regiuni nu vor fi de asemenea evacuate. Nucleul evacueaza mai degraba procesele în asteptare decât cele în starea "gata de executie", deoarece procesele în starea "gata de executie " au sanse mult mai mari sa fie planificate pentru executie. Alegerea procesului în asteptare care se evacueaza se face în functie de prioritate si de timpul cât procesul a stat în memorie. Daca nu sunt procese în asteptare în memorie, alegerea unui proces în starea "gata de executie " pentru a fi evacuat se face în functie de valoarea nice a procesului si de timpul cât acesta a stat în memorie.

Un proces în starea "gata de executie " trebuie sa stea în memorie cel putin 2 secunde înainte de a fi evacuat, iar un proces poate fi încarcat doar daca a fost evacuat de cel putin timp de 2 secunde. Daca procesul încarcator nu gaseste nici un proces de evacuat si daca nici unul dintre procesele care trebuiesc încarcate nu au stat evacuate cel putin 2 secunde, atunci procesul încarcator se pune în asteptare pe evenimentul: doreste sa încarce un proces în memorie dar nu are loc suficient. Ceasul va trezi procesul încarcator o data pe secunda. Nucleul trezeste de asemenea procesul încarcator daca un alt proces intra în starea de asteptare, devenind astfel mai potrivit pentru a fi evacuat decât procesele examinate anterior. Daca procesul încarcator evacueaza un proces sau daca se pune în asteptare pentru ca nu poate evacua un proces, el îsi va relua executia de la începutul algoritmului, încercând sa încarce un proces.

Figura 11.10 Secventa de operatii de evacuare/încarcare

Figura 11.10 descrie cinci procese si timpii pe care acestea i-au petrecut în memorie sau în zona de evacuare ca urmare a trecerii printr-o secventa de operatii evacuare/încarcare. Pentru simplificare sa presupunem ca toate procesele lucreaza intens cu UCP si nu apeleaza nici o functie sistem; din aceasta cauza schimbarea contextului va avea loc doar ca rezultat al întreruperilor de ceas la intervale de o secunda. Procesul încarcator se executa cu cea mai mare prioritate de planificare, astfel se executa rapid la intervale de o secunda, daca are ce face. Mai mult, sa presupunem ca procesele sunt de aceeasi marime iar sistemul poate contine cel mult doua procese simultan în memoria principala. Initial, procesele A si B sunt în memoria principala, iar celelalte procese sunt evacuate. Procesul încarcator nu poate evacua/încarca nici un proces timp de 2 secunde, deoarece nici un proces nu a stat în memorie sau pe dispozitivul de swap timp de 2 secunde (cerinta de rezidenta), dar la sfârsitul celei de-a doua secunde, el evacueaza procesele A si B si încarca procesele C si D; încearca sa încarce si procesul E, dar nu poate deoarece nu mai are loc în memorie. La secunda 3 procesul E este posibil sa fie ales pentru a fi încarcat deoarece el a stat în zona de swap 3 secunde, dar procesul încarcator nu poate evacua procese din memoria principala deoarece timpul lor de rezidenta este sub 2 secunde. La sfârsitul celei de-a 4-a secunde, procesul încarcator evacueaza procesele C si D încarca procesele E si A.

Procesul încarcator alege procesele de încarcat bazându-se pe marimea timpului cât acestea au stat evacuate. Un alt criteriu ar putea fi încarcarea procesului în starea "gata de executie" care are prioritatea cea mai mare, deoarece acesta are o probabilitate mai mare de a fi executat.

Algoritmul pentru alegerea unui proces care urmeaza sa fie evacuat pentru a face loc în memorie are, totusi, serioase neajunsuri. Mai întâi procesul încarcator evacueaza un proces bazându-se pe prioritatea acestuia, pe timpul de rezidenta în memorie si pe valoarea nice. Desi evacueaza un proces numai pentru a crea spatiu pentru un proces care urmeaza sa fie încarcat, el poate evacua un proces care sa nu asigure memorie suficienta pentru procesul ce se va incarca. De exemplu, daca procesul încarcator încearca sa încarce un proces care ocupa 1Mo iar sistemul nu contine memorie libera, este inutil sa evacueze un proces care ocupa numai 2 Ko de memorie. O strategie alternativa ar fi sa evacueze grupuri de procese, dar numai daca acestea asigura memorie suficienta pentru procesul care trebuie încarcat.

În al doilea rând, daca procesul încarcator se pune în asteptare deoarece nu poate gasi memorie suficienta pentru a încarca un proces, el cauta din nou un proces pentru a-l încarca desi alesese unul anterior. Motivul este acela ca alte procese evacuate îl pot trezi între timp si acestea pot fi mai potrivite pentru încarcare decât procesul ales anterior. În unele implementari, procesul încarcator încearca sa evacueze mai multe procese mai mici pentru a face loc unui proces mare sa fie încarcat înainte sa caute alt proces eligibil pentru încarcare; în aceasta consta revizuirea algoritmului procesului încarcator prezentata în figura 11.9.

În al treilea rând, daca procesul încarcator alege pentru evacuare un proces în starea "gata de executie", este posibil ca acesta sa nu se fi executat de când el a fost încarcat mai înainte. Figura 11.11 ilustreaza un asemenea caz, în care nucleul încarca procesul D la secunda 2, planifica procesul C si apoi, la secunda 3, evacueaza procesul D în favoarea procesului E (ca urmare a actiunii valorii nice ) chiar daca procesul D nu s-a executat.

Figura 11.11 Neajunsuri la încarcare/evacuare

Un ultim inconvenient este demn de mentionat: daca procesul încarcator încearca sa evacueze un proces dar nu gaseste spatiu în zona de swap, poate rezulta o blocare a sistemului daca sunt îndeplinite urmatoarele patru conditii:

toate procesele din memoria principala sunt inactive (sunt în asteptare);

toate procesele în starea "gata de executie " sunt evacuate;

nu exista spatiu pe dispozitivul de swap pentru noi procese;

· nu exista spatiu în memoria principala pentru procesele care trebuie încarcate.

Preocuparile pentru rezolvarea deficientelor procesului încarcator prezentate mai înainte au scazut în ultimii ani, când au fost implementati algoritmii de paginare la cerere pentru sistemele UNIX.