E.4 Markov-láncok E.4 Markov-láncok. Sok sorbanállási hálózat viselkedése leírható "folytonos idejű Markovláncok " segítségével

E.4 Markov-láncok

E.4 Markov-láncok

◆ Sok sorbanállási hálózat viselkedése leírható "folytonos idejű Markovláncok " segítségével. ◆ Egy Markov-láncot (MC) meghatároznak az alapját adó sorbanállási hálózat állapotai és az ezek közötti átmenetintenzitások. ◆ Globális egyensúlyi egyenletek egy sorbanállási hálózat alapján kapott Markov-lánc esetén:

πj qji = πi

j∈S

qij ,

∀i ∈ S

j∈S

➤ S: Állapottér (A sorbanállási hálózat összes állapotának halmaza) ➤ qij: Átmenetintenzitás az i és j átmenetek között ➤ pi: Az i állapot stacionárius valószínűsége Performance Modeling of Computer Systems  Gunter Bolch • Universität Erlangen-Nürnberg

Számítógép-rendszerek hatékonyság-elemzése Sztrik János, Baják Szabolcs • Debreceni Egyetem, Informatikai Kar

E.187

E.4 Markov-láncok

◆ Szavakban: • összes beérkezés az i állapotba = összes távozás az i állapotból • az i állapotba való átmenetintenzitások összege = az i állapotból való átmenetintenzitások összege ◆ Egyszerűsített globális egyensúlyi egyenletek:

∀i ∈ S :

πj qji − πi

j=i

qij = 0

j=i

πQ = 0

◆ Vagy a generátormátrixszal:

➤ p: A stacionárius valószínűségek vektora (π1, ... , πn)

qii = −

qij

j=i

Performance Modeling of Computer Systems  Gunter Bolch • Universität Erlangen-Nürnberg


E.188

E.4 Markov-láncok

➤ Q: Generátormátrix qij átmenetintenzitásokkal

◆ Példa: Zárt csillaghálózat

µ1

µ2

➤ Jobok száma K = 3 ➤ Kiszolgálási intenzitások: 1/µ1 = 5 sec és 1/µ2 = 2.5 sec (exp. eloszlás) ➤ Stratégia: FCFS ➤ A Markov-lánc állapottere:

{(3, 0), (2, 1), (1, 2), (0, 3)} ➤ Állapot: (k1, k2) → k1 job az 1-es és k2 job a 2-es csomópontnál Performance Modeling of Computer Systems  Gunter Bolch • Universität Erlangen-Nürnberg


E.189

E.4 Markov-láncok

➤ Stacionárius valószínűségek: π(k1, k2)

➤ Állapotátmenet diagram vagy átmenetdiagram:

µ1 3,0

µ1 2,1

1,2 µ2

µ2

µ1 0,3 µ2

➤ Globális egyensúlyi egyenletek (Markov-egyenletrendszer):

π(3, 0)µ1 π(2, 1)(µ1 + µ2 ) π(1, 2)(µ1 + µ2 ) π(0, 3)µ2


= = = =

π(2, 1)µ2 , π(3, 0)µ1 + π(1, 2)µ2 , π(2, 1)µ1 + π(0, 3)µ2 , π(1, 2)µ1 .


E.190

E.4 Markov-láncok

➤ Generátormátrix:

 −µ1  µ2 Q=  0 0

µ1 −(µ1 + µ2 ) µ2 0

0 µ1 −(µ1 + µ2 ) µ2

 0 0   µ1  −µ2

➤ A stacionárius valószínűségek vektora:

π = (π(3, 0), π(2, 1), π(1, 2), π(0, 3)) ➤ Generátormátrix µ1 = 0.2 és µ2 = 0.4 esetén:

  −0.2 0.2 0 0  0.4 −0.6 0.2 0  . Q=  0 0.4 −0.6 0.2  0 0 0.4 −0.4 Performance Modeling of Computer Systems  Gunter Bolch • Universität Erlangen-Nürnberg


E.191

E.4 Markov-láncok

➤ A πQ = 0 egyenletrendszer megoldásával kapjuk meg a stacionárius

valószínűségeket:

π(3, 0) = 0.5333 ,

π(2, 1) = 0.2667 ,

π(1, 2) = 0.1333 ,

π(0, 3) = 0.0667

➤ A stacionárius valószínűségekből kapjuk a marginális valószínűségeket:

π1 (0) = π2 (3) = π(0, 3) = 0.0667 , π1 (1) = π2 (2) = π(1, 2) = 0.133 , π1 (2) = π2 (1) = π(2, 1) = 0.2667 , π1 (3) = π2 (0) = π(3, 0) = 0.5333 .

