Alocarea spatiului de evacuare - UNIX

Alocarea spatiului de evacuare - UNIX

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, eliberand 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.

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 campurile 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.