Arvutiteadus, küberneetika ja programmeerimine

N teeninduskanaliga teenindussüsteem võtab vastu Poissoni päringute voo intensiivsusega λ. Taotluste teenindamise intensiivsus iga kanali järgi. Pärast teenuse lõppu vabastatakse kõik kanalid. Sellise järjekorrasüsteemi käitumist saab kirjeldada Markovi juhusliku protsessiga t, mis tähistab päringute arvu süsteemis.

2. QS keeldumiste ja täieliku vastastikuse abiga massivoogude puhul. Graafik, võrrandisüsteem, arvutatud seosed.

Probleemi sõnastamine.N teeninduskanaliga teenindussüsteem võtab vastu Poissoni päringute voo intensiivsusega λ. Iga kanali rakenduse teenindamise intensiivsus on µ. Rakendust teenindavad kõik kanalid korraga. Pärast teenuse lõppu vabastatakse kõik kanalid. Kui äsja saabunud päring tabab päringut, võetakse see ka kätte. Mõned kanalid jätkavad esimese päringu teenindamist, ülejäänud aga uue päringu teenindamist. Kui süsteem juba teenindab n rakendust, lükatakse äsja saabunud rakendus tagasi. Sellise järjekorrasüsteemi käitumist saab kirjeldada Markovi juhusliku protsessiga ξ(t), mis on päringute arv süsteemis.

Selle protsessi võimalikud olekud E = (0, 1, . . . . , n). Leiame vaadeldava QS-i omadused statsionaarses režiimis.

Vaadeldavale protsessile vastav graafik on toodud joonisel 1.

Riis. 1. QS tõrgetega ja täielik vastastikune abi Poissoni voogude jaoks

Loome algebraliste võrrandite süsteemi:

Selle süsteemi lahendus on järgmisel kujul:

Siin χ =λ/nµ on keskmine süsteemi sisenevate päringute arv kõigi kanalite ühe päringu teenindamise keskmise aja jooksul.

Mitme kanaliga järjekorrasüsteemi omadused koos rikete ja kanalitevahelise täieliku vastastikuse abiga.

1. Teenuse keelamise tõenäosus (tõenäosus, et kõik kanalid on hõivatud):

2. Päringu teenindamise tõenäosus (suhteline süsteemi võimsus):

Vaatleme mitme kanaliga järjekorrasüsteemi (kokku n kanalit), mis võtab vastu päringuid intensiivsusega λ ja teenindatakse intensiivsusega μ. Süsteemi saabunud päring teenindatakse, kui vähemalt üks kanal on vaba. Kui kõik kanalid on hõivatud, lükatakse järgmine süsteemi saabunud päring tagasi ja lahkub QS-ist. Nummerdame süsteemi olekud hõivatud kanalite arvu järgi:

• S 0 – kõik kanalid on vabad;
• S 1 – üks kanal on hõivatud;
• S 2 – kaks kanalit on hõivatud;
• Sk- hõivatud k kanalid;
• Sn– kõik kanalid on hõivatud.

Riis. 7.24
Joonisel 6.24 on kujutatud olekugraafik, milles Si- kanali number; λ – vastuvõetud päringute intensiivsus; μ – vastavalt teenindustaotluste intensiivsus. Päringud sisenevad järjekorrasüsteemi pideva intensiivsusega ja hõivavad järk-järgult kanaleid üksteise järel; kui kõik kanalid on hõivatud, lükatakse järgmine QS-i saabuv päring tagasi ja lahkutakse süsteemist.
Määrakem sündmuste voogude intensiivsused, mis kannavad süsteemi olekust olekusse, liikudes piki olekugraafikut nii vasakult paremale kui ka paremalt vasakule.
Näiteks olgu süsteem olekus S 1, st üks kanal on hõivatud, kuna selle sisendis on päring. Niipea kui päringu teenindamine on lõpetatud, läheb süsteem olekusse S 0 .
Näiteks kui kaks kanalit on hõivatud, siis teenusevoog, mis edastab süsteemi olekust S 2 osariigis S 1 on kaks korda intensiivsem: 2-μ; vastavalt, kui on hõivatud k kanalite puhul on intensiivsus k-μ.