➤ Kihasználtságok:

ρ1 = 1 − π1 (0) = 0.9333 ,


ρ2 = 1 − π2 (0) = 0.4667 .


E.192

E.4 Markov-láncok

➤ Áteresztőképesség:

λ = λ1 = λ2 = ρ1 µ1 = ρ2 µ2 = 0.1867 .

➤ A jobok átlagos száma:

K1 =

3

kπ1 (k) = 2.2667 ,

K2 =

k=1

3

kπ2 (k) = 0.7333 .

k=1

➤ Átlagos válaszolási idők:

T1 =

K1 = 12.1429 , λ1


T2 =

K2 = 3.9286 . λ2


E.193

E.4 Markov-láncok

◆ Példa: M/M/1 - rendszer:

➤ Az alapul vett Markov-lánc állapottere:

{0, 1, 2, 3, 4, ...... } ➤ Átmenetdiagram:

λ 0

λ 1

µ

λ

2 µ


λ

λ n

µ

µ

µ


E.194

E.4 Markov-láncok

➤ A stacionárius valószínűségek vektora:

π = (π0, π1, π2, π3, π4, ..... ) λ

µ


 −λ  µ   Q= 0  0  .. .

λ −(λ + µ) µ 0 .. .

0 λ −(λ + µ) µ .. .

0 0 λ −(λ + µ) .. .

 ··· · · ·  · · ·  · · ·  .. .


0 = −π0 λ + π1 µ , 0 = −πk (λ + µ) + πk−1 λ + πk+1 µ ,


k≥1


E.195

E.4 Markov-láncok

➤ A π1 és π2 stacionárius valószínűségek:

π1 =

λ π0 , µ

π2 =

λ·λ π0 µ·µ

➤ Általánosan:

k λ πk = π0 µ

➤ A normalizáló feltétel használatával:

π0 = 1 −


λ µ


E.196

E.4 Markov-láncok

➤ ρ = λ/µ helyettesítéssel:

π0 = 1 − ρ ➤ M/M/1 - rendszer stacionárius valószínűségei:

πk = (1 − ρ)ρk ➤ M/M/1 - rendszer kihasználtsága:

ρ = 1 − π0 ➤ A jobok átlagos száma M/M/1 - rendszer esetén:

K=


ρ 1−ρ


E.197

E.4 Markov-láncok

◆ Zárt csillaghálózat E2-eloszlású kiszolgálási idejű egyik kiszolgálóval:

µ11

µ12

µ2

➤ Jobok száma: K = 2 ➤ Kiszolgálási idők:

–

Kiszolgáló 2: exp. eloszlás, µ2 = 0.4

–

Kiszolgáló 1: E2-eloszlás,ahol a két fázis aránya µ11 = µ12 = 0.4

➤ A hálózat állapotát megadja a csomópontokban lévő jobok száma és az

1-es csomópontban lévő job l = 0, 1, 2 fázisa: (k1, l; k2) ➤ A hálózat stacionárius valószínűsége:

p(k1, l; k2) Performance Modeling of Computer Systems  Gunter Bolch • Universität Erlangen-Nürnberg


E.198

E.4 Markov-láncok

➤ Átmenetdiagram:

µ11 2,1;0

µ12

µ11

µ12

2,2;0

1,1;1

1,2;1

µ2

µ2

µ2

0,0;2


π(2, 1; 0)µ11 π(2, 2; 0)µ12 π(1, 1; 1)(µ11 + µ2 ) π(1, 2; 1)(µ12 + µ2 ) π(0, 0; 2)µ2


= = = = =

π(1, 1; 1)µ2 , π(2, 1; 0)µ11 + π(1, 2; 1)µ2 , π(2, 2; 0)µ12 + π(0, 0; 2)µ2 , π(1, 1; 1)µ11 , π(1, 2; 1)µ12 .


E.199

E.4 Markov-láncok


 −µ11  0  Q=  µ2  0 0

µ11 −µ12 0 µ2 0

 0 0 0 µ12 0 0   −(µ11 + µ2 ) µ11 0   0 −(µ12 + µ2 ) µ12  µ2 0 −µ2

➤ Generátormátrix a kiszolgálási intenzitások értékeivel:

  −0.4 0.4 0 0 0  0 −0.4 0.4 0 0     0 −0.8 0.4 0  Q =  0.4   0 0.4 0 −0.8 0.4  0 0 0.4 0 −0.4



E.200

E.4 Markov-láncok

