II. Elemi sorbanállási elmélet


A sorbanállási elméletre vonatkozó "elemi" jelző azt fejezi ki, hogy olyan rendszereket vizsgálunk, amelyek tiszta Markov-folyamatok, és ennek következtében az állapotátmenetek leírására egyszerű, könnyen kezelhető összefüggéseket kapunk. Az előző fejezetben azokkal az egyenletekkel foglalkoztunk, amelyek a születési-halálozási folyamatok abszolút valószínűségeit az időtől függetlenül írták le. A (3) összefüggés a fejezet lényeges eredménye; a továbbiakban ennek egyszerű alkalmazásaival foglalkozunk. A későbbiek során a következőképpen járunk el. Bevezetünk egy $X(t)$ sztochasztikus folyamatot, ami a $t$-edik időpillanatban a kiszolgáló egységnél tartózkodó igényeket jelöli majd. A beérkezési és kiszolgálási folyamatok eloszlásainak felhasználásával megadjuk a $h$ időintervallum alatti átmeneti valószínűségeket. Ha -- feltevésünk szerint -- a fellépő eloszlások exponenciálisak, az $X(t)$ folyamat Markov-típusú lesz, sőt születési-halálozási folyamat. Konkrét rendszereknél mindig meghatározzuk a születési, halálozási intenzitásokat, és ezek felhasználásával megkeressük az egyenletrendszer megoldását. Ezt követően kiszámítjuk a rendszer működésére vonatkozó jellemzőket (pl. átlagos sorhossz, kihasználtságok, átlagos várakozási idő stb.) Az előbbi fejezetben a sztochasztikus folyamatok különböző osztályait tanulmányoztuk. Kiemeltük, hogy a sorbanállási rendszerek vizsgálatában alapvető szerepük van a Markov-folyamatoknak. Ezen belül is egy speciális Markov-folyamatot vizsgáltunk meg - a születési-halálozási folyamatot. Megmutattuk, hogy a születési-halálozási folyamatoknak -- a számításokban -- az az igen ,,jó'' tulajdonságuk van, hogy mind a születések, mind a halálozások közötti idő exponenciális eloszlású (ami közvetlen következménye annak, hogy ezek Markov-folyamatok - feltéve, hogy a rendszer nem üres). Ezután megadtuk a folyamat állapotegyenleteit. Jelen fejezetben ezeknek az egyenleteknek határátmenet útján adódó alakjait vizsgáljuk, így a születési-halálozási sorbanállási rendszerek stacionárius viselkedését kapjuk meg. Az elemi sorbanállási elmélet egyrészt történeti okokból, másrészt pedig azért fontos, mert alkalmas arra, hogy szemléltesse a bonyolultabb sorbanállási rendszerek jellemzőit. A kapott eredmények betekintést nyújtanak sok egyéb sorbanállási rendszer viselkedésébe. Nem szabad elfelejtenünk, hogy a születési-halálozási folyamat miképpen felel meg a sorbanállási rendszereknek. Pl. tekintsünk egy orvosi várószobát (amelyben esetleg várakozni kell), és tekintsünk egy orvosi rendelőt, mint egy kiszolgálóegységet. Minden egyes időpontot, amikor egy páciens belép az utcáról a várószobába, úgy tekintünk, mint egy igény beérkezését a sorbanállási rendszerbe; másrészt ezt a beérkezést úgy is fel lehet fogni, mint egy populáció új tagjának születését - a populációt a jelenlevő páciensek alkotják. Hasonlóképpen, amikor (kezelés után) egy páciens elhagyja a rendelőt, ezt mint a sorbanállási rendszerből való távozást tekintjük, a születési-halálozási folyamat terminológiájában ez a populáció egy tagjának halálát jelenti. A $\lambda_k$ születési és a $\mu_k$ halálozási együtthatók szabad választásával különféle sorbanállási rendszerek konstruálására van lehetőségünk, mint ezt rövidesen látni fogjuk. Először azonban határozzuk meg a stacionárius megoldásokat az általános esetre.

