Scenarii pentru regasirea unui buffer - UNIX

Scenarii pentru regasirea unui buffer - UNIX

Asa cum se arata in figura 2.1, algoritmii de nivel superior din subsistemul de fisiere utilizeaza algoritmi pentru gestiunea buffer-ului cache. Algoritmii de nivel superior determina numarul dispozitivului logic si numarul blocului pe care doresc sa-l acceseze cand incearca sa regasesca un bloc. De exemplu, daca un proces doreste sa citeasca date din fisier, nucleul determina care sistem de fisiere contine fisierul si care bloc din sistemul de fisiere contine datele (vezi capitolul 4). Cand citeste date dintr-un anumit bloc disc, nucleul verifica daca blocul este in sistemul de buffere. Daca nu este ii asigneaza un buffer liber. Cand scrie datele unui anumit bloc disc, nucleul verifica daca blocul este in sistemul de buffere, iar daca nu este, asigneaza un buffer liber pentru acel bloc.

algoritm getblk

intrari: numarul sistemului de fiiere;

numarul blocului;

ieire: buffer blocat care poate fi asociat blocului

/* scenariul 1 */

marcheaza buffer-ul ocupat;

scoate buffer-ul din lista buffere-lor libere ;

return buffer;

}

else /* blocul nu este in listele hash */

scoate buffer-ul din lista buffere-lor libere ;

if (buffer-ul marcat pentru scriere intarziata)

/* scenariul 2 -- se gasete un buffer liber */

scoate buffer-ul din vechea lista hash;

pune bufferul in noua lista hash;

return buffer;

}

}

Figura 3.4. Algoritmul pentru alocarea bufferelor

Algoritmii pentru citirea si scrierea blocurilor disc utilizeaza algoritmul getblk (figura 3.4) pentru alocarea de buffere din sistemul de buffere.Acest subcapitol descrie cinci scenarii tipice pe care nucleul le urmeaza in algoritmul getblk pentru alocarea unui buffer pentru un bloc disc.

Nucleul gaseste blocul in lista hash si buffer-ul sau este liber.

Nucleul nu gaseste blocul in lista hash, astfel ca el aloca un buffer din lista buffere-lor libere.

Nucleul nu gaseste blocul in lista hq si incercand sa aloce un buffer din FLB (ca in scenariul 2), il gaseste marcat 'imtarzire la scriere'. Nucleul trebuie sa scrie acest buffer pe disc si sa aloce alt buffer.

Nucleul nu poate gasi blocul in lista hash, iar lista buffere-lor libere este goala.

Nucleul gaseste blocul in lista hash, dar buffer-ul este momentan ocupat.

Se va prezenta in detaliu fiecare scenariu.

Cand cauta un bloc in sistemul de buffere (dupa numarul dispozitivului si cel de bloc), nucleul gaseste lista hash care ar trebui sa contina blocul. Apoi parcurge lista pana cand (primul scenariu) gaseste buffer-ul ale carui numere de dispozitiv si de bloc se potrivesc cu cele cautate. Nucleul verifica daca buffer-ul este liber, si daca este, marcheaza buffer-ul 'ocupat' astfel incat alte procese sa nu-l mai poata accesa. Apoi nucleul scoate buffer-ul din lista buffere-lor libere , deoarece un buffer nu poate fi simultan si ocupat si in lista buffere-lor libere. Daca alte procese incearca sa acceseze blocul pe timpul cat buffer-ul este blocat, acestea se pun in asteptare pana cand buffer-ul este eliberat. Figura 3.5 descrie primul scenariu, in care nucleul cauta blocul 4 in lista hash marcata 'numarul blocului 0 mod 4'.

Gasind bufferul, nucleul il scoate din lista buffere-lor libere si realizeaza legatura directa intre blocurile 5 si 28.Inainte de a continua cu alte scenarii, sa vedem ce se intampla cu un buffer dupa ce este alocat. Nucleul poate citi date de pe disc in buffer, sau poate sa scrie date in buffer sau posibil pe disc. Nucleul lasa buffer-ul marcat 'ocupat', pentru ca nici un alt proces sa nu-l poata accesa si sa nu-i poata schimba continutul cat timp este ocupat, pastrandu-se astfel integritatea datelor din buffer.

Figura 3.5. Scenariul 1 pentru gasirea unui buffer:

buffer-ul este in lista hash