➤ A πQ = 0 megoldásával vagy a globális egyensúlyi egyenletekkel:

π(2, 1; 0) = 0.2219 , π(2, 2; 0) = 0.3336 , π(1, 1; 1) = 0.2219 , π(1, 2; 1) = 0.1102 , π(0, 0; 2) = 0.1125 . ➤ Marginális valószínűségek:

π1 (0) = π2 (2) = π(0, 0; 2) = 0.1125 , π1 (1) = π2 (1) = π(1, 1; 1) + π(1, 2; 1) = 0.3321 , π1 (2) = π2 (0) = π(2, 1; 0) + π(2, 2; 0) = 0.5555 . ➤ A marginális valószínűségek használatával az összes többi

hatékonyságjellemző számolható.



E.201

E.4 Markov-láncok

◆ Példa: Egyszerű zárt sorbanállási hálózat:

µ2 µ1 µ3

➤ Jobok száma K = 2 ➤ Kiszolgálási idők: exp. el.,: µ1 = 4/sec, µ2 = 1/sec és µ3 = 2/sec ➤ Stratégia: FCFS



E.202

E.4 Markov-láncok

➤ Útvonalvalószínűségek:

p12 = 0.4,

p13 = 0.6

p21 = p31 = 1 ➤ A Markov-lánc állapottere:

{(2, 0, 0), (0, 2, 0), (0, 0, 2), (1, 1, 0), (1, 0, 1), (0, 1, 1)}

➤ Állapot: (k1, k2, k3) → k1 job az 1-es csomópontban, k2 job a 2-es

csomópontban és k3 job a 3-as csomópontban

➤ Stacionárius valószínűségek: π(k1, k2, k3)



E.203

E.4 Markov-láncok

➤ Átmenetdiagram:

2, 0, 0 µ3 p31 µ3 p31

µ1 p21 µ1 p13

µ2 p21

1, 0, 1

0, 0, 2

0, 2, 0

1, 1, 0 µ1 p12

µ1 p13

µ1 p12

µ3 p31

µ2 p21

µ2 p21 µ1 p13

0, 1, 1



E.204

E.4 Markov-láncok

➤ Globális egyensúlyi egyenletek:

(1) π(2, 0, 0)(µ1 p12 + µ1 p13 ) = π(1, 0, 1)µ3 p31 + π(1, 1, 0)µ2 p21 , (2) π(0, 2, 0)µ2 p21 = π(1, 1, 0)µ1 p12 , (3) π(0, 0, 2)µ3 p31 = π(1, 0, 1)µ1 p13 , (4) π(1, 1, 0)(µ2 p21 + µ1 p13 + µ1 p12 ) = π(0, 2, 0)µ2 p21 + π(2, 0, 0)µ1 p12 + π(0, 1, 1)µ3 p31 , (5) π(1, 0, 1)(µ3 p31 + µ1 p12 + µ1 p13 ) = π(0, 0, 2)µ3 p31 + π(0, 1, 1)µ2 p21 + π(2, 0, 0)µ1 p13 , (6) π(0, 1, 1)(µ3 p31 + µ2 p21 ) = π(1, 1, 0)µ1 p13 + π(1, 0, 1)µ1 p12 .



E.205

E.4 Markov-láncok

■ A Globális egyensúlyi egyenletek megoldása: ◆ Iteratív módszer: ➤ Globális egyensúlyi egyenletek: πQ = 0 ➤ Skalárral történő szorzás: πQ∆ = 0 ➤ π hozzáadása mindkét oldalhoz: πQ∆ + π = π ➤ Egységmátrix kiemelése : π(Q∆ + I) = π ➤ Iteráció: π(j+1) = π(j)(Q∆ + I) ➤ ∆ megválasztása aszerint, hogy az iteráció konvergens legyen :

∆ = 1/max |qii| vagy ∆ = 0.99/max |qii|



E.206

E.4 Markov-láncok

◆ Példa: Csillaghálózat: ➤ Generátormátrix:



 −0.2 0.2 0 0  0.4 −0.6 0.2 0   Q=  0 0.4 −0.6 0.2  0 0 0.4 −0.4 ➤ Skalár ∆:

∆=

1 1 = = 1.6667 max |qii | 0.6

➤ Invariáns mátrix:



0.6667  0.6667 (Q∆ + I) =   0 0 Performance Modeling of Computer Systems  Gunter Bolch • Universität Erlangen-Nürnberg

0.3333 0 0.6667 0

0 0.3333 0 0.6667



0  0  0.3333  0.3333


E.207

E.4 Markov-láncok

