Facultatea de Electronică, Telecomunicații si Tehnologia InformatieiUniversitatea “Politehnica” București

Algoritm optimizat de rezolvare a problemei celor k clienţi aplicat la memorii externe

CoordonatorConf. Dr. Ing. Ștefan Stăncescu

AbsolventSăvulescu Alexandru Costin

Problema celor k clienți în cazul acceselor la disc în sistemele multi-threading

• Este o problemă de concurență, întâlnită în mai multe domenii precum accesul la bazele de date, accesul la disc, traficul în rețea, etc.

• Problema fundamentală presupune existența unui singur server și a unui număr de k clienți.

• Dificultatea constă în alegerea de către server a care dintre cereri să soluționeze mai întâi.

• Problema fundamentală presupune timpi de soluționare (execuție) a cererilor de valoare 0.

• Variante ale problemei celor k clienți reprezintă cazuri în care cererile nu au timp de soluționare zero sau există mai multe servere cu mai mulți clienți.

Problema celor k clienți din punct de vedere al programării accesului la disc

• Se pune problema găsirii unor soluții optime de programare a acceselor la disc pentru obținerea unor valori pentru funcții cost cât mai mici.

• Funcțiile cost pot fi determinate de timpul mediu/maxim de căutare, timpul mediu/maxim de acces, latența rotațională medie, etc.

• În cazul accesului la disc, serverul este reprezentat de capul sau capetele de citire, iar clienții sunt reprezentați de cererile de citire/scriere asupra discului prin intermediul capului.

• Analiza constă în evaluarea unor algoritmi de programare a accesului la disc în funcție de anumite funcții cost.

Fizica unității de disc magnetic

• Capetele de citire se plimbă de-alungul platanelor, însă nu independent.

• Platanele se rotesc de-lungul axlui cu o viteza aproximativ constantă

• Se urmărește mutarea capului pe distanțe cât mai scurte.

Componentele unei suprafețe

• Fiecare platană este împărțită într-un număr de piste.• Fiecare pistă are un număr de sctoare.• Termenul de cilindru reprezintă totalitatea pistelor

care se află sub același cap în același timp. • Pentru a satisface o cerere I/O, controlerul de disc

trebuie să mute capul la locația necesară, determinată de pistă și numărul sectorului.

Dezavantajele discurilor magnetice din punct de vedere al vitezei

• Există o discrepanță foarte mare între timpii de lucru ai microprocesorului și ai memoriei interne față de cei ai unităților de stocare externe în cadrul unui sistem de procesare.

• Vitezele de lucru ale microprocesoarelor și memoriilor interne au crescut exponențial de-alungul timpului, în timp ce din punct de vedere al unităților secundare de stocare, acestea au crescut nesemnificativ.

• Aceste viteze sunt cu câteva ordine de mărime mai mari față de cele ale unităților de stocare externe, perfomanța sistemului fiind limitată de acestea.

• Se dorește minimizarea timpilor de acces la memoria

externă prin folosirea unor anumitor tipuri de algoritmi

pentru sporirea performanței.

Tehnologia SSD (Solid-State Drive) ca alternativă la unitățile de stocare clasice

(hard-disk-uri)

• O unitate SSD este un dispozitiv de stocare a datelor care folosește memorie în stare solidă pentru a stoca date persistente.

• Are la bază de obicei memorie flash NAND și datorită faptului că emulează interfața unui hard-disk, îl poate înlocui cu succes.

• Avantaje: acces aleator foarte rapid, timpi de acces neglijabili datorită absenței elementelor mecanice, viteze de citire mai mari față de hard-disk-urile convenționale, lipsa zgomotului, greutate și dimensiuni reduse, rezistența la șocuri, consum de energie mic.

• Dezavantaje: preț ridicat, aproximativ de 5 ori mai mare per GB față de hard-disk-urile convenționale, capacitate de stocare mai mică, un ciclu limitat de scrieri (ștergeri).

• Aceste neajunsuri vor fi îmbunătățite pe parcurs și se așteaptă ca aceste dispozitive să ia locul unitățilorhard-disk convenționale în viitorul apropiat.

Prezentarea algoritmilor de programare a acceselor la disc

