GESTIUNEA BUFFER-ULUI CACHE

GESTIUNEA BUFFER-ULUI CACHE

Asa cum a fost mentionat in capitolul anterior, nucleul pastreaza fisierele pe dispozitive de memorare permitand proceselor sa stocheze informatii noi sau sa regaseasca informatii stocate anterior. Cand un proces doreste sa acceseze date dintr-un fisier, nucleul aduce datele in memoria principala unde procesele le pot examina, le pot modifica si pot cere ca acestea sa fie salvate din nou in sistemul de fisiere. De exemplu, sa revedem programul copy din figura 1.3: nucleul citeste datele din primul fisier in memorie iar apoi scrie datele in cel de-al doilea fisier. In timp ce trebuie sa transfere datele din fisier in memorie, nucleul trebuie de asemenea sa transfere si date auxiliare in memorie pentru a le manipula. Spre exemplu, superblocul unui sistem de fisiere descrie,printre altele, spatiul liber disponibil din sistemul de fisiere. Nucleul citeste superblocul in memorie pentru a-i accesa datele si il scrie inapoi in sistemul de fisiere cand doreste sa salveze datele. In mod similar, inodul descrie aranjarea unui fisier. Nucleul citeste un inod in memorie cand doreste sa acceseze datele dintr-un fisier si rescrie inodul inapoi in sistemul de fisiere cand doreste sa actualizeze starea fisierului. El manipuleaza aceste date auxiliare fara cunoasterea explicita a proceselor care ruleaza.

Nucleul poate citi si scrie direct pe si de pe disc in toate accesele la sistemul de fisiere, dar timpul de raspuns al sistemului si transferul pot fi afectate din cauza ratei de transfer scazute a discului. Nucleul incearca de aceea sa minimizeze frecventa de acces la disc prin mentinerea unui sistem de buffere interne de date, numit buffer cache, care contine datele din blocurile disc recent utilizate.

In figura 2.1 s-a prezentat pozitia modulului buffer cache in cadrul arhitecturii nucleului, si anume intre subsistemul de fisiere si blocul driverelor de dispozitiv . Cand se citesc date de pe disc, nucleul le cauta mai intai in buffer-ul cache. Daca datele sunt deja in buffer-ul cache, nucleul nu mai trebuie sa le citeasca de pe disc. In cazul in care datele nu sunt in buffer, nucleul le citeste de pe disc si le aduce in buffer-ul cache, folosind un algoritm care incearca sa salveze in buffer-ul cache cat de multe date utile.

Similar, datele care se scriu pe disc sunt aduse in buffer-ul cache astfel incat ele sa fie acolo in cazul in care nucleul va incerca sa le citeasca ulterior. Nucleul incearca de asemenea sa minimizeze frecventa operatiilor de scriere pe disc determinand daca este cu adevarat necesar ca datele sa fie stocate pe disc sau daca sunt date intermediare care vor fi curand rescrise.

Algoritmii de nivel inalt ai nucleului impun buffer-ului cache sa pre-stocheze date sau sa le scrie cu intarziere (delay-write) pentru a maximiza efectul stocarii. Acest capitol descrie algoritmii folositi de nucleu pentru a manipula buffere-le cache.

1 Antetul unui buffer

Pe timpul initializarii sistemului nucleul aloca spatiu pentru un numar de buffere in concordanta cu dimensiunea memoriei si performantele sistemului. Un buffer consta din doua parti: o zona de memorie care contine date de pe disc si un antet (header) prin care se identifica buffer-ul. Deoarece este o corespondenta biunivoca intre antet si zona de date, prin 'buffer' se vor referi in continuare ambele componente, contextul urmand sa clarifice la care anume se face referirea.

