Structura sistemului de buffere - UNIX

Structura sistemului de buffere - UNIX

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 buffer-lor libere este o lista circulara dublu inlantuita de buffere care are un antet de buffer special pentru a-i marca inceputul si sfarsitul (figura 3.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 3.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 3.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.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 numarele asociate lor si utilizeaza o functie de dispersie dependenta numai de numarul blocului. Totusi, implementarile reale folosesc si numarul dispozitivului.

Figura 3.3. 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.