Hooldusprotsess on surma- ja paljunemisprotsess. Selle konkreetse juhtumi Kolmogorovi võrrandid on järgmisel kujul:

(7.25)
Nimetatakse võrrandeid (7.25). Erlangi võrrandid .
Olekute tõenäosusväärtuste leidmiseks R 0 , R 1 , …, Rn, on vaja kindlaks määrata algtingimused:
– R 0 (0) = 1, st süsteemi sisendis on päring;
– R 1 (0) = R 2 (0) = … = Rn(0) = 0, st algsel ajahetkel on süsteem vaba.
Olles integreerinud diferentsiaalvõrrandi süsteemi (7.25), saame olekutõenäosuste väärtused R 0 (t), R 1 (t), … Rn(t).
Kuid meid huvitavad palju rohkem olekute piiravad tõenäosused. Kui t → ∞ ja kasutades surma ja paljunemise protsessi vaatlemisel saadud valemit, saame võrrandisüsteemi (7.25) lahendi:

(7.26)
Nendes valemites intensiivsuse suhe λ / μ rakenduste voogu on mugav määrata ρ .Seda kogust nimetatakse arvestades rakenduste voo intensiivsust, ehk keskmine QS-i saabunud rakenduste arv ühe rakenduse keskmise teenindamise ajal.

Võttes arvesse tehtud märget, on võrrandisüsteem (7.26) järgmine:

(7.27)
Neid piirtõenäosuste arvutamise valemeid nimetatakse Erlangi valemid .
Teades kõiki QS olekute tõenäosusi, leiame QS efektiivsuse karakteristikud, st absoluutse läbilaskevõime. A, suhteline läbilaskevõime K ja ebaõnnestumise tõenäosus R avatud
Süsteemi saabunud taotlus lükatakse tagasi, kui see leiab, et kõik kanalid on hõivatud:

.
Tõenäosus, et taotlus võetakse teenusesse vastu:

K = 1 – R avatud,
Kus K– süsteemi teenindatavate vastuvõetud taotluste keskmine osakaal või QS-i poolt teenindatavate rakenduste keskmine arv ajaühikus, jagatud selle aja jooksul saadud taotluste keskmise arvuga:

A=λ·Q=λ·(1-P avatud)
Lisaks on riketega QS-i üks olulisemaid omadusi keskmine hõivatud kanalite arv. IN n-kanali QS tõrgetega, see arv langeb kokku QS-i rakenduste keskmise arvuga.
Keskmise taotluste arvu k saab arvutada otse olekute P 0, P 1, ..., P n tõenäosuste kaudu:

,
st leiame diskreetse juhusliku muutuja matemaatilise ootuse, mille väärtus on 0 kuni n tõenäosustega R 0 , R 1 , …, Rn.
Veelgi lihtsam on k väärtust väljendada läbi QS-i absoluutvõimsuse, s.t. A. Väärtus A on keskmine rakenduste arv, mida süsteem ajaühikus teenindab. Üks hõivatud kanal teenindab μ päringut ajaühiku kohta, seejärel keskmine hõivatud kanalite arv

Seni oleme arvestanud ainult selliseid QS-e, kus iga päringut saab teenindada ainult üks kanal; hõivamata kanalid ei saa hõivatud kanaleid teenindada.

Üldiselt see alati nii ei ole: on järjekorrasüsteeme, kus sama päringut saab korraga teenindada kaks või enam kanalit. Näiteks saavad sama katkise masina hooldada kaks töötajat korraga. Selline kanalitevaheline “vastastikune abi” võib toimuda nii avatud kui ka suletud QS-is.

Kanaliülese vastastikuse abiga QS-i kaalumisel tuleb arvestada kahe teguriga.

1. Kui kiiresti kiireneb rakenduse teenindamine, kui sellega ei tööta korraga mitte üks, vaid mitu kanalit?

2. Mis on "vastastikuse abistamise distsipliin", st millal ja kuidas võtavad mitu kanalit sama taotluse teenindamist?

Vaatame kõigepealt esimest küsimust. On loomulik eeldada, et kui rakenduse teenindamiseks ei tööta mitte üks kanal, vaid mitu kanalit, siis teenusevoo intensiivsus k suurenemisega ei vähene, st see kujutab endast mingit mittekahanevat funktsiooni arvust k kanalid. Tähistame seda funktsiooni Funktsiooni võimalik vorm on näidatud joonisel fig. 5.11.

