Alocarea unui inod la un fisier nou - UNIX

Alocarea unui inod la un fisier nou - UNIX

Nucleul utilizeaza algoritmul iget pentru a aloca un inod cunoscut (al carui sistem de fisiere si numar de inod a fost determinat anterior). In algoritmul namei, nucleul determina numarul inodului pentru care are loc potrivirea unei componente din numele caii cu numele unei intrari din director. Un alt algoritm, ialloc asigneaza (aloca) un inod disc unui fisier nou creat.

Asa cum s-a mentionat in capitolul 2, sistemul de fisiere contine o lista de inoduri. Un inod este liber daca campul tip are valoarea 0. Cand un proces are nevoie de un inod nou, nucleul ar putea teoretic sa caute un inod liber in lista de inoduri. Insa o astfel de cautare este neeconomica, necesitand cel putin o operatiune de citire (posibil de pe disc) pentru fiecare inod. Pentru imbunatatirea performantei, superblocul sistemului de fisiere contine o zona in care pastreaza numerele de inoduri libere din sistemul de fisiere.

In figura 4.12 se prezinta algoritmul ialloc pentru asignarea de noi inoduri. Pentru a evita conditiile de concurenta, nucleul verifica mai intai daca alte procese nu au blocat accesul la lista de inoduri libere din superbloc. Daca lista cu numere de inoduri din superbloc nu este goala, nucleul asigneaza urmatorul numar de inod, aloca un inod liber in memoria interna pentru inodul disc asignat folosind algoritmul iget (citind inodul de pe disc daca este necesar), copiaza inodul disc in inodul din memoria interna, initializeaza campurile inodului si returneaza inodul blocat. Actualizeaza inodul disc pentru a arata ca acum este folosit: o valoare diferita de zero a campului din inod ce contine tipul fisierului indica faptul ca inodul disc este asignat.

algoritm ialloc /* asigneaza un inod */

intrare: sistemul de fisiere

iesire: inod blocat

if (lista de inoduri din superbloc este goala)

/* lista inodurilor din superbloc nu este goala */

obtine un numar de inod din lista de inoduri din superbloc;

obtine inod (algoritm iget);

if (inodul nu este liber nici acum) /* a fost alocat altui fisier !!! */

/* inodul este liber */

initializeaza inodul;

scrie inodul pe disc;

decrementeaza contorul inodurilor libere din sistemul de fisiere;

return (inod);

}

}

Figura 4.12. Algoritmul pentru alocarea de inoduri noi

Daca lista inodurilor libere din superbloc este goala, nucleul citeste bloc cu bloc lista de inoduri de pe disc si umple lista din superbloc cu numere de inoduri libere, memorand totodata cel mai mare numar de inod gasit. Acesta, numit si inod memorat, este ultimul salvat in superbloc. Cand nucleul va cauta din nou inoduri libere pe disc, va utiliza ca punct de plecare inodul memorat. In acest fel se elimina timpul ce s-ar pierde cu citirea blocurilor disc ce nu contin inoduri libere. Dupa completarea unui nou set de numere de inoduri libere, nucleul reia algoritmul de alocare a inodurilor. La fiecare asignare a unui inod disc, nucleul decrementeaza contorul cu numarul inodurilor libere aflat in superbloc.

In continuare se prezinta modul in care se manipuleaza lista de inoduri libere din superbloc la asignarea unui inod liber. Daca lista arata ca primul sir al figurii 4.13 (a) atunci cand nucleul aloca un inod, el decrementeaza indexul pentru urmatorul numar valid de inod la 18 si utilizeaza numarul de inod 48. Daca lista arata ca primul sir al figurii 4.13 (b), nucleul va observa ca sirul este gol si cauta pe disc inoduri libere incepand de la numarul de inod 470, care este inodul memorat. Cand nucleul completeaza lista libera din superbloc, el memoreaza ultimul inod ca punct de start pentru urmatoarea cautare pe disc. Nucleul asigneaza apoi un inod care tocmai a fost luat de pe disc (471 in figura).

Figura 4.13. Doua siruri de numere de inoduri libere

Algoritmul pentru eliberarea inodurilor este mult mai simplu. Dupa incrementarea numarului total de inoduri disponibile in sistemul de fisiere, nucleul verifica daca superblocul este blocat. Daca este, pentru a evita conditiile de concurenta algoritmul se incheie imediat. Numarul inodului nu este depus in superbloc, insa poate fi gasit pe disc si este disponibil pentru reasignare.

algoritm ifree  /* eliberare inod */

intrare: numar inod din sistemul de fisiere

iesire: niciuna

else

return;

pune numarul inodului in lista inodurilor libere;

Figura 4.14. Algoritmul pentru eliberarea inodurilor

Daca lista nu este blocata, nucleul verifica daca mai este spatiu in lista de inoduri, si daca este, plaseaza numarul de inod in lista dupa care algoritmul se incheie. Daca lista este plina, se compara numarul inodului eliberat cu cel al inodului memorat. Daca este mai mic, devine noul inod memorat. Vechiul inod memorat nu este pierdut, deoarece nucleul il poate gasi la urmatoarea cautare in lista de inoduri de pe disc. Ideal ar fi sa nu existe inoduri libere ale caror numere sunt mai mici decat numarul inodului memorat, dar in realitate sunt posibile si astfel de situatii.

