Efektywność systemów

informatycznych

Wykład 6

TEMAT:Niemarkowskie systemy

kolejkowe

2

Niemarkowskie systemy kolejkowe



System kolejkowy nazywamy

System kolejkowy nazywamy

niemarkowskim,

niemarkowskim,

jeśli proces

jeśli proces

, którego wartość oznacza

, którego wartość oznacza

liczbę zgłoszeń w systemie w chwili

liczbę zgłoszeń w systemie w chwili

t,

t,

nie jest

nie jest

procesem Markowa.

procesem Markowa.



Przykładami systemów niemarkowskich są

Przykładami systemów niemarkowskich są

systemy:

systemy:



M|G|1

M|G|1



GI|M|1

GI|M|1



GI|G|1

GI|G|1



Do analizy systemów niemarkowskich

Do analizy systemów niemarkowskich

wykorzystuje się różne techniki, a między

wykorzystuje się różne techniki, a między

innymi:

innymi:



Metoda procesów włożonych,

Metoda procesów włożonych,



Rozszerzanie przestrzeni stanów.

Rozszerzanie przestrzeni stanów.



W dalszym ciągu, omówione zostaną wybrane

W dalszym ciągu, omówione zostaną wybrane

systemy typu M|G|.. .

systemy typu M|G|.. .

)

(t



3

System M|G|1



Niech ciąg zmiennych losowych

Niech ciąg zmiennych losowych

oznacza odstępy

oznacza odstępy

czasu, między kolejnymi zgłoszeniami w

czasu, między kolejnymi zgłoszeniami w

strumieniu wejściowym. Zgodnie z typem systemu:

strumieniu wejściowym. Zgodnie z typem systemu:



Niech ciąg zmiennych losowych

Niech ciąg zmiennych losowych

oznacza czasy

oznacza czasy

obsługi kolejnych zgłoszeń w rozpatrywanym

obsługi kolejnych zgłoszeń w rozpatrywanym

systemie, zgodnie z typem systemu kolejkowego

systemie, zgodnie z typem systemu kolejkowego

(M|G|1) mamy:

(M|G|1) mamy:



Niech wartość procesu

Niech wartość procesu

oznacza liczbę

oznacza liczbę

zgłoszeń w systemie w chwili

zgłoszeń w systemie w chwili

t

t

,

,



Z przyjętych założeń wynika, że proces

Z przyjętych założeń wynika, że proces

nie jest procesem Markowa

nie jest procesem Markowa

)

(t



1

)

(



n

n



 





,....

2

,

1

,

0

,

1















n

t

e

t

P

t

F

t

n





1

)

(



n

n



 





 

,...

2

,

1

,









n

E

oraz

t

P

t

G

n

n







)

(t



4

System M|G|1 – slajd 2



W celu wyznaczenia charakterystyk procesu

W celu wyznaczenia charakterystyk procesu

,

,

rozpatrzymy ten proces w chwilach

rozpatrzymy ten proces w chwilach

, gdzie

, gdzie

t

t

n

n

oznacza chwilę zakończenia obsługi n-tego

oznacza chwilę zakończenia obsługi n-tego

zgłoszenia, a

zgłoszenia, a

t

t

n

n

+0

+0

oznacza „moment tuż po”

oznacza „moment tuż po”

chwili

chwili

t

t

n

n

, czyli będziemy rozpatrywali ciąg

, czyli będziemy rozpatrywali ciąg

.

.



W celu określenia własności ciągu

W celu określenia własności ciągu

wprowadźmy dodatkową zmienna losową

wprowadźmy dodatkową zmienna losową

oznaczającą liczbę zgłoszeń, które napłynęły do

oznaczającą liczbę zgłoszeń, które napłynęły do

systemu w czasie obsługi

systemu w czasie obsługi

n-tego zgłoszenia. Można zapisać następująca

n-tego zgłoszenia. Można zapisać następująca

zależność:

zależność:

(6.1)

(6.1)



Łatwo zauważyć, że ciąg

Łatwo zauważyć, że ciąg

jest jednorodnym

jest jednorodnym

łańcuchem Markowa.

łańcuchem Markowa.

)

(t







,..

2

,

1

0





n

n

t

...

,

2

,

1

)

0

(







n

t

n

n





1

)

(



n

n



n





























1

g

1

0

g

1

1

1

n

n

n

n

n

n

dy

dy









1

)

