10 septembrie 2012

Arhitectura sistemelor UNIX - partea a II-a

Continuăm seria de articole inspirate din lucrarea lui Maurice J. Bach, "The Design of the UNIX Operating System". În articolul trecut am reușit să acoperim primele două capitole. Astăzi luăm în colimator capitolul al treilea, intitulat "Buffer cache"-ul.

Citind acest capitol am avut în permanență o senzație de deja-vu. "Buffer cache"-ul din sistemul de operare seamănă izbitor de bine cu cel implementat în Oracle. În primul rând, are același scop, acela de a stoca în memorie (a "cache"-ui, dacă îmi este permis a spune așa), datele cel mai frecvent utilizate, astfel încât operațiile cu discul, lente prin natura lor, să fie minimizate și astfel să se asigure o optimizare a operațiilor de citire sau/și scriere. În al doilea rând, avem de-a face cu același model de organizare a datelor, pe bază de blocuri de dimensiune fixă. Evident, structura internă a blocului e diferită, dar la nivel conceptual, ideea de "vâjâială" de blocuri e aceeași. Există și alte asemănări interesante, pe care le vom puncta la momentul potrivit, pe parcursul acestui articol.

Structura blocului în "Buffer Cache"

Figura 1 - Structura blocului de sistem de operare
Asemănător blocului Oracle, cel de la nivelul sistemului de operare conține, pe lângă datele sale de identificare, referite în general ca "header", datele propriu-zise, așa cum sunt ele stocate pe disc. "Figura 1" ilustrează structura unui astfel de bloc. Se poate observa că avem de-a face, practic, cu niște liste dublu înlănțuite. Corespondența între bloc și locația efectivă pe disc este dată de perechea "identificator dispozitiv/număr bloc". Atributul "status" poate indica dacă:
  • blocul este în starea "locked/busy" sau "free"
  • conține date valide sau nu
  • kernel-ul trebuie să scrie mai întâi datele pe disc înainte de a realoca blocul
  • kernel-ul este în proces de scriere sau citire a blocului
  • un proces așteaptă ca blocul să devină "free"

Cum arata buffer cache-ul?

Cea mai simplă definiție ar fi că buffer cache-ul e o colecție de blocuri de dimensiune fixă. Evident că, atunci când intrăm în detalii, lucrurile devin mai complicate, dar nu de nedigerat. E suficient să ne uităm cu atenție la "Figura 1" pentru a intui cât de cât felul în care aceste blocuri sunt organizate în cadrul acestei structuri de memorie. Observăm în primul rând niște pointeri spre blocuri "free", adică acele blocuri care sunt disponibile pentru noi alocări. Asta înseamnă că la nivelul kernel-ului se ține evidența unei liste cu blocurile libere. Apropos, e clar că e vorba de o listă dublu înlănțuită. Analog, există pointeri spre blocuri grupate în ceea ce autorul numește "hash queue". Ideea e simplă și se regăsește și în buffer cache-ul bazei de date Oracle, doar că aceste liste nu se numesc "hash queues", ci "bucket"-uri sau "chains", dar e fix același lucru. În ce constă "șmecheria"? Imaginați-vă că buffer cache-ul ar fi format dintr-o singură listă înlănțuită, cu zeci/sute de mii de blocuri. Timpul necesar parcurgerii unei astfel de liste ar fi foarte mare, deci ineficient. Soluția ar fi de a sparge această listă în mai multe, iar fiecare bloc să fie "mapat" pe o singură astfel de listă. Este ceea ce fac în general algoritmii de "hashing". Cel mai simplu algoritm de hashing ar fi funcția "mod", cea care ne dă restul împărțirii. Să presupunem că "buffer cache-ul" nostru ar fi format din patru liste "hash". Acum, fiecare bloc de pe disc, pornind de la numărul său (identificatorul) ar trebui alocat uneia din cele patru liste, într-o manieră cât mai uniformă. Aplicăm funcția "mod" și vedem ce ne iese:
block 99: 99 % 4 = 3 => se duce în a patra listă (numărătoarea începe de la zero)
block 60: 60 % 4 = 0 => se duce în prima listă
block 13: 13 % 4 = 1 => se duce în a doua listă
block 26: 26 % 4 = 2 => se duce în a treia listă
Asta înseamnă că un bloc nu se poate regăsi decât într-una din cele patru liste sau, evident, în niciuna dacă nu e "cache"-uit. În "Figura 2" schițăm structura "buffer cache"-ului.
Figura 2 - Structura "Buffer Cache"-ului

Implementările reale ale algoritmului de "hashing" țin cont de combinatia "număr dispozitiv/număr bloc". Scopul didactic primează, prin urmare vom merge pe abordarea simplistă în care fiecare bloc are doar un număr de ordine. În "Figura 1" se poate observa distribuția blocurilor în listele corespunzătoare, precum și lista blocurilor libere, reprezentate prin acea linie îngroșată, ce leagă fiecare bloc liber. "Freelist header" reprezintă un bloc "surogat" care leagă cele două capete ale listei. În cazul în care nu mai există nici un bloc liber, această listă va conține doar acest bloc surogat.

Pe baza listei cu blocurile libere ("free list"-ul) kernel-ul implementează un algoritm de tip LRU (Least Recently Used). Asta înseamnă că ori de câte ori are nevoie de un bloc nou, "necacheuit" (o Doamne, nu căutati cuvântul asta în DEX), din "free list", acesta va fi alocat din capul listei și niciodată de la coada sa. În "Figura 2", dacă kernelul ar trebui să aloce, să zicem blocul 39, atunci blocul 3 va "zbura" din "free list", dat fiind că e chiar în capul listei. Dacă blocul este deja în "buffer cache" atunci, evident, acesta va fi scos din "free list", chiar dacă el un se află în capul listei (de exemplu, blocul 97). Ceea ce este important de remarcat este faptul că, odată ce blocul a fost eliberat, el va fi plasat la coada "free list"-ului. Exceptie fac doar cazurile în care operația ce a vizat acel bloc s-a încheiat cu eroare sau, așa cum vom vedea imediat, atunci cand blocul trebuie mai întâi scris pe disc. În amble astfel de situații blocurile vor fi plasate în capul listei.

Trecem și mecanismul LRU la capitolul asemănări cu "buffer cache"-ul bazei de date Oracle și mergem mai departe.

Scenarii: cum este obținut un bloc din "buffer cache"?

Alocarea unui bloc în buffer cache se face prin intermediul algoritmului "getblk", iar cel responsabil de returnarea blocului în "free list" poartă denumirea de "brelse". Să luăm în colimator primul algoritm, prezentat în "Listingul 1".
Listing 1 - Algoritmul "getblk"

Putem discuta de cinci scenarii mari:
  1. în încercarea de a obține un bloc, kernel-ul caută să vadă dacă acesta nu este deja în cache și, noroc chior, îl găsește în lista hash asociată și, în plus, e și liber, adică e în "free list"
  2. kernel-ul nu găsește blocul cache-uit, adica nu e în lista hash asociată, prin urmare alocă un nou bloc din "free list"
  3. kernel-ul nu găsește blocul cache-uit și alocă un nou bloc din "free list", însă respectivul bloc este marcat ca "delayed write", prin urmare kernel-ul trebuie să scrie acel bloc pe disc și să aloce unul nou
  4. kernel-ul nu găsește blocul cache-uit și încearcă să aloce unul nou din "free list', dar, ghinion, nu mai există nici un bloc "free"
  5. kernel-ul gasește blocul cache-uit în lista hash asociată, însă respectivul bloc este marcat ca "busy"
