PS Laborator rom FR (PDF)

Procese stocastice
Lucrare de laborator

Cercetarea sistemelor cu fire de așteptare prin metoda simulării
manuale
Scopul lucrării : familiarizarea cu algoritmul de simulare a sistemelor cu fire de așteptare, cu
prelucrarea datelor obținute în urma similarii și cu calculul indicilor de performanță observați.
Funcționarea sistemelor de calcul (calculatoare, servere, rețele, etc,) poate fi deseori formalizata
sub forma de sisteme cu fire de așteptare (cu unul sau mai multe servere, conectate uneori în rețea)
în care sosesc cererile (clienții) pentru a fi prelucrate (servite). Cele din urma pot fi studiate atât
prin metode analitice (dar numai în unele cazuri simple), cât și prin metode de simulare care sunt
alternative sau complementare metodelor analitice. Simularea acestor fenomene necesită
cunoașterea modului de funcționare a sistemelor, modul în care clienții ajung și sunt serviți.
Informația despre sosiri și serviri este foarte importantă și este necesar de a fi recoltate pe teren
observând sistemele reale sau lansând anumite ipoteze cu privire la valorile reale ale parametrilor
fluxurilor de clienți.
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 distribuțiile statistice ale intervalelor de timp dintre sosirile succesive ale clienților
și ale duratelor lor de servire (ele sunt generate în măsura necesita ții pe parcursul
procesului de simulare ceea ce produce un consum mic de resurse de calcul și de
memorie).
Achizitie de date
Distribuția intervalelor de
servire a clienților

Distribuția intervalelor dintre
sosirile succesive ale clienților

Sourca de
clienti

Clienți:
durata de sejur...

Coadă de
așteptare

Server

lungimea medie,
durata de așteptare...
Evalurea sistemului

Fig.1. Considerații generale

1

Plecări ale
clienților

gradul de utilizare

Cazul cela mai simplu e sa definim sosirile și serviciile cu ajutorul unui tabel :
No.
clientului
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Perioada dintre
sosirile succesive
10
15
14
9
13
9
11
8
9
10
11
13
17
10
15

Perioada de serviciu
9
17
16
13
14
13
16
14
10
13
14
17
10
7
10

Duratele sunt exprimate în unități convenționale de timp (de fapt, e vorba de secunde, ore, minute,
milisecunde, etc, dar nu contează pentru simulare, pentru că se lucrează cu unități convenționale
de timp).
Pentru a simula acest sistem vom defini:
 doua tipuri de evenimente
 sosirile – ele provoacă creșterea numărului de clienți n în sistem, modifica variabilele de
stare ale serverului și/sau parametrii firului de așteptare;
 plecările – ele reduc numărul de clienți n în sistem, schimba starea serverului, fapt care
cauzează unele schimbări în coada de clienți din fata lor.
 o regula de oprire – pentru a termina corect simularea (cu crearea unui raport statistic
conținând rezultatele și performanțele observate) este dată o stare de oprire. Două cazuri
posibile:



oprire după scurgerea a unei durate de simulare date;
oprire după servirea unui anumit număr de clienți.

În acest exemplu vom utiliza prima metodă de oprire a simulării după consumarea a 150 de unită ți
de timp.

2

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 întreținerea acestei
liste și de tratarea evenimentelor în ordine cronologică . Rolul sau se reduce la doua opera ții:
includerea în listă a ultimului (celui mai recent) eveniment creat și extragerea evenimentului cu
timpul minimal pentru a fi prelucrat.
În exercițiul următor vom încerca sa realizam manual procedura de simulare a unui sistem cu fire
de așteptare cu un singur server. Pentru a facilita aceasta activitate vom organiza calculele într-un
tabel :
Tabel de simulare
Tipul
Starea
evenimen- Lungimea
Numărul
serverului
tului
cozii de
clientului
0 – liber
s –sosire
așteptare
1- ocupat
p – plecare
START
0
0

Numărul
evenimentului

Ceasul
sistem

0

0

1

10

1

s

0

1

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

2

19

1

p

0

0

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

3

25

2

s

0

1

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

4

39

3

s

1

1

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

5

42

2

p

0

1

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

6

48

4

s

1

1

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

7

58

3

p

0

1

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

8

61

5

s

1

1

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

9

70

6

s

2

1

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

10

71

4

p

1

1

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

11

81

7

s

2

1

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

12

85

