Sisteme de Asteptare

8/13/2019 Sisteme de Asteptare

1/11

1

Sisteme de ateptare pentru calculul paralel i distribuit(Queuing systems for parallel and distributed processing)

Asist. drd. Felician ALECUCatedra de Informatic Economic

Academia de Studii Economice Bucureti

RezumatPerformanele sistemelor de ateptare n condiii de suprasolicitare joac un rol

important n ceea ce privete percepia consumatorilor asupra calitii serviciilor. Timpiide ateptare i ntrzierile sunt inevitabile n cadrul acelor sisteme de ateptare carerspund unor cereri aleatoare a cror apariie n timp i spaiu este guvernat de anumitelegi probabilistice cunoscute sau necunoscute. A oferi , n cadrul unui sistem de ateptare,capaciti de servire suficiente pentru a evita ateptrile n absolut orice circumstaneimplic costuri uriae. Din acest motiv, scopul teoriei ateptrii este acela de a ne asista nproiectarea unor sisteme de servire n care exist un echilibru ntre costurile de operare itimpii de ateptare ai utilizatorilor sistemului.

Cuvinte cheieTeoria ateptrii, sistem de ateptare, reea de ateptare, sisteme distribuite

geografic, planificarea programelor paralele, sisteme de calcul paralel i distribuit,eficiena programelor paralele.

1. IntroducereTeoria ateptrii este principalul instrument folosit n studiul fenomenelor de

congestionare care apar atunci cnd numrul cererilor depete capacitatea de servire.Termenul coadprovine din cuvntul latin codai semnific dispunerea sub forma unuiir a unor persoane aflate n ateptare.

Teoria ateptrii se constituie ca o ramur a cercetrilor operaionale ce are caobiectiv abordarea matematic a cozilor sau a firelor de ateptare. Firele de ateptare iteoria ateptrii i-au gsit aplicabilitate n diverse domenii cum ar fi telecomunicaiile,controlul traficului, anticiparea performanelor computerelor, serviciile medicale(planificarea paturilor dintr-un spital), traficul aerian, vnzarea biletelor de avion,

industria minier, etc.n ceea ce privete latura practic, se pleac de la un sistem din lumea real carese analizeaz iar n urma analizei se decide asupra modelului matematic care descrie celmai bine sistemul. Acest model matematic poate fi unul nou creat sau se poate apela launul deja existent. Prin analizarea acestui model matematic se obin o serie de concluziicare pot fi extinse asupra sistemului original. Activitatea de creare a unui modelmatematic are la baz simplificarea i aproximarea sistemului iniial. Astfel, detaliileconsiderate a fi nesemnificative nu sunt incluse n cadrul analizei. De asemenea, pentru a


2/11

2

se putea transpune comportamentul sistemului sub forma unui model matematic estenecesar ca datele primare s fie transformate n mrimi matematice folosind aproximarea.De multe ori, n ceea ce privete comportamentul sistemului real se fac o serie depresupuneri bazate mai ales pe intuiia i experiena analistului dect pe observaiiefectuate n cadrul sistemului [1].

Atunci cnd se alege un model matematic, se poate opta pentru un model realisticdar care poate s nu conduc la nici un fel de rezultate sau se poate opta pentru un modelsimplificat care s genereze rezultate aproximative. Marea majoritate a rezultatelor exactedin cadrul teoriei ateptrii s-au obinut n acele sisteme n care ritmul de sosire alconsumatorilor i/sau ritmul de servire al staiilor sunt guvernate de o lege deprobabilitate exponenial negativ. Din fericire, n cazul majoritii sistemelor deateptare cel puin ritmul de sosire al consumatorilor n sistem este exponenial negativdeoarece sosirile consumatorilor pot fi modelate dup o distribuie de tip Poisson [4].

n practic, teoria ateptrii este n special folosit pentru a scoate n evidendisfuncionalitile existente n cadrul unui sistem aflat n funciune i pentru a artadireciile de eficientizare a funcionrii acestuia prin indicarea valorilor pe care trebuie s