{\Cim \'Altal\'anos stacion\'arius megold\'as}

Az előző fejezetben láttuk, hogy a születési-halálozási folyamatok időtől függő megoldása gyakorlatilag kezelhetetlenné válik, amint bonyolultabb születési-halálozási $\lambda_k$, $\mu_k$ intenzitásokat veszünk. Továbbá, még ha a $P_k(t)$ függvényeket meg is tudnánk határozni, nem világos, mennyire segít minket ez a függvényhalmaz abban, hogy jobban át tudjuk tekinteni a sorbanállási rendszer viselkedését. Ezért természetes, hogy azt kérdezzük, vajon a $P_k(t)$ valószínűségek $t$ növekedésével megállapodnak-e végül is (stabilizálódnak-e), megszűnik-e időbeli változásuk, beáll-e stacionárius állapot. Legyen

\begin{displaymath} P_k:=\lim\limits_{t\to\infty}P_k(t), \end{displaymath}

ahol $P_k$ jelenti azon esemény valószínűségét, hogy a rendszer hosszú működés után a $k$ állapotban van. Nagyon fontos, hogy megértsük: jóllehet a $P_k$ mennyiségek ( feltéve, hogy léteznek ) nem a $t$ függvényei, ebből nem következik, hogy a határesetben nem megy át a folyamat az egyik állapotból a másikba. A populáció tagjainak száma változik az idővel, azonban annak valószínűségét, hogy a rendszer $k$ tagú lesz, nagy $t$-re éppen $P_k$ adja meg. Feltételezve, hogy a konstans határérték létezik, a születési-halálozási folyamatokra felírt (29, 30) egyenletekben a $\lim\limits_{t\to\infty}{dP_k(t) \over dt}$ mennyiséget nullával tehetjük egyenlővé. Ebből azonnal egy lineáris egyenletrendszer adódik

\begin{displaymath}0=-(\lambda_k+\mu_k)P_k+\lambda_{k-1}P_{k-1}+\mu_{k+1}P_{k+1},\qquad\hbox{ ha } k\geq 0, \leqno(1)\end{displaymath}

feltételezve, hogy $\mu_0=\lambda_{-1}=0$. Megköveteljük, hogy ez a teljes eseményrendszer is legyen, melyre normalizáló feltételként hivatkozunk majd :

\begin{displaymath} \sum_{k=0}^\infty P_k=1. \leqno(2) \end{displaymath}

Egyensúlyi helyzetben a befelé irányuló folyamnak egyenlőnek kell lennie a kifelé irányuló folyammal. A $k$ állapotra koncentrálva megfigyelhetjük, hogy - a beáramlás intenzitása a $k$ állapotba = $\lambda_{k-1}P_{k-1}+\mu_{k+1}P_{k+1}$, - a kiáramlás intenzitása a $k$ állapotból = $(\lambda_k+\mu_k)P_k$. Egyensúlyi helyzetben ez a két érték meg kell, hogy egyezzen, így azonnal kapjuk, hogy

\begin{displaymath} \lambda_{k-1}P_{k-1}+\mu_{k+1}P_{k+1}=(\lambda_k+\mu_k)P_k. \end{displaymath}

Amint azt az $I.3.$ részben láttuk

\begin{displaymath} \lambda_{k-1}P_{k-1}=\mu_kP_k , \end{displaymath}

és az általános megoldás könnyen adódik

\begin{displaymath} P_k={\lambda_0\lambda_1...\lambda_{k-1} \over \mu_1\mu_2...\mu_k}P_0. \end{displaymath}

Az összes $P_k$ valószínűséget az intenzításokkal és az egyetlen ismeretlen $P_0$ állandóval fejeztük ki:

\begin{displaymath} P_k=P_0\prod_{i=0}^{k-1}{\lambda_i \over \mu_{i+1}},\qquad k=0,1,2,... . \leqno(3) \end{displaymath}

(Az üres szorzat értéke definíció szerint $1$.) A normalizáló feltétel segítségével meghatározhatjuk a $P_0$-t, nevezetesen

\begin{displaymath} P_0={1 \over 1+\sum\limits_{k=1}^\infty\prod\limits_{i=0}^{k-1}{\lambda_i \over \mu_{i+1}}}. \end{displaymath}

Ez a szorzatalakú megoldás az egyik legfontosabb egyenlete az elemi sorbanállási elméletnek. Most megvizsgáljuk a $P_k$ stacionárius valószínűségek létezésének feltételeit. Pontosabban azt kell megnézni, hogy ezek a mennyiségek valóban valószínűségeloszlást alkotnak-e. Ehhez viszont az szükséges, hogy a $P_0>0$ legyen. Ez az egyenletekben szereplő születési és halálozási együtthatókra ró ki feltételt. Lényegében azt követeljük meg, hogy a rendszer alkalomadtán üres is legyen. Az, hogy ez feltétele a stabilitásnak rögtön ésszerűnek látszik. Pontosabban osztályozhatjuk a lehetőségeket, ha előbb definiáljuk az alábbi két összeget:

\begin{displaymath}S_1:=\sum\limits_{k=0}^\infty\prod\limits_{i=0}^{k-1}{\lambda_i \over \mu_{i+1}},\end{displaymath}


\begin{displaymath}S_2:=\sum\limits_{k=0}^\infty{1 \over \lambda_k\prod\limits_{i=0}^{k-1}{\lambda_i \over \mu_{i+1}}}.\end{displaymath}

Azt mondjuk, hogy a születési-halálozási folyamat minden egyes állapota ergodikus, ha

\begin{displaymath} S_1<\infty , S_2=\infty ; \end{displaymath}

rekurrens nulla, ha

\begin{displaymath} S_1=\infty , S_2=\infty ; \end{displaymath}

átmeneti (tranziens), ha

\begin{displaymath} S_1=\infty , S_2<\infty . \end{displaymath}

Az ergodikus esetben $P_0>0$, és ekkor kapjuk a $\{P_k\}$ stacionárius valószínűségeket. Ez a legfontosabb eset számunkra. Az ergodikusság elégséges feltétele teljesül, ha a $\{\lambda_k/\mu_k\}$ sorozat egy bizonyos $k$ értéktől kezdve végig $1$ alatt marad, pontosabban ha létezik valamilyen $k_0$ pozitív egész szám és $\varepsilon>0$ úgy, hogy minden $k\geq k_0$ értékre fennáll

\begin{displaymath} {\lambda_k \over \mu_k}<1-\varepsilon. \end{displaymath}

A legtöbb megvizsgálandó sorbanállási rendszerben teljesül ez a feltétel.

{\Cim A sorban\'all\'asi rendszerek jellemzői}

Ahhoz, hogy egy sorbanállási rendszert teljesen jellemezzünk, meg kell adnunk azt a sztochasztikus folyamatot, amely a beérkező igényeket írja le, és le kell írnunk a kiszolgálás szabályait és struktúráját. A beérkező folyamatot általában az egymás után beérkező igények közötti időintervallumok valószínűségeloszlása segítségével írjuk le. Ezt az $A(t)$ szimbólummal jelöljük, ahol $A(t)=P($két egymás utáni beérkezési időköz$ \le t).$


A sorbanállás elméletében többnyire feltesszük, hogy az egymás utáni beérkezések közötti időközök (röviden beérkezési időközök), azonos eloszlású független valószínűségi változók (a beérkezési folyamat ún. {\dlt fel\'uj\'\i t\'asi folyamatot} alkot). A másik sztochasztikus mennyiség, amit meg kell adni, a beérkező igények által a feldolgozással szemben támasztott követelmények (munka) nagysága; ezt kiszolgálási időnek nevezzük és valószínűségeloszlását $B(x)$-szel jelöljük, azaz


$B(x)=P($kiszolgálási idő$\le x).$


A kiszolgálás ideje annak az időintervallumnak a hosszát jelenti, amelyet az igény a kiszolgáló egységben eltölt.


A kiszolgálás szabályára és struktúrájára vonatkozóan további menynyiségeket kell meghatározni. Az egyik a befogadóképesség, ami nem más, mint a várakozó sor maximális hossza. Ezt rendszerint $K$-val jelöljük, és értékét gyakran végtelennek tekintjük. Egy további jellemző a rendelkezésre álló kiszolgáló állomások (csatornák) száma. A kiszolgálási elv adja meg az igények kiszolgálásának sorrendjét. A leggyakrabban használt kiszolgálási elvek : FIFO (First In - First Out) - érkezési sorrendben; LIFO (Last In - First Out) - fordított sorrendben; SIRO (Service In Random Order) - véletlen sorrendben történő kiszolgálások. Ha a beérkező igényeket bizonyos csoportokba tartozás szerint meg lehet különböztetni, és a csoportok között prioritást lehet megállapítani, akkor ezen a prioritáson alapul a kiszolgálás sorrendje. Ez az egyik legalkalmasabb ütemezési elv, mivel így az igények közötti fontossági sorrendet felállítva történik a kiszolgálás. A prioritásos sorbanállási elvnek két fő típusa van: abszolút és relatív. Az előbbi azt jelenti, hogy ha egy igény kiszolgálása folyamatban van, és érkezik egy magasabb prioritású igény, akkor az éppen kiszolgálás alatt álló folyamat kiszolgálása megszakad, és újra beáll a várakozási sorba, míg a magasabb prioritású kiszolgálása elkezdődik. Relatív priorításnál a kiszolgálás nem szakad meg, hanem annak végeztével a kiszolgáló a legmagasabb priorítással rendelkező igénnyel folytatja munkáját. A számítógéprendszerek egyik leggyakoribb kiszolgálási elve a TS (Time Sharing) vagy más terminológiával RR (Round Robin) -- időosztásos diszciplina --, ami a következőt jelenti. A kiszolgálásra várakozó jobok mindegyikét a CPU bizonyos $q$, ú.n. kvantum ideig szolgálja ki. Ha ennyi idő alatt a job kiszolgálása teljesen befejeződik, akkor távozik a CPU-tól, ha nem, akkor ismét beáll a várakozók sorába. Ez az elv azt eredményezi, hogy a rövid CPU időt igénylő jobok nem tartózkodnak sokáig a CPU-nál. Mivel ezt az elvet elég nehéz matematikailag modellezni, vagyis megfelelő sztochasztikus folyamatot konstruálni hozzá, ezért szívesebben foglalkozunk ezen elv határesetével, amikor is a $q$ nagyon kicsi. Ekkor kapjuk az ú.n. PS (Processor Sharing) -- osztott processzoros -- kiszolgálási diszciplinát. Ekkor, ha $\Delta t$ idő alatt $k$ job tartózkodik a CPU-nál, akkor mindegyik kiszolgálása folyik, de nem $1$, hanem $1/k$ intenzitással. Vagyis $\Delta t$ idő alatt mindegyik job igényelt kiszolgálási idejéből $\Delta t/k$ egység telt el.


A sorbanállási rendszerek hatékonyságának és teljesítményének vizsgálatához a következő mérőszámokat fogjuk meghatározni: az {\dlt ig\'enyek v\'arakoz\'asi ideje}; a rendszerben levő igények száma; a {\dlt foglalts\'agi intervallum hossza} (vagyis az a folytonos időintervallum, amelyben a kiszolgálós egység állandóan foglalt); az üresjárati időszak hossza; a pillanatnyi munkahátralék nagysága. Mindegyik mennyiség valószínűségi változó, és így teljes valószínűségszámítási jellemzésüket (vagyis eloszlásfüggvényüket) keressük, amit általában nehéz megadni, így sokszor megelégszünk az átlagos menynyiségekkel és szórásokkal. Az elemi sorbanállási elmélet egyrészt történeti okokból, másrészt pedig azért fontos, mert alkalmas arra, hogy a bonyolultabb sorbanállási rendszerek jellemzőit is meg lehessen határozni.


Egyszerűség kedvéért tekintsünk először egy egykiszolgálós rendszert. A sorbanállási rendszerek teljesítményének mérésére legalkalmasabb eszköz a torlódás vizsgálata. Legyen $\varrho$ a következő dimenzió nélküli menynyiség:

\begin{displaymath} \varrho = \hbox{forgalmi intenzit\'as} = {\hbox{\'atlagos k... ...'asi idő}\over \hbox{\'atlagos be\'erkez\'esi idők\uml oz}}. \end{displaymath}

Az $1$-nél nagyobb forgalmi intenzitás azt mutatja, hogy az igények gyorsabban érkeznek, mint ahogy egy kiszolgálóegység (szerver, csatorna) ki tudná szolgálni őket. Jelölje $\chi(A)$ az $A$ esemény karakterisztikus függvényét, azaz

\begin{displaymath} \chi(A)=\cases{1&\hbox{, ha $A$ teljes\uml ul,}\cr 0&\hbox{, ha nem $A$ teljes\uml ul} ,} \end{displaymath}

és $X (t)=0$ azt az eseményt, hogy a kiszolgáló tétlen a $t$ időpillanatban. Ekkor a szerver időegységre eső kihasználtsága a $[0,T]$ intervallumon

\begin{displaymath} {1 \over T}\int\limits_0^T\chi\left(X(t)\ne 0\right)dt\ , \end{displaymath}

Ha $T\to\infty$ esetén a fenti mennyiségeknek létezik határértéke, akkor a szerver kihasználtságán ezt az $U_s$-sel jelölt mennyiséget értjük. Továbbá $1$ valószínűséggel fennáll

\begin{displaymath} U_s=\lim_{T\to\infty}{1 \over T}\int\limits_0^T\chi\left(X(t)\ne 0\right) dt=1-P_0={E\delta \over E\delta + Ei} ,\leqno(4) \end{displaymath}

ahol $P_0$ annak stacionárius valószínűsége, hogy a szerver tétlen, $E\delta$ a kiszolgáló egység átlagos foglaltsági periódushosszát, $Ei$ pedig az átlagos tétlenségi periódushosszát jelöli. (Lásd pl. Cohen (1976, 1982), Ross (1970))

A (4) összefüggés Markov-folyamatoknál speciális esete a következő, gyakran felhasználható relációnak. Legyen $X(t)$ egy ergodikus Markov-folyamat, $A$ pedig diszkrét állapotterének egy részhalmaza. $X(t)$ az idő folyamán felváltva tartózkodik $A$-ban és $\overline{A}$-ban. Ekkor $1$ valószínűséggel

\begin{displaymath}\lim_{T\to \infty} {1\over T}\left( \int\limits_0^T \chi(X(t) \in A) dt \right)=\sum_{i \in A} P_i \leqno(5)\end{displaymath}


\begin{displaymath}= { m(A) \over m(A) + m(\overline{A}) } ,\end{displaymath}

ahol $m(A)$ és $m(\overline{A})$ az $A$ ill. az $\overline{A}$ részhalmazban való átlagos tartózkodási időt jelöli egy visszatérés alkalmával, $P_i$ pedig az $X(t)$ folyamat ergodikus eloszlása. (Lásd Tomkó (1981, 1982)) Egy $m$ párhuzamos szerverből álló rendszerben $T$ idő alatt átlagosan $\lambda T/m$ igény érkezik szerverenként, feltéve, hogy a forgalom egyenletesen kerül elosztásra az $m$ kiszolgáló egység között. Ha minden beérkezett kérés kiszolgálása átlagosan $1/\mu$ ideig tart, akkor egy szerver teljes foglaltsági idejének várható értéke $\lambda T/m\mu$, így

\begin{displaymath} \varrho={\lambda \over m\mu}. \end{displaymath}

Mivel a kihasználtság maximum $1$ lehet, így az $m$ szerveres rendszer kihasználtsági tényezőre vonatkozó korrekt kifejezés:

\begin{displaymath} \varrho=\min\left\{{\lambda \over m\mu},1\right\}. \end{displaymath}

Másik gyakran használt teljesítménymérő mutató a számítógépes rendszerek sorbanállási modelljének analízisében a rendszer átbocsátóképessége. Ezt a mennyiséget úgy definiálhatjuk, mint az időegységenként kiszolgált igények átlagos számát. $m$ szerveres rendszerben minden időegység alatt átlag $m\varrho\mu$ igény kiszolgálása fejeződik be, így az

\begin{displaymath} \hbox{\'atbocs\'at\'ok\'epess\'eg}=m\varrho\mu=\min\{\lambda ,m\mu\}. \end{displaymath}

Ami azt jelenti, hogy az átbocsátóképesség ekvivalens a $\lambda$ érkezési intenzitással, amennyiben a $\lambda$ kisebb, mint a maximális kiszolgálási sebesség ($m\mu$), azon túl az átbocsátóképesség beáll $m\mu$-re.


Az igények szempontjából a legjelentősebb teljesítménymérő eszköz az az iidő, amit egy igény a várakozási sorban vagy a rendszerben tölt. Definiáljuk a $W_j$ várakozási időt, mint a $j$-edik igény várakozási sorban eltöltött idejét, és a $T_j$ válaszidőt, mint az igény által e rendszerben eltöltött teljes időt. Ezen jelöléseket használva a következő egyenlőséget kapjuk:

\begin{displaymath} T_j=W_j+S_j, \end{displaymath}

ahol $S_j$ a kiszolgálási időt jelöli. $W_j$ és $T_j$ is valószínűségi változó, várható értékük $\overline{W_j}$ és $\overline{T_j}$ alkalmas a rendszer teljesítményének mérésére. A rendszer teljesítményének vizsgálata történhet a várakozási sor hosszának mérésével is. A $Q(t)$ valószínűségi változó jelentse a $t$ időpillanatban a sorban található igények számát, és $N(t)$ a $t$ időpillanatban a rendszerben található igények számát. Egy rendszerben levő igény vagy a várakozási sorban van, vagy éppen kiszolgálás alatt áll, tehát $m$ szerveres rendszer esetén:

\begin{displaymath} Q(t) = \max\{0,N(t)-m\} . \end{displaymath}

Mielőtt rátérnénk az elemi sorbanállási rendszerek vizsgálatára, néhány, Kendalltól származó jelölést vezetünk be, melyek segítségével osztályozhatjuk a rendszereket. A következő jelölés általánosan használt: N/A/B/m/K, ahol


N: az igényforrások száma, A: a beérkezési időközök eloszlásfüggvénye, B: a kiszolgálási idő eloszlásfüggvénye, m: a kiszolgálók száma, K: a várakozási sor kapacitása.


Ha az A és B eloszlások exponenciálisak, akkor az M jelölést (Markov) használjuk. Továbbá, ha a befogadóképesség és az igényforrás számossága végtelen, akkor ezeket a jelöléseket elhagyjuk. Így pl. az M/M/1 szimbólum, egy egy kiszolgálós Poisson beérkezéssel és exponenciális kiszolgálási idővel jellemzett rendszert jelöl. Az M/G/m rendszernél a beérkezések Poisson-folyamat szerint történnek, a kiszolgálási idők általános eloszlásúak, és $m$ szerver áll rendelkezésünkre. Az N/M/M/r rendszer esetén az igények $N$ forrásból származnak ahol exponenciális eloszlású ideig tartózkodnak, a kiszolgálást $r$ egység végzi exponenciális eloszlású ideig.

Nyitólap    Tartalomjegyzék    Fejezetek ( B I II III IV F )    Letöltések
FRAME-mel FRAME nélkül
<<   Előző Következő  >>