Ahhoz, hogy teljesen jellemezzünk egy sorbanállási rendszert, azonosítanunk kell azt a sztochasztikus folyamatot, amely a beérkező igényeket írja le, és meg kell adnunk 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, mint valószínűségi változók eloszlásának segítségével jellemezhetjük. Ezt az szimbólummal jelöljük, ahol .

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 (ezért a beérkezési folyamat ún. felújítási folyamatot alkot). A másik sztochasztikus mennyiség, amelyet meg kell adni, a beérkező igények által a csatornával 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 -szel jelöljük, azaz .

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 mennyiségeket kell meghatározni. Ilyen jellemző a rendelkezésre álló kiszolgáló egységek (csatornák, kiszolgálók, szerverek, stb.) száma, valamint a befogadóképesség, ami nem más, mint a kiszolgálóegységben és a várakozási sorban tartózkodó igények maximális száma, amit gyakran végtelennek tekintünk. A kiszolgálási sorrend írja le azt a szabályt, amely szerint a várakozók közül sorra kerülnek az egyes igények kiszolgálás céljából. A leggyakrabban használt kiszolgálási elvek: FIFO (First In, First Out) érkezési sorrendben; LIFO (Last In, First Out) fordított sorrendben történő kiszolgálások. Ha a beérkező igényeket bizonyos csoportokba tartozás szerint meg lehet különböztetni, akkor a csoportok között prioritást lehet megállapítani, és 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 a kiszolgálás megszakad, és újra beáll a várakozási sorba. He legközelebb rákerül a kiszolgálás, akkor az kezdődhet az elejétől vagy a megszakítás helyétől. A relatív prioritásos esetben a fontosabb igény beérkezésekor a kiszolgálás nem szakad meg, hanem folytatódik, majd a befejezéskor a legfontosabb várakozó igény kiszolgálása kezdődik.

A sorbanállási rendszerek hatékonyságának és teljesítményének vizsgálatához a következő rendszerjellemzőket igyekszünk meghatározni: az igények várakozási ideje; a rendszerben levő igények száma; a foglaltsági intervallum hossza (vagyis az a folytonos időintervallum, amelyben a kiszolgáló egység állandóan foglalt); az üresjárati időszakasz hossza; a pillanatnyi munkahátralék eloszlása. 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 mennyiségekkel.

Az elemi sorbanállási elmélet egyrészt történeti okokból fontos, másrészt pedig azért, mert alkalmas arra, hogy szemléltesse a bonyolultabb sorbanállási rendszerek jellemzőit is.

Az 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 egy dimenzió nélküli mennyiség, amelyet a következőképpen lehet definiálni:

Feltételezzünk egy végtelen populációjú modellt, jelöljük a beérkezési intenzitást -val, ami nem más, mint az átlagos beérkezési időköz reciproka, valamint az átlagos kiszolgálási időt -vel. Ekkor a következőt kapjuk:

Az -nél nagyobb forgalmi intenzitás azt mutatja, hogy az igények gyorsabban érkeznek, mint ahogy egy szerver (kiszolgálóegység, csatorna) ki tudná szolgálni őket.

Jelölje az esemény karakterisztikus függvényét, azaz

és azt az eseményt, hogy a kiszolgáló tétlen a időpillanatban. Ekkor a szerver időegységre eső kihasználtsága

ahol egy elegendően hosszú időintervallum. Ha esetén a fenti mennyiségnek létezik határértéke, akkor a szerver kihasználtságán ezt az -sel jelölt mennyiséget értjük. Továbbá valószínűséggel fennáll

ahol annak stacionárius valószínűsége, hogy a szerver tétlen, a kiszolgáló egység átlagos foglaltsági periódushosszát, pedig az átlagos tétlenségi periódushosszát jelöli.

Ez az összefüggés Markov-folyamatoknál speciális esete a következő, gyakran felhasználható relációnak, amelynek magyar nyelvű bizonyítása megtalálható Tomkó József cikkében [ 77 ].

10.1. Tétel. Legyen egy ergodikus Markov-folyamat, pedig állapotterének egy részhalmaza. Látható, hogy az idő folyamán felváltva tartózkodik -ban és -ban. Ekkor valószínűséggel

ahol és az ill. az részhalmazban való átlagos tartózkodási időt jelöli egy ciklus alkalmával, pedig az folyamat ergodikus eloszlása.

Egy párhuzamos szerverből álló rendszerben T idő alatt átlagosan igény érkezik szerverenként, feltéve, hogy a forgalom egyenletes eloszlású az kiszolgáló egység között. Ha minden beérkezett kérés kiszolgálása átlagosan ideig tart, akkor egy adott szerver teljes foglaltsági idejének várható értéke . Osszuk el ezt a mennyiséget -vel, így

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

A másik gyakran használt teljesítménymérő eszköz a rendszer átbocsátóképességének vizsgálata. Ezt a mennyiséget úgy definiálhatjuk, mint az időegységként kiszolgált igények átlagos számát: szerveres rendszerben minden időegység alatt igény kiszolgálása fejeződik be, így az

Ez azt jelenti, hogy az átbocsátóképesség ekvivalens a érkezési intenzitással ha a kisebb, mint a maximális kiszolgálási sebesség (), azon túl az átbocsátóképesség beáll -re.

Az igények szempontjából a legjelentősebb teljesítménymérő eszköz az az idő, amit a várakozási sorban vagy a rendszerben töltenek. Definiáljuk a várakozási időt, mint a -dik igény várakozási sorban eltöltött idejét, és a 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:

ahol a kiszolgálási időt jelöli. és is valószínűségi változó, várható értékük és 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 valószínűségi változó jelentse a időpillanatban a sorban található igények számát, és a 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 szerveres rendszer esetén: