Strainu onLine

Descriere: Sistemele de calcul pot fi reprezentate cu ajutorul modelelor de cozi de taskuri.
Materie: Evaluarea Performanţelor
Referat făcut la facultate.

Download

Mai jos aveţi la dispoziţie o variantă text a referatului. Vă rugăm să reţineţi că această variantă nu are nici un fel de formatare sau poze. Unele caractere pot să nu fie arătate corect. Pentru varianta integrală vă rugăm să downloadaţi referatul.

UNIVERSITATEA POLITEHNICA BUCUREŞTI
FACULTATEA DE AUTOMATICĂ ŞI CALCULATOARE

MODELE CU COZI ÎN SISTEMELE DE CALCUL

Cuprins
Cuprins 2
Reţele de cozi 3
Tipuri de reţele 4
Încărcări paralele în reţele de cozi 4
Reţele închise 5
Modelul Serverului Central 5
Modelul Maşinii de Service 6
Reţele deschise 6
Reţele serie 6
Reţele cu feedback 7
Încărcări paralele în reţele serie 7
Sistemul bazat pe terminale 7
Sisteme cu programare cu priorităţi 8
Ce nu se poate face cu modelele cu cozi 8
Bibliografie 10

O coadă este definită ca fiind o structură formată dintr-un servant (server) şi o linie de aşteptare pentru clienţii care solicită anumite servicii ale serverului. Fiecare client este pus la sfârşitul cozii şi avansează pe măsură ce serverul serveşte clienţii de la celălalt capăt al cozii. În figura1 de mai jos este reprezentată o coadă simplă:
Prima lucrare asupra teoriei cozilor a fost publicată în 1909 de inginerul danez Agner Krarup Erlang. În 1953, David G. Kendall a introdus notaţia A/B/C pentru o coadă, unde A reprezintă funcţia de distribuţie a timpului dintre două taskuri, B este funcţia timpului de servire, iar C reprezintă numărul de servere. Pentru a fi util, un model cu cozi trebuie să reprezinte sistemul real cu suficientă precizie, dar şi să fie calculabil într-un timp finit.
Reţele de cozi
O reţea (numită uneori şi circuit) de cozi este construită conectând ieşirea unei cozi de intrarea unei alte cozi. Teoretic, o reţea de cozi poate fi orcât de complicată. O coadă poate fi alimentată de ieşirea mai multor cozi şi la rândul ei, ieşirea poate fi împărţită între mai multe cozi. În acest caz, există o probabilitate asociată cazului în care taskul ieşit din coadă intră în una din celelalte cozi. Ca alternativă, taskul poate fi împărţit în sub-taskuri, fiecare din ele fiind tratat de o coadă.
Fiecare coadă formează un „nod” al reţelei şi poate fi numerotată 1,2, …, M, unde M este numărul de cozi din reţea. Prin „probabilitate de rutare” se înţelege probabilitatea ca ieşirea nodului i să ajungă imediat la intrarea nodului j.
Reţelele de cozi se pretează foarte bine la modelarea unor sisteme de calcul inter-conectate, fiecare din ele fiind modelată ca o coadă. De exemplu, un model simplu pentru calculator, constând dintr-un procesor şi un disc, poate fi reprezentat printr-o reţea de 2 cozi.
Unii autori preferă termenul de circute de cozi în loc de reţele de cozi din cauza asemănării cu circuitele electrice:
• circuitele presupun o curgere (de electroni, respectiv cereri)
• circuitele au intrări şi ieşiri
• circuitele pot fi combinate în serie, paralel sau orice combinaţie a celor 2
• circuitele pot fi partiţionate în subcircuite (sau subrutine)
• subcircuitele pot fi scurtcircuitate (eliminate), pentru a simplifica problema
• circuitele pot avea feedback (circuite închise)
Tipuri de reţele
O reţea de cozi poate fi deschisă, închisă sau mixtă. Într-o reţea deschisă, taskurile vin la nodurile de intrare de la o sursă externă şi părăsesc reţeaua pe la nodurile de ieşire. Se presupune că sursa are un număr infinit de taskuri, iar numărul de taskuri prezente la un moment dat în coadă poate varia.
Într-o reţea închisă există un număr fix de taskuri care circulă între nodurile reţelei. Nu există niciun task care să intre sau să iasă.
Reţelele mixte sunt un amestec al celor două tipuri prezentate anterior. Unele cereri intră in reţea, sunt tratate şi părăsesc reţeaua, în timp ce altele se plimbă între nodurile reţelei fără să iasă niciodată. Un exemplu simplu pentru acest tip de reţele îl reprezintă un computer multi-tasking, în care cererile interactive (partea închisă a reţelei) sunt amestecate cu cereri de la clienţi externi (de exemplu cereri HTTP către un server web de pe acea maşină). O asemenea reţea este rezolvată prin calcularea necesarului de resurse al cererilor externe, apoi calculând diminuarea performanţelor cererilor interne în cazul diminuării resurselor.
O altă metodă de împărţire a reţelelor de cozi, mai puţin utilizată, este după capacitatea cozilor componente. Folosind acest criteriu, reţelele pot fi împărţite în:
• reţele non-blocante, dacă toate cozile din sisteme au o capacitate infinită;
• reţele blocante, dacă cel puţin o coadă din sistem au capacitate finită.
Un alt exemplu de situaţie în care reţeaua se poate bloca este atunci când un task este împărţit în două sau mai multe subtaskuri care trec prin cozi diferite, pentru ca ulterior să fie reunite. Subtaskul care ajunge primul va trebui săaştepe şi celelalte subtaskuri, blocând nodul curent.
Încărcări paralele în reţele de cozi
Când se doreşte construirea unui model de reţea închisă pentru un calculator, trebuie urmărite şi diferite efecte laterale care nu sunt evidente la prima vedere. Dacă se omite acest pas, analiza performanţelor poate duce la proiecţii incorecte ale performanţei.
În literatura referitoare la teroia cozilor, taskurile asociate reţelelor deschise sunt numite tranzacţii. Analog, taskurile asociate cu reţele închise pot fi de două feluri, taskuri terminale sau batch (lot). Fiecare din aceste tipuri de taskuri au anumite proprietăţi:
• Taskurile terminale sunt caracterizate de un număr constant de utilizatori sau procese N şi timpul lor de gândire Z. Rata de sosire a taskurilor noi nu este constantă şi este redusă faţă de numărul de procese aflate deja în coadă. Din punct de vedere istori, termenul provine din aplicarea teoriei cozilor la computerele multi-tasking unde un număr finit de clienţi se conectează printr-un număr finit de terminale.
• Taskurile batch sunt caracterizate de numărul de loturi, N. Obiectivul acestui tip de sisteme este maximizarea utilizării procesorului şi a dispozitivelor de I/E, în aşa fel încât lotul să fie finalizat într-un timp determinat. Deoarece aceste sisteme nu interacţionează cu utilizatorii, nu necesită folosirea unui timp de gândire.
• Tranzacţiile sunt caracterizate de rata de sosire a taskurilor noi, λ. Se folosesc când numărul de utilizatori nu este cunoscut, ca în cazul bancomatelor sau a serverelor web. Putem considera acest număr ca infinit, deoarece rata nu depinde de numărul de cereri aflate deja în coadă.
• Taskurile amestecate reprezintă un mix al claselor descrise mai sus.
Reţele închise
Reţelele închise au fost folosite cu succes în modelarea sistemelor de calcul. Două din modelele cele mai folosite sunt modelul Serverului Central şi modelului Maşinii de Service.
Modelul Serverului Central
O reţea de cozi având un server central este reprezentată în figura de mai jos.