Ilmselgelt ei too samaaegselt töötavate kanalite arvu piiramatu suurenemine alati kaasa teenuse kiiruse proportsionaalset suurenemist; Loomulikum on eeldada, et teatud kriitilise väärtuse juures ei suurenda hõivatud kanalite arvu edasine suurenemine enam teenuse intensiivsust.

Kanalite vastastikuse abiga QS-i toimimise analüüsimiseks on vaja kõigepealt määrata funktsiooni tüüp

Lihtsaim uuritav juhtum on juhtum, kui funktsioon suureneb võrdeliselt k-ga ja jääb konstantseks ja võrdseks (vt joonis 5.12). Kui kanalite koguarv, mis üksteist aidata saavad, ei ületa

Peatugem nüüd teisel küsimusel: vastastikuse abistamise distsipliinil. Nimetame selle distsipliini kõige lihtsamat juhtumit "kõik kui üks". See tähendab, et ühe päringu ilmumisel hakkavad kõik kanalid seda korraga teenindama ja jäävad hõivatuks kuni selle päringu teenindamise lõpuni; siis lülituvad kõik kanalid teise päringu teenindamisele (kui see on olemas) või ootavad selle ilmumist, kui seda ei ole jne. Ilmselgelt töötavad sel juhul kõik kanalid ühena, QS muutub ühe kanaliga, kuid kõrgema teenusega intensiivsusega.

Tekib küsimus: kas sellise kanalitevahelise vastastikuse abistamise juurutamine on tulus või kahjumlik? Vastus sellele küsimusele sõltub sellest, milline on päringute voo intensiivsus, mis tüüpi funktsioon, mis tüüpi QS (tõrgetega, järjekorraga), milline väärtus on valitud teenuse efektiivsuse tunnuseks.

Näide 1. On kolme kanaliga QS, millel on tõrkeid: rakenduste voo intensiivsus (rakendused minutis), ühe päringu teenindamise keskmine aeg ühe kanali kaupa (min), funktsioon Küsimus on selles, kas see on kasulik alates QS-i läbilaskevõime seisukohast „kõik kui üks” tüüpi kanalite vahelise vastastikuse abi kasutuselevõtmiseks "? Kas see on kasulik rakenduse keskmise süsteemis viibimise aja vähendamiseks?

Lahendus a. Ilma vastastikuse abita

Kasutades Erlangi valemeid (vt § 4) saame:

QS suhteline suutlikkus;

Absoluutne läbilaskevõime:

Taotluse keskmine QS-is viibimise aeg leitakse kui tõenäosus, et taotlus võetakse teenusesse vastu, korrutatuna keskmise teenindusajaga:

Gsist (min).

Me ei tohi unustada, et see keskmine aeg kehtib kõikidele rakendustele – nii hooldatud kui ka teenindamata. Samuti võib meid huvitada keskmine aeg, mille jooksul hooldatud rakendus süsteemis püsib. See aeg on võrdne:

6. Vastastikuse abiga.

Keskmine aeg, mil taotlus viibib ühises turukorralduses:

Keskmine aeg, mille teenindav rakendus ühises turukorralduses kulutab:

Seega on vastastikuse abi “kõik kui üks” olemasolul QS-i läbilaskevõime märgatavalt vähenenud. Seda seletatakse keeldumise tõenäosuse suurenemisega: kui kõik kanalid on hõivatud ühe päringu teenindamisega, võivad saabuda ka teised päringud, mis loomulikult tagasi lükatakse. Mis puudutab rakenduse ühises turukorralduses veedetud keskmist aega, siis see, nagu arvata võiks, vähenes. Kui püüame mingil põhjusel täielikult vähendada aega, mida rakendus QS-is veedab (näiteks kui QS-is viibimine on rakendusele ohtlik), võib selguda, et vaatamata läbilaskevõime vähenemisele siiski kasulik ühendada kolm kanalit üheks.