Cand nucleul termina de folosit bufferul, el il elibereaza urmand algoritmul brelse (figura 3.6). In algoritmul brelse nucleul trezeste toate procesele care asteptau eliberarea buffer-ului respectiv, cat si pe cele care asteptau un buffer liber (unul oarecare). In ambele cazuri, buffer-ul eliberat este disponibil pentru a fi utilizat de catre procesele care asteptau acest eveniment. Apoi, nucleul plaseaza buffer-ul la sfarsitul listei buffere-lor libere , daca nu a aparut o eroare de I/O sau daca blocul nu a fost marcat ca 'vechi'. In aceste ultime cazuri, nucleul plaseaza buffer-ul la inceputul listei buffere-lor libere. Acum buffer-ul este liber, putand fi utilizat de orice proces. Primul proces care-l obtine il blocheaza, prevenind astfel folosirea lui de catre alte procese (vezi 2.2.2.4). Nucleul apeleaza algoritmul brelse cand un proces nu mai are nevoie de un buffer, precum si atunci cand trateaza o intrerupere disc pentru a elibera buffere-le folosite pentru operatii asincrone de I/O cu discul.

algoritm brelse

intrare: buffer blocat

iesire: nimic

Figura 3.6. Algoritmul pentru eliberarea unui buffer

Nucleul ridica nivelul de executie al procesorului pentru a preveni intreruperile de disc pe timpul manipularii listei buffere-lor libere. In mod similar, pot aparea efecte nedorite cand o rutina de tratare a intreruperilor apeleaza brelse pe timpul cat un proces executa getblk, astfel ca nucleul ridica de asemenea nivelul de executie al procesului in puncte critice din algoritmul getblk.

In scenariul al doilea din algoritmului getblk, nucleul cauta in lista hash care ar trebui sa contina blocul, insa acesta nu este gasit. Deoarece blocul nu poate fi in alta lista hash, inseamna ca acesta nu este in bufferul cache. Astfel, nucleul sterge primul buffer din lista buffere-lor libere . Daca buffer-ul nu a fost marcat "intarziere la scriere" , nucleul il marcheaza 'ocupat', il scoate din lista hash in care acesta se afla in acel moment, inlocuieste numerele de dispozitiv si de bloc din antetul buffer-ului cu cele ale blocului disc cautat de proces, si apoi plaseaza buffer-ul, in noua lista hash. Nucleul foloseste buffer-ul dar nu are nici o informatie asupra faptului ca buffer-ul continea date pentru alt bloc disc.

Un proces care cauta vechiul bloc disc nu-l va gasi in sistemul de buffere si va trebui sa aloce din lista buffere-lor libere un nou buffer pentru acesta. Cand nucleul termina de folosit buffer-ul, il elibereaza asa cum va fi descris mai departe. Spre exemplu, in figura 3.7 nucleul cauta blocul 18 dar nu-l gaseste in lista hash marcata 'numarul blocului 2 mod 4'. De aceea, scoate primul buffer din lista buffere-lor libere (blocul 3), il asigneaza blocului 18 si il plaseaza in lista hash corespunzatoare.

Figura 3.7. Al doilea scenariu pentru alocarea buffere-lor

In al treilea scenariu din algoritmul getblk, nucleul trebuie de asemenea sa aloce un buffer din lista buffere-lor libere . Totusi, el descopera ca buffer-ul pe care l-a scos din lista este marcat 'intarziere la scriere ' si trebuie sa-i scrie continutul pe disc inainte de a-l folosi. Nucleul incepe o operatie de scriere asincrona pe disc si incearca sa aloce un alt buffer din lista buffere-lor libere .

Cand scrierea asincrona se incheie, nucleul elibereaza buffer-ul si-l plaseaza la capul listei buffere-lor libere .De exemplu, in figura 3.8 nucleul nu poate gasi blocul 18, dar cand incearca sa aloce primele doua buffere (unul cate unul) din lista buffere-lor libere , le gaseste marcate 'intarziere la scriere '.

Figura 3.8. Al treilea scenariu pentru alocarea buffere-lor.

Nucleul le scoate din lista buffere-lor libere si incepe operatiile pentru scrierea lor pe disc. Apoi, aloca al treilea buffer din lista, blocul 4. Nucleul resigneaza campurile numar bloc si numar dispozitiv ale buffer-ului in mod corespunzator si plaseaza bufferul, acum marcat ca blocul 18, in noua sa lista hash.

In al patrulea scenariu (figura 3.9), nucleul, care actioneaza in folosul procesului A, nu gaseste blocul disc in lista hash corespunzatoare, astfel ca incearca sa aloce un buffer nou din lista buffere-lor libere (ca in scenariul al doilea).

Figura 3.9. Al patrulea scenariu pentru alocarea buffere-lor

Totusi, nu este disponibil nici un buffer in lista buffere-lor libere, asa ca procesul A se pune in asteptare pana cand un alt proces executa algoritmul brelse, eliberand un buffer. Cand nucleul planifica pentru executie procesul A,el trebuie sa caute din nou blocul in lista hash. El nu poate aloca imediat un buffer din lista buffere-lor libere deoarece este posibil ca unul din procesele care asteptau un buffer liber sa fi alocat un buffer abia eliberat pentru blocul tinta cautat de procesul A.

