Smo cu asistență reciprocă între canale. QS cu eșecuri și asistență reciprocă completă pentru fluxuri arbitrare

Până acum, am luat în considerare doar acele QS-uri în care fiecare revendicare poate fi deservită de un singur canal; canalele inactive nu pot „ajuta” pe unul ocupat în serviciu.

În general, acesta nu este întotdeauna cazul: există sisteme de așteptare în care aceeași cerere poate fi deservită simultan de două sau mai multe canale. De exemplu, aceeași mașină eșuată poate servi doi lucrători simultan. O astfel de „asistență reciprocă” între canale poate avea loc atât în ​​QS deschis, cât și în cel închis.

Atunci când luăm în considerare CMO cu asistență reciprocă între canale, trebuie luați în considerare doi factori:

1. Cu cât este mai rapid serviciul unei aplicații când nu funcționează pe ea nu unul, ci mai multe canale simultan?

2. Care este „disciplina ajutorului reciproc”, adică când și cum preiau mai multe canale serviciul aceleiași cereri?

Să luăm în considerare prima întrebare. Este firesc să presupunem că, dacă mai mult de un canal, dar mai multe canale, lucrează la deservirea unei cereri, intensitatea fluxului de serviciu nu va scădea odată cu creșterea k, adică va fi o anumită funcție nedescrescătoare a numărului k. a canalelor de lucru. Să notăm această funcție.Forma posibilă a funcției este prezentată în fig. 5.11.

Evident, o creștere nelimitată a numărului de canale care funcționează simultan nu duce întotdeauna la o creștere proporțională a ratei de serviciu; este mai firesc să presupunem că, la o anumită valoare critică, o nouă creștere a numărului de canale ocupate nu mai crește intensitatea serviciului.

Pentru a analiza funcționarea unui QS cu asistență reciprocă între canale, este necesar, în primul rând, să se stabilească tipul funcției

Cel mai simplu caz de investigare va fi cazul când funcția crește proporțional cu k când a rămâne constantă și egală când a (vezi Fig. 5.12). Dacă, în plus, numărul total de canale care se pot ajuta reciproc nu depășește

Să trecem acum la a doua întrebare: disciplina ajutorului reciproc. Cel mai simplu caz al acestei discipline îl vom desemna condiționat drept „toți ca unul”. Aceasta înseamnă că atunci când apare o solicitare, toate canalele încep să o difuzeze deodată și rămân ocupate până când serviciul acestei solicitări se încheie; apoi toate canalele trec la deservirea unei alte cereri (dacă există) sau așteaptă să apară dacă nu există etc. Evident, în acest caz, toate canalele funcționează ca unul singur, QS-ul devine monocanal, dar cu o valoare mai mare. intensitatea serviciului.

Se pune întrebarea: este benefic sau dezavantajos să se introducă o astfel de asistență reciprocă între canale? Răspunsul la această întrebare depinde de intensitatea fluxului de aplicații, ce tip de funcție, ce tip de QS (cu defecțiuni, cu o coadă), ce valoare este aleasă ca caracteristică a eficienței serviciului.

Exemplul 1. Există un QS cu trei canale cu defecțiuni: intensitatea fluxului de aplicații (aplicații pe minut), timpul mediu de service al unei aplicații pe un canal (min), funcția „? Este benefic din punct de vedere al reducerii timpului mediu de rezidență al unei aplicații în sistem?

Soluția a. Fără ajutor reciproc

Prin formulele Erlang (vezi § 4) avem:

Capacitatea relativă a QS;

Lățimea de bandă absolută:

Timpul mediu de rezidență al unei cereri în QS se găsește ca probabilitatea ca cererea să fie acceptată pentru serviciu, înmulțită cu timpul mediu de serviciu:

Esența (min).

Nu trebuie uitat că acest timp mediu se aplică tuturor solicitărilor - atât deservite, cât și neservite. S-ar putea să fim interesați de timpul mediu în care o solicitare deservită va rămâne în sistem. De data aceasta este:

6. Cu ajutor reciproc.

Timpul mediu de rezidență al unei cereri în CMO:

Timpul mediu de rezidență al unei cereri deservite în QS:

Astfel, în prezența asistenței reciproce „toți ca unul”, debitul SMO a scăzut considerabil. Acest lucru se explică printr-o creștere a probabilității de eșec: în timp ce toate canalele sunt ocupate cu o aplicație, alte aplicații pot veni și, desigur, pot fi refuzate. În ceea ce privește timpul mediu de rezidență al unei aplicații în CMO, acesta, așa cum era de așteptat, a scăzut. Dacă, dintr-un motiv oarecare, ne străduim să reducem timpul pe care aplicația îl petrece în QS în toate modurile posibile (de exemplu, dacă rămânerea în QS este periculoasă pentru aplicație), se poate dovedi că, în ciuda scăderii debitului, va fi în continuare benefic să combinați trei canale într-unul singur.

Să luăm acum în considerare impactul asistenței reciproce „toți ca unul” asupra activității CMO cu așteptări. Pentru simplitate, luăm doar cazul unei cozi nelimitate. Desigur, efectele ajutorului reciproc asupra debitului Nu va exista niciun CMO în acest caz, deoarece în orice condiții toate cererile primite vor fi servite. Se pune întrebarea despre influența asistenței reciproce asupra caracteristicilor așteptării: lungimea medie a cozii, timpul mediu de așteptare, timpul mediu petrecut în QS.

În virtutea formulelor (6.13), (6.14) § 6 pentru serviciul fără asistență reciprocă, numărul mediu de clienți din coadă va fi

timpul mediu de așteptare:

și timpul mediu petrecut în sistem:

Dacă se utilizează asistență reciprocă de tip „toți ca unul”, atunci sistemul va funcționa ca un sistem cu un singur canal cu parametri

iar caracteristicile sale sunt determinate de formulele (5.14), (5.15) § 5:

Exemplul 2. Există un QS cu trei canale cu o coadă nelimitată; intensitatea fluxului de aplicații (aplicații pe min.), timp mediu de serviciu Funcție Beneficiar în vederea:

Lungimea medie a cozii

Timp mediu de așteptare pentru service,

Timpul mediu de rezidență al unei cereri în CMO

introduceți asistență reciprocă între canale precum „toți ca unul”?

Soluția a. Fără ajutor reciproc.

Prin formulele (9.1) - (9.4) avem

(3-2)

b. Cu ajutor reciproc

Prin formulele (9.5) - (9.7) găsim;

Astfel, lungimea medie a cozii și timpul mediu de așteptare în coadă în cazul asistenței reciproce este mai mare, dar timpul mediu pe care aplicația îl petrece în sistem este mai mic.

Din exemplele luate în considerare este clar că asistența reciprocă între k? Tipul de numerar „toți ca unul”, de regulă, nu contribuie la îmbunătățirea eficienței serviciului: timpul petrecut de o aplicație în QS scade, dar alte caracteristici ale serviciului se înrăutățesc.

Prin urmare, este de dorit să se schimbe disciplina de serviciu, astfel încât asistența reciprocă între canale să nu interfereze cu acceptarea de noi cereri de serviciu dacă acestea apar în timpul în care toate canalele sunt ocupate.

Să numim condiționat „asistență reciprocă uniformă” următorul tip de asistență reciprocă. Dacă solicitarea ajunge în momentul în care toate canalele sunt gratuite, atunci toate canalele sunt acceptate pentru serviciul său; daca in momentul deservirii cererii mai ajunge una, unele dintre canale trec la deservirea acesteia; dacă, în timp ce aceste două cereri sunt servite, sosește alta, unele dintre canale sunt comutate pentru a le servi și așa mai departe, până când toate canalele sunt ocupate; dacă da, cererea nou sosită este respinsă (într-un QS cu refuzuri) sau plasată într-o coadă (într-un QS cu așteptare).

Cu această disciplină de asistență reciprocă, cererea este respinsă sau pusă la coadă numai atunci când nu este posibilă deservirea ei. În ceea ce privește „timpul” al canalelor, acesta este minim în aceste condiții: dacă există cel puțin o aplicație în sistem, toate canalele funcționează.

Am menționat mai sus că, atunci când apare o nouă solicitare, unele dintre canalele ocupate sunt eliberate și trec la deservirea cererii nou sosite. Ce parte? Depinde de tipul funcției.Dacă are forma unei relații liniare, așa cum se arată în fig. 5.12, și nu contează ce parte a canalelor să aloce pentru deservirea unei cereri nou primite, atâta timp cât toate canalele sunt ocupate (atunci intensitatea totală a serviciilor pentru orice distribuție a canalelor pe cereri va fi egală cu ). Se poate dovedi că dacă curba este convexă în sus, așa cum se arată în Fig. 5.11, atunci trebuie să distribuiți canalele între aplicații cât mai uniform posibil.

Să luăm în considerare munca -canal QS cu asistență reciprocă „uniformă” între canale.

Sistem de ecuații

QS cu eșecuri pentru un număr aleatoriu de fluxuri de servire este un model vectorial pentru fluxurile Poisson. Grafic, sistem de ecuații.

Să reprezentăm QS ca un vector , unde k m este numărul de solicitări din sistem, fiecare dintre acestea fiind deservită m aparate; L= q max- q min +1 este numărul de fluxuri de intrare.

Dacă cererea este acceptată pentru service și sistemul intră într-o stare cu intensitatea λ m.

La finalizarea deservirii uneia dintre solicitări, sistemul va intra într-o stare în care coordonatele corespunzătoare are o valoare cu o mai mică decât în ​​starea , = , i.e. va avea loc tranziția inversă.

Un exemplu de model vectorial QS pentru n = 3, L = 3, q min = 1, q max=3, P(m) = 1/3, λ Σ = λ, intensitatea întreținerii instrumentului este μ.

Un sistem de ecuații algebrice liniare este compilat din graficul stărilor cu intensități de tranziție aplicate. Din rezolvarea acestor ecuații se găsesc probabilitățile R(), prin care sunt determinate caracteristicile QS.

QS cu o coadă infinită pentru fluxurile Poisson. Grafic, sistem de ecuații, rapoarte de proiectare.

Graficul de sistem

Sistem de ecuații

Unde n– numărul de canale de servicii, l– numărul de canale de asistență reciprocă

QS cu o coadă infinită și asistență reciprocă parțială pentru fluxuri arbitrare. Grafic, sistem de ecuații, rapoarte calculate.

Graficul de sistem

Sistem de ecuații

–λ R 0 + nμ R 1 =0,

.………………

–(λ + nμ) Pk+ λ Pk –1 + nμ Pk +1 =0 (k = 1,2, ... , n–1),

……………....

-(λ+ nμ) P n+ λ P n –1 + nμ P n+1=0,

……………….

-(λ+ nμ) Pn+j+ λ Р n+j –1 + nμ Р n+j+1=0, j=(1,2,….,∞)

QS cu o coadă infinită și asistență reciprocă completă pentru fluxuri arbitrare. Grafic, sistem de ecuații, rapoarte calculate.

Graficul de sistem

…

Sistem de ecuații

QS cu o coadă finită pentru fluxurile Poisson. Grafic, sistem de ecuații, rapoarte calculate.

Graficul de sistem

Sistem de ecuații

Raport de proiectare:

,

Să luăm în considerare un sistem de așteptare multicanal (există n canale în total), în care cererile ajung cu o rată de λ și sunt deservite cu o rată de μ. O solicitare care a ajuns în sistem este deservită dacă cel puțin un canal este liber. Dacă toate canalele sunt ocupate, următoarea cerere care intră în sistem este respinsă și părăsește QS-ul. Numerotăm stările sistemului după numărul de canale ocupate:

• S 0 – toate canalele sunt gratuite;
• S 1 – un canal este ocupat;
• S 2 – două canale sunt ocupate;
• Sk- ocupat k canale;
• Sn– toate canalele sunt ocupate.

Este evident că sistemul trece de la stat la stat sub influența flux de intrare aplicatii. Să construim un grafic de stare pentru acest sistem de așteptare.

Orez. 7.24
Figura 6.24 prezintă un grafic de stare în care Si– numărul canalului; λ este intensitatea primirii cererilor; μ - respectiv, intensitatea cererilor de service. Aplicațiile intră în sistemul de așteptare cu o intensitate constantă și ocupă treptat canalele unul după altul; când toate canalele sunt ocupate, următoarea cerere care ajunge la QS va fi respinsă și va părăsi sistemul.
Să determinăm intensitățile fluxurilor de evenimente care transferă sistemul de la o stare la alta atunci când se deplasează atât de la stânga la dreapta, cât și de la dreapta la stânga de-a lungul graficului stării.
De exemplu, lăsați sistemul să fie în stare S 1, adică un canal este ocupat, deoarece există o solicitare la intrarea sa. Imediat ce cererea este procesată, sistemul va trece la starea S 0 .
De exemplu, dacă două canale sunt ocupate, atunci fluxul de servicii care transferă sistemul din stat S 2 pe stat S 1 va fi de două ori mai intens: 2-μ; respectiv, dacă este ocupat k canale, intensitatea este egală cu k-μ.

Procesul de serviciu este un proces de moarte și reproducere. Ecuațiile Kolmogorov pentru acest caz particular vor avea următoarea formă:

(7.25)
Se numesc ecuațiile (7.25). Ecuații Erlang .
Pentru a găsi valorile probabilităților stărilor R 0 , R 1 , …, Rn, este necesar să se determine condițiile inițiale:
– R 0 (0) = 1, adică există o solicitare la intrarea sistemului;
– R 1 (0) = R 2 (0) = … = Rn(0) = 0, adică în momentul initial când sistemul este liber.
După integrarea sistemului de ecuații diferențiale (7.25), obținem valorile probabilităților de stare R 0 (t), R 1 (t), … Rn(t).
Dar ne interesează mult mai mult probabilitățile limită ale stărilor. Ca t → ∞ și folosind formula obținută în considerarea procesului de moarte și reproducere, obținem soluția sistemului de ecuații (7.25):

(7.26)
În aceste formule, raportul de intensitate λ / μ la fluxul de aplicaţii este convenabil să se desemneze ρ .Această valoare este numită intensitatea redusă a fluxului de aplicații, adică numărul mediu de aplicații care sosesc în QS pentru timpul mediu de serviciu al unei aplicații.

Ținând cont de notația de mai sus, sistemul de ecuații (7.26) ia următoarea formă:

(7.27)
Aceste formule pentru calcularea probabilităților marginale sunt numite Formule Erlang .
Cunoscând toate probabilitățile stărilor QS, găsim caracteristicile de eficiență QS, adică debitul absolut DAR, debit relativ Qși probabilitatea de eșec R deschis
O solicitare care intră în sistem va fi respinsă dacă găsește că toate canalele sunt ocupate:

.
Probabilitatea ca cererea să fie acceptată pentru serviciu:

Q = 1 – R bine,
Unde Q este ponderea medie a cererilor primite deservite de sistem sau numărul mediu de cereri deservite de QS pe unitatea de timp, împărțit la numărul mediu de cereri primite în acest timp:

A=λ Q=λ (1-P deschis)
În plus, unul dintre cele mai importante caracteristici QS cu eșecuri este canale medie ocupate. LA n-canal QS cu defecțiuni, acest număr coincide cu numărul mediu de aplicații din QS.
Numărul mediu de aplicații k poate fi calculat direct în funcție de probabilitățile stărilor Р 0 , Р 1 , … , Р n:

,
adică găsim așteptarea matematică a unei variabile aleatoare discrete care ia o valoare de la 0 la n cu probabilităţi R 0 , R 1 , …, Rn.
Este chiar mai ușor de exprimat valoarea lui k în termeni de debit absolut al QS, adică. A. Valoarea lui A este numărul mediu de aplicații care sunt deservite de sistem pe unitatea de timp. Un canal ocupat servește μ cereri pe unitate de timp, apoi numărul mediu de canale ocupate

Formularea problemei. La intrare n-canalul QS primește cel mai simplu flux de cereri cu densitatea λ. Densitatea celui mai simplu flux de serviciu al fiecărui canal este egală cu μ. Dacă cererea primită pentru service găsește toate canalele libere, atunci aceasta este acceptată pentru service și deservită simultan l canale ( l < n). În acest caz, fluxul de servicii al unei cereri va avea o intensitate l.

Dacă o solicitare primită pentru service găsește o solicitare în sistem, atunci n ≥ 2l aplicația nou sosită va fi acceptată pentru service și va fi deservită simultan l canale.

Dacă o cerere primită pentru service se găsește în sistem i aplicatii ( i= 0,1, ...), în timp ce ( i+ 1)l≤ n, atunci cererea primită va fi deservită l canale cu o capacitate totală l. Dacă o aplicație recent primită se găsește în sistem j cereri, iar două inegalități sunt satisfăcute simultan: ( j + 1)l > nși j < n, atunci cererea va fi acceptată pentru service. În acest caz, unele aplicații pot fi servite l canale, cealaltă parte mai mică decât l, număr de canale, dar toate n canale care sunt distribuite aleatoriu între aplicații. Dacă în sistem se găsește o aplicație nou primită n cereri, este respinsă și nu va fi comunicată. O aplicație care a fost deservită este deservită până la capăt (aplicațiile sunt „pacient”).

Graficul de stare al unui astfel de sistem este prezentat în Fig. 3.8.

Orez. 3.8. Graficul de stare QS cu defecțiuni și parțiale

asistență reciprocă între canale

Rețineți că graficul de stare al sistemului până la stare X h coincide cu graficul de stare al sistemului clasic de așteptare cu defecțiuni, prezentat în Fig. 2, până la notarea parametrilor debitului. 3.6.

Prin urmare,

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

Graficul stărilor sistemului, pornind de la stare X hși terminând cu statul X n, coincide până la notare cu graficul de stare al QS cu asistență reciprocă completă, prezentat în Fig. 3.7. În acest fel,

.

Introducem notatia λ / lμ = ρ l ; λ / nμ = χ, atunci

Ținând cont de starea normalizată, obținem

Pentru a scurta notația suplimentară, introducem notația

Găsiți caracteristicile sistemului.

Probabilitatea serviciului de aplicație

Numărul mediu de aplicații din sistem,

Canale ocupate în medie

.

Probabilitatea ca un anumit canal să fie ocupat

.

Probabilitatea de ocupare a tuturor canalelor sistemului

3.4.4. Sisteme de așteptare cu defecțiuni și fluxuri neomogene

Formularea problemei. La intrare n-canalul QS primește un flux elementar neomogen cu o intensitate totală λ Σ , și

λ Σ = ,

unde λ i- intensitatea aplicatiilor in i-m sursa.

Deoarece fluxul de cereri este considerat ca o suprapunere a cerințelor din diverse surse, fluxul combinat cu suficientă precizie pentru practică poate fi considerat Poisson pentru N = 5...20 și λ i ≈ λ i +1 (i1,N). Intensitatea serviciului unui dispozitiv este distribuită conform legii exponențiale și este egală cu μ = 1/ t. Dispozitivele de service pentru întreținerea unei aplicații sunt conectate în serie, ceea ce echivalează cu creșterea timpului de service de atâtea ori câte dispozitive sunt combinate pentru întreținere:

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

Unde t obs – cerere timp de service; k- numărul de dispozitive de service; μ obs - intensitatea serviciului de aplicație.

În cadrul ipotezelor făcute în Capitolul 2, reprezentăm starea QS ca un vector , unde k m este numărul de solicitări din sistem, fiecare dintre acestea fiind deservită m aparate; L = q max- q min +1 este numărul de fluxuri de intrare.

Apoi numărul de dispozitive ocupate și libere ( n zan ( ),n sv ( )) in stare este definită după cum urmează:

In afara statului sistemul poate merge în orice altă stare . Din moment ce sistemul are L fluxuri de intrare, apoi din fiecare stare este posibil posibil L tranziții directe. Cu toate acestea, din cauza resurselor limitate ale sistemului, nu toate aceste tranziții sunt fezabile. Lăsați QS-ul să fie în stare și sosește o aplicație care solicită m aparate. În cazul în care un m≤ n sv ( ), atunci cererea este acceptată pentru service și sistemul intră într-o stare cu intensitatea λ m. Dacă aplicația necesită mai multe dispozitive decât sunt gratuite, atunci va primi un refuz de serviciu, iar QS-ul va rămâne în stare . Dacă se poate există aplicații care necesită m dispozitive, apoi fiecare dintre ele este deservit cu intensitatea  m, și intensitatea totală a deservirii unor astfel de solicitări (μ m) este definit ca μ m = k m μ / m. Când serviciul uneia dintre solicitări este finalizat, sistemul va intra într-o stare în care coordonatele corespunzătoare are o valoare cu una mai mică decât în ​​stare ,=, adică va avea loc tranziția inversă. Pe fig. 3.9 prezintă un exemplu de model vectorial QS pentru n = 3, L = 3, q min = 1, q max=3, P(m) = 1/3, λ Σ = λ, intensitatea întreținerii instrumentului este μ.

Orez. 3.9. Un exemplu de grafic al modelului vectorial QS cu refuz de serviciu

Deci fiecare stat caracterizat prin numărul de cereri deservite de un anumit tip. De exemplu, într-o stare
o revendicare este deservită de un dispozitiv și o revendicare de două dispozitive. În această stare, toate dispozitivele sunt ocupate, prin urmare, sunt posibile doar tranzițiile inverse (sosirea oricărui client în această stare duce la refuzul serviciului). Dacă serviciul cererii de primul tip s-a încheiat mai devreme, sistemul va trece la starea (0,1,0) cu intensitatea μ, dar dacă serviciul celui de-al doilea tip de solicitare s-a încheiat mai devreme, atunci sistemul va intra în stare (0,1,0) cu intensitatea μ/2.

Un sistem de ecuații algebrice liniare este compilat din graficul stărilor cu intensități de tranziție aplicate. Din rezolvarea acestor ecuații se găsesc probabilitățile R(), prin care se determină caracteristica QS.

Luați în considerare găsirea R otk (probabilitate de refuz de serviciu).

,

Unde S este numărul de stări ale graficului modelului vectorial QS; R() este probabilitatea ca sistemul să fie în stare .

Numărul de stări conform este definit după cum urmează:

, (3.22)

;

Să determinăm numărul de stări ale modelului vectorial QS conform (3.22) pentru exemplul prezentat în Fig. 3.9.

.

Prin urmare, S = 1 + 5 + 1 = 7.

Pentru a implementa cerințe reale pentru dispozitivele de service, un număr suficient de mare de n (40, ..., 50), iar cererile pentru numărul de dispozitive de service ale aplicației se află în practică în intervalul 8-16. Cu un asemenea raport de instrumente și cereri, modalitatea propusă de găsire a probabilităților devine extrem de greoaie, întrucât Modelul vectorial QS are un număr mare de stări S(50) = 1790, S(60) = 4676, S(70) = 11075, iar dimensiunea matricei de coeficienți a sistemului de ecuații algebrice este proporțională cu pătratul S, care necesită o cantitate mare de memorie de calculator și o cantitate semnificativă de timp de calculator. Dorința de a reduce cantitatea de calcul a stimulat căutarea posibilităților de calcul recurente R() pe baza formelor multiplicative de reprezentare a probabilităţilor de stare. Lucrarea prezintă o abordare a calculului R():

(3.23)

Utilizarea criteriului de echivalență a balanțelor globale și detaliate ale lanțurilor Markov propuse în lucrare face posibilă reducerea dimensiunii problemei și efectuarea calculelor pe un computer de putere medie folosind recurența calculelor. În plus, există posibilitatea:

– calculați pentru orice valoare n;

– accelerați calculul și reduceți costul timpului mașinii.

Alte caracteristici ale sistemului pot fi definite în mod similar.