Datele dintr-un buffer corespund datelor dintr-un bloc de disc logic al unui sistem de fisiere, iar nucleul determina continutul buffer-ului prin examinarea campurilor de identificare din antet. Bufferul este copia din memoria interna a blocului disc. Asocierea dintre continutul blocului disc si buffer este temporara (pana cand nucleul decide sa asocieze buffer-ului alt bloc). Un bloc disc nu poate fi asociat simultan mai multor buffere. Daca doua buffere ar contine datele corespunzatoare unui bloc disc, nucleul nu ar sti care buffer contine datele curente si ar putea rescrie incorect datele pe disc. De exemplu, sa presupunem ca un bloc disc este asociat buffer-elor, A si B. Daca nucleul scrie date mai intai in buffer-ul A si apoi in buffer-ul B, blocul disc trebuie sa contina informatiile din buffer-ul B.

Figura 1. Antetul bufferului

In cazul in care se va scrie pe disc intai buffer-ul B si apoi buffer-ul A, blocul disc va contine date incorecte. Antetul buffer-ului (figura 1) contine un camp numarul dispozitivului si un camp numar de bloc care specifica sistemul de fisiere, respectiv numarul blocului de date de pe disc. Prin intermediul lor buffer-ul este identificat in mod unic.

Numarul dispozitivului este numarul logic al sistemului de fisier (vezi paragraful 2.2.1), nu numarul unitatii dispozitivului fizic (discului). Antetul contine de asemenea un pointer la zona de date a buffer-ului, a carei dimensiune trebuie sa fie cel putin egala cu cea mai mare dimensiune a unui bloc disc, si un camp stare care prezinta starea curenta a buffer-ului. Starea unui buffer este o combinatie a urmatoarelor conditii:

Buffer-ul este momentan blocat (se vor folosi termenii 'blocat ' sau 'ocupat ', si termenii 'liber ' sau ' deblocat ' pentru starea opusa)

Bufferul contine date valide.

Nucleul trebuie sa scrie continutul buffer-ului pe disc inainte de reasignarea acestuia; aceasta conditie este cunoscuta ca intarziere scriere.

Nucleul citeste sau scrie continutul bufferului pe disc.

Un proces asteapta ca bufferul sa devina liber.

Antetul mai contine si doua seturi de pointeri, folositi de algoritmii de alocare a buffere-lor pentru a mentine intreaga structura a sistemului de buffere.

2 Structura sistemului de buffere

Nucleul stocheaza datele intr-un sistem de buffere conform algoritmului 'cel mai putin recent folosit' : dupa ce aloca un buffer unui bloc disc, nucleul nu-l poate utiliza pentru alt bloc pana cand toate celalalte buffere nu vor fi utilizate. Nucleul mentine o lista a buffere-lor libere (free list), care pastreaza buffer-ele cel mai putin recent folosite in ordinea inversa a eliberarii lor.

Lista buffere-lor libere este o lista circulara dublu inlantuita de buffere care are un antet de buffer special pentru a-i marca inceputul si sfarsitul (fig 2).

Fiecare buffer este pus in lista buffere-lor libere la initializarea sistemului. Nucleul ia un buffer din capatul listei cand doreste un buffer liber (cand nu doreste unul anume), dar poate lua un buffer din interiorul listei cand cauta un anumit bloc si il identifica in sistemul de buffere. In ambele cazuri, buffer-ul este scos din lista.

Figura 2. Lista bufferelor libere (free list)

Cand nucleul introduce un buffer in sistemul de buffere, il ataseaza, de obicei, la coada listei, si rareori in capul listei (pentru cazurile in care apar erori), dar niciodata nu-l ataseaza in mijlocul listei.Pe masura ce nucleul scoate buffere din lista buffere-lor libere, un buffer cu date valide avanseaza catre capul listei (vezi figura 2). Din aceasta cauza, buffere-le care se afla cel mai aproape de capul listei nu au fost folosite atat de recent ca cele de la sfarsitul listei.