Vaatleme nüüd ootusega „kõik kui üks“ tüüpi vastastikuse abistamise mõju QS-i tööle. Lihtsuse huvides võtame ainult piiramatu järjekorra juhtumi. Loomulikult ei mõjuta vastastikuse abi andmine QS-i läbilaskevõimet, kuna mis tahes tingimustel teenindatakse kõiki sissetulevaid taotlusi. Tekib küsimus vastastikuse abistamise mõjust ootamise tunnustele: järjekorra keskmine pikkus, keskmine ooteaeg, keskmine teenuses viibimise aeg.

Vastastikuse abita kättetoimetamise valemite (6.13), (6.14) § 6 kohaselt on järjekorras olevate päringute keskmine arv

keskmine ooteaeg:

ja keskmine viibimisaeg süsteemis:

Kui kasutatakse "kõik kui üks" tüüpi vastastikust abi, töötab süsteem parameetritega ühe kanalina

ja selle omadused määratakse valemitega (5.14), (5.15) § 5:

Näide 2. Seal on kolme kanaliga QS piiramatu järjekorraga; rakenduste voo intensiivsus (rakendusi minutis), keskmine teenindusaeg Funktsioon Kasulik tähendus:

järjekorra keskmine pikkus,

Keskmine teeninduse ooteaeg,

Keskmine aeg, mil taotlus viibib ühises turukorralduses

kasutusele võtta vastastikuse abistamise kanalite vahel nagu "kõik kui üks"?

Lahendus a. Vastastikune abi puudub.

Valemite (9.1) - (9.4) järgi on meil

(3-2)

b. Vastastikuse abiga

Kasutades valemeid (9.5) - (9.7) leiame;

Seega on vastastikuse abistamise korral keskmine järjekorra pikkus ja keskmine ooteaeg järjekorras suurem, kuid rakenduse keskmine süsteemis viibimise aeg on väiksem.

Vaadeldavate näidete põhjal on selge, et vastastikune abi "Kõik kui üks" sularaha tüüp reeglina ei aita kaasa teenuse efektiivsuse tõstmisele: päringu QS-is viibimise aeg väheneb, kuid muud teenuse omadused halvenevad.

Seetõttu on soovitav muuta teenindusdistsipliini nii, et kanalite vastastikune abi ei segaks uute teenusepäringute vastuvõtmist, kui need ilmuvad ajal, mil kõik kanalid on hõivatud.

Nimetagem järgmist vastastikuse abi liiki ühtseks vastastikuseks abiks. Kui päring saabub ajal, mil kõik kanalid on vabad, aktsepteeritakse kõiki kanaleid selle teenindamiseks; kui rakenduse teenindamise ajal saabub teine, lülitub osa kanaleid selle teenindamisele; kui nende kahe päringu teenindamise ajal saabub teine, lülituvad mõned kanalid selle teenindamisele jne, kuni kõik kanalid on hõivatud; kui see nii on, lükatakse äsja saabunud taotlus tagasi (keeldumisega QS-is) või pannakse see järjekorda (ootusega QS-is).

Selle vastastikuse abistamise põhimõtte kohaselt lükatakse taotlus tagasi või pannakse järjekorda ainult siis, kui seda ei ole võimalik kätte toimetada. Mis puudutab kanalite “seisakuid”, siis see on nendel tingimustel minimaalne: kui süsteemis on vähemalt üks päring, siis kõik kanalid töötavad.

Eespool mainisime, et uue päringu ilmumisel vabastatakse osa hõivatud kanaleid ja lülituvad ümber äsja saabunud päringu teenindamiseks. Mis osa? See sõltub funktsiooni tüübist, kui sellel on lineaarne seos, nagu on näidatud joonisel fig. 5.12, ja pole vahet, milline osa kanalitest on eraldatud äsja saabunud päringu teenindamiseks, kui kõik kanalid on hõivatud (siis võrdub teenuste koguintensiivsus kanalite päringute vahel jaotamisel ). Võib tõestada, et kui kõver on ülespoole kumer, nagu on näidatud joonisel fig. 5.11, siis peate kanalid päringute vahel võimalikult ühtlaselt jaotama.

Vaatleme -kanali QS-i toimimist kanalitevahelise "ühtlase" vastastikuse abiga.

Probleemi sõnastamine. Sissepääsu juures n-kanal QS võtab vastu lihtsaima päringute voo tihedusega λ. Lihtsaima teenusevoo tihedus iga kanali jaoks on μ. Kui saadud teenusetaotlus leiab, et kõik kanalid on vabad, võetakse see hoolduseks ja teenindatakse samaaegselt l kanalid ( l < n). Sel juhul on ühe rakenduse teenuste voog intensiivne l.

Kui saabunud teenusepäring leiab süsteemist ühe päringu, siis millal n ≥ 2läsja saabunud taotlus võetakse teenindusse ja seda teenindatakse samaaegselt l kanalid.

Kui saadud teenindustaotlus on süsteemis kinni i rakendused ( i= 0,1, ...), samas ( i+ 1)l≤ n, siis teenindatakse saabunud taotlust lüldise jõudlusega kanalid l. Kui äsja saabunud taotlus jääb süsteemi vahele j rakendused ja samal ajal rahuldatakse kaks ebavõrdsust ühiselt: ( j + 1)l > n Ja j < n, siis võetakse taotlus kätte. Sel juhul saab mõnda rakendust hooldada l kanalid, teine ​​osa on väiksem kui l, kanalite arvu, kuid kõik on teenindusega hõivatud n kanalid, mis on rakenduste vahel juhuslikult jaotatud. Kui äsja saabunud taotlus jääb süsteemi vahele n rakendusi, lükatakse see tagasi ja seda ei teenindata. Teeninduseks saabunud avaldus teenindatakse lõpuni ("patsiendi" taotlused).

Sellise süsteemi olekugraafik on näidatud joonisel fig. 3.8.

Riis. 3.8. Rikete ja osaliste QS-olekute graafik

kanalite vastastikune abi

Pange tähele, et süsteemi olekugraafik kuni olekuni x h kuni vooluparameetrite märgistuseni kattub see klassikalise riketega järjekorrasüsteemi olekugraafikuga, mis on näidatud joonisel fig. 3.6.

Seega

(i = 0, 1, ..., h).

Süsteemi oleku graafik alates olekust x h ja lõpetades riigiga x n, langeb kuni märgistuseni kokku täieliku vastastikuse abiga QS-i olekugraafikuga, mis on näidatud joonisel fig. 3.7. Seega

.

Tutvustame tähistust λ / lμ = ρ l ; λ / nμ = χ, siis

Võttes arvesse normaliseeritud seisundit, saame

Edasise märgistuse lühendamiseks tutvustame tähistust

Leiame süsteemi omadused.

Teeninduse taotlemise tõenäosus

Keskmine rakenduste arv süsteemis on

Keskmine hõivatud kanalite arv

.

Tõenäosus, et konkreetne kanal on hõivatud

.

Kõigi süsteemikanalite hõivatuse tõenäosus

3.4.4. Rikete ja heterogeensete voogudega järjekorrasüsteemid

Probleemi sõnastamine. Sissepääsu juures n-kanaliga QS süsteem võtab vastu heterogeense lihtsaima voolu koguintensiivsusega λ Σ ja

λ Σ = ,

kus λ i– rakenduste intensiivsus i allikas.

Kuna päringute voogu peetakse erinevatest allikatest pärit nõuete superpositsiooniks, võib praktika jaoks piisava täpsusega kombineeritud voogu pidada Poissoni jaoks. N = 5...20 ja λ i ≈ λ i +1 (i1,N). Ühe seadme teenindusintensiivsus on jaotatud vastavalt eksponentsiaalseadusele ja on võrdne μ = 1/ t. Päringu teenindamiseks mõeldud teenindusseadmed on ühendatud järjestikku, mis võrdub teenindusaja pikendamisega nii mitu korda, kui palju seadmeid teenindamiseks kombineeritakse:

t obs = kt, μ obs = 1 / kt = μ/ k,

Kus t obs – küsi teenindusaega; k– teenindusseadmete arv; μ obs – taotlege hoolduse intensiivsust.

Peatükis 2 võetud eelduste raames esitame QS-i oleku vektorina, kus k m– rakenduste arv süsteemis, millest igaüks on teenindatud m seadmed; L = q max – q min +1 – sisendvoogude arv.

Seejärel hõivatud ja vabade seadmete arv ( n zan ( ),n sv ( )) võimeline on määratletud järgmiselt:

Riigilt süsteem võib minna mis tahes muusse olekusse . Kuna süsteem töötab L sisendvoogusid, siis igast olekust on see potentsiaalselt võimalik L otsesed üleminekud. Piiratud süsteemiressursside tõttu ei ole aga kõik need üleminekud teostatavad. Olgu SMO seisukorras ja saabub nõudlik palve m seadmeid. Kui m≤ n sv ( ), siis võetakse taotlus teenindamiseks vastu ja süsteem läheb olekusse intensiivsusega λ m. Kui rakendus nõuab rohkem seadmeid, kui on saadaval, keeldutakse selle teenindamisest ja QS jääb olekusse . Kui sa saad seal on nõutavad rakendused m seadmeid, siis igaüht neist hooldatakse intensiivsusega  m ja selliste päringute teenindamise koguintensiivsus (μ m) on määratletud kui μ m = k m μ / m. Kui ühe päringu teenindamine on lõpetatud, läheb süsteem olekusse, kus vastava koordinaadi väärtus on ühe võrra väiksem kui olekus ,=, s.t. toimub vastupidine üleminek. Joonisel fig. 3.9 näitab QS-i vektormudeli näidet n = 3, L = 3, q min = 1, q max = 3, P(m) = 1/3, λ Σ = λ, seadme hoolduse intensiivsus – μ.

Riis. 3.9. Näide teenusetõrgetega QS vektormudeli graafikust

Nii et iga osariik mida iseloomustab teatud tüüpi teenindatud rakenduste arv. Näiteks osariigis
ühte päringut teenindab üks seade ja ühte päringut kaks seadet. Selles olekus on kõik seadmed hõivatud, seetõttu on võimalikud ainult vastupidised üleminekud (mis tahes päringu saabumine selles olekus toob kaasa teenuse keelamise). Kui esimest tüüpi päringu teenindamine on varem lõppenud, läheb süsteem olekusse (0,1,0) intensiivsusega μ, kuid kui teist tüüpi päringu teenindamine on varem lõppenud, läheb süsteem olekusse (0,1,0) intensiivsusega μ/2.

Kasutades olekugraafikut koos üleminekuintensiivsustega, koostatakse lineaarsete algebraliste võrrandite süsteem. Nende võrrandite lahendusest leitakse tõenäosused R(), mille abil määratakse QS-i omadused.

Kaaluge leidmist R otk (teenusest keeldumise tõenäosus).

,

Kus S– vektori QS mudeli graafiku olekute arv; R() on tõenäosus, et süsteem on olekus .

Olekute arv vastavalt sellele määratakse järgmiselt:

, (3.22)

;

Määrame vektori QS mudeli olekute arvu vastavalt (3.22) joonisel näidatud näite jaoks. 3.9.

.

Seega S = 1 + 5 + 1 = 7.

Teenindusseadmetele esitatavate tegelike nõuete rakendamiseks piisavalt suur hulk n (40, ..., 50) ja taotlused teenindavate seadmete arvu kohta rakenduses jäävad praktikas vahemikku 8–16. Sellise instrumentide ja taotluste suhte korral muutub tõenäosuste leidmise väljapakutud viis äärmiselt tülikaks, sest QS vektormudelil on suur hulk olekuid S(50) = 1790, S(60) = 4676, S(70) = = 11075 ja algebralise võrrandisüsteemi koefitsiendimaatriksi suurus on võrdeline ruuduga S, mis nõuab palju arvutimälu ja märkimisväärselt palju arvutiaega. Soov arvutuste arvu vähendada ärgitas otsima korduvaid arvutusvõimalusi R(), mis põhineb olekutõenäosuste esitamise multiplikatiivsetel vormidel. Töös esitatakse lähenemine arvutamisele R():

(3.23)

Töös välja pakutud Markovi ahelate globaalsete ja detailsete saldode samaväärsuse kriteeriumi kasutamine võimaldab vähendada probleemi dimensiooni ja teostada arvutusi keskmise võimsusega arvutil arvutuste korduse abil. Lisaks on võimalik:

– tehke arvutused mis tahes väärtuste jaoks n;

– kiirendada arvutusi ja vähendada masina ajakulu.

Sarnasel viisil saab määrata ka teisi süsteemi omadusi.