Algoritmul First-Come, First-Served (FCFS)

• Este de fapt varianta adaptată la unitățile de disc a algoritmului First-In, First-Out (FIFO).

• Un algoritm foarte simplu din punct de vedere al complexității, prima cerere sosită este și cea soluționată, următoarele cereri sosite urmând a fi soluționate pe rând, în funcție de ordinea sosirii lor.

• Este un algoritm slab ca performanțe datorită mișcărilor aleatoare ale capului pe suprafața discului, însă simplu și ușor de implementat.

Algoritmul SCAN (Elevator)

• Cererile sunt soluționate numai într-o anumită direcție de parcurgere a discului, celelalte fiind plasate într-o coadă de așteptare.

• Variante îmbunătățite ale acestui algoritm includ C-SCAN, LOOK, C-LOOK.

Algoritmul Shortest Seek-Time First (SSTF)• Reprezintă oarecum o îmbunătățire a FCFS.

• Controlerul de disc păstrează un buffer cu cererile nou sosite, fiecare având atașat un număr de cilindru.

• Algoritmul determină care este cererea cea mai apropiată de poziția curentă a capului, iar apoi soluționează cererea următoare.

• Avantaje majore față de FCFS însă poate apărea “înfometarea” dacă noi cereri apar aproape de poziția curentă a capului, cele mai depărtate neapucând să fie soluționate.

Algoritmul C-LOOK• Reprezintă o îmbunătățire a algoritmului SCAN normal, cel mai performant din această familie, mai performant și decât SCAN, C-SCAN, LOOK, C-LOOK.

• Algoritmul îndeplinește cereri doar într-o singură direcție începând de la cel din extrema interioară a dicului și deplasându-se spre exterior și soluționând cererile ce apar pe parcurs pâna la ultima. Apoi se

mută din nou pe poziția din extrema

interioară a discului.

Mediul de simulare DiskSim 4.0

• Reprezintă un simulator al sistemelor de stocare magnetică foarte eficient, exact și puternic configurabil. Poate simula discuri, controlere intermediare, magistrale, drivere de dispozitiv, memorii cache ale blocurilor de disc, organizări de date pentru tablouri de discuri.

• Inițial a facut parte dintr-un simulator complet de sistem (SimOS) și poate fi integrat ușor în astfel de sisteme complete de simulare.

• Modelează performanțele unui subsistem de stocare, însă nu salvează sau restaurează efectiv datele pentru fiecare cerere.

• Programul funcționează numai sub sistemele de operare Linux și vine sub formă de surse scrise în limbajul C și necesită compilare.

O comandă de rulare a simulatorului DiskSim arată astfel:

disksim <parfile> <outfile> <tracetype> <tracefile> <synthgen> [ par override... ]

unde: disksim reprezintă numele simulatorului. <parfile> reprezintă fișierul de parametri ai discului. <outfile> reprezintă fișierul în care vor fi depuse rezutatele simulării. Poate fi folosit “stdout” pentru acest parametru, rezultatele fiind afișate direct pe ecran.

<tracetype> reprezintă formatul fișierului workload. Se poate alege între “ascii”, “raw” sau “validate”, însă de cele mai multe ori se folosește “ascii”.

<synthgen> reprezintă o valoare booleană care specifică dacă pentru simulare se folosește generatorul intern de workload. 1 reprezintă activarea generatorului, 0 reprezintă neactivarea sa. [par override...] reprezintă un set de declarații adiționale ce se folosesc pentru a specifica de la linia de comandă alte valori ale anumitor parametri ale simulării.

Exemplul unei linii de comanda:./disksim SeagateCheetah15k5.parv results.out ascii trace1.trace 0 "disk*" "Scheduler:Scheduling policy" 4

Aici s-a folosit un exemplu de rescriere a parametrilor modificăndu-se politica de programare a acceselor la folosirea algoritmului cu numărul 4, cod ce reprezintă algoritmul SSTF.

Optimizarea unui algoritm de programare a acceselor la disc

• Din punct de vedere al performanțelor, majoritatea tipurilor de algoritmi produc rezultate destul de apropiate, fiind dificilă departajarea evidentă a vreunui tip anume de algoritm.

