Eseményvezérelt szimuláció

Hálózati szimulációs technikák (BMEVITTD094/2005) október 3.

Vidács Attila Dang Dinh Trang Távközlési és Médiainformatikai Tanszék Budapesti M szaki és Gazdaságtudományi Egyetem

Eseményvezérelt szimuláció DES – Discrete-Event Simulation A rendszer állapota: (állapot)változók egy halmaza, amelyek egy adott pillanatban meghatározzák a rendszert (megfelel pontossággal). Diszkrét rendszer: A rendszerváltozók értékei diszkrét értékek. A rendszer modelljében az állapotváltozók értéke pillanatszer en változik különböz id pontokban. Ezek az id pontok események bekövetkezésének id pontjai. –

esemény = Pillanatnyi történés amely megváltoztathatja a rendszer állapotát.

Ötlet: A szimulációs id az egyik eseményt l a következ eseményig halad el re. Egy esemény két paraméter határoz meg: – –

2

id pontja (azaz mikor kell az eseményt kezelni) típusa (azaz hogyan kell az eseményt kezelni) Hálózati szimulációs technikák (BMEVITTD094/2005) - Vidács Attila

1

DES végrehajtása 1. Inicializálás – – –

A szimuláció órájának nullázása. A rendszer kezdeti állapotának beállítása. A következ események generálása minden eseménytípusból (ameddig csak lehet), és az eseménylista felállítása.

2. Id léptetése –

A szimuláció órájának állítása a soron következ esemény id pontjára.

3. Eseménykezelés –

–

Az esemény kezelése (az esemény által kiváltott üj események generálása és az eseménylistába illesztése), és a rendszerállapot frissítése. A kezelt esemény eltávolítása a listából.

4. Leállási feltétel –

3

Ha a leállási feltétel igazzá válik, a szimuláció leállítása, ellenkez esetben GOTO 2.

Hálózati szimulációs technikák (BMEVITTD094/2005) - Vidács Attila

DES komponensei és felépítése Rendszerállapot: –

A rendszer (globális) állapotváltozói

Szimulációs óra: –

Az aktuális szimulációs id t tartalmazó globális változó

Eseménylista: –

Az elkövetkez események id pontjainak listája

Statisztikai számlálók: –

A rendszer teljesítményér l statisztikai információkat tároló változók.

Inicializáló rutin: – – –

4

A szimulációs modell t = 0 id pontbeli inicializálására szolgáló alprogram. Beállítja az állapotváltozók kezdeti értékeit és a véletlenszám generátorok „seed” értékeit. Tartalmazhat bemeneti paraméterek bekérését vezérl rutinokat is.


2

DES komponensei és felépítése (2) Id zít rutin (ütemez / scheduler / event list manager): – – –

Karbantartja az eseménylistát Meghatározza a következ esemény id pontját az eseménylistából, és az esemény id pontjára állítja a szimuláció óráját. A szimulátor program magja, a leggyakrabban hívott része a programnak.

Esemény rutin: – – –

Frissíti a rendszer állapotát egy esemény bekövetkezésekor. Új eseményeket generál(hat). Minden eseménytípushoz tartozik egy külön esemény rutin.

Nyomkövet („trace”) rutin: – – –

Közbens értékeket ír a kimenetre a szimuláció futása alatt. A hibajavítást támogatja. Ki/be kapcsolható.

5


DES komponensei és felépítése (3) Könyvtári rutinok: –

Alprogramok csoportja véletlen események el állítására a modellben meghatározott eloszlások alapján.

Riport generátor: – –

A kívánt teljesítmény-paraméterek becslését végzi a statisztikai számlálók értékeib l. A szimuláció végén jelentést készít a kívánt formátumban.

F program: – –

6

A szimulátor komponenseit összef zi. Meghívja az id zít rutint a következ esemény meghatározására, majd átadja a vezérlést a megfelel esemény rutinnak a rendszer állapotának frissítéséhez. A f program ellen rzi a leállási feltételt, majd átadja a vezérlést a riport generátornak a szimuláció végén.


3

start inicializáló rutin

f program

1.

szimulációs óra = 0

0.

init rutin meghívása

2.

Rendszerállapot és számlálók inicializálása

1.

id zít rutin meghívása

3.

Eseménylista inicializálás

2.

esemény rutin meghívása

0

id zít rutin 1

ismételten

i

1.

Köv. esemény típusának meghatározása (i)

2.

Szimulációs óra állítása

esemény rutin (i) 2 1.

Rendszerállapot frissítése

2.

Számlálók állítása

3.

Események generálása és eseménylistához f zése

vége a szimulációnak ?

nem

igen

riport generátor 1.

Paraméterek becslése

2.

Riport generálása

stop

Példa: Egy kiszolgálós sor (folyt.) – esemény rutin, érkezés érkezés

Következ érkezés beütemezése

Sorhossz++

Hibaüzenet és a szimuláció leállítása

i

Foglalt a kiszolgáló?

n

Késleltetés = 0 az adott csomagra; statisztikák gy jtése Késleltetett csomagok száma++

i A sor betelt?

A kiszolgáló állapota foglalt

n Csomag érkezési idjének tárolása

A csomag kiszolgálási idejének ütemezése

return

4

Egyéb szimulációs technikák Folytonos szimuláció – –

Az állapotváltozók folytonosan változnak az id ben. Tipikusan differenciálegyenletek adják meg az összefüggést az állapotváltozók változásának sebessége között.

Kombinált diszkrét-folytonos szimuláció – –

Bizonyos rendszerek se nem diszkrétek, se nem folytonosak. 3 féle kapcsolat lehet diszkrét és folytonos állapotváltozók között: Egy diszkrét esemény hatására egy folytonos állapotváltozó értéke egy diszkrét mennyiséggel változik. Egy diszkrét esemény megváltoztatja egy folytonos állapotváltozó értékét meghatározó összefüggést. Egy folytonos állapotváltozó értékének változása elér egy küszöbértéket, és diszkrét eseményt generál.

9


Egyéb szimulációs technikák (2) Monte Carlo (MC) szimuláció –

– –

10

(Általában) statikus szimuláció: Bizonyos determinisztikus vagy sztochasztikus problémák megoldása véletlenszámok használatával, ahol az id el rehaladása nem játszik lényeges szerepet. Megjegyzés: Egyes szerz k MC szimuláció néven illetnek minden véletlenszámot használó szimulációt. Széles körben használt olyan statisztikai problémák megoldására, amelyek analitikusan nem (vagy csak nagyon nehezen) megoldhatók.


5

Eseményvezérelt szimuláció

Recommend Documents