Anexa 3

Procese stocasticeLucrare de laboratorCercetarea sistemelor cu fire de ateptare prin metoda simulriimanuale

Scopul lucrrii : familiarizarea cu algoritmul de simulare a sistemelor cu fire de ateptare, cu prelucrarea datelor obinute n urma similarii i cu calculul indicilor de performan observai.Funcionarea sistemelor de calcul (calculatoare, servere, reele, etc,) poate fi deseori formalizata sub forma de sisteme cu fire de ateptare (cu unul sau mai multe servere, conectate uneori n reea) n care sosesc cererile (clienii) pentru a fi prelucrate (servite). Cele din urma pot fi studiate att prin metode analitice (dar numai n unele cazuri simple), ct i prin metode de simulare care sunt alternative sau complementare metodelor analitice. Simularea acestor fenomene necesit cunoaterea modului de funcionare a sistemelor, modul n care clienii ajung i sunt servii. Informaia despre sosiri i serviri este foarte important i este necesar de a fi recoltate pe teren observnd sistemele reale sau lansnd anumite ipoteze cu privire la valorile reale ale parametrilor fluxurilor de clieni.Fluxurile de sosiri i de serviri pot fi descrise n dou moduri: folosind tabele: pentru fiecare client este indicat momentul n care aceasta ar trebui s intre n sistem i durata sa de serviciu. Acesta metoda necesita stocarea multor date ceea ce provoac un consum important de memorie; definind distribuiile statistice ale intervalelor de timp dintre sosirile succesive ale clienilor i ale duratelor lor de servire (ele sunt generate n msura necesitaii pe parcursul procesului de simulare ceea ce produce un consum mic de resurse de calcul i de memorie).

Achizitie de date

3Distribuia intervalelor dintre sosirile succesive ale clienilor

Distribuia intervalelor de servire a clienilor

Sourca de clienti

Coad de ateptare

Server

Plecri ale clienilor

Clieni:durata de sejur...

lungimea medie, durata de ateptare...Evalurea sistemului

gradul de utilizare

Fig.1. Consideraii generale

Cazul cela mai simplu e sa definim sosirile i serviciile cu ajutorul unui tabel :

No. clientuluiPerioada dintre sosirile succesivePerioada de serviciu

1109

21517

31416

4913

51314

6913

71116

8814

9910

101013

111114

121317

131710

14107

151510

Duratele sunt exprimate n uniti convenionale de timp (de fapt, e vorba de secunde, ore, minute, milisecunde, etc, dar nu conteaz pentru simulare, pentru c se lucreaz cu uniti convenionale de timp).

Pentru a simula acest sistem vom defini: doua tipuri de evenimente sosirile ele provoac creterea numrului de clieni n n sistem, modifica variabilele de stare ale serverului i/sau parametrii firului de ateptare; plecrile ele reduc numrul de clieni n n sistem, schimba starea serverului, fapt care cauzeaz unele schimbri n coada de clieni din fata lor. o regula de oprire pentru a termina corect simularea (cu crearea unui raport statistic coninnd rezultatele i performanele observate) este dat o stare de oprire. Dou cazuri posibile: oprire dup scurgerea a unei durate de simulare date; oprire dup servirea unui anumit numr de clieni.n acest exemplu vom utiliza prima metod de oprire a simulrii dup consumarea a 150 de uniti de timp.

Pentru o prelucrare corect a evenimentelor mai e nevoie de un ceas de sistem i de o lista cu calendarul evenimentelor: evenimentul cel mai apropiat trebuie s fie ntotdeauna n capul listei. Gestionarul de evenimente (nucleul programului de simulare) e responsabil de ntreinerea acestei liste i de tratarea evenimentelor n ordine cronologic . Rolul sau se reduce la doua operaii: includerea n list a ultimului (celui mai recent) eveniment creat i extragerea evenimentului cu timpul minimal pentru a fi prelucrat.n exerciiul urmtor vom ncerca sa realizam manual procedura de simulare a unui sistem cu fire de ateptare cu un singur server. Pentru a facilita aceasta activitate vom organiza calculele ntr-un tabel :Tabel de simulare

Numrul evenimen- tuluiCeasul sistemNumrul clientuluiTipul evenimen- tuluis sosirep plecareLungimea cozii de ateptareStarea serverului 0 liber1- ocupatCalendarul evenimentelor (Timpul, Num. clientului, Tipul evenimentului)

00-START00(10,1,s), (150,-,Stop)

1101s01(19,1,p), (25,2,s), (150,-,Stop)

2191p00(25,2,s) , (150,-,Stop)

3252s01(42,2,p), (39,3,s), (150,-,Stop)

4393s11(42,2,p), (48,4,s), (150,-,Stop)

5422p01(58,3,p), (48,4,s), (150,-,Stop)

6484s11(58,3,p), (61,5,s), (150,-,Stop)

7583p01(61,5,s), (71,4,p), (150,-,Stop)