• Pentru sistemele reale, majoritatea abordărilor din punct de vedere al acceselor la disc caută implementarea unui algoritm care să furnizeze o performanță globală maximă pentru orice tip de sarcină de lucru.

• Acest lucru nu este posibil datorită faptului că sarcinile de lucru ale unui sistem real sunt extrem de variate, se modifică pe parcursul timpului și astfel nu nici un tip de algoritm care să se comporte optim în orice tip de situație.

• O soluție optimă ar fi ca în loc de a se încerca găsirea unui algoritm care să se comporte optim pentru orice fel desarcină de lucru, să se folosească algoritmii deja existenți însă într-un mod inteligent și eficient, bazat pe analiza sarcinilor de lucru din sistem și de performanța sistemului.

• Dacă anumite tipare din componența sarcinilor de lucru ar puteafi observate în timp real, atunci sistemul ar putea prin intermediulunui analizator de cereri I/O să aleagă cel mai potrivit algoritm încazul sarcinii de lucru respective pentru a îmbunătății performanțacorespunzător.

Variantă de optimizare a algoritmului FCFS

• FCFS reprezintă unul dintre cei mai utilizați, cei mai simpli și usor de implementat algoritmi de programare acceselor.

• Limita superioară a funcției de cost a timpului de căutare este diferența dintre cei mai îndepărtați doi cilindri, adică cel imediat aflat lângă axul discului și primul din marginea exterioară a aceluiași disc.

• Limita inferioară a funcției cost a timpului de căutare este diferența dintre oricare doi cilindri consecutivi, excepând situația în care două cereri apelează același cilindru.

• Considerăm costul total ca suma funcțiilor cost reprezentate de distanțele dintre 2 cereri consecutive din coada de așteptare în valoare absolută.

• Optimizarea constă în impunerea unei condiții de distanță maximă care trebuie îndeplinită pentru ca cererea să fie

acceptată sau respinsă.• Am considerat ca acestă condiție să fie dată de diferența

între o cerere și următoarea să fie mai mică sau cel mult egală

cu distanța între cilindrul cererii de start și cea mai mică valoare a cilindrului aflată în coada de așteptare.

• Dacă acestă condiție este îndeplinită, atunci cererea este soluționată.

În caz contrar, aceasta este respinsă și introdusă într-o coadă

intermediară.

ExempluFie coada de așteptare cu următoarele valori: 98, 183, 37, 122, 14, 124, 65, 67.

Pentru algoritmul FCFS normal, costul total va fi:

|98 - 183| + |183 - 37| + |37 - 122| + |122 - 14| + |14 - 124| + |124 – 65| + |65 - 67| = 85 + 146 + 85 + + 108 + 110 + 59 + 2 = 595.

În cazul algoritmului FCFS optimizat, calculele sunt după cum urmează:

|98 - 183| = 85 > 84, cererea este respinsă și este adăugată în coada intermediară care va conține valoarea 183.|98 - 37| = 61 < 84, cererea este soluționată, costul total fiind 61.|37 - 122| = 85 > 84, cererea este respinsă și adăugată în coada intermediară care va conține valorile 183, 122.|37 - 14| = 23 < 84, cererea este rezolvată, costul total fiind 61 + 23 = 84.|14 - 124| = 110 > 84, cerera este respinsă și adăugată în coada intermediară care va conține 183, 122, 124.|14 - 65| = 51 < 84, cererea este rezolvată, costul total fiind 61 + 23 + 51 = 134.|65 - 67| = 2 < 84, cererea este rezolvată, costul total fiind 61 + 23 + 51 + 2 = 136. În coada intermediară au rămas acum trei valori care se vor rezolva după metota FCFSclasică, adică secvențial.|67 - 183| = 116, costul total devenind 136 + 116 = 252.|183 - 122| = 61, costul total devenind 252 + 61 = 313.|122 - 124| = 2, costul total devenind 313 + 2 = 315.

Față de costul algoritmului FCFS clasic de 595 de unități, costul obținut cu algoritmul optimizat este de 315 unități, cu o îmbunătățire de aproximativ 94% în acest caz.