Figura 3.10. Concurenta pentru alocarea unui buffer liber.

In acest fel, cautand din nou blocul, se asigura ca un singur buffer contine blocul disc. Figura 3.10 ilustreaza concurenta dintre doua procese pentru ocuparea unui buffer liber.

Ultimul scenariu (figura 3.11) este complicat, deoarece implica relatii complexe intre mai multe procese. Sa presupunem ca nucleul, actionand pentru procesul A, cauta un bloc disc si aloca un buffer, dar se pune in asteptare inaintea eliberarii buffer-ului. De exemplu, daca procesul A incearca sa citeasca un bloc disc si aloca un buffer ca in scenariul 2, el se va pune apoi in asteptare cat timp dureaza operatiile de I/O cu discul. In timp ce procesul A este in asteptare, sa presupunem ca nucleul planifica pentru executie un al doilea proces, B, care incearca sa acceseze blocul disc al carui buffer tocmai a fost blocat de procesul A. Procesul B (urmand scenariul 5) va gasi blocul blocat in lista hash. Deoarece este ilegal sa utilizeze un buffer blocat si este ilegal sa aloce un al doilea buffer pentru acelasi bloc disc, procesul B marcheaza bufferul ' in cerere' si apoi se pune in asteptare pana cand procesul A elibereaza bufferul.

Figura 3.11. Al cincilea scenariu pentru alocarea buffere-lor.

Procesul A eventual va elibera buffer-ul si va nota daca acesta este 'in cerere'. El trezeste toate procesele care asteapta pe evenimentul 'buffer-ul devine liber', incluzand aici si procesul B. Cand nucleul planifica din nou procesul B, acesta trebuie sa verifice daca buffer-ul este liber.

Un alt proces, C, putea sa astepte eliberarea aceluiasi buffer si putea fi planificat de nucleu sa ruleze inaintea procesului B. Dar procesul C se putea pune in asteptare, lasand bufferul blocat. Din aceasta cauza procesul B trebuie sa verifice daca intr-adevar buffer-ul este liber.

Procesul B trebuie sa mai verifice si daca buffer-ul contine blocul disc pe care l-a solicitat initial, deoarece procesul C putea sa aloce buffer-ul unui alt bloc, ca in scenariul 2. Cand se executa procesul B, acesta verifica daca buffer-ul este cel asteptat, iar in caz negativ este necesar sa caute din nou blocul. Daca ar urma sa aloce automat un buffer din lista buffere-lor libere, s-ar scapa din vedere posibilitatea ca un alt proces sa fi alocat deja un buffer pentru acel bloc.

In final, procesul B va gasi blocul, posibil alocand un nou buffer din lista buffere-lor libere conform scenariului al doilea. In figura 3.11 de exemplu, un proces care cauta blocul 99 il gaseste in lista hash corespunzatoare, dar blocul este marcat ca 'ocupat'. Procesul se pune in asteptare pana cand blocul devine liber si apoi reia algoritmul de la inceput.

Figura 3.12. Concurenta pentru un buffer blocat

In figura 3.12 se descrie o situatie de concurenta pentru un buffer blocat.

Algoritmul pentru alocarea buffere-lor trebuie sa ofere siguranta. Adica, procesele nu trebuie sa astepte la nesfarsit, ci trebuie sa obtina candva un buffer. Nucleul garanteaza ca toate procesele care asteapta buffere vor fi trezite, deoarece el aloca buffere pe timpul executiei apelurilor sistem si le elibereaza la revenirea din acestea. Procesele in modul utilizator nu controleaza direct alocarea buffere-lor de catre nucleu. Nucleul pierde controlul asupra unui buffer numai cand asteapta terminarea operatiilor de I/O intre buffer si disc. Se poate ca driverul de disc sa fie defect, neputand sa intrerupa C.P.U., ceea ce impiedica nucleul sa elibereze buffere. Driverul de disc trebuie sa monitorizeze hardware-ul in asemenea cazuri si sa intoarca o eroare catre nucleu. Pe scurt, nucleul poate garanta ca procesele care asteapta un buffer vor fi trezite.

Este de asemenea posibil sa ne imaginam cazul in care un proces trebuie neaparat sa acceseze un buffer. In al patrulea scenariu, de exemplu, daca asteapta cateva procese ca un buffer sa devina liber, nucleul nu garanteaza ca vor obtine bufferul in ordinea in care l-au cerut. Un proces poate fi in asteptare si poate fi trezit cand un buffer devine liber, dar se poate pune din nou in asteptare pentru ca un alt proces a reusit sa obtina controlul mai inainte asupra bufferu-lui. Teoretic, aceasta se poate prelungi la nesfarsit, dar practic, nu reprezinta o problema din cauza numarului mare de buffere configurate in sistem.