le ating anumite variabile de sistem pentru a se ajunge la un nivel satisfctor alperformanelor.Principalul avantaj al teoriei ateptrii este acela c ne pune la dispoziie

informaii extrem de importante despre timpii de ateptare care apar n sistem pe bazaunor date minimale despre caracteristicile sosirilor n sistem, caracteristicile staiilor deservire i disciplina sistemului.

2. Structura unui sistem de ateptareUn sistem de ateptare reprezint un model generic care se compune din

urmtoarele trei elemente (Fig. 1): clienii (consumatorii)care solicit un serviciu; staia de servire ce are ca menire satisfacerea cererilor clienilor; ntr-un

sistem de ateptare staia de servire poate avea un singur post sau pot existamai multe posturi (numr finit sau infinit) identice care lucreaz n paralel;

firul de ateptare sau coada care se formeaz n cazul n care consumatoriitrebuie s atepte.

Modelele din teoria ateptrii se difereniaz ntre ele n ceea ce privete: legile de probabilitate ce guverneaz sosirea clienilor i servirea acestora; numrul posturilor din staia de servire; disciplina firului de ateptare;

structura populaiei consumatorilor (numr finit sau infinit de consumatori).Din acest motiv, este evident faptul c exist nenumrate modele de sisteme i

reele de ateptare. Pentru descrierea celor mai utilizate, n literatura de specialitate s-aimpus o notaie de forma

A/B/msauA|B|mundeAiBsunt simboluri de litere iar mreprezint o constant numeric. Aceast notaiea fost folosit pentru prima dat de ctre Kendall n 1953.


3/11

3

Fig. 1 Structura unui sistem de ateptare

Semnificaia celor trei simboluri este urmtoarea: prima liter indic legea de probabilitate care guverneaz sosirile

consumatorilor n sistem. cea de-a doua liter simbolizeaz legea de probabilitate care descrie procesul

de servire. constanta numeric desemneaz numrul de posturi identice care funcioneaz

n paralel n cadrul staiei de servire

Literele A i B pot lua una din valorile prezentate in Tab. 1 n timp ce constantanumeric poate lua valori de la 1 la .

Desigur c poate prea straniu faptul c dintre toate distribuiile de probabilitateposibile doar patru (M, D, E, H) au asociate simboluri speciale, toate celelalte fiindincluse in categoria generic G care, evident, include i categoriile anterioare. Motivulpentru care doar cele patru distribuii de probabilitate au fost evideniate este acela cnumai aceste distribuii ofer avantaje semnificative n ceea ce privete analiza sistemuluide ateptare [1].

SIMBOL SEMNIFICAIEM Distribuie Poisson (distribuie exponenial negativ)D Distribuie deterministic (la intervale constante)

Ek Distribuie Erlang de ordinul kHk Distribuie hyperexponenial de ordinul kG Distribuie generic (orice fel de distribuie)

Tab. 1 Distribuii de probabilitate care au simboluri speciale asociate

Alte abrevieri care s-au impus sunt cele referitoare la cele mai ntlnite disciplinede servire:

Sursa

(populaie)

Sosireaclienilor

Fir de ateptare(coada)

Staie de servire

Servireaclienilor

Plecareaclienilor

Post 1

Post n

.

.

.


4/11

4

FIFO indic faptul c primul client sosit este i primul servit (first-in, first-out);

LIFO presupune servirea ultimului consumator dispus n coada de ateptare(last-in,first-out);

SIRO semnific faptul c servirea se face n mod aleator (service in randomorder).

Prin interconectarea a dou sau mai multe sisteme de ateptare obinem o reea deateptare (reea de sisteme de ateptare Fig. 2). n cadrul unei reele de ateptare,populaia surs a unui sistem poate proveni din clienii care au prsit un alt sistem deateptare aparinnd reelei.

