Efektywność systemów

informatycznych

Wykład 9

TEMAT: Metoda analizy średnich

2

Twierdzenie Little’a



Rozpatrzmy następujące wielkości:

Rozpatrzmy następujące wielkości:

(9.1)

(9.1)

gdzie

gdzie

- liczba zgłoszeń w systemie w chwili t.

- liczba zgłoszeń w systemie w chwili t.

Jeśli granica (9.1) (istnieje w jakimś sensie

Jeśli granica (9.1) (istnieje w jakimś sensie

zbieżności) to można ja interpretować jako

zbieżności) to można ja interpretować jako

średnią liczbę zgłoszeń w systemie w

średnią liczbę zgłoszeń w systemie w

warunkach stabilności.

warunkach stabilności.

Przyjmijmy oznaczenie:

Przyjmijmy oznaczenie:











t

t

L

du

u

t

0

)

(

)

(

1

lim







)

(t



)}

(

{



L

E

EL

3

Twierdzenie Little’a - 2



Jeśli

Jeśli

N(t)

N(t)

oznacza liczbę liczbe zgłoszeń

oznacza liczbę liczbe zgłoszeń

przybyłych do systemu w przedziale

przybyłych do systemu w przedziale

(0, t)

(0, t)

, to

, to

przez

przez





(

(





)

)

oznaczamy wartość graniczną:

oznaczamy wartość graniczną:

(9.2)

(9.2)

Dla strumieni rekurencyjnych, gdzie

, mamy

)

(

)

(

lim













t

t

N

t







}

{

0

T

E

1

)

(

lim

:

)

(

lim

1

1







































t

t

N

P

czyli

const

t

t

N

t

t

4

Twierdzenie Little’a - 3



Przez

Przez

V(

V(





)

)

oznaczamy wartość:

oznaczamy wartość:

(9.3)

(9.3)

gdzie

gdzie V

j

oznacza czas przebywania j-tego

zgłoszenia w systemie. Przez EV oznaczmy
wielkość:

(9.3.A)













n

j

j

n

V

n

V

1

)

(

1

lim

)

(





)}

(

{



V

E

EV 

5

Twierdzenie Little’a - 4

Twierdzenie 9.1 (Little’a)
Jeśli z prawdopodobieństwem 1 istnieją granice

(9.2) i (9.3) oraz

to istnieje granica (9.1),

oraz:

Analogicznie, istnienie granic (9.1) i (9.2)

implikuje istnienie granicy (9.3).

Uwaga
Dla systemów M|M|n|N oraz M|G|1|N założenia

twierdzenia Little’a sa spełnione jeśli spełnione
są warunki istnienia rozkładu granicznego
(warunki ergodyczności) (np. <1).

EV

EL

















i

EV





EL

6

MVA dla sieci otwartych Jacksona



MVA polega na wyznaczaniu wartości oczekiwanych

MVA polega na wyznaczaniu wartości oczekiwanych

poszczególnych charakterystyk sieci, a nie ich

poszczególnych charakterystyk sieci, a nie ich

rozkładów).

rozkładów).



Rozpatrzmy otwarta sieć Jacksona z węzłami typu M|M|

Rozpatrzmy otwarta sieć Jacksona z węzłami typu M|M|

1.

1.



Dysponując rozwiązaniem układu równań równowagi:

Dysponując rozwiązaniem układu równań równowagi:

i zakładając, ze spełniony jest warunek

i zakładając, ze spełniony jest warunek

możemy, korzystając z rozkładu granicznego liczby

możemy, korzystając z rozkładu granicznego liczby

zgłoszeń w systemie typu M|M|1, wyznaczyć oczekiwaną

zgłoszeń w systemie typu M|M|1, wyznaczyć oczekiwaną

liczbę zgłoszeń w systemie w warunkach stabilności:

liczbę zgłoszeń w systemie w warunkach stabilności:

(9.4)

(9.4)





W









,..,

,

2

1



W

i

i

i

,..,

1

, 







i

i

i

i

i

k

i

k

i

i

k

EL

































,

1

)

1

(

0

7

MVA dla sieci otwartych Jacksona -
2



Dysponując wartościami

Dysponując wartościami





i

i

oraz

oraz

El

El

i

i

z twierdzenia

z twierdzenia

Little’a wyznaczamy

Little’a wyznaczamy

EV

EV

i

i

:

:

(9.5)

(9.5)

Podobnie można wyznaczyć oczekiwany czas pobytu

Podobnie można wyznaczyć oczekiwany czas pobytu

zgłoszenia w sieci. Jeśli przez

zgłoszenia w sieci. Jeśli przez

L

L

oznaczymy:

oznaczymy:

(9.6)

(9.6)

Wówczas, traktując siec jako jeden system obsługi,

Wówczas, traktując siec jako jeden system obsługi,

oznaczając przez

oznaczając przez

EV

EV

oczekiwany czas pobytu

oczekiwany czas pobytu

zgłoszenia w sieci, z twierdzenia Little’a

zgłoszenia w sieci, z twierdzenia Little’a

otrzymujemy:

otrzymujemy:

)

