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:nowicki@isi.wat.edu.pl, 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

]/ 