Fig. 2 Reea de ateptare

Capacitatea sistemului reprezint un alt parametru important n descrierea unuisistem de ateptare i semnific numrul maxim de consumatori ce pot fi la un moment

dat n sistem, unde prin numrul de clieni din sistem nelegem att clienii care sunt ncadrul staiei de servire ct i pe cei care se afla n coada de ateptare. Prin capacitateacozii de ateptare nelegem numrul maxim de consumatori din care poate fi format firulde ateptare.

Pe baza legilor de probabilitate i a caracteristicilor staiei de servire se potcalcula duratele de ateptare att pentru consumatori ct i pentru staii ntr-un anumitinterval de timp. n cazul n care se asociaz costuri timpilor de ateptare, se obine o

Sistemde

ateptare1

Sistemde

ateptare2

Sistemde

ateptare3

Sistemde

ateptare4

Sistemde

ateptare5

Punct n care consumatorii fac oalegere n privina sistemului

ctre care s se ndrepte

Punct n care consumatorii serentlnesc

Punct de intrare nreeaua de ateptare

Punct de ieire dinreeaua de ateptare


5/11

5

funcie economic care se dorete a fi minimizat acionnd fie asupra ritmului de sosirefie asupra capacitii staiei.

3. Extensii ale modelelor clasice

Modelele de ateptare clasice au la baz o serie de ipoteze legate decomportamentul consumatorilor cum ar fi faptul c nici un consumator nu sedescurajeaz, prsind astfel coada, pe parcursul ateptrii pentru a fi servit. n plus,atunci cnd un consumator nu este acceptat n cadrul unui sistem de ateptare datoritfaptului c acesta funcioneaz la capacitate maxim, se presupune ca utilizatorul nu vareveni mai trziu ci se va ndrepta ctre un alt sistem care ofer servicii similare.

Modelele pot fi extinse prin exprimarea ritmurilor de sosire i de servire suburmtoarea form:

nn c= n= 0, 1, 2, ...

nn d= n= 1, 2, 3, ...

unde i sunt constante iar c i d sunt coeficieni ai cror valori depind de stareasistemului de ateptare.

Cu ajutorul extensiilor aduse acestor modele putem lua n considerare o serie decomportamente ale consumatorilor care pn acum erau considerate imposibile.

Un prim caz ar fi acela al utilizatorilor care prospecteaz starea sistemului deateptare i pe baza celor observate decid s nu se alture firului de ateptare ci s sendrepte ctre alte sisteme care ofer servicii similare.

O a doua situaie ar fi reprezentat de cazul unui consumator care, dei se afl nateptare n coad, decide s prseasc chiar dac nu a beneficiat nc de serviciul pentrucare a ateptat.

Cele mai utilizate forme ale coeficienilor cni dnsunt:

( )

a

n jnc

+=

n= 0, 1, 2, ...bn nd = n= 1, 2, 3, ...

undej, ai bsunt constante pozitive.Prin ajustarea valorilor lui ai/sau bpot fi modelate tipurile comportamentale ale

utilizatorilor indiferent de numrul posturilor de servire prezente n sistem sau decapacitatea acestora.

O extensie deosebit de important a modelelor de ateptare clasice o reprezintacele sistemele n care consumatorii au ataate prioriti care sunt luate n considerare dectre staia de servire [4]. n cazul tuturor modelelor clasice, ordinea n care utilizatorii auacces la staia de servire este determinat de disciplina firului de ateptare. Din acestmotiv consumatorii sunt difereniai doar pe baza ordinii n care au sosit n cadrul

sistemului de ateptare fr s se in cont de tipul i de durata serviciului pe care lsolicit.

Uzual, consumatorii poteniali ai unui sistem de ateptare sunt mprii n claseiar fiecrei astfel de clase i se asociaz o prioritate. Ori de cte ori un client prsetesistemul, urmtorul consumator servit va face parte din clasa cu cea mai mare prioritateasociat. Alegerea uni anumit consumator din cadrul clasei cu prioritatea cea mai ridicatse efectueaz n concordan cu disciplina asociat clasei respective.