Listing 2 - Pseudocod pentru algoritmul "brelse"
Este, de asemenea, important de văzut ce se întâmplă cu un bloc, de îndată ce el este obținut. Pai, dacă blocul nu fusese cache-uit, atunci, cel mai probabil, kernel-ul va încerca să inițializeze respectivul bloc cu datele efective de pe disc. Dacă este vorba de o operație de scriere, atunci kernel-ul va scrie în acel bloc și, eventual, va propaga modificările pe disc. Pe parcursul acestor operații, blocul asupra căruia se operează va fi marcat ca "busy", astfel încât să se asigure integritatea buffer-ului. Nici un alt proces nu va mai putea manipula acel bloc până când el nu va fi "eliberat" prin intermediul algoritmului deja menționat "brelse". Acesta, de îndată ce eliberează blocul, ceea ce e echivalent cu a-l pune în "free list", va "trezi" toate procesele care intraseră în starea "sleep" datorită faptului că au încercat să acceseze un bloc "busy". "Listingul 2" prezintă logica algoritmului "brelse". Remarcați felul în care este actualizat "free list"-ul, prin ridicarea nivelului de întrerupere, mecanism prezentat în articolul precedent.

Scenariul 1
Să revenim la "Figura 2". Ce se întâmplă daca kernel-ul este solicitat să aloce blocul 4? Este fix scenariul de care discutăm. Blocul 4 este deja cache-uit și, în plus, e și în "free list". Conform algoritmului, blocul 4 va fi marcat ca "busy", scos din "free list" și returnat apelantului.
Scenariul 2
În acest scenariu încercăm să obținem blocul 18. Mai întâi kernel-ul determină lista hash în care să caute: 18 mod 4 = 2, deci a treia listă. Dat fiind că nu găsește acest bloc, rezultă că acesta nu este cache-uit, prin urmare va trebui alocat un nou bloc, luat din capul "free list"-ului, bloc care va fi așezat frumușel în lista hash corespunzătoare.
Scenariul 3
Vrem să obținem blocul 18. Dat fiind că nu găsește acest bloc, va trebui să aloce un nou bloc, din capul "free list"-ului. Constată însă că acel bloc a fost modificat și trebuie mai întâi scris pe disc. Prin urmare, kernel-ul va scoate blocul din "free list" și va porni o scriere asincronă a respectivului bloc pe disc. Mai departe va încerca să aloce următorul bloc din "free list", însă, în cazul de față, dă din nou peste un bloc care trebuie mai întâi scris pe disc, deci va aplica aceeași pași. În sfârșit, găsește blocul 4 din free list și va aplica fix scenariul 2.
Scenariul 4
În acest scenariu, kernel-ul încearcă sa aloce un nou bloc din "free list" și constată că nu mai există nici un bloc "free", adică "free list"-ul este gol goluț. Criză! Așa că, procesul care își dorea blocul cu pricina va intra în starea "sleep", așteptând să fie "trezit" de un alt proces, ca urmare a invocării algoritmului "brelse". Dacă vă mai amintiți în "Listingul 2", algoritmul "brelse" avea grijă să trezească "frumoasele din pădurea adormită". Când procesul revine la viață, va relua pașii obișnuiți, exemplificați în scenariile anterioare.
Scenariul 5
Acest ultim scenariu e destul de banal. Kernelul dorește alocarea unui bloc pe care îl găsește în lista hash corespunzătoare, dar, din păcate, acel bloc este "busy", adică e manipulat de un alt proces. Prin urmare, mare lucru nu e de făcut, decât să se aștepte eliberarea blocului cu pricina. Procesul va intra în starea "sleep" și, asemănător "Scenariului 4", va aștepta să fie trezit de alte procese, care, inevitabil, vor apela algoritmul "brelse".

Interacțiunea cu dispozitivul de stocare

Algoritmii "getblk" și "brelse" sunt responsabili de managementul alocării blocurilor în "buffer cache" și operează cu datele din header-ul blocurilor: adresa blocului, pointeri, status etc. Citirea datelor efective de pe disc (vezi în "Figura 1", ptr to data area), precum și scrierea acestora cad în sarcina algoritmilor "bread" și "breada" pentru citire, respectiv "bwrite" pentru scriere.

Listing 3 - Algoritmul "bread"
În primul rând, haideți să vedem cum ajung datele de pe disc în blocul din "buffer cache". Să presupunem că trebuie să citim blocul 18 de pe disc. Mai întai kernel-ul va invoca "getblk" pentru a identifica, eventual aloca, blocul în "buffer cache". Presupunând că blocul 18 nu se găsește în memorie, el va fi alocat conform scenariilor deja prezentate. Buuun, avem un bloc alocat în buffer cache, dar trebuie să-i asociem și datele evective de pe disc. Fiecare bloc din "buffer cache" duce în spate datele corespunzătoare de pe disc, altfel nu și-ar avea sensul. Discutăm practic de inițializarea zonei de memorie referite de către "ptr to data area" din "header"-ul blocului. Ei bine, este ceea ce face algoritmul "bread", prezentat în "Listingul 3".

Interesante sunt ultimele trei linii deoarce acestea conțin interacțiunea efectivă cu dispozitivul fizic. Ce se întâmplă de fapt? Kernel-ul semnalizează "driver"-ului dispozitivului de stocare cererea sa de citire, după care procesul intră în starea "sleep". Acest lucru este important de reținut, deoarece din acest moment procesul poate fi dealocat de pe procesor, făcând loc altor procese. "Driver"-ul comunică cu dispozitivul fizic, iar în momentul în care datele au fost efectiv citite de pe disc, "controller"-ul dispozitivului fizic va întrerupe procesorul, semnalizând astfel că datele au fost citite. Întreruperea este tratată de kernel, care va "trezi" toate procesele aflate în starea "sleep".

Listing 4 - Algoritmul "breada"
O variație a algoritmului "bread" este "breada" (block read ahead). Acesta este folosit în citirile secvențiale, adică echivalentul lui "multi block read count" din Oracle. Ideea ar fi cam așa: "dă-mi blocul X, dar, ca parte a operațiunii, lansează și o operație de citire asincronă a blocului Y, care mă aștept să-l citesc imediat după aceea și, prin urmare, ar fi SUPER ca el să fie deja în buffer cache". Algoritmii de pe nivelele superioare, de obicei cele din sistemele de fișiere, folosesc acest algoritm ori de câte ori sesizează o cerere de citire secvențială. Să luăm spre exemplu citirea unui fișier format din 300 de blocuri. Algoritmul "breada", prezentat în "Listingul 4", primește ca argumente de intrare, adresa blocului care trebuie citit și returnat, precum și o a doua adresă de bloc ce urmează a fi citit asincron. Astfel, dacă blocurile acestui fișier ar fi numerotate de la 1 la 300, citirea lui s-ar putea face prin 300 de operații de citire de tipul: breada(1, 2), breada(2, 3) ... breada(299, 300), bread(300). Avantajul față de varianta utilizării doar a funcției "bread" ar fi acela că "breda" anticipează că blocul furnizat sub forma celui de-al doilea parametru urmează a fi cerut într-un apel viitor și încearcă a-l trage din timp în cache. Evident, nu există nici o garanție că respectivul bloc va ajunge în cache înainte de a fi solicitat, dar sunt șanse mari să ajungă, caz în care avem parte de o optimizare elegantă.

Dacă facem o "disecție" riguroasă a algoritmului din "Listingul 4", nu se poate să nu ne întrebăm ce se întâmplă cu cel de-al doilea bloc după ce s-a lansat citirea asincronă? Blocul a fost alocat în buffer cache, iar pentru inițializarea datelor a fost notificat "driver"-ul dispozitivului de stocare să le aducă, dar, atenție, procesul nu intră în starea "sleep" așteptând semnalul de la dispozitivul fizic. Dacă ar face asta, nu s-ar mai chema citire asincronă. Asta înseamnă că cel de-al doilea bloc rămânde în starea "busy" pentru că, ne amintim, algoritmul "getblk" returnează un bloc "lock"-at. Ei bine, atunci când dispozitivul fizic termină de adus datele pentru cel de-al doilea bloc, va întrerupe procesorul, semnalizând astfel că a încheiat operația de citire. Această întrerupere este tratată de kernel care determină (deocamdata nu-mi este nici mie foarte clar cum) că blocul cu pricina a fost inițializat printr-o citire asincronă și invocă automat algoritmul "brelse". Din fericire, toate acestea țin de bucătăria internă a kernel-ului, iar utilizatorii obișnuiți nu trebuie să-și bată capul cu astfel de detalii.
Listing 5 - Algoritmul "bwrite"

