Efektywność systemów
informatycznych
Wykład 2
TEMAT:Modele matematyczne SI i
analityczne metody wyznaczania
wartości wskaźników efektywności.
Modele strumieni zdarzeń
Efektywność systemów
informatycznych
Wykład 2
TEMAT:Modele matematyczne SI i
analityczne metody wyznaczania
wartości wskaźników efektywności.
Modele strumieni zdarzeń
2
Rekurencyjne strumienie zdarzeń
Przyjmijmy, że interesuje nas występowanie w czasie
Przyjmijmy, że interesuje nas występowanie w czasie
określonych zdarzeń (awarii , napływania zgłoszeń do
określonych zdarzeń (awarii , napływania zgłoszeń do
SI, zgłoszeń do systemu obsługi)
SI, zgłoszeń do systemu obsługi)
Oznaczmy przez
Oznaczmy przez
t
t
i
i
, i=1, 2, ..
, i=1, 2, ..
chwile występowania
chwile występowania
rozpatrywanych zdarzeń. Wówczas ciąg
rozpatrywanych zdarzeń. Wówczas ciąg
nazywamy strumieniem zdarzeń.
nazywamy strumieniem zdarzeń.
Strumienie deterministyczne i stochastyczne.
Strumienie deterministyczne i stochastyczne.
Dalej rozpatrywane będą stochastyczne rekurencyjne
Dalej rozpatrywane będą stochastyczne rekurencyjne
strumienie zdarzeń.
strumienie zdarzeń.
Rozpatrzmy następujący ciąg zmiennych losowych:
Rozpatrzmy następujący ciąg zmiennych losowych:
Zmienne losowe
Zmienne losowe
T
T
i
i
oznaczają odstępy czasu między
oznaczają odstępy czasu między
kolejnymi zdarzeniami. W zależności od własności
kolejnymi zdarzeniami. W zależności od własności
ciągów
ciągów
(t
(t
i
i
), (T
), (T
i
i
)
)
mamy do czynienia z różnymi typami
mamy do czynienia z różnymi typami
strumieni zdarzeń.
strumieni zdarzeń.
1
i
i
t
0
..
,
2
,
1
0
,
1
t
i
t
t
T
i
i
i
3
Rekurencyjne strumienie zdarzeń -
2
Strumień
Strumień
(t
(t
i
i
),
),
dla którego ciąg
dla którego ciąg
(T
(T
i
i
)
)
jest ciągiem
jest ciągiem
łącznie niezależnych zmiennych losowych, nazywa
łącznie niezależnych zmiennych losowych, nazywa
się
się
strumieniem o ograniczonych następstwach.
strumieniem o ograniczonych następstwach.
Przyjmijmy dalej, że
Przyjmijmy dalej, że
F
F
i
i
,
,
i=1, 2, .. są dystrybuantami
i=1, 2, .. są dystrybuantami
rozkładu prawdopodobieństwa zmiennych losowych
rozkładu prawdopodobieństwa zmiennych losowych
T
T
i
i
i=1, 2, .., czyli:
i=1, 2, .., czyli:
Strumień o ograniczonych następstwach, dla
Strumień o ograniczonych następstwach, dla
którego:
którego:
gdzie:
gdzie:
F
F
jest pewna dystrybuantą, nazywamy
jest pewna dystrybuantą, nazywamy
opóźnionym strumieniem rekurencyjnym.
opóźnionym strumieniem rekurencyjnym.
Jeśli dodatkowo
Jeśli dodatkowo
to mamy do czynienia ze
to mamy do czynienia ze
strumieniem rekurencyjnym
strumieniem rekurencyjnym
..
,
2
,
1
},
{
)
(
i
t
T
P
t
F
i
i
F
...
3
2
F
F
,..
2
,
1
,
.
,
1
i
F
F
tzn
F
F
i
4
Rekurencyjne strumienie zdarzeń -
3
Jeśli natomiast:
Jeśli natomiast:
to
to
(t
(t
i
i
)
)
jest stacjonarnym strumieniem rekurencyjnym.
jest stacjonarnym strumieniem rekurencyjnym.
Ze strumieniem rekurencyjnym można związać
Ze strumieniem rekurencyjnym można związać
proces zliczający określono następująco:
proces zliczający określono następująco:
0
0
0
1
)
(
)
(
1
(
)
(
1
(
1
)
(
u
tdF
du
u
F
du
u
F
t
F
t
}
:
max{
)
(
t
t
n
t
n
{0}
N
5
Rekurencyjne strumienie zdarzeń -
4
Mówimy, że dysponujemy pełnym opisem
Mówimy, że dysponujemy pełnym opisem
probabilistycznym strumienia
probabilistycznym strumienia
(t
(t
i
i
)
)
i=1,2,..
i=1,2,..
jeśli
jeśli
dysponujemy dystrybuantami
dysponujemy dystrybuantami
F
F
1
1
, F
, F
.
.
Podstawowe charakterystyki strumieni
Podstawowe charakterystyki strumieni
rekurencyjnych
rekurencyjnych
:
:
Rozkład czasu do wystąpienia r-tego zdarzenia,
Rozkład czasu do wystąpienia r-tego zdarzenia,
Rozkład chwilowy procesu zliczającego
Rozkład chwilowy procesu zliczającego
zdarzenia,
zdarzenia,
Oczekiwana liczba zdarzeń do chwili
Oczekiwana liczba zdarzeń do chwili
t
t
,
,
Operacje na strumieniach rekurencyjnych:
Operacje na strumieniach rekurencyjnych:
Sumowanie i rozrzedzanie strumieni
Sumowanie i rozrzedzanie strumieni
Niepojedynczy strumień zdarzeń.
Niepojedynczy strumień zdarzeń.
6
Rekurencyjne strumienie zdarzeń -
5
Rozkładu czasu do wystąpienia r-tego zdarzenia
Rozkładu czasu do wystąpienia r-tego zdarzenia
Ze związku
Ze związku
wynika, że:
wynika, że:
Rozkład sumy niezależnych zmiennych
Rozkład sumy niezależnych zmiennych
losowych
losowych
0
..
,
2
,
1
0
,
1
t
i
t
t
T
i
i
i
1
,
1
r
T
t
r
i
i
r
z
X
Y
z
Y
X
Z
Z
Y
X
x
dF
x
z
F
y
dF
y
z
F
z
Y
X
P
z
F
F
Z
Y
X
Z
F
Y
F
X
0
0
)
(
)
(
)
(
)
(
}
{
)
(
~
,
,
~
,
~
7
Rekurencyjne strumienie zdarzeń -
6
Jeśli istnieje
Jeśli istnieje
to
to
Zatem, jeśli przez
Zatem, jeśli przez
K
K
r
r
oznaczymy dystrybuantę
oznaczymy dystrybuantę
t
t
r
r
:
:
to otrzymujemy:
to otrzymujemy:
)
(
)
(
z
F
dz
d
z
f
Z
Z
dx
x
f
x
z
f
dy
y
f
y
z
f
z
f
z
X
Y
z
Y
X
Z
0
0
)
(
)
(
)
(
)
(
)
(
}
{
)
(
t
t
P
t
K
r
r
r
i
i
r
r
r
r
i
t
i
r
t
T
P
t
F
t
F
F
u
dF
u
t
F
t
T
P
t
K
2
)
1
(
)
1
(
1
)
1
(
1
0
1
}
{
)
(
:
gdzie
)
(
*
)
(
)
(
}
{
)
(
8
Rekurencyjne strumienie zdarzeń -
7
Jeśli przyjmiemy oznaczenia:
Jeśli przyjmiemy oznaczenia:
To
To
oraz
oraz
))
(
(
)
(
)
(
))
(
(
)
(
)
(
)
(
0
0
*
t
K
L
t
dK
e
dt
t
k
e
t
k
L
s
k
t
K
dt
d
t
k
r
s
r
st
r
st
r
r
r
r
1
*
)
1
(
*
)
1
(
1
1
*
1
*
*
*
))
(
(
))
(
(
)
(
))
(
(
))
(
(
)
(
))
(
(
))
(
(
)
(
)
(
1
))
(
(
)
(
r
r
r
s
s
r
r
r
s
f
t
f
L
s
f
t
F
L
t
f
L
s
f
t
F
L
t
f
L
s
f
s
k
s
t
K
L
s
K
1
*
*
1
*
)
1
(
*
1
*
)
(
)
(
)
(
)
(
)
(
r
r
r
s
f
s
f
s
f
s
f
s
k
9
Rekurencyjne strumienie zdarzeń -
7
Dla strumienia rekurencyjnego:
Dla strumienia rekurencyjnego:
Dla strumienia stacjonarnego otrzymujemy:
Dla strumienia stacjonarnego otrzymujemy:
stąd:
stąd:
r
r
r
r
s
f
s
f
s
f
s
f
s
f
s
k
)
(
)
(
)
(
)
(
)
(
)
(
*
1
*
*
*
)
1
(
*
1
*
))
(
1
(
1
)
(
1
1
1
))
(
(
1
1
1
))
(
1
(
1
(
)
(
*
*
*
1
s
f
s
s
f
s
s
t
F
L
s
t
F
L
s
f
1
*
*
*
)
(
))
(
1
(
1
)
(
r
r
s
f
s
f
s
s
k
10
Rekurencyjne strumienie zdarzeń -
8
Rozkład chwilowy procesu zliczającego
Rozkład chwilowy procesu zliczającego
(t)
(t)
określony jest następującym wektorem:
określony jest następującym wektorem:
Można pokazać, że:
Można pokazać, że:
Inna metoda wyznaczania
Inna metoda wyznaczania
P(t)
P(t)
polega na
polega na
wykorzystaniu funkcji tworzącej rozkładu
wykorzystaniu funkcji tworzącej rozkładu
chwilowego procesu
chwilowego procesu
(t):
(t):
,..
2
,
1
,
0
},
)
(
{
)
(
gdzie
)
(
)
(
,..
2
,
1
,
0
i
i
t
P
t
P
t
P
t
P
i
i
i
,...
2
,
1
,
0
),
(
)
(
)
(
1
n
t
K
t
K
t
P
n
n
n
dt
z
t
G
e
z
t
G
L
z
s
G
z
z
t
P
z
t
G
st
k
k
k
)
,
(
))
,
(
(
)
,
(
oraz
1
,
)
(
)
,
(
0
*
0
11
Rekurencyjne strumienie zdarzeń -
9
Dowodzi się zależności:
Dowodzi się zależności:
Dla strumienia rekurencyjnego:
Dla strumienia rekurencyjnego:
Dla strumienia stacjonarnego:
Dla strumienia stacjonarnego:
))
(
1
(
)
(
)
1
(
)
(
1
)
,
(
*
*
1
*
*
s
zf
s
s
f
z
s
zf
z
s
G
))
(
1
(
)
(
1
)
,
(
*
*
*
s
zf
s
s
f
z
s
G
))
(
1
(
)
(
1
)
1
(
)
(
1
)
,
(
*
*
*
*
s
zf
s
s
s
f
z
s
zf
z
s
G
12
Rekurencyjne strumienie zdarzeń -
10
Oczekiwana liczba zdarzeń do chwili t
Oczekiwana liczba zdarzeń do chwili t
W praktyce wykorzystuje się zależność:
W praktyce wykorzystuje się zależność:
Dla strumienia rekurencyjnego:
Dla strumienia rekurencyjnego:
1
)
(
)}
(
{
)
(
r
r
t
K
t
E
t
H
)
(
1
)
(
1
))
(
(
)
(
*
*
1
*
s
f
s
f
s
t
H
L
s
H
)
(
1
)
(
1
)
(
*
*
*
s
f
s
f
s
s
H
13
Rekurencyjne strumienie zdarzeń -
11
Dla stacjonarnego strumienia rekurencyjnego:
Dla stacjonarnego strumienia rekurencyjnego:
t
H(t)
zatem
1
1
)
(
1
))
(
1
(
1
1
)
(
2
*
*
*
s
s
f
s
f
s
s
s
H
14
Rekurencyjne strumienie zdarzeń -
12
Rozrzedzanie strumieni zdarzeń
Rozrzedzanie strumieni zdarzeń
Jeśli jest zadany pewien strumień zdarzeń, to
Jeśli jest zadany pewien strumień zdarzeń, to
przez jego „rozrzedzenie” można tworzyć inne
przez jego „rozrzedzenie” można tworzyć inne
strumienie. Operacja rozrzedzania polega na
strumienie. Operacja rozrzedzania polega na
zaliczaniu do nowego strumienia tylko
zaliczaniu do nowego strumienia tylko
niektórych zdarzeń ze strumienia pierwotnego.
niektórych zdarzeń ze strumienia pierwotnego.
Szczególnie interesująca jest operacja
Szczególnie interesująca jest operacja
rekurencyjnego rozrzedzania.
rekurencyjnego rozrzedzania.
Załóżmy, że z pierwotnego strumienia zdarzeń
Załóżmy, że z pierwotnego strumienia zdarzeń
odrzucamy pierwszych
odrzucamy pierwszych
1
1
zdarzeń, a następne
zdarzeń, a następne
zaliczamy do nowego strumienia. Potem znowu
zaliczamy do nowego strumienia. Potem znowu
odrzucamy
odrzucamy
2
2
zdarzeń a kolejne zaliczamy itd..
zdarzeń a kolejne zaliczamy itd..
Jeśli ciąg (
Jeśli ciąg (
i
i
)
)
i=1,2,..
i=1,2,..
jest ciągiem niezależnych
jest ciągiem niezależnych
zmiennych losowych o identycznym rozkładzie to
zmiennych losowych o identycznym rozkładzie to
mówimy o rekurencyjnej operacji rozrzedzania.
mówimy o rekurencyjnej operacji rozrzedzania.
15
Rekurencyjne strumienie zdarzeń -
13
Tw.2.1.
Tw.2.1.
Strumień otrzymany z opóźnionego strumienia
Strumień otrzymany z opóźnionego strumienia
rekurencyjnego za pomocą rekurencyjnej
rekurencyjnego za pomocą rekurencyjnej
operacji rozrzedzania jest również
operacji rozrzedzania jest również
opóźnionym strumieniem rekurencyjnym.
opóźnionym strumieniem rekurencyjnym.
Wyznaczymy rozkład zmiennej losowej
Wyznaczymy rozkład zmiennej losowej
oznaczającej odstępy czasu między kolejnymi
oznaczającej odstępy czasu między kolejnymi
zdarzeniami w strumieniu rozrzedzonym.
zdarzeniami w strumieniu rozrzedzonym.
Przyjmijmy następujące oznaczenia
Przyjmijmy następujące oznaczenia
dodatkowe:
dodatkowe:
,..
3
,
2
,
'
i
T
i
))
(
(
)
(
)),
(
(
)
(
},
{
)
(
},
{
)
(
1
1
'
1
1
'
t
B
L
s
t
B
L
s
t
T
P
t
B
t
T
P
t
B
s
s
16
Rekurencyjne strumienie zdarzeń -
14
Można wykazać, że:
Można wykazać, że:
1
,
,...
1
,
0
},
{
oraz
1
,
}
{
)
(
:
gdzie
))
(
(
)
(
)
(
))
(
(
)
(
)
(
0
*
*
*
*
1
1
i
k
k
P
a
z
z
a
z
E
z
G
s
f
G
s
f
s
s
f
G
s
f
s
i
D
k
k
k
k
17
Rekurencyjne strumienie zdarzeń -
15
Sumowanie strumieni zdarzeń
Sumowanie strumieni zdarzeń
Inna operacją wykonywaną na strumieniach
Inna operacją wykonywaną na strumieniach
zdarzeń jest sumowanie. Jeśli
zdarzeń jest sumowanie. Jeśli
rozpatrywalibyśmy n różnych strumieni
rozpatrywalibyśmy n różnych strumieni
zdarzeń, to strumieniem sumarycznym byłby
zdarzeń, to strumieniem sumarycznym byłby
strumień, do którego zaliczylibyśmy wszystkie
strumień, do którego zaliczylibyśmy wszystkie
zdarzenia ze strumieni sumowanych.
zdarzenia ze strumieni sumowanych.
Ogólnie suma strumieni rekurencyjnych nie
Ogólnie suma strumieni rekurencyjnych nie
jest strumieniem rekurencyjnym (wyjątkiem
jest strumieniem rekurencyjnym (wyjątkiem
są strumienie Poissona).
są strumienie Poissona).
Prawdziwa jest jedynie następująca własność:
Prawdziwa jest jedynie następująca własność:
Jeśli
Jeśli
)
,
(
~
)
(
),
(
)
(
,..,
1
),
,
(
~
)
(
1
z
t
G
t
t
t
n
i
z
t
G
t
n
i
i
i
i
18
Rekurencyjne strumienie zdarzeń -
16
To zachodzi zależność:
To zachodzi zależność:
n
i
i
z
t
G
z
t
G
1
)
,
(
)
,
(
19
Rekurencyjne strumienie zdarzeń -
17
Strumienie niepojedyncze
Strumienie niepojedyncze
Rozpatrzmy strumień zdarzeń
Rozpatrzmy strumień zdarzeń
(t
(t
i
i
)
)
i=1,2,..
i=1,2,..
i
i
załóżmy, że w chwili wystąpienia zdarzenia
załóżmy, że w chwili wystąpienia zdarzenia
przybywa paczka zgłoszeń o liczności
przybywa paczka zgłoszeń o liczności
i.
i.
,
,
Zakładamy, że ciąg (
Zakładamy, że ciąg (
i
i
)
)
i=1,2,..
i=1,2,..
jest ciągiem
jest ciągiem
zmiennych losowych i.i.d. oraz
zmiennych losowych i.i.d. oraz
(t
(t
i
i
)
)
i=1,2,..
i=1,2,..
i
i
(
(
i
i
)
)
i=1,2
i=1,2
są stochastycznie niezależne,
są stochastycznie niezależne,
Przyjmijmy następujące oznaczenia:
Przyjmijmy następujące oznaczenia:
Jeśli strumień zdarzeń
Jeśli strumień zdarzeń
(t
(t
i
i
)
)
i=1,2,..
i=1,2,..
jest opóźnionym
jest opóźnionym
strumieniem rekurencyjnym to strumień
strumieniem rekurencyjnym to strumień
zgłoszeń nazywamy opóźnionym strumieniem
zgłoszeń nazywamy opóźnionym strumieniem
quasi-rekurencyjnym.
quasi-rekurencyjnym.
1
,
d
(z)
oraz
,..
2
,
1
,
0
}
{
0
k
k
,
z
z
k
d
k
P
k
k
i
20
Rekurencyjne strumienie zdarzeń -
18
Oznaczmy przez
Oznaczmy przez
*
*
(t)
(t)
proces zliczający
proces zliczający
zgłoszenia w przedziale czasu
zgłoszenia w przedziale czasu
(0, t)
(0, t)
. Proces
. Proces
ten można a formalnie określić następująco:
ten można a formalnie określić następująco:
Dalej, niech:
Dalej, niech:
)
(
0
)
(
*
t
i
i
t
0
},
)
(
{
)
(
,
)
(
)
,
(
)
,
(
))
,
(
(
)
,
(
)
(
)
,
(
0
},
)
(
{
)
(
0
0
*
0
*
*
k
k
t
P
t
P
z
t
P
z
t
G
dt
z
t
G
e
s
z
t
G
L
z
s
g
z
t
P
z
t
G
k
k
t
P
t
P
k
k
k
k
st
s
k
k
k
k
21
Rekurencyjne strumienie zdarzeń -
19
Podstawowe własności procesu
Podstawowe własności procesu
*
*
(t) :
(t) :
)}
(
{
var
)
(
var
}}
{
(
)
(
var
)}
(
{
}
{
)}
(
{
3
))
(
,
(
)
,
(
2
))
(
,
(
))
(
)(
(
)
(
)
,
(
1
2
0
*
0
0
0
*
0
t
E
t
E
t
t
E
E
t
E
z
s
g
z
s
g
z
t
G
z
t
P
z
t
P
z
t
G
k
k
k
k
k
k