MEMORIA
11. GESTIUNEA MEMORIEI PRIN SWAPPING
Algoritmul de planificare al U.C.P. descris mai inainte este puternic influentat de politicile de gestiune a memoriei . U.C.P. nu poate executa un proces care exista in intregime in memoria secundara; cel putin o parte a procesului trebuie sa fie continuta in 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 ramana (cel putin partial) in memoria principala si gestioneaza partile din spatiul de adrese virtuale ale procesului care nu sunt rezidente in 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 principala. Dupa un anumit timp, nucleul citeste datele din zona de swap inapoi in memoria principala.
Din punct de vedere al evolutiei in timp, sistemele UNIX au transferat procese intregi intre 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 in sistem .
Exista trei etape in descrierea algoritmului de swapping: gestiunea spatiului pe dispozitivul de swap, evacuarea proceselor din memoria principala si incarcarea proceselor in memoria principala.
11.1 Alocarea spatiului de evacuare
Dispozitivul de swap este un dispozitiv de tip bloc intr-o sectiune configurabila a discului. In timp ce nucleul aloca spatiu pentru fisiere bloc cu bloc, in zona de swap spatiul este alocat in grupuri de blocuri contigue. Alocarea spatiului pe dispozitivul de swap este tranzitorie, depinzand de modul de planificare a proceselor. Un proces care rezida pe dispozitivul de swap va migra, in cele din urma, inapoi in memoria principala, elib 121j95b erand spatiul pe care l-a ocupat in zona de swap. Deoarece viteza este critica iar sistemul poate face operatii de intrare/iesire mai rapid intr-o singura operatie multibloc decat in cateva operatiuni cu cate un singur bloc, nucleul aloca spatiu contiguu in 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 intr-o lista inlantuita de blocuri libere, accesibila din superblocul sistemului de fisiere, iar spatiul liber pentru dispozitivul de swap este pastrat intr-o tabela in 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 in care fiecare intrare contine o adresa a unei resurse alocabile si numarul corespunzator de unitati de resursa disponibile; nucleul interpreteaza adresa si unitatile in 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 inceputul zonei de swap.
Figura 11.1 ilustreaza o tabela initiala a zonei de swap care contine 10.000 de blocuri, incepand de la adresa 1.
Figura 11.1 Tabela map initiala
Deoarece nucleul aloca si elibereaza resurse, acesta actualizeaza tabela astfel incat aceasta continua sa contina informatii corecte despre resursele libere.
algoritm malloc /*algoritm pentru alocarea spatiului de pe dispozitivul de swap*/
intrari : ( 1 ) adresa map / * indica ce tabela map se foloseste * /
( 2 ) numarul solicitat de unitati
iesiri : adresa ,în caz de succes
0 ,altfel
return
Figura 11.2.Algoritmul pentru alocarea spatiului gestionat
in tabelele map
Nucleul cauta in tabela map prima intrare care contine spatiu suficient pentru a satisface cererea facuta. Daca cererea consuma toate resursele intrarii in tabela map, nucleul sterge intrarea din tabela si comprima tabela in mod corespunzator. Altfel, nucleul ajusteaza câmpurile de adresa si numar de unitati ale intrarii in concordanta cu cantitatea de resurse alocate. Figura 11.3 ilustreaza configuratia tabelei map dupa alocarea a 100 de unitati, apoi inca 50 de unitati, si inca 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, incepand cu adresa 251.
Figura 11.3 Alocarea spatiului pe dispozitivul de swap
Cand elibereaza resursele, nucleul gaseste pozitia corecta in tabela prin intermediul adresei. Exista trei cazuri posibile :
Resursele eliberate acopera complet un gol in tabela: ele sunt contigue cu intrarile ale caror adrese le preced si le urmeaza imediat in tabela. In acest caz nucleul combina noile resurse eliberate si intrarile existente ( doua) intr-o singura intrare in tabela.Numarul de intrari scade cu una.
Resursele eliberate acoper partial un gol in tabela map. Daca adresele resurselor eliberate sunt contigue cu intrarea a carei adresa le precede sau cu intrarea a carei adresa le urmeaza imediat in tabela( dar nu cu amandoua) , atunci nucleul ajusteaza campurile de adresa si numarul de unitati pentru intrarea respectiva , tinand cont de cantitatea de resurse eliberata.Numarul intrarilor din tabela map ramane 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 in pozitia corespunzatoare.
Revenind la exemplul anterior, daca nucleul elibereaza 50 de unitati de resurse incepand cu adresa 101, tabela map contine o noua intrare pentru resursele eliberate, intrucat resursele eliberate nu sunt contigue cu niciuna din intrarile existente. Daca nucleul elibereaza dupa aceea 100 de unitati de resursa incepand cu adresa 1, acesta ajusteaza prima intrare in 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). in sfarsit , sa presupunem ca nucleul elibereaza 350 de unitati din spatiul de swap, incepand 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 in golul dintre prima si a doua intrare din tabela map si creaza o singura intrare pentru amandoua (si pentru resursele eliberate).
 |