Acest algoritm este eficient pentru sarcini distribuite uniform pe cilindrii discului și cu odistanță mare între ele. În caz contrar, algoritmul nu aduce îmbunătățiri semnificative, putându-se dovedi chiar în unele cazuri mai ineficient datorită operațiilor de comparare și inserție.

Aplicație pentru studiul peformanței unor algoritmi de programare a acceselor la

disc• Am realizat o aplicație în limbajul Java care împreună cu mediul de simulare DiskSim 4.0 ne

permite studierea perfomanțelor a 5 tipuri de algoritmi. Algoritmii folosiți sunt FCFS, SCAN (Elevator), C-LOOK, SSTF, SPTF.

• Prima parte este reprezentată de generatorul de workload-uri. Se pot alege tipul distribuției blocurilor (gaussian sau uniorm), intervalul de sosire a cererilor cu valoare constantă sau aleatoare, numărul de cereri generate.

• După crearea workload-urilor se poate începe simularea alegând discul de pentru care se dorește simularea. În cazul alegerii algoritmilor pentru care să se simuleze respectivul disc, este necesară alegerea tuturor celor 5, apăsând butonul “Select All”, în caz contrar putând să apară erori. Se poate alege între 3 tipuri de discuri și anume Seagate Cheetah 146GB

15000 RPM, Western Digital AAKS 250GB 7200 RPM și un model mai vechi de 1 GB și 5400 RPM, HP C3323A.

• După ce s-au selectat toate aceste opțiuni se poate începe simularea apăsând butonul “Start Simulation”. În cazul în care simularea s-a încheiat cu succes, va fi afișat un mesaj de confirmare.

• După simulare, se va apăsa butonul “Show Results”, moment în care vor fi afișate graficele cu rezultatele simulării.

• Sunt urmăriți 6 categorii de parametri, și anume, timpul de căutare al discului,

latența rotațională, timpul de transfer, timpul de acces, numărul de cereri I/O

pe secundă și timpul de răspuns al controlerului I/O, toate pentru valori medii.• Graficele conțin cele 6 categorii, fiecare categorie prezentând aceste valori

pentru fiecare algoritm.

Interfața pentru generarea de workload-uri.

Eșantion extras dintr-un fișier workload.

Prima coloană reprezintă tipul la care sosește cererea (față de momentul 0), a doua coloană reprezintă discul care se simulează, a 3-a coloană reprezintă numărul blocului, a 4-a durata unei cereri în (număr de operații), iar ultima coloană reprezintă tipul cererii, dacă este citire sau scriere, 1 reprezintă citire și 0 scriere.

Interfața principală

1. Simulare hard-disk Seagate Cheetah 15k5 pentru 1000 de cereri, distribuție gaussiană cu medie 50000 (bloc central) și dispersie 5000, interval de timp între cereri de 2 ms.

2. Simulare hard-disk Western Digital AAKS în aceleași condiții ca mai sus.

1. Simulare hard-disk HP C3323A pentru aceleași condiții de dinainte.

2. Simulare hard-disk Seagate Cheetah 15k5 pentru 5000 de cereri, distribuție gaussiană de medie 50000 (bloc central) și dispersie 5000, distanță între sosirile cererilor de 2 ms

1. Simulare hard-disk Seagate Cheetah 15k5 pentru o sarcină de lucru cu 5000 de cereri, distribuție între momentele de sorire ale cererilor aleatoare.

2. Simulare hard-disk Seagate Cheetah 15k5 pentru 1000 de cereri, distribuție gaussiană de medie 50000 (bloc central) și dispersie 500, distanță între sosirile cererilor de 0.2 ms

Concluzii și observații

• Cele mai slabe rezultate se obțin în cazul hard-disk-ului HP C3323A, datorită inferiorității sale.

• Algoritmul care se remarcă în toate cazurile studiate este SPTF. Locurile 2 și 3 sunt ocupate de SSTF, respectiv C-LOOK.

• Algoritmii SCAN clasic și FCFS ocupă cele mai slabe poziții.

• Algoritmul SPTF care a produs rezultatele cele mai bune este bazat pe reducerea distanței de poziționare a capului. Combinat cu o politică eficientă de evitare a înfometării, acest algoritm produce rezultate optime.