|
|
|
IMBUNATATIREA OPERATIILOR DE INTRARE/IESIRE
Problema esentiala, la ora actuala, in ceea ce priveste o operatie de intrare/iesire, este timpul de acces la hard disc, principalul dispozitiv periferic de memorare a informatiei. Inca exista o diferenta foarte mare intre timpii in care se desfasoara o operatie in unitatea centrala si o operatie pe hard disc. Desigur , odata cu noile tehnologii, acesti timpi s-au imbunatatit si exista premize de micsorare a lor in viitor, totusi decalajul de timp intre operatiile din UC si cele de intrare/iesire este inca foarte mare. Rolul SO este de incerca, prin diferiti algoritmi, sa imbunatateasca, adica sa micsoreze, timpul unei operatii de intrare/iesire. Multe din solutiile adoptate au fost apoi implementate in hard, in solutiile constructive ale hard discului. Doua exemple sunt edificative in acest sens:
-factorul de intretesere;
-cache-ul de hard disc.
1. Factorul de intretesere
La aparitia discurilor magnetice, se consuma foarte mult timp pentru citirea continua a sectoarelor, unul dupa altul. Astfel pentru un disc cu 80 sectoare pe pista, pentru citirea unei piste erau necesare 80 rotatii ale platanului. Aceasta deoarece, dupa citirea unui sector, era necesar un timp pentru transferul datelor spre memorie iar in acest timp capul respectiv se pozitiona pe alt sector. Deci, pentru citirea sector cu sector, era necesara o rotatie pentru citirea unui sector. O iedee simpla, venita din partea de SO, a fost de a calcula timpul de transmitere a datelor spre memorie, de a vedea pe ce sector a ajuns capul dupa aceasta transmisie si de a renumerota sectoarele. Exemplu:
Fie un disc cu 8 sectoare, numerotate in ordine , ca in figura 6.6.
Fig. 6.6. Hard disc cu 8 sectoare.
Daca acest disc are un factor de intretesere egal cu 2, aceasta inseamna ca, dupa ce capul a mai parcurs doua sectoare, datele au fost transmise in memorie. La o rotatie se citesc trei sectoare. La prima rotatie, sectoarele 1,2,3, la a doua rotatie, sectoarele 4,5,6, la a treia rotatie sectoarele 7 si 8. Pentru un factor de intretesere 2 noua numerotare a sectoarelor va fi ca in figura 6.7.
Fig. 6.7. Hard discul dupa trei rotatii.
Se observa ca, prin introducerea factorului de intretesere, nu mai sunt necesare 8 rotatii pentru citirea unei piste ci numai trei.
Aceasta solutie a fost introdusa intai in SO, mai apoi fiind preluata in hardware de catre disc, unde factorul de intretesere era un parametru lowlevel al hard discului.
Datorita progresului tehnologic, de la factori de intretesere de 3 sau 4 s-a ajuns la un factor de valoare 1, deci la o rotatie se citeste intreaga pista.
2. Cache-ul de hard disc
Folosirea tampoanelor de date, pentru transferul de date intre hard disc si memoria sistemului, a fost preluata hardware de catre disc. Astfel s-a implementat o memorie cache la nivel de hard disc, memorie alcatuita pe acelasi principiu ca si memoria cache RAM.
3. Crearea unui hard disc cu performante superioare de catre SO
In general, timpul total de acces pentru un hard disc este dat de urmatoarele componente:
- timpul de cautare (seek time), timpul necesar pentru miscarea mecanica a capului de scriere/citire pana la pista specificata;
- latenta de rotatie ( rotational latency) este timpul de asteptare necesar pentru ca sectorul specificat sa ajunga sub capul de scriere/citire;
- timpul de transfer ( transfer time) este timpul necesar pentru a citi informatia de pe sectorul specificat;
Planificarea accesului la disc are in vedere doua lucruri:
- reorganizarea cererilor la disc pentru a minimiza timpul de cautare;
- un mod de plasare a informatiilor pe disc care sa minimizeze latenta de rotatie.
Exista algoritmi de plasare in care ideea principala este de a schimba ordinea de servire a cererilor venite de la procese, astfel incat sa se pastreze ordinea cererilor fiecarui proces.
Dintre algoritmii care minimizeaza timpii de acces amintim:
a) FCFS (First Come First Served) ;
b) SSTF ( Shortest Seek Time Firs);
c) SCAN, C SCAN ;
d) LOOK, C LOOK.
a) FCFS ( First Come First Served =primul venit , primul servit). Cererile sunt servite in ordinea sosirii.
b) SSTF (Shortest Seek Time First=cel cu cel mai scurt timp de cautare, primul) . Conform acestui algoritm, capul de scriere/citire se va deplasa de la cilindrul unde este pozitonat spre cilindrul cel mai apropiat. Este mai eficient decat FCFS, dar poate duce la intarzierea unor cereri si la infometare.
c) SCAN si C SCAN. In SCAN, capul de scriere /citire se deplaseaza de pe primul cilindru spre unul din capete si apoi baleiaza discul pana la capat si inapoi, deservind cererile. In C SCAN , se incepe de la cilindrul 0 iar cand se ajunge la sfarsit, se reia baleierea tot de la cilindrul 0. Practic, in SCAN baleierea se face in ambele sensuri, in timp ce in C SCAN intr-un singur sens, de la cilindrul 0 la ultimul. Prin analogie, algoritmul SCAN poate fi reprezentat de o lista dublu inlantuita, iar C SCAN de o lista simplu inlantuita.
d) LOOK, C LOOK. In acest algoritm, capul de scriere/citire se deplaseaza pana la ultima cerere, dupa care inverseaza sensul de miscare, imediat, fara sa mearga pana la capatul discului.
In continuare, sa luam un exemplu si sa vedem care este timpul de cautare pentru fiecare algoritm.
Fie un hard disc cu 250 cilindri, cu bratul cu capete pozitionat initial pe cilindrul 50. Fie urmatoarea coada a cererilor se acces:
50, 200, 100, 25, 250, 150, 144, 143
(a)FCFS=in ordinea sosirii ; (b) SSTF=spre cel mai apropiat cilindru ; (c) SCAN ; (d) C SCAN
Sa calculam, pentru exemplul dat, timpii de cautare pentru fiecare algoritm, timpi exprimati in numarul cilindrilor parcursi.
FCFS-Ordinea deservirii (in ordinea cererii de acces):
50,200,100,25,250,150,144,143.
-Numarul cilindrilor parcursi:
(200-50)+(200-100)+(100-25)+(250-25)+(250-150)+(150-
44)+(144-143)==150+100+75+225+100+6+1=657
SSTF-Ordinea deservirii (catre cel mai apropiat cilindru):
50,25,100,143,144,150,200,250.
-Numarul cilindrilor parcursi =(50-25)+(100-25)+(143-100)+(144-
143)+(150-144)+(200-150)+(250-200)=
25+75+43+1+6+50+50=250
SCAN-Ordinea deservirii: 50,0,25,100,143,144,150,200,250
-Numarul cilindrilor parcursi = 50+25+75+43+1+6+50+50=300
C SCAN-Ordinea deservirii: 50,100,143,144,150,200,250,0,25.
- Numarul cilindrilor parcursi = 50+43+1+56+50+50+250+25=475
Observatii:
- Cel mai timp de cautare ofera algoritmul SSTF, unul din cei mai utilizati, in ciuda faptului ca poate duce la infometare.
-Algoritmii SCAN si C SCAN se comporta mai bine pentru sistemele care au incarcare mare a discului, adica multe operatii de intrare/iesire.
- La algoritmul SSTF, cei mai favorizati din punct de vedere al timpului de acces, sunt cilindrii aflati la mijloc. De aceea, in acesti cilindri sunt alocate fisiere cu frecventa ridicata de utilizare, cum ar fi structura de directoare.
-Exista si algoritmi mai pretentiosi in care se urmareste si minimizarea latentei de rotatie.
4. Construirea unui hard disc prin tehnica RAID (Redundant Arrays of Independent Discks)
Ideea RAID este de a folosi mai multe discuri simultan la aceeasi magistrala si de a scrie informatiile in felii (stripes)care acopera toate discurile. Aceste felii sunt de fapt blocuri. Discul este vazut ca un intreg dar blocurile alterneaza in toate discurile. Pentru un ansamblu de trei discuri, blocul 1 va fi pe discul 1, blocul 2 pe discul 2, blocul 3 pe discul 3 si apoi blocul 4 pe discul 1, blocul 5 pe discul 2 s.a.m.d. Pentru un subansamblu de n discuri, blocul m va fi pe discul m modulo n.
In Raid, aceasta tehnica a stripingului se combina cu ideea de redundanta, de unde si denumirea Redundant Arrays of Independent Discks adica o multime redundanta de discuri independente. Redundanta consta in alocarea, in caz de defect, a unui disc pentru refacerea informatiei pe celelalte discuri.
Tehnica de refacere cea mai des utilizata este paritatea dar se pot utiliza si checksum-uri sau, mai rar, polinoame de control.
Cea mai simpla schema RAID este cea cu doua discuri, care mentin informatii identice, tehnica care se mai numeste mirrored discks.
In tehnica actuala RAID, exista 7 nivele:
-nivelul 0: striping fara redundanta;
-nivelul 1: discuri oglindite (mirrored discks);
-nivelul 2: coduri Hamning detectoare de erori:
-nivelul 3: un disc de paritate la fiecare grup,
bit-interleaved;
-nivelul 4: scrieri/citiri independente, block-interleaved;
-nivelul 5: informatia de paritate este imprastiata pe toate discurile;
-nivelul 6: nivelul in care de detecteaza si se corecteaza mai mult de o eroare pe disc.
Principalul dezavantaj al discurilor RAID consta in asa numitele "scrieri mici". Acest lucru se produce atunci cand se face o scriere intr-un singur disc si toate celelalte discuri trebuie accesate pentru a se recalcula paritatea, generandu-se astfel un trafic destul de mare. Acest dezavantaj poate fi contracarat prin implementarea unei cache de disc, cu o capacitate foarte mare, ceea ce face ca socul scrierilor mici sa fie absorbit de cache, utilizatorii netrebuind sa astepte calculul paritatii.