➤ A kezdeti vektor tetszőlegesen választható:

π (0) = (π(3, 0), π(2, 1), π(1, 2), π(0, 3))(0)

Normalizáló feltétel:

π(3, 0) + π(2, 1) + π(1, 2) + π(0, 3) = 1

➤ A kezdeti vektor:

π (0) = (0.65; 0.35; 0; 0)



E.208

E.4 Markov-láncok

Iteration

π(3, 0)

π(2, 1)

π(1, 2)

π(0, 3)

1 2 3 4 5 6 7 8 9 10 11

0.6667 0.5889 0.5926 0.5580 0.5597 0.5443 0.5450 0.5382 0.5385 0.5355 0.5356

0.2166 0.3000 0.2444 0.2815 0.2568 0.2733 0.2623 0.2696 0.2647 0.2680 0.2658

0.1167 0.0722 0.1259 0.1062 0.1300 0.1213 0.1319 0.1280 0.1327 0.1309 0.1330

0 0.0389 0.0371 0.0543 0.0535 0.0612 0.0608 0.0642 0.0641 0.0656 0.0655

➤ Pontos értékek:



E.209

E.4 Markov-láncok

◆ Az iteratív módszer mindig alkalmazható, de nagyon sok számolási időt és memóriát igényel ◆ Más módszerek (gyorsabbak és kisebb memóriaigényűek): ➤ Stacionárius módszerek: ➤ Hatvány módszer ➤ Jacobi-módszer ➤ Gauß-Seidel-módszer ➤ Többszintű módszer ➤ Tranziens módszerek: ➤ Uniformizálás

π(3, 0) = 0.5333, π(2, 1) = 0.2667, π(1, 2) = 0.1333, π(0, 3) = 0.0667 Performance Modeling of Computer Systems  Gunter Bolch • Universität Erlangen-Nürnberg


E.210

E.4 Markov-láncok

■ A Globális egyensúlyi egyenletek tranziens megoldása: ◆ Globális egyensúlyi egyenletek: πQ = 0 csak a stacionárius eloszlásra érvényesek ◆ A tranziens állapot esetén:

dπ(t) = π(t)Q , dt

π(0) = (π0 (0), π1 (0), . . . )

➤ A tranziens esetben az "állapotba érkezés" és az "ebből az állapotból

távozás" közötti különbség az állapot állapotvalószínűségéből származtatható. ➤ Megoldás nagyon nehéz (Uniformizálás!).



E.211

E.4 Markov-láncok

◆ Példa: Születési folyamat (pl. beérkezések egy sorbanállási halózatba):

λ 0

λ 1

λ 2


 −λ λ  0 −λ  Q= 0 0  .. .. . .


 0 0 ... λ 0 . . .  −λ λ . . .  .. .. . . . . .


E.212

E.4 Markov-láncok

➤ Egyensúlyi egyenletek:

d π0 (t) = −λπ0 (t) , dt d πk (t) = −λπk (t) + λπk−1 (t) , dt

k≥1

➤ Kezdeti feltételek:

1 k=0 πk (0) = 0 k≥1



E.213

E.4 Markov-láncok

➤ A születési folyamat állapotvalószínűsége (Poisson-folyamat, Poisson

eloszlás):

(λt)k −λt πk (t) = , e k!

k≥0

➤ Annak valószínűsége, hogy t idő alatt k születés történt

(k job érkezett) ➤ Annak valószínűsége, hogy t idő alatt történt születés(beérkezés) P( TA >

t ):

π0 (t) = e−λt ➤ Két születés (beérkezés) közötti idő eloszlása: P( TA ≤ t ) = 1 - π0(t) = 1 - e-λt ➤ A beérkezési időközök exponenciális eloszlásúak !! Performance Modeling of Computer Systems  Gunter Bolch • Universität Erlangen-Nürnberg


E.214

E.4 Markov-láncok

1

Poisson eloszlás λ = 0.5 0.8

Probabilities

0.6

0.4

π0 (t)

λ = 0.5

π1 (t) π2 (t) π3 (t)

0.2

π4 (t)

t 0

5


10

15

20


E.215

E.4 Markov-láncok

Poisson eloszlás λ = 1 1

0.8

Probabilities

0.6

0.4

π0 (t)

λ = 1.0

π1 (t) π2 (t) π3 (t)

0.2 π4 (t)

t 0

5


10

15

20


E.216

E.4 Markov-láncok E.4 Markov-láncok. Sok sorbanállási hálózat viselkedése leírható "folytonos idejű Markovláncok " segítségével

Recommend Documents