Seria: Informatyka
Metody niezawodności i
eksploatacji
Wykład 7
Modele kolejkowe systemów
rozproszonych

dr hab. inż. Tadeusz Nowicki prof.

nadzw. WAT

e-mail:[e-mail], tel. 6-

837118

Podstawy teorii systemów

kolejkowych

W teorii systemów kolejkowych dla pojedynczego systemu
masowej obsługi (SMO) (systemu kolejkowego) rozróżniamy
następujące elementy:

• proces napływu zadań,
• rozkład czasu obsługi zadania,
• liczbę procesorów (kanałów obsługi),
• pojemność systemu (maksymalna liczba zadań w
systemie),

• wielkość populacji zadań,
• dyscyplinę obsługi zadania w SMO.

Procesor 2

Proces

napływu

zadań

Procesor 1

Procesor k

Bufor (kolejka)

Straty

Obsługa zadań

Podstawy teorii systemów

kolejkowych

Notacja Kendall’a : A/S/m/B/K/SD
gdzie
A - rozkład czasu między napływającymi zadaniami,
S - rozkład czasu obsługi zadania,
m - liczba kanałów obsługi (procesorów),
B - maksymalna liczba zadań w systemie,
K - wielkość populacji zadań,
SD - dyscyplina obsługi zadań.

Przykłady rozkładów czasu między napływającymi
zadaniami oraz rozkładów czasu obsługi zadania:
M - wykładniczy,
E

k

- Erlanga rzędu k,

H

k

- hiper wykładniczy rzędu k,

D - deterministyczny (stały czas),
G - dowolny rozkład, itd..

Podstawy teorii systemów

kolejkowych

Oznaczenia:

 - średnia intensywność napływu zadań (liczba na

jednostkę czasu),

s - czas obsługi zadania,

 - średnia intensywność obsługi zadań (liczba na jednostkę

czasu),

n - liczba zadań w systemie,

n

q

- liczba zadań w kolejce,

n

s

- liczba zadań obsługiwanych,

r - czas odpowiedzi systemu (czas przebywania zadania w
systemie),

w - czas czekania na obsługę.

 = 1/E[] gdzie  - czas pomiędzy napływem kolejnych

zadań do systemu

 = 

i

= t

i

-t

i-1

, t

i

- zmienna losowa, chwila napływu i-tego

zadania; t

i-1

= 0

natomiast  = 1/E[s].

Podstawy teorii systemów

kolejkowych

Jeśli  ma rozkład wykładniczy, to strumień nazywamy

strumieniem

Poissona.

Wszystkie

zmienne

podane

wcześniej poza  i  są zmiennymi losowymi.
Pewne istotne relacje pomiędzy podanymi zmiennymi:

• warunki stabilności - osiągane są gdy spełniony jest
warunek:

  m (średnia intensywność napływu zadań jest

mniejsza od

średniej intensywności obsługi zadań),

• liczba zadań w systemie a liczba zadań w kolejce:

n = n

q

+ n

s

(liczba zadań w systemie jest zawsze

równa sumie liczby

zadań w kolejce i liczby zadań w obsłudze) zatem

E[n] = E[n

q

]+E[n

s

]

• prawo Little’a

E[n] =  E[r] oraz E[n

q

] =   E[w]

• czas odpowiedzi (przebywania zadania w systemie) a czas
oczekiwania

r = w + s zatem E[r] = E[w] + E[s]

Podstawy teorii systemów

kolejkowych

Cechy procesów Poissona:

• suma k procesów Poissona o średnich intensywnościach


i

jest procesem Poissona o intensywności







k

i

i

1





• rozdzielanie procesu Poissona według rozkładu
prawdopodobieństwa

p=(p

1

, p

2

,..., p

k

)

daje to strumienie Poissona o intensywnościach

odpowiednio

równych 

i

= p

i

, i=1,...,k



1



2



k





p

1

p

2

p

k

p

1

p

2

p