6/11

6

n Fig. 3 se prezint reprezentarea schematic a unui sistem de ateptare cu rclasede prioriti. Fiecare utilizator al sistemului este ncadrat n una din cele r clase iarfiecare clas are asociat un numr k (k = 1, ..., r) care reprezint prioritatea claseirespective. Prin convenie se consider c cu ct valoarea este mai mic cu att prioritateaclasei este mai mare.

Fig. 3 Sistem de ateptare cu rclase de prioriti

Sosirile n cadrul fiecrei clase sunt Poisson de parametru kpentru clasa k. Seobserv c prin utilizarea claselor de prioriti se obin de fapt rfire de ateptare paralelecare concureaz pentru obinerea accesului la serviciul oferit de staia de servire.

Prioritile care difereniaz clasele de utilizatori pot fi clasificate n doucategorii:

preemptive n sistemele de ateptare care utilizeaz astfel de prioriti,utilizatorii cu prioritate ridicat nu vor fi niciodat nevoii s atepte n firdatorit consumatorilor cu prioritate mai sczut. Astfel, dac la coad se

Staie deservire

.

.

.

11X X XX

22X XX

33X

.

.

.

k-1k - 1XX

kkX X XX

k+1k + 1X XX

r-2r - 2XX

r-1r - 1X

rrXX

Rata desosire

Fire de ateptare Prioritate


7/11

7

aeaz un consumator care face parte dintr-o clasa cu prioritate mai ridicatdect cea a clientului care tocmai este servit atunci servirea acestuia din urmeste ntrerupt urmnd a fi reluat integral sau continuat din punctul din cares-a rmas. De asemenea, este posibil ca, n compensaie pentru faptul cservirea i-a fost ntrerupt, utilizatorului n cauz sa-i fie asociat o nou

prioritate mai ridicat dect cea anterioar; nonpreemptive servirea unui consumator din cadrul unui sistem de ateptarecare utilizeaz prioriti nonpreemptive nu va fi niciodat ntrerupt datoritsosirii n cadrul sistemului a unui consumator care face parte dintr-o clas cuprioritate mai ridicat. Servirea acestuia din urm se va face doar dup ceclientul din staia de servire prsete sistemul.

Multe sisteme de ateptare opereaz cu sisteme de prioriti diferite pentru clasediferite. Astfel, utilizatorii care fac parte dintr-o clas care are asociat o prioritate foarteridicat pot obine servicii preemptive n timp ce consumatorii unei clase cu prioritatemedie pot beneficia doar de servicii nonpreemptive fa de cei din clasele cu prioriti

inferioare. n interiorul claselor aceluiai sistem de ateptare pot fi folosite disciplinediferite [1].Astzi, sistemele de ateptare n care sosirea clienilor din diverse locaii

geografice se poate face prin intermediul liniilor telefonice sunt ntlnite la tot pasul.Apelurile sunt preluate de ctre un computer care memoreaz data, ora, originea i naturaapelului. Succesiunea acestor apeluri care solicit un anumit serviciu reprezint de faptcoada de ateptare numai c de data aceasta ea nu mai poate fi localizat fizic deoareceexist doar n memoria unui computer.

Staia de servire, fie c este o main sau o persoan, urmeaz s se deplaseze ladomiciliul solicitanilor pentru efectuarea serviciului solicitat. Un astfel de sistem poartnumele desistem de ateptare distribuit geografic.

Consumatorii i/sau posturile staiei de servire se caracterizeaz prin faptul c auo distribuie geografic. Exist i o incint a staiei de servire care este localizat static idin care pleac n teritoriu posturile componente. Fie consumatorii de deplaseaz ctrestaia de servire fie posturile acesteia sunt cele care merg la locaiile consumatorilorpentru completarea serviciului.