Cand nucleul acceseaza un bloc disc, el cauta un buffer care are numarul dispozitivului si cel de bloc corespunzatoare. In loc sa caute in intregul sistem de buffere, nucleul organizeaza buffere-le in liste separate, ce sunt identificate folosind o functie de hash (de dispersie) ce are ca parametri numarul blocului si numarul dispozitivului. Nucleul leaga buffer-le intr-o lista circulara dublu inlantuita numita lista hash (hash queue),similara cu structura listei buffer-lor libere. Numarul de buffere dintr-o lista hash variaza pe durata de viata a unui sistem asa cum vom vedea. Nucleul trebuie sa utilizeze o functie de dispersie care distribuie bufferele uniform in setul de liste hash, dar care trebuie sa fie simpla pentru a nu fi afectate performantele sistemului. Numarul de liste hash din sistem este configurat de administratorul de sistem la instalarea sistemului.

Figura 3 ilustreaza dispunerea buffere-lor in listele hash. Antetele listelor hash sunt in partea stanga a figurii, iar patratelele de pe fiecare rand sunt buffere din lista hash. Astfel, patratele marcate cu 28, 4 si 64 reprezinta buffere-le din lista hash corespunzatoare 'numarului blocului 0 mod 4' (numar bloc modulo 4 egal cu 0). Liniile intrerupte dintre buffere reprezinta pointerii din lista (inainte si inapoi). Pentru simplificare, in urmatoarele figuri nu se vor mai reprezenta acesti pointeri, insa existenta lor este implicita. Similar, figura identifica blocurile numai prin numerele asociate lor si utilizeaza o functie de dispersie dependenta numai de numarul blocului. Totusi, implementarile reale folosesc si numarul dispozitivului.

Figura Buffere-le din listele hash

Oricare dintre buffere se afla intr-o lista hash, insa pozitia sa in cadrul listei nu prezinta o semnificatie anume. Dupa cum am stabilit mai inainte, doua buffere nu pot contine simultan datele aceluiasi bloc disc. Din aceasta cauza fiecare bloc disc se afla doar intr-o singura lista hash, iar in cadrul acesteia o singura data. Deoarece un buffer se poate gasi simultan in lista buffere-lor libere si intr-o lista hash, nucleul are la dispozitie doua cai pentru a-l gasi:

- el cauta in listele hash daca doreste un bloc anume si scoate un buffer din lista buffere-lor libere daca doreste un buffer liber oarecare. Urmatorul paragraf va ilustra modul in care nucleul gaseste un anumit bloc in buffer-ul cache si cum manipuleaza bufferele din listele hash si din lista buffere-lor libere. Concluzionand, un buffer se afla intr-una din listele hash, insa nu este obligatoriu sa fie in lista buffere-lor libere.

3 Scenarii pentru regasirea unui buffer

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 regaseasca 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 fisiere;

numarul blocului;

iesire: buffer blocat care poate fi asociat blocului

S

while (buffer-ul nu este gasit)

S

if (blocul este in listele hash)

S

if (buffer ocupat) /* scenariul 5 */

S

sleep (pana bufferul devine liber);

continue; /* salt la while */

}

/* scenariul 1 */

marcheaza buffer-ul ocupat;

scoate buffer-ul din lista buffere-lor libere ;

return buffer;

}

else /* blocul nu este in listele hash */

S

if (nu exista buffere in lista buffere-lor libere)

/* scenariul 4 */

S

sleep (pana cand orice buffer devine liber);

continue; /* salt la while */

}

scoate buffer-ul din lista buffere-lor libere ;

if (buffer-ul marcat pentru scriere intarziata)

S /* scenariul 3 */

scriere asincrona a buffer-ului pe disc;

continue; /* salt la while */

}

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

scoate buffer-ul din vechea lista hash;

pune bufferul in noua lista hash;

return buffer;

}

}

Figura 4. Algoritmul pentru alocarea bufferelor