Dacă dorim să aplicăm acest model pentru un computer, putem considera că nodul 1 reprezintă procesorul, pe când nodurile 2 până la M reprezintă dispozitivele de intrare-ieşire (I/E) – de exemplu controllerele de hard-disk. Cererile sunt tratate de CPU, apoi sunt rutate cu o anumită probabilitate către dispozitivul de I/E i. După ce a fost tratată de dispozitivul i, cererea se întoarce la CPU. În acest model, procesarea unei cereri de către un computer este reprezentată prin mai multe vizite la CPU şi dispozitivele de I/E. Drumul de la CPU până la el însuşi (cu probabilitatea aferentă), reprezintă terminarea unui task în sistem şi începutul altuia.
Acest sistem este deosebit de util când se doreşte modelarea resurselor interne (CPU şi discuri) a unor sisteme multi-program. În aceste sisteme, numărul de programe (numărul de taskuri aflate la un moment dat în memorie) este limitat în favoarea eficienţei sistemului. Dacă supunem sistemul unei încărcări medii sau ridicate, îl aducem rapid la limită. De aceea, presupunerea că numărul de taskuri este constant este o aproximaţie bună a sistemului real.

Modelul Maşinii de Service
Acest model, dezvoltat iniţial în studiul operaţiilor, este folosit deseori pentru a reprezenta sisteme interactive de calcul. O asemenea reţea are un nod cu mai multe servere (nod terminal), folosit pentru a reprezenta terminalele clienţilor. Celelalte cozi reprezintă celelalte resurse ale sistemului, putând fi conectate oricum, deşi de cele mai multe ori se foloseşte modelul serverului central sau diverse variante ale acestuia.
Taskurile încep la nodul terminal şi intră în sistem, unde circulă între CPU şi dispozitivele de I/E până ajunge din nou la nodul terminal. Timpul petrecut în sistem este timpul de răspuns al sistemului, iar timpul petrecut în nodul terminal reprezintă timpul de gândire al utilizatorului. Numărul de taskuri de sistem este egal cu numărul de terminale (adică numărul de servere din noud terminal). În acest fel nu există un timp de aşteptare în cazul acestui nod, timpul de tratare fiind egal cu timpul de gândire.