Servirea poate fi fcut acolo unde se afl localizat consumatorul, n incinta staieide servire sau pe parcursul traseului de la domiciliul clientului ctre staia de servire. npractic pot fi ntlnite cazuri n care servirea consumatorilor se realizeaz princombinarea celor trei variante anterioare. Un exemplu n acest sens l reprezint serviciilede ambulan.

Momentul, locaia i durata serviciului solicitat sunt elemente care variaz de laun consumator la altul. Structura spaiului geografic din care provin clienii joac un rolfoarte important pentru sistemul de ateptare n ansamblu. Distribuie spaial aconsumatorilor i caracteristicile drumului de la staia de servire pn la consumatorreprezint factori critici n ceea ce privete calitatea serviciilor oferite.


8/11

8

4. Aplicaii ale firelor de ateptare n procesarea paralel idistribuit

n ultimii ani sistemele paralele i distribuite au devenit din ce n ce mai atractivepentru aplicaii cu cerine de calcul intensive cum ar fi cele destinate simulrii unorsisteme complexe (aerodinamic, meteorologie). Principalul avantaj al unor astfel de

sisteme este raportul mai mult dect atractiv dintre pre i performanele care pot fiobinute [3].

Pentru a putea beneficia din plin de multiplicitatea resurselor, programele paralelesunt divizate in taskuri independente care intra n competiie pentru fi executate peprocesoarele sistemului. Independena a dou taskuri nseamn obinerea aceluiairezultat indiferent dac ele sunt executate secvenial n orice ordine sau n paralel [5].

Funcionarea sistemelor de calcul, fie ele secveniale sau paralele, are la bazorganizarea de fire de ateptare pentru accesul la resursele partajate ale sistemului(procesor, memorie, dispozitive periferice). Astfel, pentru fiecare resurs exist un sistemde ateptare n care resursa respectiv reprezint staia de servire iar taskurile din sistemformeaz clienii [2].

n cazul procesorului, coada de ateptare poart numele de fir de execuie. Firelede execuie fac trecerea de la programarea secvenial la programarea concurent. Un firde execuie reprezint de fapt o list n care se gsesc acele procese care sunt gata deexecuie.

Dac aceast list este meninut n memoria partajat a sistemului, accesultrebuie s se efectueze ntr-o seciune critic pentru prevenirea situaiei n care douprocesoare ar putea s aleag acelai proces pe care s-l planifice n execuie simultan.Excluderea mutual pentru accesul la resursele critice se asigur folosind mecanismestandard din sistemele uniprocesor (semafoare, bariere, mutex-uri, monitoare, etc.).Astfel, atunci cnd un procesor intr n seciunea critic, acesta are acces exclusiv la listade procese gata de execuie. n funcie de disciplina de servire i de modul de

implementare a prioritilor n sistemul de ateptare, procesorul extrage un proces dinlist dup care prsete seciunea critic i ncepe s execute procesul.

Conform definiiei date de Tanenbaum, un sistem distribuit reprezint o coleciede calculatoare independente i interconectate ntre ele care apar utilizatorului ca unsingur calculator [7]. Putem afirma c sistemele distribuite sunt alctuite din mai multecalculatoare autonome mpreun cu componentele hardware i software de interconectarecare asigur mecanismele de comunicaie i sincronizare. n categoria sistemelordistribuite sunt incluse multiprocesoarele, multicalculatoarele conectate prin reele deinterconectare statice sau dinamice precum i reelele locale de staii. Se consider cnoiunea de sistem distribuit este o noiune mai cuprinztoare care o nglobeaz i peaceea de sistem paralel.

Un sistem de distribuit este gestionat de un sistem de operare distribuit careasigur utilizarea partajat a resurselor sistemului, distribuirea proceselor de calcul icomunicaia ntre procese. Sistemele de operare distribuite reprezint extensia pentruarhitecturi cu procesoare multiple a sistemelor de operare multitasking n care se potdefini i executa concurent mai multe procese.