În sfârșit, ajungem la algoritmul de scriere, denumit "bwrite" și prezentat în "Listingul 5". Tangențial, acest algoritm a fost prezentat în "Scenariul 3", atunci când am discutat despre "getblk". Atunci am văzut că, într-un fel, kernel-ul amână scrierea blocurilor cât mai mult posibil. Atunci când însă dă peste un bloc marcat ca "delayed write" (sau în termeni Oracle, "dirty") va invoca algoritmul "bwrite" prin care va iniția scrierea asincronă a blocului pe disc. Atunci când dispozitivul întrerupe procesorul semnalizându-i că a terminat de scris, kernel-ul își dă seama că a fost vorba de o scriere asincronă și va invoca algoritmul "brelse" pentru acel bloc. Interesant e că blocul nu va fi așezat la coada "free list"-ului, ci în capul ei. Este și normal, dat fiind că acel bloc marcat ca "delayed write" a fost luat, inițial, din capul listei.

Avantaje și dezavantaje ale "buffer cache"-ului

Succint, trecem la avantaje, următoarele:
  1. accesarea unitară a discului: e asemeni unui API, unde detaliile de implementare sunt ascunse
  2. mai puține operații lente cu discul
  3. asigura integritatea datelor citite/scrise de pe disc
Evident, trebuie punctate și dezavantajele. Cele mai importante sunt:
  1. vulnerabilitatea în cazul în care sistemul "crapă", iar datele din blocurile "dirty" nu au fost scrise
  2. operează cu date duplicate: le găsim și pe disc și în memorie

Exerciții

1. Fie algoritmul de "hashing" dat de funcția "mod" (restul împărțirii). Cea mai bună astfel de funcție ar fi cea care distribuie uniform în listele "hash" predefinite. Care ar fi acea funcție? Ar trebui o astfel de funcție să țină seama și de numărul dispozitivului și nu doar de numărul blocului?

Răspuns
Cea mai bună funcție de hash ar fi cea care nu permite coleziuni, adică să nu se întâmple ca pentru două valori de intrare diferite valoarea de hash să fie identică. Astfel de algoritmi există, deși ei sunt complecși și nu știu cât de potriviți ar fi pentru problema noastră (spre exemplu MD5). Pentru o distribuție cât mai bună a blocurilor este indicat a se folosi și numărul dispozitivului, astfel încât două blocuri cu același număr dar dispozitive diferite să nu corespundă aceleiași liste "hash". Spre exemplificare luăm algoritmul lui D. J. Bernstein, implementat mai jos în ruby:
#!/usr/bin/env ruby
def djb_hash str
  hash = 5381
  str.each_byte do |b|
    hash = (((hash << 5) + hash) ^ b) % (2 ** 32)
  end
  hash
end

puts djb_hash("1/300") % 4
puts djb_hash("2/300") % 4
Progrămelul de mai sus afișează:
0
3
Asta înseamnă că blocul 300 din dispozitivul logic 1 se va duce în prima listă hash, iar cel de-al doilea în cea de-a patra. Am asigurat astfel o distribuție mai bună a blocurilor.

2. În algoritmul "getblk", atunci când un bloc este scos din "free list", nivelul de prioritate a întreruperilor este ridicat! De ce?

Răspuns
Dat fiind că avem de-a face cu o listă dublu înlănțuită, trebuie actualizați doi pointeri într-o operație atomică. Altfel, dacă o întrerupere intervine după actualizarea primului pointer, atunci riscăm să corupem lista.

3. În algoritmul "getblk", deși nu este specificat în listing, înainte de a verifica dacă un bloc este "busy", prioritatea întreruperilor este ridicată. De ce?