k

Podstawy teorii systemów

kolejkowych

• strumień wyjściowy ze SMO

jeśli średnia intensywność strumienia napływu

zadań jest mniejsza

od średniej intensywności obsługi zadań (  ), to

strumień

wyjściowy ze SMO jest strumieniem Poissona o

intensywności ,

proces

or







  

• zasada ta jest znacznie ogólniejsza





2



  

i



1



m

kolejka

kolejka

System kolejkowy M/M/1

1. Parametry:

•  – intensywność napływu zadań do systemu,
•  – intensywność obsługi zadań,
2. Intensywność ruchu: =/
3. Warunek stabilności: 1
4. Prawdopodobieństwo zera zadań w systemie: p

o

= 1- 

5. Prawdopodobieństwo n zadań w systemie: p

n

= (1- ) 

n

,

n=0,1,...,
6. Średnia liczba zadań w systemie: E[n]= /(1- )
7. Wariancja liczby zadań w systemie: Var[n]=/(1- )

2

8. Prawdopodobieństwo n zadań w kolejce:



























0

k

,

)

1

(

0

k

,

1

)

k

n

(

P

1

k

2

q

System kolejkowy M/M/1

9. Średnia liczba zadań w kolejce: E[n

q

]= 

2

/(1- )

10. Wariancja liczby zadań w kolejce:

Var[n

q

]= 

2

(1+- 

2

)/(1- )

2

11. Dystrybuanta łącznego czasu odpowiedzi: F(r)= 1-e

-r(1-)

12. Średni czas odpowiedzi: E[r]=(1/)/(1-)
13. Wariancja czasu odpowiedzi: Var[r]= (1/

2

)/(1-)

2

14. Dystrybuanta łącznego czasu oczekiwania na obsługę:
F(w)= 1- e

-w(1-)

15. Średni czas oczekiwania na obsługę: E[w]= [(1/)]/(1-

)
16. Wariancja czasu oczekiwania na obsługę: Var[w]= (2-
)/[

2

(1-)

2

]

17. Prawdopodobieństwo n lub więcej zadań w systemie: 

n

18. Średnia liczba zadań obsługiwanych w jednym okresie
ciągłej zajętości

procesora: /(1- )

19. Średni czas zajętości procesora: 1/[(1- )]

System kolejkowy M/M/m

1. Parametry:

•  – intensywność napływu zadań do systemu,
•  – intensywność obsługi zadań,
• m - liczba procesorów,

2. Intensywność ruchu: =/(m)
3. Warunek stabilności: 1
4. Prawdopodobieństwo zera zadań w systemie:

1

1

m

1

n

n

m

0

!

n

)

m

(

)

1

(

!

m

)

m

(

1

p



































5. Prawdopodobieństwo n zadań w systemie:























m

n

,

!

m

m

p

m

n

,

!

n

)

m

(

p

p

m

n

0

m

0

n

System kolejkowy M/M/m

6. Prawdopodobieństwo, że są zadania w kolejce (niezerowa
kolejka)
(zadań jest więcej niż m): =P(m zadań)=p

0

(m

)m

/[m!(1-

)]
7. Średnia liczba zadań w systemie: E[n]=m+  /(1- )
8. Wariancja liczby zadań w systemie: Var[n]=m+ 

[m+(1+- )/(1+ )

2

]

9. Średnia liczba zadań w kolejce: E[n

q

]= /(1- )

10. Wariancja liczby zadań w kolejce: Var[n

q

]=(1+- )/

(1- )

2

11. Średni czas odpowiedzi: E[r]=(1/)/(1+/[m(1- )])
12. Wariancja czasu odpowiedzi: Var[r]=(1/

2

)/(1+[(2-  )]/

[m

2

(1- )

2

])

13. Dystrybuanta łącznego czasu oczekiwania na obsługę:
F(w)= 1- e

-wm(1-)

14. Średni czas oczekiwania na obsługę: E[w]= E[n

q

]/= /

[m(1-)]
15. Wariancja czasu oczekiwania na obsługę: Var[w]= (2-

)/[m

2



2

(1-)]

System kolejkowy M/M/m/B (ze skończoną

kolejką)

1. Parametry:

•  – intensywność napływu zadań do systemu,
•  – intensywność obsługi zadań,
• m - liczba procesorów,
• B – pojemność systemu, Bm
2. Intensywność ruchu: =/(m)
3. Warunek stabilności: 1
4. Prawdopodobieństwo zera zadań w systemie:

1

1

m

1

n

n

m

1

m

B

0

!

n

)

m

(

)

1

(

!

m

)

m

)(

1

(

1

p











































dla
m=1



































1

,

B

1

1

1

,

1

1

p

1

B

0

System kolejkowy M/M/m/B (ze skończoną

kolejką)

5. Prawdopodobieństwo n zadań w systemie:



























B

n

m

,

!

m

m

p

m

n

0

,

!

n

)

m

(

p

p

m

n

0

n

0

n

6. Średnia liczba zadań w
systemie:







B

1

n

n

np

]

n

[

E

dla
m=1

1

B

1

B

1

)

1

B

(

1

]

n

[

E























7. Średnia liczba zadań w
kolejce:











B

1

m

n

n

q

p

)

m

n

(

]

n

[

E

dla
m=1

1

B

B

q

1

B

1

1

]

n

[

E























System kolejkowy M/M/m/B (ze skończoną

kolejką)

8. Średni czas odpowiedzi: E[r]=E[n

q

]/[(1-p

B

)]

9. Średni czas oczekiwania: E[w]=E[r]-1/= E[n

q

]/[(1-

p

B

)]

System kolejkowy M/G/1

1. Parametry:

•  – intensywność napływu zadań do systemu,
• E[s] – średni czas obsługi zadań,

• C

s

– wariancja czasu obsługi zadań,

2. Intensywność ruchu: =E[s]
3. Warunek stabilności: 1
4. Prawdopodobieństwo zera zadań w systemie: p

0

=1-

5. Średnia liczba zadań w systemie: E[n]=+ (1+ C

s

2

)/

[2(1- )]
6. Wariancja liczby zadań w systemie:

2

2

2

4

3

3

2

)

1

(

4

])

s