(



n

n



5

System M|G|1 – slajd 3



Można pokazać, że rozkład zmiennej

Można pokazać, że rozkład zmiennej

określony jest zależnościami:

określony jest zależnościami:

(6.2)

(6.2)

oraz:

oraz:

(6.2.A)

(6.2.A)

n





  





 

 

0

,

!

,....

1

,

0

,

!

|

0

































k

x

dG

e

k

x

k

P

p

czyli

k

e

k

x

x

k

P

t

k

n

k

t

k

n

n











 



















0

x

xdG

E

n

6

System M|G|1 – slajd 4



Wykorzystując związek (6.1) oraz zależności

Wykorzystując związek (6.1) oraz zależności

(6.2), można wyznaczyć macierz

(6.2), można wyznaczyć macierz

prawdopodobieństw przejść w jednym kroku

prawdopodobieństw przejść w jednym kroku

łańcucha :

łańcucha :

1

)

(



n

n



 



















































2

1

0

1

1

0

2

1

0

2

2

1

1

0

0

0

0

0

2

1

0

1

p

p

p

p

p

p

p

p

p

p

p

p

p

p

i

i

i

i

i















7

System M|G|1 – slajd 5



Graficzna reprezentacja łańcucha ma

Graficzna reprezentacja łańcucha ma

postać:

postać:



Rozkład stacjonarny łańcucha

Rozkład stacjonarny łańcucha

wyznaczamy jako rozwiązanie następującego

wyznaczamy jako rozwiązanie następującego

układu równań:

układu równań:

(6.3)

(6.3)

1

)

(



n

n



p

p

0

0

1

1

2

2

i

i

0

0

p

p

1

1

p

p

1

1

p

p

1

1

p

p

2

2

p

p

2

2

p

p

2

2

p

p

0

0

p

p

0

0

p

p

i

i

p

p

i

i

P

P

i-1

i-1

1

)

(



n

n























1

0

k

k







8

System M|G|1 – slajd 6



Rozwiązanie układu (6.3) przedstawia się w

Rozwiązanie układu (6.3) przedstawia się w

literaturze w postaci funkcji tworzącej

literaturze w postaci funkcji tworzącej

rozkładu stacjonarnego:

rozkładu stacjonarnego:



Przyjmując oznaczenia:

Przyjmując oznaczenia:

Można pokazać, że jeśli

Można pokazać, że jeśli

to:

to:

(6.8)

(6.8)

1

,

)

(

0













z

z

z

k

k

k































0

*

0

)

(

))

(

(

)

(

1

}

{

)

(

t

dG

e

t

G

L

s

g

z

z

p

z

E

z

p

st

s

k

k

k

n

1













z

z

g

z

g

z

z

















))

1

(

(

))

1

(

(

)

1

(

)

1

(

)

(

*

*









9

System M|G|1 – slajd 7



Zależność (6.8) jest znana w literaturze jako

Zależność (6.8) jest znana w literaturze jako

„wzór Pollaczka-Chinczyna”.

„wzór Pollaczka-Chinczyna”.



Dowodzi się, że zachodzi następująca równość:

Dowodzi się, że zachodzi następująca równość:

Zatem, rozkład stacjonarny łańcucha

Zatem, rozkład stacjonarny łańcucha

określa rozkład graniczny procesu

określa rozkład graniczny procesu

.

.

Inaczej, można zapisać, że:

Inaczej, można zapisać, że:



Wykorzystując funkcję tworzącą można

Wykorzystując funkcję tworzącą można

wyznaczyć np. wartość oczekiwaną zmiennej

wyznaczyć np. wartość oczekiwaną zmiennej

:

:

(6.9)

(6.9)

0

,

}

)

