Alocarea blocurilor de date - UNIX

Alocarea blocurilor de date - UNIX

Cand un proces scrie date intr-un fisier nucleul trebuie sa aloce blocuri disc din sistemul de fisiere (folosite ca blocuri directe de date sau ca blocuri de indirectare). Superblocul sistemului de fisiere contine o lista in care sunt pastrate numerele de blocuri disc libere din sistemul de fisiere. Programul utilitar mkfs (make file system) organizeaza blocurile de date ale sistemului de fisiere intr-o lista inlantuita, fiecare element fiind un bloc disc care contine o lista de numere de blocuri disc libere, si o intrare din aceasta lista reprezinta numarul urmatorului bloc din lista inlantuita. Figura 4.18 prezinta un exemplu de lista inlantuita, unde primul bloc este lista libera din superbloc, iar celalalte blocuri din lista inlantuita contin numere de blocuri libere.

Cand nucleul intentioneaza sa aloce un bloc dintr-un sistem de fisiere (algoritmul alloc, figura 4.19), aloca urmatorul bloc disponibil din lista aflata in superbloc. Odata alocat, blocul nu poate fi realocat pana cand el nu devine liber. Daca blocul alocat este ultimul bloc disponibil din superbloc, nucleul il trateaza ca un pointer la un bloc care contine o alta lista de blocuri libere.

El citeste blocul, completeaza lista din superbloc cu noua lista de numere de blocuri, si apoi permite utilizarea blocului (care a fost tratat ca pointer). El aloca un buffer pentru bloc si sterge datele din buffer (le pune pe 0). Blocul disc a fost asignat si nucleul are acum la dispozitie un buffer cu care lucreaza. Daca sistemul de fisiere nu contine blocuri libere, procesul apelator receptioneaza o eroare.

Daca un proces scrie mai multe date intr-un fisier, el cere repetat sistemului blocuri pentru a stoca datele, insa nucleul i le aloca bloc cu bloc (nu se aloca mai multe blocuri deoadata). Programul mkfs incearca sa organizeze lista inlantuita initiala cu numere de blocuri libere, astfel incat numerele de blocuri distribuite unui fisier sa fie unul langa celalalt. Aceasta duce la marirea performantelor sistemului deoarece se reduce timpul de cautare pe disc si perioada in care un proces asteapta citirea unui fisier secvential.

Figura 4.18. Lista inlantuita a numerelor blocurilor disc libere

Figura 4.18 prezinta numere de blocuri dispuse intr-un tipar obisnuit, bazat probabil pe viteza de rotatie a discului. Din pacate, ordinea numerelor de blocuri libere din lista inlantuita se abate foarte mult de la acest mod de dispunere pe masura ce procesele scriu si sterg fisiere, deoarece numerele de blocuri intra si parasesc aleator lista libera. Nucleul nu sorteaza numerele de blocuri in lista libera.

Algoritmul free pentru eliberarea unui bloc este invers celui de alocare a unui bloc. Daca lista din superbloc nu este plina, numarul blocului eliberat este plasat in lista. Daca lista este plina, blocul eliberat devine bloc de legatura, adica nucleul scrie lista din superbloc in blocul eliberat si scrie blocul pe disc. Apoi, plaseaza numarul blocului nou eliberat in lista din superbloc, acesta fiind singurul element al listei.

algoritm alloc  /* alocarea unui bloc din sistemul de fisiere */

intrare: numarul sistemului de fisiere

iesire: buffer pentru noul bloc

scoate un bloc din lista libera din superbloc;

if (s-a scos ultimul bloc)

obtine buffer pentru blocul scos din superbloc(algoritm getblk );

continutul bufferului este pus pe zero;

decrementeaza contorul total al blocurilor libere;

marcheaza faptul ca superblocul a fost modificat;

return buffer; }

Figura 4.19. Algoritmul pentru alocarea blocurilor disc

In exemplul din figura 4.20 se prezinta o secventa de operatii alloc si free asupra listei libere din superbloc care initial contine un singur numar (vezi figura 4.20 (a)). Nucleul elibereaza blocul numarul 949 si plaseaza numarul acestuia in lista libera (vezi figura 4.20 (b)). Dupa aceea, se solicita doua blocuri. Nucleul asigneaza intai blocul numarul 949 (vezi figura 4.20 (c)), dupa care aloca si scoate blocul numarul 109 din lista libera. Deoarece lista libera din superbloc este acum goala, nucleul copiaza in lista din superbloc continutului blocului 109, urmatorul element din lista inlantuita (vezi figura 4.20 (d)), iar urmatorul bloc de legatura devine blocul 211.

Algoritmii pentru asignarea si eliberarea inodurilor si blocurilor disc sunt similari, nucleul utilizand superblocul ca un cache pentru indici de resurse libere (numere de blocuri si numere de inoduri).

Figura 4.20. Cereri si eliberari de blocuri disc

Nucleul pastreaza o lista inlantuita cu numere de blocuri in care va putea fi regasit numarul oricarui bloc liber din sistemul de fisiere. O astfel de lista nu se pastreaza si pentru inodurile libere.

Motivele acestei tratari diferentiate sunt :

Pentru a determina daca un nod este liber nucleul verifica daca campul tip fisier este 0. In cazul blocurilor, el nu poate determina daca un bloc este liber doar printr-o simpla inspectare. Astfel, este necesara o metoda externa pentru identificarea blocurilor libere, iar implementarile obisnuite utilizeaza o lista inlantuita.

Blocurile disc se preteaza la folosirea in structuri de tip lista inlantuita. Un bloc disc poate cuprinde cu usurinta liste mari cu numere de blocuri libere. In schimb, inodurile nu au loc suficient pentru pastrarea unui numar mare de numere de inoduri libere.

Utilizatorii consuma mult mai multe blocuri disc decat inoduri, astfel ca performantele legate de cautarea blocurilor disc libere au un rol important in stabilirea performantelor generale ale sistemului.