8615s11(71,4,p), (70,6,s), (150,-,Stop)

9706s21(71,4,p), (81,7,s), (150,-,Stop)

10714p11(81,7,s), (85,5,p), (150,-,Stop)

11817s21(85,5,p), (89,8,s), (150,-,Stop)

12855p11(89,8,s), (98,6,p), (150,-,Stop)

13898s21(98,6,p), (98,9,s), (150,-,Stop)

14986p11(98,9,s), (114,7,p), (150,-,Stop)

15989s21(114,7,p), (108,10,s), (150,-,Stop)

1610810s31(114,7,p), (119,11,s), (150,-,Stop)

171147p21(119,11,s), (128,8,p), (150,-,Stop)

1811911s31(128,8,p), (132,12,s), (150,-,Stop)

191288p21(132,12,s), (138,9,p), (150,-,Stop)

2013212s31(138,9,p), (149,13,s), (150,-,Stop)

211389p21(149,13,s), (151,10,p), (150,-,Stop)

2214913s31(151,10,p), (159,14,s), (150,-,Stop)

23150-STOP31(151,10,p), (159,14,s)

Evaluarea indicilor de performantaScopul simulrii e de a evalua performanele sistemului innd cont de parametrii de intrare (fluxul de clieni i de serviri, numrul de servere, ordinea servirilor, etc.), deci e necesar sa definim i sa calculam indicii de performana ai sistemului care ne intereseaz.

Serverul

Bazndu-ne pe tabelul de simulare de mai sus ne propunem sa reprezentam pe un grafic starea serverului n funcie de timp pe parcursul simulrii.B(t)

1

t0102030405060708090100110120130140150Fig.2. Dinamica utilizrii serverului pe parcursul simulrii

Durata integrala de ocupare a serverului corespunde ariei dintre axa OX si B(t):Tsim

Tocupat= o

B( t ) dt

unde Tsim e durata de simulare, B(t) e starea serverului n momentul t.

Gradul de utilizare (ncrctura) se va calcula ca raportul dintre durata integrala de ocupare a serverului i durata de simulare (cu alte cuvinte, indicele ceasului n momentul opririi simulrii):T sim

K= Tocupat =T sim

o

B ( t ) dt T sim

Pentru cazul nostru:

K= T ocupat =T sim

134150

= 0,89

Putem conclude ca serverul a fost destul de ncrcat pe parcursul acestei simulri.

Coada de ateptareVarierea lungimii cozii de ateptare pe parcursul simulrii e prezentata mai jos :Q(t) 3

2

1

t0102030405060708090100110120130140150Fig.3. Dinamica cozii de ateptare pe parcursul simulriiParametrii de care ne vom interesa sunt: lungimea media a cozii de ateptare Lq, durata medie de ateptare pentru clienii care s-au reinut in coada de ateptare Tq, lungimea maximala a cozii de ateptare, etc. Pentru a calcula aceti parametri vom avea nevoie de durata totala de reateptate pentru toi clienii (durata integrala T).

Lungimea medie a firului de ateptare:

TsimTQ(t)dto

Lq TTsim

TsimQ(t)dtoTsim

Retinerea medie a unui client n coada de ateptare:TsimQ (t)dt ,Tq ToNqNqunde Nq e numrul de clieni care au petrecut n coada de ateptare o durata completa i au fost servii ulterior de ctre server.Parametrul T poate fi calculat tinad cont el corespunde suprafeei dintre Q(t) i axa OX. inndcont de datele obinute pe parcursul simulrii :T = 1*(42-39) + 1*(58-48) + 1*(70-61) + 2*(71-70) + 1*(81-71) + 2*(85-81) + 1*(89-85)+ 2*(108-89) + 3*(114-108) + 2*(119-114) + 3*(128-119) + 2*(132-128) + 3*(138-132) + 2*(149-138) + 3*(150-149) = 190Nq = 8(doar clienii 3,4,5,6,7,8,9 si 10 au petrecut in coada de ateptare o durata completa)

qT T Nq

190 23.758

TLq Tsim

1901.27 150

Lungimea maximala a cozii de ateptare Lqmax= 3

Tabel de simulare cu acumulatori statisticiCu scopul de a simplifica calculele si de a optimiza calcularea i colectarea datelor utilizate pentru calcularea indicilor de performa va propunem un tabel care conine cteva variabile complementare (acumulatori statistici) calculate pe parcursul simulrii.

Num evenCeas sistemNum. clientTip evenim. ssosiri pplec.Lungimea curenta a cozii de ateptareStarea serverului 0 liber1- ocupatDurata integrala de util, a serveruluiDurata integrala de ateptare n coadaNumrul clienilor reinuti in coadaCalendarul evenimentelor (Timpul, Num. clientului, Tipul evenimentului)

itijQ(t)B(t)TocupatTNq

00-START00000(10,1,s), (150,-,Stop)

1101s01000(19,1,p), (25,2,s), (150,-,Stop)