Algoritmii pentru citirea si scrierea blocurilor disc utilizeaza algoritmul getblk (figura 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 'intarziere 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 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 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 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

S

trezeste toate procesele care asteapta ca orice buffer sa devina

liber;

trezeste toate procesele care asteapta ca acest buffer sa devina

liber;

/* blocheaza intreruperile*/

ridica nivelul de executie al procesorului;

if (continutul buffer-ului este valid si buffer-ul nu este ' vechi ')

insereaza buffer-ul la sfarsitul listei buffere-lor libere;

else

insereaza buffer-ul la inceputul listei buffere-lor libere;

/* activeaza intreruperile */

coboara nivelul de execuTie al procesorului;

deblocheaza buffer-ul;

Figura 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 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 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 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 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 reasigneaza 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 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 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 10. Concurenta pentru alocarea unui buffer liber.

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

Ultimul scenariu (figura 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 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 acluiasi 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 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 12. Concurenta pentru un buffer blocat

In figura 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.

4. Citirea si scrierea blocurilor disc

Dupa prezentarea algoritmului de alocare a buffere-lor, procedurile pentru citirea si scrierea blocurilor disc vor fi mai usor de inteles. Pentru a citi un bloc disc (figura 13), un proces foloseste algoritmul getblk pentru a-l cauta in buffer-ul cache.Daca este in buffer-ul cache nucleul il poate returna imediat fara citirea fizica a blocului de pe disc. Daca nu este in buffer-ul cache nucleul apeleaza driverul de disc pentru a 'planifica' o cerere de citire si se pune in asteptare pana la terminarea operatiilor de I/O. Driverul de disc specifica controlerului de disc ca doreste sa citeasca date, iar acesta transmite apoi datele la buffer. In final, controlerul de disc intrerupe procesorul cand s-au terminat operatiile de I/O si rutina de tratare a intreruperii de disc trezeste procesele care asteapta, continutul blocului disc fiind acum in buffer. Modulele care solicitau blocul respectiv au acum datele; cand nu mai au nevoie de buffer, acesta este eliberat, pentru a putea fi accesat si de alte procese.

algoritm bread /* citire bloc */

intrare: numarul blocului din sistemul de fisiere;

iesire: buffer continand date;

S

obtine buffer pentru bloc (algoritm getblk);

if (datele din buffer sunt valide)

return (buffer);

initiaza operatia de citire a discului;

sleep (pana la incheierea operatiei de citire)

return (buffer);

Figura 1 Algoritmul pentru citirea unui bloc disc

Capitolul 5 prezinta modul in care modulele de nivel inalt ale nucleului (cum ar fi subsistemul de fisiere) pot anticipa necesitatea unui al doilea bloc disc cand un proces citeste secvential un fisier. Modulele solicita a doua operatie asincrona de I/O in speranta ca datele vor fi in memorie cand va fi nevoie de ele, sporind astfel performantele sistemului. Pentru a realiza aceasta, nucleul executa algoritmul de citire in avans a unui bloc, breada (figura 14): nucleul verifica daca primul bloc este in buffer-ul cache si, daca nu este, invoca driver-ul de disc pentru a citi acel bloc. Daca al doilea bloc nu este in buffer-ul cache, nucleul comanda driver-ului de disc sa-l citeasca asincron. Apoi procesul se pune in asteptare pana cand operatiile de I/O pentru primul bloc s-au terminat.

Cand este trezit, procesul intoarce buffer-ul pentru primul bloc si nu-l intereseaza cand se termina operatiile de I/O pentru al doilea bloc. Cand operatiile de I/O pentru al doilea bloc s-au terminat, controlerul de disc intrerupe sistemul; rutina de tratare a intreruperii recunoaste ca operatiile de I/O au fost asincrone si elibereaza buffer-ul (algoritmul brelse).

algoritm breada /* citire bloc si citire in avans */

intrari: (1) numarul blocului din sistemul de fisiere pentru citire

imediata;

(2) numarul blocului din sistemul de fisiere pentru citire

asincrona;

iesire: buffer cu date din citirea imediata;

S

if (primul bloc nu este in buffer-ul cache);

S

obtine buffer pentru blocul (1) (algoritm getblk);

if (datele din buffer nu sunt valide)

initiaza citirea de pe disc;

}

if (blocul (2) nu este in buffer-ul cache)

S

obtine buffer pentru al doilea bloc (algoritm getblk);

if (datele din buffer sunt valide)

elibereaza buffer-ul (algoritm brelse);

else

initiaza citirea de pe disc;

}