Reţele deschise
Reţelele deschise sunt folosite pentru a modela sisteme de calcul cu un număr variabil de taskuri sau cu o rată constantă de joburi noi. Sistemele de operare batch şi reţelele de comunicaţie sunt sisteme de acest fel.
Reţele serie
Cel mai obişnuit tip de reţea serie este aranjamentul tandem, în care avem mai multe cozi, ieşirea uneia ducând direct la intrarea următoareia. Acest tip de reţele pot fi tratate ca mai multe reţele independente. Demonstraţia acestei afirmaţii poate fi găsită în [3].
Mai putem avea şi situaţia în care ieşirea uneia din cozi este împărţită în mai multe canale, care duc spre cozi diferite. Exită două cazuri particulare foarte importante de astfel de reţele serie:
• Reţelele cu feedback, în care ieşirea cozii poate duce înapoi la intrare şi despre care vom vorbi în paragraful următor;
• Reţelele în care nu există nicio cale de intrare sau ieşire din circuit, caz în care avem o reţea închisă.
Reţele cu feedback
Până acum am vorbit de cozi în care cererile sosesc din exterior fără o ordine precisă, intră în coadă, sunt tratate şi apoi părăsesc coadă fără să se întoarcă vreodată. Totuşi, în realitate există şi cazuri în care clienţii care deja au fost serviţi se întorc în coadă:
• Un client uită să cumpere ceva şi trebuie să se întoarcă la magazin;
• Copii stau la coadă să se dea pe tobogan;
• Anumite pachete trebuie retransmise în reţea.
Această situaţie este numită feedback. În astfel de sisteme, sosirile se produc cu o rată notată cu λ. Cererile care au fost tratate ori ies din coadă, ori se întorc la intrare cu o probabilitate p. Rata cererilor care vin de la ieşire este deci pλ1, unde λ1 este rata totală la intrare (cereri noi + cereri venite ca feedback). Putem deci scrie ecuaţia: λ1 = λ + pλ1. De aici obţinem că rata totală la intrare este: λ1 = λ/(1-p).
Putem spune că feedback-ul este o transformare ce dilată timpul cu o scală V egală cu numărul mediu de vizite la server. Lungimea Q a cozii este invariantă. Un exemplu de astfel de sistem este canalul de comandă al unui satelit. Dacă 30% din mesaje se pierd şi trebuie retransmise, vom avea V = 1/(1-p) = 1,429. Timpul total de răspuns este R = VRv = 2,310 s.
Încărcări paralele în reţele serie
După cum am spus mai sus, putem avea reţele deschise combinate cu reţele închise, având deci taskuri amestecate. Aceleaşi noduri servesc două tipuri de taskuri, tipul de circuit fiind determinat de tipul de task. În mod analog, putem avea o reţea deschisă cu mai multe streamuri de intrare, fiecare cu alte tipuri de taskuri. Acest model poate fi aplicat pe un model tandem simplu pentru a ţine cont de faptul că procesorul şi discul trebuie să trateze atât cereri de la kernelul sistemului de operare cât şi de la diverse programe-utilizator.
Sistemul bazat pe terminale