2191d00900(25,2,s) , (150,-,Stop)

3252s01900(42,2,p), (39,3,s), (150,-,Stop)

4393s112300(42,2,p), (48,4,s), (150,-,Stop)

5422d012631(58,3,p), (48,4,s), (150,-,Stop)

6484s113231(58,3,p), (61,5,s), (150,-,Stop)

7583d0142132(61,5,s), (71,4,p), (150,-,Stop)

8615s1145132(71,4,p), (70,6,s), (150,-,Stop)

9706s2154222(71,4,p), (81,7,s), (150,-,Stop)

10714d1155243(81,7,s), (85,5,p), (150,-,Stop)

11817s2165343(85,5,p), (89,8,s), (150,-,Stop)

12855d1169424(89,8,s), (98,6,p), (150,-,Stop)

13898s2173464(98,6,p), (98,9,s), (150,-,Stop)

14986d1182645(98,9,s), (114,7,p), (150,-,Stop)

15989s2182645(114,7,p), (108,10,s), (150,-,Stop)

1610810s3192845(114,7,p), (119,11,s), (150,-,Stop)

171147d21981026(119,11,s), (128,8,p), (150,-,Stop)

1811911s311031126(128,8,p), (132,12,s), (150,-,Stop)

191288d211121397(132,12,s), (138,9,p), (150,-,Stop)

2013212s311161477(138,9,p), (149,13,s), (150,-,Stop)

211389d211221658(149,13,s), (151,10,p), (150,-,Stop)

2214913s311331878(151,10,p), (159,14,s), (150,-,Stop)

23150-STOP311341908151,10,p), (159,14,s)

Rezultatele simulrii:valorile finale ale acumulatorilor statistici

Mersul lucrrii :

Studiai algoritmul simulrii manuale; Datele iniiale pentru simulare sunt n anexa, recalculai valorile din tabel n funcie de numrul Dumneavoastr din lista din registrul grupei; Efectuai simularea manuala a sistemului cu ateptare cu un singur server utilizndu tabelul cu acumulatori statistici. Regula pentru a opri simularea: servirea a primilor 25 de clieni (cu alte cuvinte, simularea se va opri n momentul plecrii din sistem a clientului cu num. 25) Desenai graficele varierii strii serverului i a cozii de ateptare pe parcursul simulrii. Ct a durat servirea a 25 clieni? Calculai indicii de performana observai n urma simulrii.

Bonus: Refacei simularea pentru cazul cnd avei doua servere n paralel (sau un server cu doua canale) cu o coada comuna de ateptare n fata lor. Clientul e servit de oricare dintre cele doua servere, dac ambele servere sunt ocupate el va atepta n coda de ateptare. (Indicaie: n acest caz serverul va avea trei stri: 0 - doua canale libere, 1 - un canal ocupat iar altul liber, 2 - ambele canale ocupate) Ct a durat servirea a 25 clieni n acest caz? Calculai indicii de performana observai n urma simulrii sistemului cu doua servere paralele. Comparai rezultatele celor doua simulri i prezentai concluziile.

Prezentarea lucrrii:

Lucrarea se prezint sub forma de referat cu urmtorul coninut: Titlul lucrrii, numele studentului i a profesorului; Scopul lucrrii; Tabelul cu datele iniiale pentru simulare; Rezultatele lucrrii; Concluzii.

Date pentru lucrarea de laborator

No. clieP de serviciuntuluiPerioada dintre sosirile succesivePerioada de serviciu

121+k11+k

266+k151+k

3169+k20+k

430+k71+k

5163+k27+k

634+k49+k

767+k141+k

810+k133+k

92+k59+k

1017+k5+k

11140+k43+k

12122+k64+k

1376+k148+k

148+k114+k

1524+k129+k

1638+k86+k

1760+k46+k

1833+k42+k

1920+k70+k

20313+k169+k

2166+k200+k

2275+k170+k

23284+k10+k

2448+k120+k

2529+k78+k

2631+k58+k

2743+k53+k

28116+k85+k

2922+k72+k

3067+k11+k

31170+k113+k

unde k este numrul studentului n lista grupei din care face parte.

Anexa 1

Tabel de simulare

Numrul evenimen- tuluiCeasul sistemNumrul clientuluiTipul evenimen- tuluis sosirep plecareLungimea cozii de ateptareStarea serverului 0 liber1- ocupatCalendarul evenimentelor (Timpul, Num. clientului, Tipul evenimentului)

Anexa 2

Tabel de simulare cu acumulatori statistici

Num evenCeas sistemNum. clientTip evenim. ssosiri pplec.Lungimea curenta a cozii de ateptareStarea serverului 0 liber1- ocupatDurata integrala de util, a serveruluiDurata integrala de ateptare n coadaNumrul clienilor reinuti in coadaCalendarul evenimentelor (Timpul, Num. clientului, Tipul evenimentului)

itijQ(t)B(t)TocupatTNq

11