Efektywność systemów
informatycznych
Wykład 6
TEMAT:Niemarkowskie systemy
kolejkowe
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
,
,
,
,
,