5

p

1

1

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

13

89

8

s

2

1

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

14

98

6

p

1

1

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

15

98

9

s

2

1

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

16

108

10

s

3

1

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

17

114

7

p

2

1

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

18

119

11

s

3

1

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

19

128

8

p

2

1

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

20

132

12

s

3

1

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

21

138

9

p

2

1

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

22

149

13

s

3

1

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

23

150

-

STOP

3

1

(151,10,p), (159,14,s)

3

Calendarul evenimentelor
(Timpul, Num. clientului, Tipul
evenimentului)
(10,1,s), (150,-,Stop)

Evaluarea indicilor de performanta
Scopul simulării e de a evalua performanțele sistemului ținând cont de parametrii de intrare (fluxul
de clienți și de serviri, numărul de servere, ordinea servirilor, etc.), deci e necesar sa definim și sa
calculam indicii de performanța ai sistemului care ne interesează.

Serverul
Bazându-ne pe tabelul de simulare de mai sus ne propunem sa reprezentam pe un grafic starea
serverului în funcție de timp pe parcursul simulării.
B(t)
1

t
0
10

20

30

40

50

60

70

80

90

100

110

120

130

140

150

Fig.2. Dinamica utilizării serverului pe parcursul simulării
Durata integrala de ocupare a serverului corespunde ariei dintre axa OX si B(t):

unde Tsim – e durata de simulare, B(t) – e starea serverului în momentul t.
Gradul de utilizare (încărcătura) se va calcula ca raportul dintre durata integrala de ocupare a
serverului și durata de simulare (cu alte cuvinte, indicele ceasului în momentul opririi simulării):

Pentru cazul nostru:

Putem conclude ca serverul a fost destul de încărcat pe parcursul acestei simulări.

4

Coada de așteptare
Varierea lungimii cozii de așteptare pe parcursul simulării e prezentata mai jos :
Q(t)
3

2

1
t
0

10

20

30

40

50

60

70

80

90

100

110

120

130

140

150

Fig.3. Dinamica cozii de așteptare pe parcursul simulării
Parametrii de care ne vom interesa sunt: lungimea media a cozii de așteptare Lq, durata medie de
așteptare pentru clienții care s-au reținut in coada de așteptare Tq, lungimea maximala a cozii de
așteptare, etc. Pentru a calcula acești parametri vom avea nevoie de durata totala de reașteptate
pentru toți clienții (durata integrala TΣ).
Tsim

T  Q(t)dt
o

Lungimea medie a firului de așteptare:
Tsim

Q(t)dt

Lq  T  o
Tsim
Tsim
Retinerea medie a unui client în coada de așteptare:
Tsim

Q(t)dt ,

Tq  T 
Nq

o

Nq

unde Nq e numărul de clienți care au petrecut în coada de așteptare o durata completa
și au fost serviți ulterior de către server.
Parametrul TΣ poate fi calculat tinad cont el corespunde suprafeței dintre Q(t) și axa OX. Ținând
cont de datele obținute pe parcursul simulării :
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*(149138) + 3*(150-149) = 190
Nq = 8

(doar clienții 3,4,5,6,7,8,9 si 10 au petrecut in coada de așteptare o durata completa)

T
190
Tq   
 23.75
Nq
8

Lq 

T 190

 1.27
Tsim 150

Lungimea maximala a cozii de așteptare Lqmax= 3
5

Tabel de simulare cu acumulatori statistici
Cu scopul de a simplifica calculele si de a optimiza calcularea și colectarea datelor utilizate pentru
calcularea indicilor de performață va propunem un tabel care conține câteva variabile
complementare (acumulatori statistici) calculate pe parcursul simulării.
Tip
evenim.
s–sosiri
p–plec.

Durata
Lungimea
Starea
Durata
Numărul
integrala
curenta a serverului integrala
clienților
de
cozii de 0 – liber
de util, a
reținuti in
aşteptare
așteptare 1- ocupat serverului
coada
în coada
Q(t)
B(t)
Tocupat
TΣ
Nq

Num
even

Ceas
sistem

Num.
client

i

ti

j

0

0

-

START

0

0

0

0

0

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

1

10

1

s

0

1

0

0

0

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

2

19

1

d

0

0

9

0

0

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

3

25

2

s

0

1

9

0

0

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

4

39

3

s

1

1

23

0

0

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

5

42

2

d

0

1

26

3