if (blocul (1) era initial in buffer-ul cache)

S

citeste blocul (1) (algoritmul bread);

return buffer;

}

sleep (pana cand primul buffer alocat contine date valide);

return buffer;

Figura 14. Algoritmul pentru citirea blocului in avans

Daca nu ar elibera buffer-ul, acesta ar ramane blocat, si deci, inaccesibil tuturor proceselor. Este imposibil ca buffer-ul sa se deblocheze inaintea incheierii operatiei de I/O deoarece continutul sau este invalid. Mai tarziu, daca procesul doreste sa citeasca al doilea bloc, ar trebui sa-l gaseasca in buffer-ul cache, operatiile de I/O terminandu-se intre timp.

Daca la inceputul algoritmului breada primul bloc era in buffer-ul cache, nucleul verifica imediat daca al doilea bloc este in cache, procedand asa cum am aratat mai sus.

Algoritmul pentru scrierea continutului unui buffer intr-un bloc disc este similar (figura 15). Nucleul informeaza driverul de disc ca are un buffer al carui continut ar trebui scris, iar driverul planifica blocul pentru operatii de I/O. Daca scrierea este sincrona, procesul apelant se pune in asteptare pana la terminarea operatiilor de I/O, iar la trezire elibereaza buffer-ul. Daca scrierea este asincrona, nucleul incepe scrierea pe disc dar nu asteapta terminarea acesteia. Nucleul va elibera buffer-ul la terminarea operatiilor de I/O.

Exista situatii descrise in urmatoarele doua capitole, cand nucleul nu scrie imediat datele pe disc. Daca executa o scriere cu intarziere, el marcheaza buffer-ul in mod corespunzator, elibereaza buffer-ul utilizand algoritmul brelse si continua fara a planifica operatii de I/O. Nucleul scrie blocul pe disc inainte ca alt proces sa poata realoca buffer-ul altui bloc asa cum s-a prezentat in scenariul al treilea din getblk. Daca un proces acceseaza buffer-ul inainte de a trebui sa fie scris, se elimina o operatie cu discul, ceea ce duce la cresterea performantelor sistemului. Practic, se amana cat se poate de mult scrierea unui buffer pe disc in speranta ca el va fi modificat de acelasi proces sau de altele.

algoritm bwrite /* scriere bloc */

intrare: buffer;

iesire: nimic;

S

initiaza scrierea pe disc;

if (operatiile de I/O sunt sincrone)

S

sleep (pana la terminarea operatiilor de I/O);

elibereaza buffer-ul (algoritm brelse);

}

else if (bufferul este marcat pentru scriere intarziata)

marcheaza buffer-ul sa fie pus in capul

listei buffere-lor libere;

Figura 15. Algoritmul pentru scrierea blocurilor disc

O scriere intarziata este diferita de o scriere asincrona. Cand are loc o scriere asincrona, nucleul incepe imediat operatia cu discul, dar nu asteapta ca ea sa se termine.

La o scriere intarziata, nucleul amana scrierea pe disc cat se poate de mult, iar apoi, urmand al treilea scenariu din algoritmul getblk, marcheaza bufferul ca 'vechi' si scrie asincron blocul pe disc. La incheiarea operatiei, controlerul de disc intrerupe sistemul si elibereaza buffer-ul (folosind algoritmul brelse) punand-ul in capul listei buffere-lor libere, deoarece era marcat 'vechi'. Din cauza celor doua operatii de I/O asincrone, citirea blocului in avans si scrierea intarziata, nucleul poate invoca algoritmul brelse dintr-o rutina de tratare de intrerupere. Din aceasta cauza, el trebuie sa blocheze intreruperile in orice procedura care manipuleaza buffere-le din lista buffere-lor libere deoarece brelse plaseaza buffere-le in aceasta lista.