Figura 11.5 Alocarea spatiului de swap gestionat in 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 in mod dinamic dispozitive de swap. Daca un dispozitiv este in 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 in memorie, aceasta necesitate aparând in 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 in memorie pentru procesele care au fost evacuate anterior si acum trebuiesc reancarcate .
Cazul apelului fork iese din discutie deoarece este singurul caz in care memoria interna ocupata anterior de catre proces nu este abandonata.
Cand nucleul decide ca un proces poate fi ales pentru evacuarea din memoria principala, el decrementeaza contorul de referin]a 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 in memorie(pentru cazurile 1-3), impiedicand procesul incarcator sa il evacueze in timp ce se deruleaza operatia curenta de evacuare. Nucleul salveaza adresa de evacuare a regiunii in intrarea din tabela de regiuni.
Nucleul transfera maximum de date posibile in fiecare operatie I/O direct intre zona de swap si spatiul de adrese al utilizatorului evitand buffer-le cache. Daca hardware-ul nu poate transfera mai multe pagini intr-o operatie, software-ul nucleului trebuie sa transfere succesiv cate 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 in 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 incarcator asteapta terminarea fiecarei operatii I/O inainte de a evacua alte date.
Nu este necesar ca nucleul sa scrie intreg spatiul virtual de adrese al unui proces pe dispozitivul de evacuare. In schimb, el copiaza memoria fizica asignata unui proces in spatiul alocat pe dispozitivul de swap, ignorand adresele virtuale neasignate. Când nucleul încarca înapoi in 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 in 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 incepe la adresa virtuala 64ko, ramanand un spatiu de 62 ko in spatiul virtual de adresa. Cand nucleul evacueaza procesul, el evacueaza paginile de la adresele virtuale 0, 1ko, 64ko, 65ko, 66ko, si 128ko; nu se aloca spatiu in 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
Cand nucleul incarca procesul in memorie, el stie ca acesta are un gol de 62 ko prin consultarea tabelei map a procesului din memorie si asigneaza memorie fizica in concordanta cu aceasta. Figura 11.7 prezinta acest caz.
 |