(

{

lim

)

(

lim



















k

k

t

P

t

P

k

k

t

k

t







1

)

(



n

n



)

(t



















~

oraz

)

(

D

t



 





 





















0

2

2

2

2

1

|

gdzie

,

1

2

t

dG

t

z

E

z















10

System M|G|1 – slajd 8



Wykorzystując rozkład graniczny procesu

Wykorzystując rozkład graniczny procesu

można wyznaczyć rozkład czasu oczekiwania

można wyznaczyć rozkład czasu oczekiwania

zgłoszenia na obsługę oraz czasu przebywania

zgłoszenia na obsługę oraz czasu przebywania

zgłoszenia w systemie.

zgłoszenia w systemie.



Przyjmijmy oznaczenia:

Przyjmijmy oznaczenia:

(*)

(*)

gdzie:

gdzie:



V

V

t

t

-

-

oznacza czas pobytu w systemie zgłoszenia,

oznacza czas pobytu w systemie zgłoszenia,

które przybyło do systemu w chwili

które przybyło do systemu w chwili

t

t

,

,



W

W

t

t

-

-

oznacza czas oczekiwania na obsługę

oznacza czas oczekiwania na obsługę

zgłoszenia, które przybyło do systemu w chwili

zgłoszenia, które przybyło do systemu w chwili

t

t

,

,



V – graniczny czas pobytu w systemie zgłoszenia,

V – graniczny czas pobytu w systemie zgłoszenia,



W – graniczny czas oczekiwania na obsługę

W – graniczny czas oczekiwania na obsługę

zgłoszenia.

zgłoszenia.

)

(t



V

V

W

W

D

t

D

t









,

11

System M|G|1 – slajd 9



Jeśli

Jeśli

to:

to:

(6.10)

(6.10)

Uwzględniając fakt, że

Uwzględniając fakt, że

otrzymujemy:

otrzymujemy:

(6.10A)

(6.10A)

1

i

))

(

(

)

(

},

{

)

(

*











t

H

L

s

h

t

W

P

t

H

s

))

(

1

(

1

1

)

(

*

*

s

g

s

s

h













0

|

*

)

(

}

{

s

h

ds

d

W

E





 





 



































1

2

1

2

2

2

2

E

E

EW

12

System M|G|1 – slajd 10



Jeśli

Jeśli

to:

to:

z zależności (*) oraz (6.10) wynika, że:

z zależności (*) oraz (6.10) wynika, że:

(6.11)

(6.11)

1

i

))

(

(

)

(

},

{

)

(

*











t

F

L

s

f

t

V

P

t

F

V

s

V

V

}

{

}

{

}

{

oraz

)

(

))

(

1

(

1

1

)

(

*

*

*







E

W

E

V

E

s

g

s

g

s

s

f

V















13

System M|G|1|N



Dysponując rozkładem granicznym procesu

Dysponując rozkładem granicznym procesu

dla systemu M|G|1, łatwo wyznaczyć rozkład

dla systemu M|G|1, łatwo wyznaczyć rozkład

graniczny dla procesu

graniczny dla procesu

, którego

, którego

wartość oznacza liczbę zgłoszeń w systemie

wartość oznacza liczbę zgłoszeń w systemie

M|G|1|N w chwili

M|G|1|N w chwili

t.

t.



Niech

Niech

,

,

wówczas dla

wówczas dla

prawdziwe są zależności:

prawdziwe są zależności:

(6.12)

(6.12)

)

(t



)

(t

N



1

..,

,

1

,

0

},

)

(

{

lim

)

(













N

k

k

t

P

N

t

N

k





1





 











 














































N

k

dla

x

oraz

x

k

N

N

k

N

N

N

N

,..,

0

1

1

0

0

0

1

0

0

1



































14

System M|G|n|0



Niech

Niech

- liczba zgłoszeń w systemie w

- liczba zgłoszeń w systemie w

chwili

chwili

t

t

. Jest to też liczba zajętych kanałów

. Jest to też liczba zajętych kanałów

systemu.

systemu.



Przyjmijmy oznaczenia:

Przyjmijmy oznaczenia:

gdzie:

gdzie:

- czas przez jaki do chwili

- czas przez jaki do chwili

t

t

było

było

obsługiwane i-te z

obsługiwane i-te z

aktualnie

aktualnie

obsługiwanych zgłoszeń,

obsługiwanych zgłoszeń,

oraz

oraz

)

(t







)

(

..,

),

(

),

(

)

(

)

(

1

t

t

t

t

X

t











)

(t

i







 

 





 

)

(

lim

}

{

)

(

,..,

1

,

,

,

,

,

,

2

1

t

P

k

t

P

t

P

k

i

x

t

k

t

P

x

x

x

t

F

k

t

k

k

i

i

k

k





























15

System M|G|n|0 – c.d. 2



Podstawowe zależności dla systemu M|G|n|0

Podstawowe zależności dla systemu M|G|n|0

mają postać:

mają postać:

1

1

0

0

Jeśli

Jeśli

to:

to:

(6.13)

(6.13)

2

2

0

0

Jeśli

Jeśli

to proces

to proces

X(t)

X(t)

posiada rozkład

posiada rozkład

graniczny określony zależnościami:

graniczny określony zależnościami:

(6.14)

(6.14)





















k

i

x

k

k

k

k

k

k

t

k

k

i

dt

t

G

x

x

x

F

x

x

x

t

F

x

x

x

F

1 0

2

1

2

1

2

1

))

