Eilių teorija – komunikacinių ir kompiuterinių sistemų analizės įrankis (0)
Įsivaizduokime paprasčiausią aptarnavimo sistemą su viena eile ir vienu aptarnavimo įrenginiu. Paraiškos atvyksta atsitiktiniais laiko momentais ir jeigu aptarnavimo įrenginys užimtas stoja į eilę.
Prisijunk prie technologijos.lt komandos!
Laisvas grafikas, uždarbis, daug įdomių veiklų. Patirtis nebūtina, reikia tik entuziazmo.
Sudomino? Užpildyk šią anketą!
Įsivaizduokime paprasčiausią aptarnavimo sistemą su viena eile ir vienu aptarnavimo įrenginiu. Paraiškos atvyksta atsitiktiniais laiko momentais ir jeigu aptarnavimo įrenginys užimtas stoja į eilę.
Tokia abstrakti aptarnavimo sistema gali būti daugelio realių objektų modelis. Pvz., jeigu aptarnavimo sistema yra eilė parduotuvėje, tai aptarnavimo įrenginys ko gero reikštų pardavėją, paraiška – pirkėją, kuris stoja į eilę, jeigu aptarnavimo įrenginys, arba serveris – pardavėjas šiuo metu aptarnauja kitą paraišką – t.y., pirkėją.
Jeigu tarpai tarp gretimų atvykstančių paraiškų ir paraiškų aptarnavimo laikai yra atsitiktiniai dydžiai, įvairios sistemos charakteristikos (pvz., vidutinis eilės ilgis, vidutinis laukimo laikas ir pan ) bus taip pat atsitiktiniai dydžiai, kuriuos įvertinti padeda tikimybių teorijos šaka, vadinama eilių teorija.
Nesunku sugalvoti įvairius skirtingus aptarnavimo sistemų variantus. Pvz., aptarnavimo sistema su keletu lygiagrečiai veikiančių serverių, sistema su dviem eilėmis su skirtingo prioriteto paraiškomis ar pan.
Nors Markovo procesais galima modeliuoti ne visas aptarnavimo sistemas (tik tas, kurių paraiškų atėjimo ir aptarnavimo srautai yra puasoniniai), tačiau Markovo procesai davė pagrindą eilų teorijos vystymuisi.Eilių teorijos pradininku laikomas danų matematikas, statistikas ir inžinierius A.K.Erlangas. Dirbdamas Kopenhahos telekomunikacijų kompanijoje Erlangas sprendė uždavinius, kiek reikia telelefonų linijų ir operatorių, norint aptarnauti įeinančius skambučius. Atliktus darbus ir skaičiavimus jis apibendrino 1909 išleistame moksliniame straipsnyje „Tikimybių teorija ir telefoniniai pokalbiai“, kuris laikomas eilių teorijos pradžia. Erlango garbei yra pavadintas apkrovos intensyvumo mato vienetas vienas ir atsitiktinių dydžių pasiskirstymo dėsnis. Garsus britų matematikas D.G.Kendallas (ženkliai prisidėjęs ir prie Markovo procesų teorijos) 1953 sukūrė A/B/C notaciją, kuri iki šiol naudojama aptarnavimo sistemoms aprašyti (pav. pavaizduota aptarnavimo sistema naudojant Kendalo notaciją būtų žymima M/M/1. T.y., vienkanalė aptarnavimo sistema su begaline eile ir puasoniniais paraiškų atėjimo ir aptarnavimo srautais. Esant puasoniniam arba paprasčiausiam srautui, aptarnavimo sistemą galima aprašyti Markovo procesu, dėl to Kendalo notacijoje žymima M ) .Maždaug 7-o dešimtmečio pradžioje L.Kleinrockas panaudodamas eilių teoriją aprašė duomenų perdavimą kompiuteriais. Jo darbai sukūrė matematinį pagrindą paketiniam duomenų siuntimui - technologijai, kuri buvo esminė šiuolaikinio interneto atsiradimui.
A.L.Scherras 1965 m. savo disertacijoje išplėtojo eilių teorijos ir Markovo procesų taikymus kompiuterių našumui įvertinti. A.L.Scheras ištyrė Masačiusetso technologijos instituto (MIT) kompiuterių centre veikiančią operacinę sistemą, kuri vienu metu leido vykdyti keleto skirtingų vartotojų programas. Jis sukūrė įvairius matavimo indeksus ir teorinius įrodymus pagrindė Markovo procesų teorija. Šiuo metu, L.Kleinrocko, A.L.Scherro ir daugybės kitų mokslininkų darbų dėka eilių teorija ir Markovo procesai tapo efektyviu įrankiu kompiuterinėms ir komunikacinių tinklų našumui įvertinti.