Un model deosebit de util pentru multe clase de sisteme interactive de calcul este cel bazat pe terminale. Schema sa este aproape identică cu cea a modelului maşinii de service.
În acest model, numărul de joburi este egal cu numărul de terminale (notat cu N). Se consideră că un job părăseşte „terminalul” atunci când utilizatorul apasă ENTER, circulă orin diversele componente ale sistemului pe măsură ce este procesat şi în cele din urmă se întoarce la terminal pentru a fi afişat rezultatul. Timpul de răspuns al sistemului (notat cu R) este timpul dintre plecarea taskului din terminal până la întoarcerea sa acolo. Analog cu modelul de mai sus, timpul de gândire al utilizatorului (notat cu Z) este timpul dintre terminarea unei comenzi şi iniţializarea următoarei comenzi.
Sisteme cu programare cu priorităţi
Până acum am presupus că politica de servire a cererilor este FIFO (primul venit, primul servit) sau preemptivă. Politica FIFO este acceătabilă pentru încărcări de un singur fel, în care toate cererile au aceleaşi necesităţi. Dacă există mai multe clase de servicii deosebite prin cererile pe care le adresează serverului, acesta se comportă după principiul ultimul sosit, primul servit cu preempţiune la reluarea procesării. În lumea reală, acestepresupuneri sunt nesatisfăcătoare şi trebuie să ţinem cont de schedulingul explicit. Se poate demonstra că şi cozile cu priorităţi pot fi implementate folosind aceleaşi principii majore ca la cozile obişnuite. Tehnica este o variantă a celei folosite pentru timpul de răspuns al unei cozi deschise cu mai multe tipuri de cereri. Să presupunem că există două tipuri de clase de sarcini, Producţie şi Dezvoltare. Dacă una din ele nu îşi atinge performanţele din specificaţii putem să-i acordăm o prioritate mai mare la accesul la procesor.
Ce nu se poate face cu modelele cu cozi
• Blocare: În paragrafele precedente am presupus că lungimea cozii este infinită. În realitate, cozile şi bufferele sunt alocate cu o dimensiune finită (limitată, în cel mai bun caz, de dimensiunea memoriei sistemului). Când un buffer finit se umple, vom dori să blocăm procesarea la resursele din „amonte”, pentru a nu se pierde date. Altfel spus, rata deservire la unul din noduri depinde de starea tuturor cozilor din sistem. De aceea, presupunerea că fiecare nod poate fi analizat separat nu mai este valabilă.
• Sosiri în grup: Dacă taskurile sosesc în număr mare într-o coadă (specific sistemelor de comunicaţie cu lungi perioade de inactivitate urmate de vârfuri de trafic – de exemplu pe linia telefonică a unui abonat), trebuie făcute anumite presupuneri pentru ca modelarea cu cozi să funcţioneze.
• Rezolvarea accesului concurent: Anumite protocoale de reţea ca ALOHA sau Ethernet folosesc reguli sofisticate pentru detecţia şi rezolvarea coliziunilor. Acestea implică back-off şi retrimiterea datelor, fiind greu de implementat folosind modele cu cozi.
• Primitive Fork/Join: Crearea de procese-copil este folosită pentru obţinerea unui anumit nivel de paralelism. Primitiva join este folosită pentru a sincroniza procesele create anterior. Din păcate, fork violează presupunearea de separabilitate pe care am făcut-o.
• Strategii din teoria jocurilor: Înşelătoria, mita şi alte metode de acest fel nu pot fi modelate corect.
• Sosiri dependente de încărcare: Sistemele de calcul care fac load-balancing, împărţind taskurile care sosesc unor resurse mai puţin utilizate sunt greu de modelat folosind cozi.
• Excludere mutuală: În sistemele distribuite se practică excluderea mutuală a taskurile în cazul acceselor la resurse partajate. Excluderea se face prin folosirea semafoarelor sau lacătelor. Nici acest lucru nu poate fi uşor modelat folosind cozi.
• Timpi de servire ne-exponenţiali: O cerinţă majoră pentru respectarea condiţiei de searabilitate este ca timpii de servire să fie exponenţiali. Dacă avem altfel de timpi de răspuns, nu se mai respectă condiţia amintită.
• Treceri dintr-o coadă în alta: E ceea ce se întâmplă la super-market, când un client nemulţumit de viteza casierei trece la altă coadă ce pare să se mişte mai repede. O strategie asemănătoare este folosită şi de anumite sisteme – de exemplu un pachet stă într-o coadă un timp, după care pachetul este eliminat deoarece el a fost deja retransmis de sursă.
• Sosiri dependente de servire: Situaţia este asemănătoare cu cea anterioară, doar că lipseşte timerul. Sursa retransmite pur şi simplu pachetul, ceea ce provoacă şi mai multă congestie la resursele deja ocupate. Mai mult, acest lucru face sistemul sensibil la fluctuaţii puternice, timpii de răspuns putând creşte rapid.
• Punerea în comun de resurse finite: cum sunt memoria RAM, memoria virtuală, accesul la reţea şi altele.
• Folosirea simultană a mai multor resurse: Un exemplu de acest fel este un dispozitiv de intrare-ieşire asincron. Procesul continuă după ce a trimis cererea de acces la subsistemul de intrare-ieşire. Din acest punct de vedere, taskul respectiv foloseşte mai multe resurse simultan, ceea ce contrazice presupunerea despre independenţa joburilor. Este dificil de reprezentat această situaţie cu reţele de cozi, dar nu imposibil (folosind modelarea corectă a cererilor şi modele cu încărcări de mai multe feluri).
• Timp de gândire: Conceptul programelor care aşteaptă input de la operatorul uman prin terminal devine depăşit în lumea modernă, unde interfeţele grafice iau partea leului.

Bibliografie
1. http://en.wikibooks.org/wiki/Computer_Systems_Engineering/Queueing_system_models
2. http://en.wikipedia.org/wiki/Queueing_theory
3. Neil J. Gunther: „Analyzing Computer System Performance with Perl::PDQ”, Springer – Verlag, 2005
4. Sanjay K. Bose: „An Introduction to Queueing Systems”, Springer-Verlag, 2002
5. http://staff.um.edu.mt/jskl1/simweb/intro.htm
–––––
Note
1 Toate figurile provin de pe Wikibooks, fiind sub licenţa GNU Free Documentation