Răspuns
Dacă nu s-ar face acest lucru, s-ar putea să ne trezim cu o informație falsă: să avem confirmarea ca blocul nu este "busy", dar imediat să devină, și invers. Pentru a înțelege mai bine, considerăm următorul scenariu: la momementul T0 verific daca blocul e "busy" și obțin răspunsul că NU. Imediat după asta, intervine o întrerupere care îmi scoate procesul de pe CPU și alocă un alt proces care îmi ia același bloc, îl pune în starea "busy" și intră apoi în "sleep", în așteptarea datelor de la "controller"-ul de disc. Între timp, procesul precedent revine pe procesor și continuă de unde a rămas, adică imediat după ce verificase starea blocului cu pricina, care la momentul T0 nu era "busy". Ghinion, deși procesul actual are impresia că manipulează un bloc care nu este folosit, în realitate el e "busy"! Ridicarea nivelului de prioritate a întreruperilor în acest punct al logicii algoritmului ne salvează de astfel de situații.

4. În algoritmul "brelse", un bloc marcat ca având date invalide este pus în capul "free list"-ului. Cum se poate întâmpla ca un bloc cu date invalide să se regăsească "cache"-uit?

Răspuns
Acest lucru este posibil dacă operația de citire de pe disc s-a finalizat cu eroare. Ne amintim, de asemenea, că "brelse" este apelat și din codul care tratează întreruperile de disc în cazul citirilor asincrone, deci "brelse" trebuie să fie pregătit și pentru astfel de cazuri.

5. Să presupunem că avem în cache un bloc marcat ca "delayed write". Ce se întâmplă cu acest bloc când un alt proces are nevoie de el și îl găsește în lista "hash" asociată? Dar când acest bloc este preluat din "free list"?

Răspuns
Dacă un proces are nevoie de un bloc, va invoca "getblk" care, mai departe, va căuta dacă respectivul bloc nu este deja "cache"-uit, adică se va uita în lista "hash" corespunzătoare. Presupunând că îl găsește în cache, chiar dacă este marcat ca "delayed write", îl va folosi ca atare. De fapt, asta e și ideea, de a amâna scrierea bloclui cât mai mult posibil și a beneficia astfel de avantajele cache-ului. Pe de altă parte, dacă "getblk" nu găsește blocul în lista "hash" și trebuie să preia un bloc nou din "free list", presupunând că blocul din lista "free" este "delayed write", îl va scrie asincron pe disc și va prelua următorul bloc din "free list" (scenariul 3).

6. Dacă mai multe procese "se bat" pentru un bloc, kernel-ul garantează că respectivele procese nu vor rămâne în starea "sleep" la infinit, dar nu garantează că un anumit proces s-ar putea să nu "pună mâna" niciodată pe blocul solicitat. Cum ar trebui rescris "getblk" astfel încât acest lucru să nu se întâmple?

Răspuns
Principala problemă a algoritmului "getblk" este faptul că procesele care "se bat" pe un același bloc și intră în starea "sleep", nu sunt "trezite" în aceeași ordine atunci când blocul cu pricina se eliberează. Deci, teoretic, un proces poate sa intre într-o buclă infinită de "sleep-wakeup". Problema s-ar putea rezolva prin implementarea unor cozi care să memoreze ordinea în care procesele au intrat în sleep.

7. Rescrieți algoritmii "getblk" și "brelse" astfel încât să nu folosească metoda LRU (least recently used), ci FIFO (First In First Out). Repetați utilizând metoda "cel mai recent utilizat" bloc.

Răspuns
Implementarea algoritmului în C nu cred că e importantă și oricum cunoștințele mele în acest limbaj de programare sunt limitate. În orice caz, cheia problemei stă în modul în care se face preluarea, respectiv returnarea blocurilor din/în "free list". Pentru metoda FIFO, la oricare capăt al "free list"-ului am opera, important e ca "getblk" și "brelse" să preia și să returneze blocurile la același capăt al listei. Pentru metoda "cel mai utilizat bloc", "getblk" ar trebui să preia blocul din coada listei, iar "brelse" să returneze blocurile tot la coadă.

