Efektywność systemów
informatycznych
Wykład 9
TEMAT: Metoda analizy średnich
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
)
(