Figura 11.7 Încarcarea unui proces in 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 cat timp o operatie este in desfasurare. Totusi, in 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 il evacueze.
11.2.1 Evacuarea in 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. In 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 in modul utilizator. Deoarece procesul fiu este in starea "gata de executie", procesul incarcator îl poate încarca in cele din urma in memorie, unde îl va planifica; procesul fiu isi va termina partea de apel fork si va reveni in modul utilizator.
11.2.2 Evacuarea in cazul apelului sistem brk
Daca un proces necesita mai multa memorie fizica decât ii este alocata in 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 luand in calcul noua memorie virtuala, dar nu asigneaza memorie fizica(intrucat nu este disponibila). In final, nucleul evacueaza procesul printr-o operatie de evacuare normala, completand cu zero spatiul nou alocat in zona de swap (Figura 11.8).
Figura 11.8 Actualizarea tabelei map din memorie pentru
evacuarea extinsa
Cand nucleul va incarca mai tirziu procesul in memorie, acesta va aloca memorie fizica in concordanta cu noua tabela map. Cand procesul isi va relua executia, el va avea memorie suficienta.
11.3 Incarcarea proceselor
Procesul 0, incarcatorul, este singurul proces care incarca procese in memorie de pe dispozitivele de swap. La sfarsitul initializarii sistemului, procesul incarcator intra intr-o bucla infinita, in care singura sa sarcina este sa faca incarcarea/evacuarea proceselor. El incearca sa incarce procese din zona de swap, si evacueaza procese daca este nevoie de spatiu in memoria principala.
Daca nu are nici o sarcina de rezolvat, procesul incarcator se pune in asteptare(de exemplu, daca nu exista procese de incarcat) sau daca este incapabil sa faca altceva (nu exista procese care pot fi alese pentru a fi evacuate); nucleul il trezeste periodic, asa cum se va vedea in continuare.
Nucleul planifica procesul incarcator sa se execute asa cum planifica orice alt proces,dar acesta se executa numai in modul kernel.
Procesul incarcator nu face apeluri de functii sistem dar utilizeaza functii interne ale nucleului pentru a executa transferul.
|
algoritm swapper /*încarca procesele evacuate în memorie*/ intrare: nici una; iesire: nici una; if (este loc suficient pentru proces în memoria principala) /* bucla2:se afla aici în algoritmul revizuit */ for (toate procesele încarcate în memoria principala, care nu sunt în starea zombie si nu sunt blocate în memorie) if (procesul ales nu este în asteptare sau cerintele de rezidenta nu sunt satisfacute ) sleep(eveniment : trebuie sa încarce un proces); else evacueaza procesul; goto la bucla; /*goto bucla 2 în algoritmul revizuit */ |
Figura 11.9 Algoritmul swapper
Rutina de tratare a intreruperii de ceas masoara timpul cat fiecare proces a stat in memoria interna sau a fost evacuat. Când procesul incarcator este trezit pentru a încarca procese, el verifica toate procesele care sunt in 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 incarcator încarca procesul in memorie, executând operatiile inverse evacuarii: aloca memorie fizica, citeste procesul din zona de swap si elibereaza spatiul de swap.
Daca procesul incarcator a terminat cu succes incarcarea unui proces, el cauta un alt proces in starea "gata de executie" dar evacuat pentru a-l incarca in memorie si repeta procedura descrisa mai inainte. Poate aparea, in final, una din urmatoarele situatii:
Nu exista procese in starea "gata de executie" pe dispozitivul de swap : procesul incarcator trece in starea de asteptare pana când îl trezeste un proces de pe dispozitivul de swap sau pana când nucleul evacueaza un proces care este in starea "gata de executie " (a se revedea diagrama starilor din figura 7.1).
Procesul incarcator gaseste un proces potrivit pentru a fi incarcat, dar sistemul nu dispune de memorie suficienta: procesul incarcator incearca sa evacueze un alt proces, si, daca reuseste, reia algoritmul de incarcare, cautand un proces pentru a-l incarca in memorie.
Daca procesul incarcator trebuie sa evacueze un proces, el examineaza toate procesele din memorie. Procesele in starea "zombie" nu vor fi evacuate deoarece ele nu ocupa memorie fizica; procesele blocate in memorie pe timpul operatiilor cu regiuni nu vor fi de asemenea evacuate. Nucleul evacueaza mai degraba procesele in asteptare decât cele in starea "gata de executie", deoarece procesele in starea "gata de executie " au sanse mult mai mari sa fie planificate pentru executie. Alegerea procesului in asteptare care se evacueaza se face in functie de prioritate si de timpul cat procesul a stat in memorie. Daca nu sunt procese in asteptare in memorie, alegerea unui proces in starea "gata de executie " pentru a fi evacuat se face in functie de valoarea nice a procesului si de timpul cat acesta a stat in memorie.
Un proces in starea "gata de executie " trebuie sa stea in memorie cel putin 2 secunde inainte de a fi evacuat, iar un proces poate fi incarcat doar daca a fost evacuat de cel putin timp de 2 secunde. Daca procesul incarcator nu gaseste nici un proces de evacuat si daca nici unul dintre procesele care trebuiesc incarcate nu au stat evacuate cel putin 2 secunde, atunci procesul incarcator se pune in asteptare pe evenimentul: doreste sa incarce un proces in memorie dar nu are loc suficient. Ceasul va trezi procesul incarcator o data pe secunda. Nucleul trezeste de asemenea procesul incarcator daca un alt proces intra in starea de asteptare, devenind astfel mai potrivit pentru a fi evacuat decat procesele examinate anterior. Daca procesul incarcator evacueaza un proces sau daca se pune in asteptare pentru ca nu poate evacua un proces, el isi va relua executia de la inceputul algoritmului, incercand sa incarce un proces.
Figura 11.10 Secventa de operatii de evacuare/incarcare
Figura 11.10 descrie cinci procese si timpii pe care acestea i-au petrecut in memorie sau in zona de evacuare ca urmare a trecerii printr-o secventa de operatii evacuare/incarcare. 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 intreruperilor de ceas la intervale de o secunda. Procesul incarcator 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 in memoria principala. Initial, procesele A si B sunt in memoria principala, iar celelalte procese sunt evacuate. Procesul incarcator nu poate evacua/incarca nici un proces timp de 2 secunde, deoarece nici un proces nu a stat in memorie sau pe dispozitivul de swap timp de 2 secunde (cerinta de rezidenta), dar la sfarsitul celei de-a doua secunde, el evacueaza procesele A si B si incarca procesele C si D; incearca sa incarce si procesul E, dar nu poate deoarece nu mai are loc in memorie. La secunda 3 procesul E este posibil sa fie ales pentru a fi incarcat deoarece el a stat in zona de swap 3 secunde, dar procesul incarcator nu poate evacua procese din memoria principala deoarece timpul lor de rezidenta este sub 2 secunde. La sfarsitul celei de-a 4-a secunde, procesul incarcator evacueaza procesele C si D incarca procesele E si A.
Procesul incarcator alege procesele de incarcat bazandu-se pe marimea timpului cat acestea au stat evacuate. Un alt criteriu ar putea fi incarcarea procesului in 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 in memorie are, totusi, serioase neajunsuri. Mai intai procesul incarcator evacueaza un proces bazandu-se pe prioritatea acestuia, pe timpul de rezidenta in memorie si pe valoarea nice. Desi evacueaza un proces numai pentru a crea spatiu pentru un proces care urmeaza sa fie incarcat, el poate evacua un proces care sa nu asigure memorie suficienta pentru procesul ce se va incarca. De exemplu, daca procesul incarcator incearca sa incarce 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 incarcat.
In al doilea rand, daca procesul incarcator se pune in asteptare deoarece nu poate gasi memorie suficienta pentru a incarca un proces, el cauta din nou un proces pentru a-l incarca desi alesese unul anterior. Motivul este acela ca alte procese evacuate il pot trezi intre timp si acestea pot fi mai potrivite pentru incarcare decat procesul ales anterior. In unele implementari, procesul Incarcator Incearca sa evacueze mai multe procese mai mici pentru a face loc unui proces mare sa fie incarcat inainte sa caute alt proces eligibil pentru incarcare; in aceasta consta revizuirea algoritmului procesului incarcator prezentata In figura 11.9.
In al treilea rand, daca procesul Incarcator alege pentru evacuare un proces In starea "gata de executie", este posibil ca acesta sa nu se fi executat de cand el a fost Incarcat mai Inainte. Figura 11.11 ilustreaza un asemenea caz, In care nucleul Incarca procesul D la secunda 2, planifica procesul C si apoi, la secunda 3, evacueaza procesul D in favoarea procesului E (ca urmare a actiunii valorii nice ) chiar daca procesul D nu s-a executat.
Figura 11.11 Neajunsuri la incarcare/evacuare
Un ultim inconvenient este demn de mentionat: daca procesul incarcator incearca sa evacueze un proces dar nu gaseste spatiu in zona de swap, poate rezulta o blocare a sistemului daca sunt indeplinite urmatoarele patru conditii:
toate procesele din memoria principala sunt inactive (sunt in asteptare);
toate procesele in starea "gata de executie " sunt evacuate;
nu exista spatiu pe dispozitivul de swap pentru noi procese;
nu exista spatiu in memoria principala pentru procesele care trebuie incarcate.
Preocuparile pentru rezolvarea deficientelor procesului incarcator prezentate mai inainte au scazut in ultimii ani, cand au fost implementati algoritmii de paginare la cerere pentru sistemele UNIX.
|