1

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

6

48

4

s

1

1

32

3

1

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

7

58

3

d

0

1

42

13

2

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

8

61

5

s

1

1

45

13

2

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

9

70

6

s

2

1

54

22

2

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

10

71

4

d

1

1

55

24

3

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

11

81

7

s

2

1

65

34

3

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

12

85

5

d

1

1

69

42

4

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

13

89

8

s

2

1

73

46

4

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

14

98

6

d

1

1

82

64

5

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

15

98

9

s

2

1

82

64

5

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

16

108

10

s

3

1

92

84

5

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

17

114

7

d

2

1

98

102

6

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

18

119

11

s

3

1

103

112

6

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

19

128

8

d

2

1

112

139

7

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

20

132

12

s

3

1

116

147

7

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

21

138

9

d

2

1

122

165

8

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

22

149

13

s

3

1

133

187

8

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

23

150

-

STOP

3

1

134

190

8

151,10,p), (159,14,s)

Calendarul evenimentelor
(Timpul, Num. clientului, Tipul
evenimentului)

Rezultatele simulării:
valorile finale ale acumulatorilor
statistici

6

Mersul lucrării :
 Studiați algoritmul simulării manuale;
 Datele inițiale pentru simulare sunt în anexa, recalculați valorile din tabel în funcție de
numărul Dumneavoastră din lista din registrul grupei;
 Efectuați simularea manuala a sistemului cu așteptare cu un singur server utilizându tabelul
cu acumulatori statistici. Regula pentru a opri simularea: servirea a primilor 25 de clienți
(cu alte cuvinte, simularea se va opri în momentul plecării din sistem a clientului cu
num. 25)
 Desenați graficele varierii stării serverului și a cozii de așteptare pe parcursul simulării.
 Cât a durat servirea a 25 clienți?
 Calculați indicii de performanța observați în urma simulării.
 Refaceți simularea pentru cazul când aveți doua servere în paralel (sau un server cu doua
canale) cu o coada comuna de așteptare în fata lor. Clientul e servit de oricare dintre cele
doua servere, dacă ambele servere sunt ocupate el va aștepta în coda de așteptare.
(Indicație: în acest caz serverul va avea trei stări: 0 - doua canale libere, 1 - un canal
ocupat iar altul liber, 2 - ambele canale ocupate)
 Cât a durat servirea a 25 clienți în acest caz?
 Calculați indicii de performanța observați în urma simulării sistemului cu doua servere
paralele.
 Comparați rezultatele celor doua simulări și prezentați concluziile.
Prezentarea lucrării:
Lucrarea se prezintă sub forma de referat cu următorul conținut:






Titlul lucrării, numele studentului și a profesorului;
Scopul lucrării;
Tabelul cu datele inițiale pentru simulare;
Rezultatele lucrării;
Concluzii.

7

Anexa 1
Date pentru lucrarea de laborator

No. clientului

Perioada dintre
sosirile
succesive

Perioada de
serviciu

1

21+k

11+k

2

66+k

151+k

3

169+k

20+k

4

30+k

71+k

5

163+k

27+k

6

34+k

49+k

7

67+k

141+k

8

10+k

133+k

9

2+k

59+k

10

17+k

5+k

11

140+k

43+k

12

122+k

64+k

13

76+k

148+k

14

8+k

114+k

15

24+k

129+k

16

38+k

86+k

17

60+k

46+k

18

33+k

42+k

19

20+k

70+k

20

313+k

169+k

21

66+k

200+k

22

75+k

170+k

23

284+k

10+k

24

48+k

120+k

25

29+k

78+k

26

31+k

58+k

27

43+k

53+k

28

116+k

85+k

29

22+k

72+k

30

67+k

11+k

31

170+k

113+k

unde k este numărul studentului în lista grupei din care face parte.
8

Anexa 2

Tabel de simulare cu acumulatori statistici
Num
even

Ceas
sistem

Num.
client

i

ti

j

Tip
evenim.
s–sosiri
p–plec.

Durata
Lungimea
Starea
Durata
Numărul
integrala
curenta a serverului integrala
clienților
de
cozii de 0 – liber
de util, a
reținuti in
aşteptare
așteptare 1- ocupat serverului
coada
în coada
Q(t)
B(t)
Tocupat
TΣ
Nq

9

Calendarul evenimentelor
(Timpul, Num. clientului, Tipul
evenimentului)