[

E

(

)

1

(

3

]

s

[

E

]

s

[

Var

]

n

[

E

]

n

[

Var























System kolejkowy M/G/1

7. Średnia liczba zadań w kolejce: E[n

q

]=

2

(1+ C

s

2

)/[2(1-

)]
8. Wariancja liczby zadań w kolejce: Var[n

q

]=Var[n]- + 

2

9. Średni czas odpowiedzi: E[r]=E[n]/=E[s]+ E[s](1+

C

s

2

)/[2(1- )]

10. Wariancja czasu odpowiedzi:

Var[r]=Var[s]+E[s

3

]/[3(1-)]+ 

2

(E[s

2

])

2

/[4(1- )

2

]

11. Średni czas oczekiwania: E[w]= E[s](1+ C

s

2

)/[2(1- )]

12. Wariancja czasu oczekiwania: Var[w]=Var[r]-Var[s]

13. Dystrybuanta czasu procesora bez pracy: F(I)=1-e

-I

-

wykładniczy

14. Średnia liczba zadań obsługiwanych w czasie ciągłej
pracy procesora:

1/(1-)

15. Średni czas ciągłej zajętości procesora: E[s]/(1- )
16. Wariancja czasu ciągłej zajętości procesora: E[s

2

]/(1-

)

3

–(E[s])

2

/(1- )

2

System kolejkowy M/G/1 z podziałem czasu

(time sharing)

1. Parametry:

•  – intensywność napływu zadań do systemu,
• E[s] – średni czas obsługi zadań,

2. Intensywność ruchu: =E[s]<1
3. Warunek stabilności: 1
4. Prawdopodobieństwo n zadań w systemie: p

n

=(1-) 

n

,

n=0,1,...,
5. Średnia liczba zadań w systemie: E[n]= /(1- )
6. Wariancja liczby zadań w systemie: Var[n]= /(1- )

2

7. Średni czas odpowiedzi: E[r]=E[s]/(1- )
Uwaga: podobne wyniki jak dla systemu M/M/1; strategia
time sharing aproksymuje szeregowanie zadań typu round-
robin z małym kwantem czasu.

System kolejkowy M/G/

1. Parametry:

•  – intensywność napływu zadań do systemu,
• E[s] – średni czas obsługi zadań,

2. Intensywność ruchu: =E[s]
3. Warunek stabilności: 1
4. Prawdopodobieństwo zera zadań w systemie: p

0

=e

-

5. Prawdopodobieństwo n zadań w systemie: p

n

=(e

-

/n!) 

n

,

n=0,1,...,
6. Średnia liczba zadań w systemie: E[n]= 
7. Wariancja liczby zadań w systemie: Var[n]= 
8. Liczba zadań w kolejce jest zawsze równa zero, zatem
E[n

q

]=0

9. Czas odpowiedzi jest równy czasowi obsługi, czyli ma ten
sam rozkład

10. Średni czas odpowiedzi: E[r]=E[s]

Uwaga: dla przypadku M/M/ zachodzi E[s]=1/, co należy

wstawić do powyższych wyników

System kolejkowy G/M/1

1. Parametry:

• E[] – średni czas pomiędzy napływem zadań do systemu,
•  – intensywność czasu obsługi zadań,
• jeśli L

r

(f) jest transformatą Lapunowa gęstości czasu , to

niech  będzie

rozwiązaniem równania =L(-  )

2. Intensywność ruchu: =1/(E[] )
3. Warunek stabilności: 1
4. Prawdopodobieństwo zera zadań w systemie: p

0

=1- 

5. Prawdopodobieństwo n zadań w systemie: p

n

= 

n-1

(1-

) , n=1,...,
6. Średnia liczba zadań w systemie: E[n]=/(1-)
7. Wariancja liczby zadań w systemie: Var[n]=(1+-)/(1-

)

2

8. Dystrybuanta łącznego czasu odpowiedzi: F(r)=1-e

(1-)r

,

r0
9. Średni czas odpowiedzi: E[r]=1/[(1- )]
10. Wariancja czasu odpowiedzi: Var[r]=[1/{(1- )}]

2

System kolejkowy G/M/1

11. Dystrybuanta czasu oczekiwania na obsługę: F(w)=1-
e

(1-)w

, w0

12. Średni czas oczekiwania na obsługę: E[w]= /[(1- )]
13. Wariancja czasu oczekiwania na obsługę: Var[w]= (2-
)/[

2

(1- )

2

]

14. Prawdopodobieństwo n lub więcej zadań w systemie:


n

(1- )/(1- )

Uwaga: dla strumienia Poissona = .

System kolejkowy G/G/m

1. Parametry:

• E[] – średni czas pomiędzy napływem zadań do systemu,
•  – intensywność napływu zadań do systemu, =1/ E[]
• E[s] – średni czas obsługi zadań,
•  – intensywność czasu obsługi zadań, =1/ E[s
2. Intensywność ruchu: =  /(m )
3. Warunek stabilności: 1
4. Średnia liczba zadań w obsłudze: E[n

s

]=m

5. Średnia liczba zadań w systemie: E[n]=E[n

q

]+m

6. Wariancja liczby zadań w systemie: Var[n]=Var[n

q

]+

Var[n

s

]

7. Średni czas odpowiedzi: E[r]=E[w]+E[s] lub E[r]=E[n]/
8. Wariancja czasu odpowiedzi: Var[r]=Var[w]+Var[s]

9. Średni czas oczekiwania na obsługę: E[w]=E[n

q

]/ 