Smo mit gegenseitiger Unterstützung zwischen den Kanälen. QS bei Ausfällen und volle gegenseitige Hilfeleistung bei Massenströmen. Diagramm, Gleichungssystem, berechnete Verhältnisse. Warteschlangensysteme mit Ausfällen und inhomogenen Abläufen

Formulierung des Problems. Am Eingang N-Kanal-QS empfängt den einfachsten Anforderungsfluss mit der Dichte λ. Die Dichte des einfachsten Serviceflusses jedes Kanals ist gleich μ. Wenn bei der eingegangenen Serviceanfrage alle Kanäle frei sind, wird sie gleichzeitig für den Service angenommen und bedient l Kanäle ( l < N). In diesem Fall hat der Servicefluss einer Anfrage eine Intensität l.

Wenn eine zur Wartung eingegangene Anfrage eine Anfrage im System findet, dann N ≥ 2l Neu eingegangene Anträge werden zur Zustellung angenommen und gleichzeitig bearbeitet l Kanäle.

Wenn die Anfrage zur Wartung im System gefunden wird ich Anwendungen ( ich= 0,1, ...), während ( ich+ 1)l≤ N, dann wird die empfangene Anfrage bearbeitet l Kanäle mit einer Gesamtkapazität l. Wird eine neu eingegangene Bewerbung im System gefunden J Anfragen, und zwei Ungleichungen werden gleichzeitig erfüllt: ( J + 1)l > N Und J < N, dann wird der Antrag zur Zustellung angenommen. In diesem Fall können einige Anträge zugestellt werden l Kanäle, der andere Teil kleiner als l, Anzahl der Kanäle, aber alle N Kanäle, die zufällig auf die Anwendungen verteilt werden. Wenn eine neu eingegangene Bewerbung im System gefunden wird N Bewerbungen werden abgelehnt und nicht zugestellt. Eine bearbeitete Anwendung wird bis zum Ende bearbeitet (Anwendungen sind „geduldig“).

Der Zustandsgraph eines solchen Systems ist in Abb. dargestellt. 3.8.

Reis. 3.8. QS-Zustandsdiagramm mit Ausfällen und Teilausfällen

gegenseitige Unterstützung zwischen den Kanälen

Beachten Sie, dass der Zustandsgraph des Systems bis zum Zustand ist X H stimmt mit dem Zustandsgraphen des klassischen Warteschlangensystems mit Ausfällen überein, dargestellt in Abb. 2, bis hin zur Notation der Flussparameter. 3.6.

Somit,

(ich = 0, 1, ..., H).

Diagramm der Systemzustände, ausgehend vom Zustand X H und endet mit dem Staat X N, stimmt bis zur Notation mit dem Zustandsgraphen von QS mit voller gegenseitiger Unterstützung überein, dargestellt in Abb. 3.7. Auf diese Weise,

.

Wir führen die Notation λ / ein lμ = ρ l ; λ / Nμ = χ, also

Unter Berücksichtigung des normalisierten Zustands erhalten wir

Um die weitere Notation zu verkürzen, führen wir die Notation ein

Finden Sie die Eigenschaften des Systems.

Anwendungsdienstwahrscheinlichkeit

Die durchschnittliche Anzahl der Anwendungen im System,

Durchschnittlich ausgelastete Kanäle

.

Wahrscheinlichkeit, dass ein bestimmter Kanal belegt ist

.

Die Wahrscheinlichkeit der Belegung aller Kanäle des Systems

3.4.4. Warteschlangensysteme mit Ausfällen und inhomogenen Abläufen

Formulierung des Problems. Am Eingang N-Kanal QS erhält einen inhomogenen Elementarstrom mit einer Gesamtintensität λ Σ , und

λ Σ = ,

wo λ ich- die Intensität der Anwendungen in ich-m Quelle.

Da der Anforderungsfluss als Überlagerung von Anforderungen aus verschiedenen Quellen betrachtet wird, kann der kombinierte Fluss mit ausreichender Genauigkeit für die Praxis als Poisson betrachtet werden N = 5...20 und λ ich ≈ λ ich +1 (ich1,N). Die Serviceintensität eines Geräts verteilt sich nach dem Exponentialgesetz und beträgt μ = 1/ T. Servicegeräte zur Wartung einer Anwendung werden in Reihe geschaltet, was einer Erhöhung der Servicezeit um das Vielfache gleichkommt, da viele Geräte zur Wartung zusammengefasst werden:

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

Wo T obs – Servicezeit anfordern; k- die Anzahl der Servicegeräte; μ obs – die Intensität des Anwendungsdienstes.

Im Rahmen der in Kapitel 2 getroffenen Annahmen stellen wir den QS-Zustand als Vektor dar, wobei k M ist die Anzahl der Anfragen im System, die jeweils bearbeitet werden M Haushaltsgeräte; L = Q max- Q min +1 ist die Anzahl der Eingabeströme.

Dann ist die Anzahl der belegten und freien Geräte ( N zan ( ),N sv ( )) fähig ist wie folgt definiert:

Nicht im Land Das System kann in jeden anderen Zustand wechseln . Da hat das System L Eingabeströme, dann ist es von jedem Zustand aus potenziell möglich L direkte Übergänge. Aufgrund der begrenzten Ressourcen des Systems sind jedoch nicht alle dieser Übergänge machbar. Lassen Sie das QS im Staat sein und es kommt ein entsprechender Antrag M Haushaltsgeräte. Wenn M≤ N sv ( ), dann wird die Anforderung zur Bearbeitung angenommen und das System geht in einen Zustand mit der Intensität λ über M. Wenn die Anwendung mehr Geräte benötigt, als es kostenlose gibt, erhält sie einen Denial-of-Service und der QS bleibt im Status . Wenn möglich Es gibt Anwendungen, die Folgendes erfordern M Geräte, dann wird jedes von ihnen mit der Intensität  gewartet M, und die Gesamtintensität der Bearbeitung solcher Anfragen (μ M) ist definiert als μ M = k M μ / M. Wenn die Bearbeitung einer der Anfragen abgeschlossen ist, geht das System in einen Zustand über, in dem die entsprechende Koordinate einen Wert hat, der um eins kleiner ist als im Zustand ,=, d.h. Es findet ein umgekehrter Übergang statt. Auf Abb. In Abb. 3.9 zeigt ein Beispiel eines QS-Vektormodells für N = 3, L = 3, Q min = 1, Q max=3, P(M) = 1/3, λ Σ = λ, die Intensität der Instrumentenwartung beträgt μ.

Reis. 3.9. Ein Beispiel für ein QS-Vektormodelldiagramm mit Denial-of-Service

Also jeder Staat gekennzeichnet durch die Anzahl der bearbeiteten Anfragen eines bestimmten Typs. Zum Beispiel in einem Staat
Ein Anspruch wird von einem Gerät und ein Anspruch von zwei Geräten bedient. In diesem Zustand sind alle Geräte beschäftigt, daher sind nur umgekehrte Übergänge möglich (das Eintreffen eines Kunden in diesem Zustand führt zu einer Dienstverweigerung). Wenn die Bearbeitung der Anfrage des ersten Typs früher beendet wurde, wechselt das System in den Status (0,1,0) mit der Intensität μ, aber wenn der Dienst des zweiten Anforderungstyps früher beendet wurde, geht das System in den Zustand über (0,1,0) mit Intensität μ/2.

Aus dem Zustandsgraphen mit angelegten Übergangsintensitäten wird ein System linearer algebraischer Gleichungen erstellt. Aus der Lösung dieser Gleichungen werden die Wahrscheinlichkeiten ermittelt R(), anhand derer das QS-Merkmal bestimmt wird.

Erwägen Sie die Suche R otk (Wahrscheinlichkeit einer Dienstverweigerung).

,

Wo S ist die Anzahl der Graphzustände des QS-Vektormodells; R() ist die Wahrscheinlichkeit, dass sich das System in diesem Zustand befindet .

Die Anzahl der Staaten ist wie folgt definiert:

, (3.22)

;

Bestimmen wir die Anzahl der Zustände des QS-Vektormodells nach (3.22) für das in Abb. gezeigte Beispiel. 3.9.

.

Somit, S = 1 + 5 + 1 = 7.

Um reale Anforderungen an Servicegeräte umzusetzen, ist eine ausreichend große Anzahl erforderlich N (40, ..., 50) und die Anforderungen an die Anzahl der Servicegeräte der Anwendung liegen in der Praxis im Bereich von 8–16. Bei einem solchen Verhältnis von Instrumenten und Anfragen wird die vorgeschlagene Methode zur Ermittlung der Wahrscheinlichkeiten äußerst umständlich, da Das QS-Vektormodell verfügt über eine große Anzahl von Zuständen S(50) = 1790, S(60) = 4676, S(70) = 11075 und die Größe der Koeffizientenmatrix des algebraischen Gleichungssystems ist proportional zum Quadrat S, was viel Computerspeicher und viel Computerzeit erfordert. Der Wunsch, den Rechenaufwand zu reduzieren, regte die Suche nach wiederkehrenden Rechenmöglichkeiten an R() basierend auf multiplikativen Darstellungsformen von Zustandswahrscheinlichkeiten. Der Beitrag stellt einen Ansatz zur Berechnung vor R():

(3.23)

Die Verwendung des in der Arbeit vorgeschlagenen Kriteriums der Äquivalenz der globalen und detaillierten Bilanzen von Markov-Ketten ermöglicht es, die Dimension des Problems zu reduzieren und Berechnungen auf einem Computer mit durchschnittlicher Leistung unter Verwendung der Wiederholung von Berechnungen durchzuführen. Darüber hinaus besteht die Möglichkeit:

– Berechnen Sie für beliebige Werte N;

– Beschleunigen Sie die Berechnung und reduzieren Sie die Kosten für Maschinenzeit.

Andere Eigenschaften des Systems können auf ähnliche Weise definiert werden.

Gleichungssystem

QS mit Ausfällen für eine zufällige Anzahl von Versorgungsflüssen ist ein Vektormodell für Poisson-Flüsse. Graph, Gleichungssystem.

Stellen wir QS als Vektor dar, wobei k m ist die Anzahl der Anfragen im System, die jeweils bearbeitet werden M Haushaltsgeräte; L= Q max- Q min +1 ist die Anzahl der Eingabeströme.

Wenn die Anforderung zur Bearbeitung angenommen wird, geht das System in einen Zustand mit der Intensität λ über M.

Nach Abschluss der Bearbeitung einer der Anforderungen geht das System in einen Zustand über, in dem die entsprechende Koordinate einen Wert hat, der um eins kleiner ist als im Zustand , = , d. h. Es findet ein umgekehrter Übergang statt.

Ein Beispiel für ein QS-Vektormodell für N = 3, L = 3, Q min = 1, Q max=3, P(M) = 1/3, λ Σ = λ, die Intensität der Instrumentenwartung beträgt μ.

Aus dem Zustandsgraphen mit angelegten Übergangsintensitäten wird ein System linearer algebraischer Gleichungen erstellt. Aus der Lösung dieser Gleichungen werden die Wahrscheinlichkeiten ermittelt R(), anhand derer die QS-Merkmale bestimmt werden.

QS mit einer unendlichen Warteschlange für Poisson-Ströme. Diagramm, Gleichungssystem, berechnete Verhältnisse.

Systemdiagramm

Wo N– Anzahl der Servicekanäle, l– Anzahl der sich gegenseitig unterstützenden Kanäle

QS mit unendlicher Warteschlange und teilweiser gegenseitiger Unterstützung für willkürliche Ströme. Diagramm, Gleichungssystem, berechnete Verhältnisse.

Systemdiagramm

Gleichungssystem

–λ 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 mit unendlicher Warteschlange und vollständiger gegenseitiger Unterstützung für beliebige Ströme. Diagramm, Gleichungssystem, berechnete Verhältnisse.

Systemdiagramm

Gleichungssystem

QS mit einer endlichen Warteschlange für Poisson-Ströme. Diagramm, Gleichungssystem, berechnete Verhältnisse.

Systemdiagramm

Gleichungssystem

Auslegungsverhältnisse:

,

In den allermeisten Fällen ist das Warteschlangensystem in der Praxis mehrkanalig, d. h. mehrere Anwendungen können parallel bedient werden und daher , Servicekanalmodelle(wobei die Anzahl der Servicekanäle N>1) sind zweifellos von Interesse.
Der von diesem Modell beschriebene Warteschlangenprozess wird durch die Intensität des Eingangsflusses λ charakterisiert, während nicht mehr als N Kunden (Anwendungen). Die durchschnittliche Bearbeitungszeit für eine Anfrage beträgt 1/μ. Der Betriebsmodus des einen oder anderen Dienstkanals hat keinen Einfluss auf den Betriebsmodus anderer Dienstkanäle des Systems, und die Dauer des Dienstvorgangs für jeden der Kanäle ist eine Zufallsvariable, die einem Exponentialverteilungsgesetz unterliegt. Das ultimative Ziel der Verwendung parallel geschalteter Servicekanäle besteht darin, (im Vergleich zu einem Einkanalsystem) die Geschwindigkeit der Serviceanforderungen durch gleichzeitige Bedienung zu erhöhen N Kunden.
Die stationäre Lösung des Systems hat die Form:
;
Wo, .
Formeln zur Berechnung von Wahrscheinlichkeiten werden aufgerufen Erlang-Formeln.
Bestimmen wir die probabilistischen Eigenschaften der Funktion eines Mehrkanal-QS bei Ausfällen im stationären Modus:
Ausfallwahrscheinlichkeit:
.
da der Antrag abgelehnt wird, wenn er zu einem Zeitpunkt eintrifft, an dem alle Kanäle belegt sind. Wert R otk charakterisiert die Vollständigkeit des Dienstes des eingehenden Stroms;
die Wahrscheinlichkeit, dass der Antrag zur Zustellung angenommen wird(es ist auch der relative Durchsatz des Systems) ergänzt R otk bis zu eins:
.
absolute Bandbreite

durchschnittliche Anzahl der vom Dienst belegten Kanäle() die folgende:

Der Wert charakterisiert den Belastungsgrad des QS.
Beispiel. Lassen N-channel QS ist ein Rechenzentrum (CC) mit drei ( N=3) austauschbare PCs zur Lösung eingehender Aufgaben. Der Fluss der im CC eintreffenden Aufgaben hat eine Intensität von λ=1 Aufgabe pro Stunde. Die durchschnittliche Dienstdauer beträgt ca. =1,8 Stunden.
Zur Berechnung der Werte ist erforderlich:
- Wahrscheinlichkeiten der Anzahl belegter CC-Kanäle;
- die Wahrscheinlichkeit einer Verweigerung der Zustellung des Antrags;
- relative Kapazität des CC;
- absolute Kapazität von CC;
- die durchschnittliche Anzahl der im CC beschäftigten PCs.
Bestimmen Sie, wie viel zusätzlicher PC Sie kaufen müssen, um den Durchsatz des Rechenzentrums um das Zweifache zu steigern.
Lösung.
Definieren wir den Parameter μ des Serviceflusses:
.
Die reduzierte Intensität des Bewerbungsflusses
.
Wir ermitteln die Grenzwahrscheinlichkeiten von Zuständen mithilfe der Erlang-Formeln:

Die Wahrscheinlichkeit, dass die Zustellung des Antrags verweigert wird
.
Relativer VC-Durchsatz
.
Absoluter Durchsatz von CC:
.
Durchschnittliche Anzahl belegter Kanäle – PC

Somit sind im etablierten Betriebsmodus des QS durchschnittlich 1,5 von drei Rechnern belegt – die restlichen anderthalb bleiben im Leerlauf. Die Arbeit des betrachteten CC kann kaum als zufriedenstellend angesehen werden, da das Zentrum im Durchschnitt in 18 % der Fälle keine Bewerbungen bearbeitet (Р 3 = 0,180). Es liegt auf der Hand, dass die Kapazität des Rechenzentrums bei gegebenem λ und μ nur durch eine Erhöhung der PC-Anzahl erhöht werden kann.
Lassen Sie uns ermitteln, wie viel PC-Nutzung erforderlich ist, um die Anzahl der nicht bearbeiteten Anfragen, die beim CC eingehen, um das Zehnfache zu reduzieren, d. h. sodass die Wahrscheinlichkeit des Scheiterns bei der Lösung von Problemen 0,0180 nicht überschreitet. Dazu verwenden wir die Formel für die Ausfallwahrscheinlichkeit:

Machen wir die folgende Tabelle:

Bei der Analyse der Daten in der Tabelle ist zu beachten, dass die Erweiterung der Anzahl der CC-Kanäle für die gegebenen Werte von λ und μ auf 6 PC-Einheiten die Zufriedenheit der Anwendungen zur Problemlösung um 99,22 % gewährleistet, da mit N= 6 Wahrscheinlichkeit einer Dienstverweigerung ( R otk) beträgt 0,0078.

Betrachten wir ein Mehrkanal-Warteschlangensystem (es gibt insgesamt n Kanäle), bei dem Anfragen mit einer Rate von λ eingehen und mit einer Rate von μ bedient werden. Eine im System eingetroffene Anfrage wird bedient, wenn mindestens ein Kanal frei ist. Wenn alle Kanäle belegt sind, wird die nächste im System eingehende Anfrage abgelehnt und verlässt das QS. Wir nummerieren die Systemzustände nach der Anzahl der belegten Kanäle:

• S 0 – alle Kanäle sind kostenlos;
• S 1 – ein Kanal ist belegt;
• S 2 – zwei Kanäle sind belegt;
• Sk- beschäftigt k Kanäle;
• SN– Alle Kanäle sind belegt.

Reis. 7.24
Abbildung 6.24 zeigt einen Zustandsgraphen, in dem Sich- Kanal Nummer; λ ist die Intensität des Bewerbungseingangs; μ - bzw. die Intensität der Serviceanfragen. Bewerbungen gelangen mit konstanter Intensität in das Warteschlangensystem und belegen nach und nach Kanäle nacheinander; Wenn alle Kanäle belegt sind, wird die nächste beim QS eintreffende Anfrage abgelehnt und verlässt das System.
Bestimmen wir die Intensitäten der Ereignisflüsse, die das System von Zustand zu Zustand überführen, wenn es sich sowohl von links nach rechts als auch von rechts nach links entlang des Zustandsgraphen bewegt.
Lassen Sie das System beispielsweise im Zustand sein S 1 , d.h. ein Kanal ist belegt, da an seinem Eingang eine Beanspruchung vorliegt. Sobald die Anfrage bearbeitet ist, wechselt das System in den Status S 0 .
Wenn beispielsweise zwei Kanäle belegt sind, dann ist der Dienstfluss, der das System aus dem Zustand versetzt S 2 pro Staat S 1 wird doppelt so intensiv sein: 2-μ; bzw. wenn beschäftigt k Kanäle ist die Intensität gleich k-μ.

Der Dienstprozess ist ein Prozess des Todes und der Reproduktion. Die Kolmogorov-Gleichungen für diesen speziellen Fall haben die folgende Form:

(7.25)
Die Gleichungen (7.25) werden aufgerufen Erlang-Gleichungen .
Um die Werte der Wahrscheinlichkeiten der Zustände zu finden R 0 , R 1 , …, RN, ist es notwendig, die Anfangsbedingungen zu bestimmen:
– R 0 (0) = 1, d. h. es liegt eine Anforderung am Systemeingang vor;
– R 1 (0) = R 2 (0) = … = RN(0) = 0, d. h. zum ersten Zeitpunkt ist das System frei.
Nach der Integration des Differentialgleichungssystems (7.25) erhalten wir die Werte der Zustandswahrscheinlichkeiten R 0 (T), R 1 (T), … RN(T).
Uns interessieren aber viel mehr die Grenzwahrscheinlichkeiten von Zuständen. Für t → ∞ und unter Verwendung der Formel, die wir bei der Betrachtung des Prozesses von Tod und Fortpflanzung erhalten, erhalten wir die Lösung des Gleichungssystems (7.25):

(7.26)
In diesen Formeln ist das Intensitätsverhältnis λ / μ Für den Bewerbungsfluss ist es zweckmäßig, diese zu benennen ρ .Dieser Wert heißt die verringerte Intensität des Bewerbungsflusses, Das heißt, die durchschnittliche Anzahl der im QS eintreffenden Bewerbungen für die durchschnittliche Bearbeitungszeit einer Bewerbung.

Unter Berücksichtigung der obigen Notation hat das Gleichungssystem (7.26) die folgende Form:

(7.27)
Diese Formeln zur Berechnung von Grenzwahrscheinlichkeiten werden aufgerufen Erlang-Formeln .
Wenn wir alle Wahrscheinlichkeiten der QS-Zustände kennen, ermitteln wir die QS-Effizienzkennwerte, also den absoluten Durchsatz A, relativer Durchsatz Q und Wahrscheinlichkeit des Scheiterns R offen
Eine im System eingehende Anfrage wird abgelehnt, wenn alle Kanäle belegt sind:

.
Die Wahrscheinlichkeit, dass der Antrag zur Zustellung angenommen wird:

Q = 1 – R ok,
Wo Q ist der durchschnittliche Anteil der eingehenden Anfragen, die vom System bearbeitet werden, oder durchschnittliche Anzahl der von QS betreuten Bewerbungen pro Zeiteinheit, bezogen auf die durchschnittliche Anzahl der in diesem Zeitraum eingegangenen Bewerbungen:

A=λ Q=λ (1-P offen)
Darüber hinaus ist eines der wichtigsten Merkmale von QS mit Misserfolgen durchschnittlich ausgelastete Kanäle. IN N-Kanal-QS mit Ausfällen, diese Zahl stimmt mit der durchschnittlichen Anzahl der Bewerbungen im QS überein.
Die durchschnittliche Anzahl der Anwendungen k kann direkt anhand der Wahrscheinlichkeiten der Zustände Р 0 , Р 1 , … , Р n berechnet werden:

,
d.h. wir finden den mathematischen Erwartungswert einer diskreten Zufallsvariablen, die einen Wert von 0 bis annimmt N mit Wahrscheinlichkeiten R 0 , R 1 , …, RN.
Noch einfacher ist es, den Wert von k als absoluten Durchsatz des QS auszudrücken, d. h. A. Der Wert von A ist die durchschnittliche Anzahl von Anwendungen, die vom System pro Zeiteinheit bedient werden. Ein belegter Kanal bedient μ-Anfragen pro Zeiteinheit, also die durchschnittliche Anzahl belegter Kanäle