(

1

(

)

,

,

,

(

,

,

,

,

lim

)

,

,

,

(

















1

0

0

0

!

oraz

..,

,

0

dla

,

!



























n

i

i

k

k

i

n

k

k





















0

)

(t

tdG



16

System M|G|



W systemie tym, każde zgłoszenie trafia

W systemie tym, każde zgłoszenie trafia

natychmiast do kanału obsługi.

natychmiast do kanału obsługi.



Podstawowe rezultaty dla systemu M|G|

Podstawowe rezultaty dla systemu M|G|





:

:

1

1

0

0

(6.16)

(6.16)

2

2

0

0

Jeśli

Jeśli

to:

to:

(6.16A)

(6.16A)







 

 





 





 

 

 























t

t

k

k

du

u

G

t

gdzie

k

e

k

t

k

t

P

t

P

0

1

0

,

!











 

0

,

!

lim













k

e

k

t

P

k

k

t

k







17

System M|G|1|PS



PS – processor sharing – system z podziałem

PS – processor sharing – system z podziałem

mocy procesora, każde zadanie trafia

mocy procesora, każde zadanie trafia

natychmiast do kanału obsługi,

natychmiast do kanału obsługi,



Przyjmuje się, że moc procesora (kanału)

Przyjmuje się, że moc procesora (kanału)

można rozdzielić między obecne w systemie

można rozdzielić między obecne w systemie

zadania, przez c

zadania, przez c

i

i

oznaczamy część mocy

oznaczamy część mocy

przydzieloną zadaniu i-temu oraz:

przydzieloną zadaniu i-temu oraz:

jeśli w systemie znajduje się

jeśli w systemie znajduje się

k

k

zgłoszeń,

zgłoszeń,



Niech

Niech

oznacza czas realizacji zadania o

oznacza czas realizacji zadania o

rozmiarze

rozmiarze

z

z

mikrooperacji, na procesorze o

mikrooperacji, na procesorze o

mocy

mocy

v

v

,

,



Czas realizacji tego zadania na procesorze o

Czas realizacji tego zadania na procesorze o

mocy

mocy

v

v

c

c

=vc

=vc

wynosi:

wynosi:

1

1







k

i

i

c

v

z





c

c

v

z

v

z

c

c













18

System M|G|1|PS- c.d. 2



Jeśli rozkład czasu realizacji zadania na

Jeśli rozkład czasu realizacji zadania na

procesorze o mocy

procesorze o mocy

v

v

jest zmienną losową o

jest zmienną losową o

rozkładzie określonym dystrybuantą

rozkładzie określonym dystrybuantą

G(t)

G(t)

, to

, to

czas realizacji na procesorze o mocy

czas realizacji na procesorze o mocy

vc

vc

ma następujący rozkład:

ma następujący rozkład:



Rozpatrzmy system M|G|1|PS przy

Rozpatrzmy system M|G|1|PS przy

założeniu, że

założeniu, że

c

c

i

i

=1/k

=1/k

jeśli w systemie znajduje

jeśli w systemie znajduje

się k zgłoszeń,

się k zgłoszeń,

c

E

c

E

E

t

c

G

t

c

P

t

c

P

t

P

t

G

c

c

c

}

{

}

{

}

{

oraz

)

(

}

{

}

{

}

{

)

(



































19

System M|G|1|PS- c.d. 3



Modelem działania systemu będzie proces:

Modelem działania systemu będzie proces:

gdzie:

gdzie:

- liczba zgłoszeń w systemie w chwili

- liczba zgłoszeń w systemie w chwili

t

t

,

,

- czas jaki pozostał do zakończenia

- czas jaki pozostał do zakończenia

wykonywania

wykonywania

i-tego

i-tego

zadania,

zadania,

 

   

 

 





t

t

t

t

Y

t









,...,

,

1



)

(t



)

(t

i







 

 





k

i

x

t

k

t

P

x

x

t

F

i

i

k

k

,..,

1

,

,

,

,

,

1















20

System M|G|1|PS- c.d. 4



Jeśli

Jeśli

to prawdziwe są

to prawdziwe są

następujące zależności:

następujące zależności:

1

1

0

0

(6.17)

(6.17)

2

2

0

0

1













 

 



 

  



k

k

t

k

t

k

k

t

P

t

P



































1

1

lim

lim







 



 





















 



k

i

x

k

k

k

k

t

k

k

i

dx

x

G

x

x

F

x

x

t

F

1 0

1

1

1

1

1

,

,

,

,

,