1

(

1

1

1

i

i

i

i

i

i

i

i

EL

EV









































W

W

i

i

i

i

i

EL

EL





1













W

i

i

i

EL

EV









1

1

0

0

8

MVA dla sieci otwartych Jacksona - 3



Jeśli przez

Jeśli przez

EV

EV

i0

i0

oznaczymy oczekiwany czas od

oznaczymy oczekiwany czas od

chwili przybycia zgłoszenia do i-tego węzła sieci

chwili przybycia zgłoszenia do i-tego węzła sieci

do chwili opuszczenia przez niego sieci, to

do chwili opuszczenia przez niego sieci, to

zachodzą następujące zależności:

zachodzą następujące zależności:

(9.7)

(9.7)

Układ (9.7) posiada jednoznaczne rozwiązanie

Układ (9.7) posiada jednoznaczne rozwiązanie

jeśli

jeśli

Q

Q

0

0

jest nierozkładalna.

jest nierozkładalna.

W

W













i

EV

q

EV

EV

j

j

ij

i

i

,

0

0

9

MVA dla sieci zamkniętych Jacksona



W przypadku zamkniętych sieci Jacksona tw.

W przypadku zamkniętych sieci Jacksona tw.

Little’a nie daje się zastosować. Przyczyna jest

Little’a nie daje się zastosować. Przyczyna jest

ustalona liczba zgłoszeń krążących w sieci.

ustalona liczba zgłoszeń krążących w sieci.



Oznaczmy przez

Oznaczmy przez

EY

EY

i

i

oczekiwaną liczbę

oczekiwaną liczbę

zgłoszeń, które zastanie w węźle i-tym

zgłoszeń, które zastanie w węźle i-tym

trafiające do niego zgłoszenie. Zachodzi

trafiające do niego zgłoszenie. Zachodzi

następująca zależność:

następująca zależność:

(9.8)

(9.8)

W sieciach otwartych zachodzi zależność

W sieciach otwartych zachodzi zależność

,

,

a uwzględniając (9.8), otrzymujemy:

a uwzględniając (9.8), otrzymujemy:

)

1

(

1

1

1













i

i

i

i

i

i

EY

EY

EV







i

i

EY

EL 

)

1

(

1

)

1

1

(

1

)

1

(

1

i

i

i

i

i

i

i

i

EL

EV

































10

MVA dla sieci zamkniętych Jacksona - 2



W sieciach zamkniętych zachodzi

W sieciach zamkniętych zachodzi

, natomiast jeśli oznaczymy przez

, natomiast jeśli oznaczymy przez

K

K

liczbę

liczbę

zgłoszeń w sieci, to spełniona jest zależność:

zgłoszeń w sieci, to spełniona jest zależność:

(9.9)

(9.9)

i

i

EY

EL 

)

1

)

1

(

(

1

)

(

(9.8)

z

zatem

a

),

1

(

)

(













K

EL

K

EV

K

EL

K

EY

i

i

i

i

i



)

(

)

(

)

(

)

(

)

(

)

1

)

1

(

(

1

)

(

K

EV

h

K

T

K

EL

K

EV

h

K

K

T

K

EL

K

EV

i

i

i

i

i

i

i

i

i





















W



Ogólnie dla sieci

Ogólnie dla sieci

zamkniętej Jacksona

zamkniętej Jacksona

spełnione są

spełnione są

następujące

następujące

zależności

zależności

rekurencyjne:

rekurencyjne:

W



 i

EL

i

,

0

)

0

(

11

MVA dla sieci zamkniętych Jacksona -
2



Przez

Przez

oznaczamy rozwiązanie

oznaczamy rozwiązanie

układu równań równowagi dla sieci

układu równań równowagi dla sieci

zamkniętej:

zamkniętej:



Wyznaczenie

Wyznaczenie

przy ustalonej

przy ustalonej

wartości K należy przeprowadzić wg

wartości K należy przeprowadzić wg

następującego algorytmu:

następującego algorytmu:

1.

1.

Rozwiązanie URR – wyznaczenie

Rozwiązanie URR – wyznaczenie

2.

2.

Dla

Dla

k

k

od

od

1

1

do

do

K

K





W

h

h

h

h

,..,

,

2

1



W











j

q

h

h

W

i

ij

i

j

,

1

)

(

),

(

K

EV

K

EL

i

i





W

h

h

h

h

,..,

,

2

1



W

W

























i

k

EV

h

k

T

k

EL

k

EV

h

k

k

T

k

EL

k

EV

i

i

i

i

i

i

i

i

i

),

(

)

(

)

(

)

(

)

(

)

1

)

1

(

(

1

)

(