Sa consideram, de exemplu, doua cazuri in care poate avea loc eliberarea inodurilor. Daca lista inodurilor libere din superbloc nu este plina, vezi figura 4.13 (a), nucleul plaseaza in lista numarul inodului si incrementeaza indexul la urmatorul inod liber. Daca lista de inoduri libere este plina, vezi figura 4.15 (a), nucleul compara numarul inodului eliberat (499) cu numarul inodului memorat (535), ai intrucat este mai mic, acesta devine noul inod memorat. Daca nucleul elibereaza apoi inodul 601 (vezi figura 4.15 (c) ), continutul listei de inoduri libere din superbloc nu va fi schimbat. Ulterior, dupa ce va consuma inodurile din lista libera, nucleul va cauta inoduri libere pe disc incepand cu numarul 499 si va regasi ainodurile 535 si 601.

Figura 4.15. Plasarea numerelor de inoduri libere in superbloc

In paragraful anterior s-au descris situatiile simple ale algoritmilor. In cele ce urmeaza consideram cazul in care nucleul asigneaza un inod nou, iar apoi aloca o copie in memoria interna pentru acesta. In algoritmul ialloc se arata ca nucleul ar putea gasi inodul deja asignat. Desi rar, urmatorul scenariu prezinta un astfel de caz (vezi figurile 4.16 si 4.17). Se considera trei procese (A, B si C) si se presupune ca nucleul, actionand in numele procesului A, asigneaza inodul I, dar adoarme inainte de a copia inodul in memoria interna. Algoritmii iget (apelat de ialloc) si bread (apelat de iget) ofera mari sanse procesului A de a adormi. Cat timp procesul A este adormit, sa presupunem ca B incearca sa aloce un nou inod, dar descopera ca lista inodurilor libere din superbloc este goala. Procesul B incepe cautarea de inoduri libere pe disc si sa presupunem ca isi incepe cautarea de la un numar de inod mai mic decat al inodului pe care A il asigneaza. Este posibil ca B sa gaseasca inodul I liber pe disc, deoarece A este inca adormit, si nucleul nu stie ca inodul I urmeaza sa fie asignat. Procesul B, fara a realiza pericolul, incheie cautarea pe disc si umple lista inodurilor libere din superbloc (I este printre elemente), dupa care asigneaza un inod si dispare din scenariu. Cand A se trezeste, el incheie asignarea inodului I. Sa presupunem acum ca procesul C va solicita ulterior un inod liber si va primi inodul I. Cand se creeaza copia din memoria interna pentru inod, el va gasi campul corespunzator tipului fisierului setat (diferit de 0), ceea ce arata ca inodul a fost deja asignat. Nucleul verifica aceasta conditie si daca inodul a fost deja alocat, incearca sa asigneze unul nou. Actualizarea inodului pe disc imediat dupa asignarea sa in ialloc, micsoreaza posibilitatea de aparitie a conditiilor de concurenta, deoarece campul tip fisier arata ca inodul este utilizat.

Pentru a preveni alte conditii de concurenta, lista de inoduri din superbloc va fi blocata pe durata citirii unui nou set de inoduri de pe disc. Daca lista din superbloc nu ar fi blocata, sa presupunem cazul in care ea este goala si un proces solicita un inod.

procesul A procesul B procesul C

Asigneaza inodul I din : :

superbloc : :

Doarme in timpul : :

citirii inodului (a) : :

: Incearca sa asigneze :

: un inod din super- bloc :

: Superblocul este gol (b) :

: Cauta inoduri libere pe disc, :

: pune inodul I in superbloc (c) :

Inodul I este utilizat in : :

memoria interna : :

: Incheie cautarea, :

: asigneaza un alt inod (d) :

: : Asigneaza inodul I din : : superbloc

: : Inodul I este utilizat ! : : Asigneaza un alt inod (c)

Timp

Figura 4.16. Conditii de concurenta ce au loc la asignarea inodurilor

Procesul incerca sa completeze lista cu inoduri de pe disc, iar pe durata operatiilor de I/O se va pune in asteptare. Daca un alt proces incearca si el sa asigneze un inod nou si gaseste lista goala, va executa ceea ce a executat si cel anterior. Aceasta dubla umplere a listei (de fapt o umplere si o rescriere) are ca efect folosirea ineficienta a resurselor, si constituie totodata o premisa importanta pentru cresterea conditiilor de concurenta de tipul celor descrise anterior. Similar, daca procesul elibereaza un inod si nu verifica daca lista este blocata, s-ar putea rescrie numere de inoduri aduse deja in lista libera aduse de un proces care executa popularea listei cu inoduri de pe disc.

Figura 4.17. Conditii de concurenta ce au loc la asignarea inodurilor

Aceasta situatie ar genera conditii de concurenta de tipul celor descrise anterior mult mai frecvente. Desi nucleul rezolva satisfacator aceste conditii de concurenta, performantele sistemului au de suferit.