5. Avantaje si dezavantaje ale buffere-lor

Folosirea buffere-lor cache are mai avantaje si, din nefericire,unele dezavantaje.

Folosirea buffer-ului cache are urnatoarele avantaje:

Permite accesul uniform la disc deoarece nucleul nu trebuie sa cunoasca motivele pentru care se excuta operatiile de I/O. Nucleul copiaza datele in si din buffere, indiferent daca aceatea sunt parti ale unui fisier, superbloc sau inod. Mecanismul de bufferare determina un cod mai modular deoarece exista o interfata unitara pentru toate componentele nucleului care executa operatii de I/O. Pe scurt, proiectarea sistemului este mai simpla.

Deoarece nucleul aliniaza intern datele, sistemul nu impune restrictii de aliniere a datelor in procesele utilizator pe timpul operatiilor de I/O. Aceasta determina o programare mai simpla si o portabilitate mai ridicata a programelor. Fara mecanismul de bufferare, programatorii ar trebui sa se asigure ca buffere-le lor de date au fost corect aliniate. Aceasta ar constitui cauza unor erori de programare, iar programele nu ar fi portabile pe sistemele UNIX care ruleaza pe masini cu proprietati mai restrictive de aliniere.

Se poate reduce traficul cu discul, ceea ce duce la cresterea performantelor sistemului si la scaderea timpului de raspuns. Procesele care citesc dintr-un sistem de fisiere pot sa gaseasca blocurile de date in buffer-ul cache, eliminandu-se necesitatea unor operatii de I/O cu discul. Folosirea scrierii intarziate elimina scrierile pe disc care nu sunt necesare.

Sansele de a gasi blocurile cautate in buffer-ul cache sunt mai mari pentru sistemele cu mai multe buffere. Intrucat buffer-ul cache este implementat in cadrul memoriei principale, numarul de buffere pe care un sistem le poate configura in mod eficient este influentat de dimensiunea memoriei care ramane pentru executia proceselor. Daca este alocata prea multa memorie pentru buffere, sistemul poate deveni prea lent din cauza swapping-ului sau paginarii excesive.

Algoritmii specifici lucrului cu buffere-le asigura integritatea sistemului deoarece ei mentin o singura imagine a blocurilor disc continute in buffer-ul cache. Daca doua procese incearca simultan sa manipuleze un bloc disc, algoritmii (de exemplu getblk ) vor serializa accesul, prevenind alterarea datelor.

Dintre dezavantajele pe care le introduce folosirea buffer-ului cache se amintesc:

Deoarece in cazul scrierii intarziate datele nu sunt transferate imediat pe disc, sistemul este vulnerabil la accidente (de exemplu, caderea tensiunii de alimentare) care ar putea lasa datele de pe disc intr-o stare necorespunzatoare. Desi implementarile recente ale sistemului au redus riscurile cauzate de aceste evenimente, ramane inca problema de baza: executarea unui apel sistem de scriere de catre un utilizator, nu-i ofera certitudinea ca datele vor fi transferate pe disc.

Fiecare operatie de citire/scriere a datelor folosite de procesele utilizator necesita o copie suplimentara. Un proces care scrie date, le copiaza in nucleu, iar nucleul le copiaza pe disc; un proces care citeste date, le citeste de pe disc in nucleu si din nucleu in procesul utilizator. Cand se transmit mari cantitati de date, copia suplimentara scade performantele. Utilizarea buffer-ului cache intr-un sistem in care se transmit cantitati mici de date duce la cresterea performantelor sistemului deoarece nucleul va pastra datele in buffere (folosind algoritmul getblk si scrierea intarziata) pana cand transferul cu discul devine optim.