n funcie de tipul sistemului de operare distribuit care ruleaz pe sistemulrespectiv pot exista unul sau mai multe fire de execuie. Sistemele de operare cumultiprocesare, care opereaz asemntor cu un sistem UNIX multitasking dar pe


9/11

9

calculatoare cu procesoare multiple, sunt caracterizate prin existena unei singure cozi deexecuie pentru ntreg sistemul. Ori de cte ori un procesor devine liber, acesta extrage unproces din firul de ateptare pentru a-l executa. Urmtorul proces care va fi executat sestabilete n funcie de disciplina firului de ateptare i de prioritile implementate ncadrul sistemului. Datorit faptului c timpul de execuie al programului paralel este finit,

putem considera c numrul proceselor n care poate fi divizat algoritmul reprezint deasemenea o mrime finit. Din acest motiv, unui astfel de sistem de calcul i putem asociaun model de ateptare n care staia de servire este compus din m posturi care lucreaz nparalel, unde m reprezint numrul de procesoare din sistem, iar sosirile au loc dintr-opopulaie finit (vezi modelul matematic al unui sistem de ateptare cu posturi de serviremultiple i cu sosiri dintr-o populaie finit).

La polul opus se afl sistemele de operare n reea i sistemele de operare realdistribuite n cazul crora exist cte o copie a sistemului de operare n fiecare element deprocesare. Aceste sisteme de operare sunt caracterizate prin existena uni numr de fire deexecuie egal cu numrul de procesoare din sistem, fiecare procesor avnd asociatpropriul fir de execuie. La nivelul fiecrui element de procesare exist un sistem de

operare care administreaz firul de execuie asociat procesorului respectiv. Datoritfaptului c timpul de execuie al programului paralel se presupune a fi finit, putemconsidera c numrul proceselor ce vor fi executate la nivelul ntregului sistem este tot unnumr finit. Din acest motiv putem asocia fiecrui nod un model de ateptare n carestaia de servire este format dintr-un singur post iar sosirile se realizeaz dintr-opopulaie finit (vezi modelul matematic al unui sistem de ateptare cu un singur post deservire i cu sosiri dintr-o populaie finit). Sistemele de ateptare din nodurile deprocesare formeaz, la nivelul ntregului sistem paralel, o reea de ateptare deoareceprocesoarele comunic i se sincronizeaz ntre ele iar execuia unui proces poate ficondiionat de rezultatele generate de execuia altor procese pe alte procesoare.

Sistemele de ateptare despre care s-a discutat anterior se pot transforma nsisteme ale cror intrri au loc dintr-o populaie infinit n cazul n care timpii de execuieai programelor paralele devin foarte mari iar numrul proceselor ce sunt executate ncadrul sistemului crete simitor (vezi modelul matematic al unui sistem de ateptare cuun singur post de servire i cu sosiri dintr-o populaie infinit, modelul matematic al unuisistem de ateptare cu posturi de servire multiple i cu sosiri dintr-o populaie infinit).

n ceea ce privete execuia unui program paralel pe procesoarele disponibile ncadrul unui sistem multiprocesor, sistemul de ateptare asociat depinde de legea deprobabilitate care descrie procesul de servire i de modul de partiionare a sarcinii totalede calcul. n cazul unui program de tip data-paralel, aceeai succesiune de instruciuni seva executa asupra unor seturi de date distincte iar rezultatul final se va obine princombinarea rezultatelor intermediare. n aceast situaie putem considera c durataserviciului este o variabil aleatoare repartizat exponenial negativ iar pentru evaluareaperformanelor sistemului de ateptare i a algoritmului de planificare ct i pentrumbuntirea acestora se poate folosi un model de tip M/M/m. Dac ns partiionarea serealizeaz n spaiul instruciunilor, legea de probabilitate ce guverneaz timpii deexecuie ai proceselor poate fi una exponenial negativ sau generic iar modelul asociatsistemului va fi unul de tip M/M/m sau M/G/m. Se poate ajunge la un model de tipM/G/m, care este foarte dificil de analizat, atunci cnd un proces poate beneficia de ocuant nelimitat de timp pentru a-i completa execuia.