8. Descrieți un scenariu în care, atunci când este invocat "bread", datele din bloc sunt deja valide.

Răspuns
Cel mai plauzibil scenariu este atunci când blocul este deja în cache ca urmare a unei citiri precedente.

9. Descrieți câteva scenarii ce se pot întâmpla în cazul algoritmului "breada". Ce se va întâmpla cu următorul apel "bread" sau "breada" atunci când blocul citit în avans ajunge în buffer? În algoritmul "breada", dacă al doilea bloc nu este în cache, se testează mai departe dacă datele din bloc sunt valide, ca și când respectivul bloc ar fi fost în cache. Cum vine asta?

Răspuns
Un posibil scenariu a fost deja prezentat sub forma citirii secvențiale a unui fișier ce numără 300 de blocuri. Logica din ce-a de-a două condiție, și anume atunci când al doilea bloc nu se află în cache, este interesantă. Mă gândesc că poate are legătura cu citirile asincrone, însă imi este destul de greu să-mi dau seama cum anume se verifică condiția "if (second block not in cache)". Dacă este vorba de o simplă parcurgere a listei "hash", fără nici o serializare, atunci e posibil ca după acestă verificare, deși nu a fost găsit nici un bloc, între timp un alt proces să fi adus blocul în cache. Deși, nu înțeleg de ce nu se face direct un "getblk", fără a se mai face "if"-ul dinainte. Dacă getblk aduce un bloc cu date valide, se face "brelse", altfel se porneste citirea datelor in bloc, asincron. No idea!

10. Gândiți-vă la felul în care algoritmul "getblk" poate fi modificat astfel încât să ia orice bloc din "free list", în cazul în care blocul solicitat nu este găsit în cache.

Răspuns
Pur și simplu, folosim o funcție aleatoare care să întoarcă un index cuprins între zero și lungimea listei "free", minus unu.

11. Anumite apeluri de sistem (sys calls), cum ar fi de pildă "umount" și "sync", solicită kernel-ului să scrie pe disc toate blocurile marcate ca "delayed write" pe disc. Descrieți un posibil algoritm care ar face asta. Ce se întâmplă cu ordinea blocurilor "delayed write" în "free list". Cum se poate asigura kernel-ul că nici un alt proces nu se "strecoară" și încearcă și el să scrie un bloc "delayed write" în timp ce procesul care a inițiat deja scrierea se află în starea "sleep", așteptând semnalul de trezire de la "controller"-ul de disc?

Răspuns
Algoritmul ar trebui să parcurgă "free list"-ul și să verifice status-ul blocului. Dacă e "dirty" ar trebui să-l scrie asincron pe disc. Când scrierea s-a terminat, procesorul va fi întrerupt iar kernel-ul va invoca "brelse" pentru respectivul bloc, returnându-l în capul listei. Deci, ordinea blocurilor se inversează, presupunând că întreruperile provenite de la "controller"-ul de disc urmează aceeși ordine. Un alt proces nu se poate "strecura" deoarece, până nu se invoca "brelse", blocul rămâne "in use", deci blocat.

12. Definim timpul de răspuns ca timpul mediu necesar unui apel de sistem (sys call) pentru a fi efectuat. Analog, definim "throughput"-ul ca numărul mediu de procese pe care sistemul le poate executa într-o perioadă de timp dată. Descrieți în ce mod "buffer cache"-ul poate ajuta timpul de răspuns. Dar "throughput"-ul?

Răspuns
Timpul de răspuns e îmbunătățit datorită faptului că pentru blocurile "cache"-uite, acestea sunt servite direct din memorie, deci mult mai rapid. În ceea ce privește "throughput"-ul, acesta este, de obicei, invers proporțional timpului de răspuns. Cu cât avem mai multe procese care "se călăresc" pe aceleași blocuri, cu atat mai mult crește gradul de serializare și, prin urmare, scade timpul de răspuns.

0 commentarii: