12.8. 12.8. A  modell | ||
|---|---|---|
| Előző | 12. fejezet - Véges-forrású rendszerek | Következő |
Ennek a modellnek a leírása Sztrik [ 70 ] cikkében található meg.
Tekintsünk egy olyan számítógépes rendszert, amely központi egységekből, terminálokból, és jobokból áll. Minden job egy terminállal van kapcsolatban, ahol nincs várakozás. Sorok csak a központi egységeknél fordulhatnak elő. Az ilyen rendszerek elemzéséhez szintén véges forrású sorbanállási modellt használunk.
Legyen a rendszerben lévő jobok száma 
, és a központi egységek száma 
. A job bizonyos időt tölt el a terminálnál, ezután a központi egységbe kerül, ahol a job kiszolgálása azonnal megkezdődik, ha az 
központi egység között van szabad, egyébként sor alakul ki. A jobokat érkezésük sorrendjében szolgálják ki, és kiszolgálási idejük azonos 
paraméterű exponenciális eloszlású valószínűségi változó. A job kiszolgálásának befejeződése után visszatér a termináljához, ahol véletlen hosszúságú ideig tartózkodik. A 
-edik job terminálnál eltöltött ideje 
eloszlásfüggvénnyel és 
sűrűségfüggvénnyel rendelkező 
valószínűségi változó. Továbbá feltesszük, hogy a konstrukcióban fellépő valószínűségi változók teljesen függetlenek.
Jelölje a 
valószínűségi változó a 
időpontban a terminálnál lévő jobok számát, 
ezeknek a joboknak az indexeit lexikografikus sorrendben, és
a központi egységnél lévő (kiszolgálás alatt lévő vagy sorbanálló) jobok indexeit érkezésük sorrendjében. Az
folyamat csak akkor Markov-folyamat, ha az 
eloszlásfüggvények exponenciálisak.
Vezessük be a 
változót, amely azt az időt jelöli, amelyet az 
job a terminálnál eltöltött a legutolsó központi egységbeli kiszolgálása óta. Az így kapott
folyamat rendelkezik a Markov tulajdonsággal.
Jelölje 
és 
az 
egészek 
-ad osztályú variációinak illetve a kombinációinak lexikografikusan rendezett halmazát. Ekkor az 
folyamat állapottere az olyan
pontokból áll, ahol
Az 
folyamat akkor van az 
állapotban, ha az
indexű jobok már 
ideje vannak a termináloknál, és 
a központi egységnél lévő jobok indexe érkezési sorrendben.
A Kolmogorov-egyenletek levezetéséhez szükségünk van tetszőleges 
intervallumban lejátszódó átmenetek vizsgálatára. Az átmeneti valószínűségeket a következő módon adhatjuk meg 
esetére.
ahol 
az 
indexeket jelöli lexikografikus sorrendben, és 
a megfelelő időket.
Ha 
akkor az átmeneti valószínűségek a következők
Vezessük be a következő függvényeket
Legyen 
a következőképpen definiálva: 
.
12.5. Tétel.
Ha 
, 
, akkor az 
folyamatnak van egyértelmű ergodikus ( stacionárius ) eloszlása, amely független a kezdeti feltételektől, azaz
A tétel bizonyítása Gnedenko-Kovalenko [ 23 ] könyvének 211. oldalán található tételből következik.
A tétel biztosítja a következő határértékek létezését, és egyértelműségét
ahol 
jelöli az 
állapotok sűrűségfüggvényét, ha 
. Feltesszük, hogy rögzített 
-ra az ergodikus eloszlásoknak létezik a sűrűségfüggvénye. Ehhez elegendő feltenni, hogy az 
-nek van sűrűségfüggvénye.
Vezessük be a
ún. normált sűrűségfüggvényeket!
12.6. Tétel. A fenti normált sűrűségfüggvények kielégítik a (12.3), (12.5) integro-differenciál-egyenleteket a (12.4), (12.6) határfeltételek mellett.
, 
esetén,
, 
esetén,
valamint
A 
jelentése a bizonyításban szerepel, és
Bizonyítás. Mivel 
Markov-folyamat, ezért sűrűségfüggvényei kielégítik a Kolgomorov-Chapman egyenleteket. Tekintsük a folyamatot rövid 
ideig. Ekkor a következő összefüggések igazak:
, 
esetén.
Hasonlóan
, 
esetén.
Végül
Ezekből az összefüggésekből a tétel állítását könnyen megkaphatjuk. A felírt összefüggések bal oldalát 
-val osztva, és figyelembe véve a normált sűrűségfüggvény definícióját, és 
határértéket véve kapjuk a tétel állítását.
A tétel (12.3)(12.5) egyenlőségeinek bal oldalán a parciális differenciálhányados szokásos jelölését használtuk fel. Ezt általában nem tehetjük meg, mivel a parciális differenciálhányados létezését nem tettük fel. Ezért használtuk a 
jelölést. Valójában 
az 
iránymenti deriváltat jelenti. A
ergodikus eloszlás meghatározásához meg kell oldani a (12.3)(12.5) egyenleteket a (12.4)(12.6) határfeltételek mellett. Legyen
Ekkor behelyettesítéssel ellenőrizhető, hogy kielégítik az 
, 
egyenleteket a 
, 
határfeltételek mellett, és ezek a 
értékek rekurzióval kifejezhetők 
függvényében. Nevezetesen
Ezek az egyenletek teljesen leírják a rendszer működését.
Jelölje 
annak a stacionárius valószínűségét, hogy a termináloknál az 
indexű jobok vannak, és a központi egységnél lévő jobok indexei érkezési sorrendben 
. Továbbá 
jelölje annak a stacionárius valószínűségét, hogy az 
indexű jobok tartózkodnak a termináloknál.
Ezek után könnyen igazolható, hogy
A 
-ra kapott összefüggést felhasználva kapjuk, hogy
Hasonlóan
Jelölje 
és 
annak a stacionárius valószínűségét, hogy a termináloknál 
, illetve a központi egységeknél 
job tartózkodik. Ekkor világos, hogy
Könnyen belátható, hogy
ahol 
a 
normalizáló feltételéből határozható meg.
Homogén esetben a következő eredményekhez jutunk
Ezért
Ezek az eredmények megegyeznek az 
modell stacionárius valószínűségeire kapott képletekkel. Látható, hogy ezek az 
eloszlásfüggvény alakjától nem függnek, csak az 
várható értékektől.
1. A terminálok kihasználtsága
Jelölje 
annak a stacionárius valószínűségét, hogy az 
-edik job a terminálnál tartózkodik, vagyis
Nyilvánvalóan az 
-edik terminál kihasználtsága
2. A CPU-k kihasználtsága
Az eddigiekhez hasonlóan egy konkrét CPU kihasználtsága
ahol 
a foglalt CPU-k átlagos számát jelöli. Így a CPU-k összkihasználtsága 
.
3. átlagos várakozási és tartózkodási idők
Így az 
-edik job átlagos várakozási ideje:
Az 
-edik job központi egységnél eltöltött átlagos 
ideje ( várakozással és kiszolgálással eltöltött idő )
Mivel
ahol 
jelöli a központi egységnél levő jobok átlagos számát, megkapjuk a
modellre vonatkozó Little-formulát
Meg kell jegyeznünk, hogy a gépkiszolgálási probléma terminológiáját használva 
az 
-edik gép kihasználtságát, 
az 
-edik gép várakozási ill. rossz állapotban való átlagos tartózkodási idejét adja.
A modell tovább általánosítható oly módon, hogy pl. a kiszolgálási intenzitások függnek a rendszer állapotától, lásd Sztrik [ 68 ], [ 69 ].
rendszer