10/11

10

Din dorina de a partaja echitabil resursele sistemului este posibil s se impunanumite limite n ceea ce privete caracteristicile proceselor din firul de execuie [6].Astfel, dac se stabilete un prag maxim al timpului procesor de care poate beneficia unproces, toate procesele al cror timp de execuie estimat depete valoarea prag vor fieliminate din sistem i nu vor ajunge n firul de execuie. De asemenea, procesele al cror

timp de execuie devine mai mare dect limita maxim impus vor fi ntrerupte ieliminate din sistem. n acest fel se garanteaz faptul c un proces nu va monopoliza deunul singur resursele sistemului.

ConcluziiTeoria ateptrii se constituie ntr-un instrument foarte util pentru previzionarea

performanelor sistemelor de calcul n general i a celor paralele n particular. Astfel,mrimile medii de interes (numrul mediu de consumatori din coad i din sistem, timpulmediu de ateptare n fir i n sistem) ne pot oferi o imagine clar asupra performanelorde ansamblu ale sistemului i a direciilor de mbuntire a acestora. Asociind un model

de ateptare unui sistem de calcul putem scoate n eviden disfuncionalitile existenteiar teoria ateptrii ne va ajuta s eficientizm funcionarea acestuia prin indicareavalorilor pe care trebuie s le ating anumii parametri ai sistemului pentru a se ajunge laun nivel satisfctor al performanelor. Sistemul de ateptare format din procesele aflaten firul de execuie ateptnd s fie rulate de ctre procesor/procesoare este gestionat dectre un program special numit planificator care face alocarea task-urilor pe procesoareledisponibile. Planificatorul implementeaz de fapt disciplina de servire la nivelulsistemului de ateptare i gestioneaz clasele de prioriti asociate proceselor. Felul ncare se face servirea clienilor afecteaz performanele sistemului n ansamblu. Din acestmotiv se dorete ca algoritmul de planificare folosit s conduc la o cretere a eficieneisistemului. Atunci cnd se dezvolt o nou versiune a acestui program, n prim faz

performanele acestora sunt estimate folosind suportul oferit de teoria ateptrii deoareceutilizarea unei versiuni instabile i netestate ar fi deranjant pentru utilizatorii sistemuluiparalel.

Teoria ateptrii ne arat c timpul petrecut de un consumator n sistem esteformat din timpul petrecut n coada de ateptare i din cel necesar servirii. n cazul n careconsumatorul din sistemul de ateptare reprezint un proces care este planificat pentruexecuie, timpul petrecut n staia de servire este de fapt timpul acestuia de execuie.Pentru ca timpul petrecut de un proces n sistem s fie ct mai mic nu este suficient s sereduc doar timpul de execuie prin folosirea unor procesoare ct mai rapide ci estenevoie i de reducerea timpului de ateptare n fir prin folosirea unor algoritmi deplanificare eficieni.


11/11

11

Bibliografie

1. S. Asmussen, Applied Probability and Queues, Springer, 20032. Gh. Dodescu, B. Oancea, M. Raceanu, Procesare Paralel, Editura Economic,

Bucureti, 2002

3. Gh. Dodescu, Sisteme de calcul i operare, Editura ASE, Bucureti, 19974. D. Gross, C. M. Harris, Fundamentals of Queuing Theory, Wiley, New York, 20035. G. W. Sabot, High Performance Computing, Addison-Wesley, 19956. A. S. Tanenbaum, Organizarea Structurat a Calculatoarelor, Computer Press Agora,

19997. A. S. Tanenbaum, Distributed Operating Systems, Prentice Hall, 1995

Sisteme de Asteptare

Documents

Transcript of Sisteme de Asteptare