Knowledge & Learning

home *** CD-ROM | disk | FTP | other *** search

/ Knowledge & Learning / WISS_LERN.iso / doslern / computer / educard / bs___2.sti < prev next >

Wrap

Text File | 1992-02-26 | 74.6 KB | 2,086 lines

YCPAA #!!# - Modellbildung - @CEInhalt @CPDas Thema von BS___2 sind Modellbildung und Systemanalyse. Start mit ⌐Systemanalyse@BS___2¬ AHBAA #!!# Systemanalyse @HEEinführung @HBErst vor wenigen Jahren (seit ca. 1967) wurde damit begonnen, das Verhalten von ⌐Betriebssystem@BS1¬en durch Modellbildungen mathematisch zu beschreiben. Das Ziel ist also, das Verhalten von Betriebssystemen in Abhängigkeit - vom Benutzerverhalten, - von der hardwaremäßigen Konfiguration der Anlage und - von speziellen Systemparametern, die das ⌐Scheduling@BS1¬ beeinflussen, mathematisch mit Hilfe von Modellen zu beschreiben. Man kann dann leicht feststellen, wie sich zum Beispiel eine Konfigurationsänderung auf das Systemverhalten auswirkt. Einige wichtige und typische Fragestellungen bei der Untersuchung von Betriebssystemen sind die folgenden: @HEa) Zeitverhalten @HBDer Benutzer eines Systems erwartet, daß die ⌐Antwortzeit@BS1¬ (response time) erstens voraussagbar ist (geringe ⌐Varianz@BS2¬ bei gleicher Aufgabenstellung) und zweitens der zu verarbeitenden Aufgabe entspricht (einfache Aufgabe - kurze Antwortzeit, komplexe Aufgabe - längere Antwortzeit). Im Batch-System (siehe ⌐Stapelbetrieb@BS2¬) entspricht die Antwortzeit (beim Time-Sharing-System) der ⌐Verweilzeit@BS2¬ (turn around time). Im Real-Time-System entspricht die Antwortzeit der Reaktion des Systems auf ein Ereignis. @HEVerweilzeit: @HBZeit vom Beginn des Auftrags (Lesen der ersten Lochkarte) bis zum Vorliegen der Ergebnisse. @HEAntwortzeit: @HBZeitspanne zwischen dem Ende einer Benutzereingabe und dem Vorliegen der vollständigen Antwort darauf. @HEb) Durchsatz @HBDie Zahl der Aufträge, die eine ⌐Bedieneinheit@BS2¬ (z. B. CPU, Kanal) in einer Zeiteinheit fertigstellt, heißt ⌐Durchsatz@BS1¬ (troughput) der Bedieneinheit (Funktionseinheit). Im ⌐Stapelbetrieb@BS2¬ ist Durchsatz = Aufträge pro Zeiteinheit Im ⌐Dialogbetrieb@BS2¬ ist Durchsatz = Transaktion pro Zeiteinheit ⌐Transaktion@BS2¬ @HB= einzelner Aufruf einer Systemfunktion (z. B. Löschen, Ersetzen, Modifizieren eines Datenfeldes) @HEAuslastung @HBUnter ⌐Auslastung@BS1¬ (utilization, relativ troughput) einer Funktionseinheit versteht man das Verhältnis von in einem Zeitraum erbrachter Leistung zu der in diesem Zeitraum maximal erbringbaren Leistung. @HL in t1..t2 erbrachte Leistung Auslastung δ = ──────────────────────────────────────── in t1..t2 maximal erbringbare Leistung Anzahl günstiger Fälle = ────────────────────────────── Anzahl aller möglichen Fälle = Wahrscheinlichkeit, daß das System arbeitet @AO ╔════════════╗ @HB @AO ║ δ = 1 - Po ║ @HB Po = Wahrscheinlichkeit, @AO ╚════════════╝ @HB daß keiner im System ist @HEc) Engpässe @HBDas Verhalten eines Systems wird wesentlich von dem Gerät bestimmt, das am ehesten voll ausgelastet ist. Es ist daher wichtig zu wissen, wo Engpässe (bottlenecks) auftreten. weiter mit ⌐Queue-Theory@BS___2¬ AHBAA #!!# Queue-Theory @HETheorie der Warteschlangen @HBDie analytischen Modelle, die im folgenden entwickelt werden, dienen dazu, Beziehungen zwischen Systemparametern und bestimmten Kriterien in Form von Gleichungen aufzustellen. Bei den Betriebssystemmodellen gelangt man so zur ⌐Warteschlangen@BS2¬. @EHGrundbegriffe der Theorie der Warteschlangen @HB @HEWarteschlangenmodell @HE┌───────────────┐ @HB∩ @HP┌┬┬┬┬┬┬┬┬┬┬┐ @HBµ @HE│ │ @HA─────────>@HP│││@HBQueue@HP│││├@HA──────────────>@HE│ @HBBedieneinheit @HE├@HA────────> @HP└┴┴┴┴┴┴┴┴┴┴┘ @HE│ │ └───────────────┘ @HB∩ : Ankunftsrate µ : Bedienrate @HBEs kommen Kunden, die die ⌐Bedieneinheit@BS2¬ benutzen wollen. Wenn die Bedieneinheit besetzt ist, sie also arbeitet, muß sich der Kunde vorerst in eine ⌐Warteschlange@BS2¬ (Queue) einreihen. Ist die Betriebs- einheit leer und er ist an der Reihe, wird er aus der Warteschlange entfernt und darf die Betriebseinheit betreten. Nach der Abfertigung in der Bedieneinheit verläßt der Kunde das System. Es wird festgelegt, daß die Betriebseinheit nur dann leer sein kann, wenn auch die Warteschlange leer ist. Es soll also nicht vorkommen, daß Kunden vor einer leeren Betriebseinheit warten müssen. @HEZeitliches Verhalten in einem Warteschlangensystem @HBVn @HL«─────────────────────────────────» @HO/│\ /│\ @HBWn @HO│@HBCn-1 @HBBn @HO│@HBCn @HL«────────────────» «──────────────» @HB BE @HA════════════════════════════════════════════════════════════ @HO/│\ @HO/│\ @HO/│\ @HO│@HBCn-1 @HO│@HBCn @HO│@HBCn+1 @HO│ │ │ @HBtn @HBtn+1 @HBQueue @HA════════════════════════════════════════════════════════════ @HO/│\ /│\ @HPtn : Ankunftszeit des n-ten Kunden @HO│@HBCn @HBAn+1 @HO│@HBCn+1 @HPAn+1: Zeit zwischen dem Eintreffen von Cn @HL«────────────» @HPund Cn+1 (Zwischenankunftszeit) @HPWn : Wartezeit des Kunden Cn in der Queue Cn : n-ter Kunde (customer) Bn : Bedienzeit für den Kunden Cn Vn : Verweilzeit des Kunden Cn @HBweiter mit ⌐Ankunftsprozeß@BS___2¬ AHBAA #!!# Ankunftsprozeß @HEAnkunftsrate @HBWenn in T Zeiteinheiten N Kunden kommen, so sagt man, sie kommen mit der Ankunftsrate ∩. @AO ╔═════════╗ @HB @AO ║ N ║ @HB @AO ║ ∩ = ─── ║ @HB @AO ║ T ║ @HB @AO ╚═════════╝ @HB @HEZwischenankunftszeit @HBDen mittleren zeitlichen Abstand mit dem die N Kunden in T Zeiteinheiten ankommen nennt man Zwischenankunftszeit A @HL T 1 A = ─── = ─── N ∩ @HBUm statistische Aussagen über den Ankunftsprozeß machen zu können, müssen einige plausible und naheliegende Annahmen gemacht werden: 1) Die Kunden sollen unabhängig voneinander ankommen. Sie dürfen sich also nicht verabreden. 2) Die Kunden müssen zufällig verteilt kommen. Es soll also nicht vor- kommen, daß die Kunden durch äußere Umstände angezogen oder abge- schreckt werden. (Beispiel: Autos fahren über ampelgesteuerte Kreuzung bei genügender Verkehrsdichte nicht mehr zufällig verteilt, sondern in gleichen zeitlichen Abständen.) 3) Es dürfen nicht zwei oder mehr Kunden gleichzeitig kommen. @HEWie groß ist die Wahrscheinlichkeit, daß in t Zeiteinheiten genau n Kunden eintreffen ? @HBPn [t] = ? @HPAntwort: Poisson-Verteilung @HAPn [t] @HP/│\ @HO*** @HP│ @HO* * @HPn @HP│ @HO* * @HP(∩*t) -∩t @HP│ @HO* * @HPPn [t] = ──────── * e @HP│ @HO* * @HPn! @HP│ @HO* * @HP│ @HO* * @HP│ @HO* * @HP│ @HO** ** @HP└────────────────────────┬───────────────────────────────────> @HA∩*t = N n @HEWie groß ist die Wahrscheinlichkeit, daß die Zwischenankunftszeit a kleiner oder gleich t ist ? @HBP [a ≤ t] ? @HPAntwort: Exponentialverteilung @HAP [a≤t] @HP/│\ @HA1 @HP│@HB_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ @HP│ @HO* * * * * @HPP [a≤t] = 1 - P [a>t] @HP│ @HO* @HP = 1 - Po [t] @HP│ @HO* @HP│ @HO* @HP -∩t @HP│ @HO* @HP = 1 - e @HP│ @HO* @HP│ @HO* @HP│@HO* @HP└────────────────────────────────────────> @HAt @HBVoraussetzung dafür, daß die Verteilungsfunktion für die Zwischen- ankunftszeiten des Ankunftsprozesses die Exponentialverteilung ist, ist die Poisson-Verteilung der Ankunftsprozesse. @HEHerleitung der Verteilung des Ankunftsprozesse @HBMan tut so, als ob bis t die Zahl Pn [t] bekannt ist, und läßt dann die Zeit um delta t (= dt) voranschreiten. Für einen genügend kleinen Zeitraum dt ist die Wahrscheinlichkeit, daß ein Kunde eintrifft, proportional zur Ankunftsrate ∩ und proportional zum Zeitintervall dt: @HL P [es kommt 1 Kunde] = ∩ * dt P [es kommt kein Kunde] = 1 - ∩ * dt @HEWie groß ist die Wahrscheinlichkeit, daß im Zeitraum [0, t + dt] genau n Kunden ankommen ? @HBEs sind zwei Fälle zu unterscheiden: a) In [0, t] sind bereits n Ankünfte erfolgt. Dann darf in der Zeit [t, t + dt] keine weitere Ankunft mehr erfolgen. b) In [0, t] sind erst n - 1 Ankünfte erfolgt. Dann muß in der Zeit [t, t + dt] genau ein Kunde neu dazu kommen. Es gilt also: @HL Pn [t + dt] = Pn [t] * P [es kommt kein Kunde in [t, t + dt]] + Pn-1 [t] * P [es kommt 1 Kunde in [t, t + dt]] <==> Pn [t + dt] = Pn [t] * (1 - ∩ * dt) + Pn-1 [t] * (∩ * dt) @HEUmrechnung: @HL Pn [t + dt] = Pn [t] * (1 - ∩ * dt) + Pn-1 [t] * ∩ * dt <==> Pn [t + dt] = Pn [t] - Pn [t] * ∩ * dt + Pn-1 [t] * ∩ * dt <==> Pn [t + dt] - Pn [t] = -∩ * dt Pn [t] + ∩ * dt * Pn-1 [t] <==> Pn [t + dt] - Pn [t] = ∩ * dt (Pn-1 [t] - Pn [t]) Pn [t + dt] - Pn [t] <==> ──────────────────── = ∩ * (Pn-1 [t] - Pn [t]) dt @HBfür dt -> 0 ergibt sich die Differentialgleichung: @HL dPn [t] dt -> 0: ───────── = ∩ * (Pn-1 [t] - Pn [t]) dt @HBWenn man annimmt, daß es keine negativen Ankünfte (= Abgänge) gibt, das heißt Pn [t] = 0 für n < 0, so erhält man @HL dPo [t] ───────── = -∩ * Po [t] dt @HELösung für Pn [t] mit Hilfe erzeugender Funktionen (z-Transformation) @HB Ansatz @HL ∞ n G (z) = Σ Pn [t] * z n=0 @HBAus dem Ansatz folgt: @HL ∞ n ∞ n+1 @HBa) @HLΣ Pn-1 [t] * z = Σ Pn [t] * z = z * G (z) n=1 n=0 ∞ dPn [t] n dG (z) @HBb) @HLΣ ───────── * z = ──────── n=0 dt dt @HBDie Differential-Differenzengleichung lautet also mit erzeugenden Funktionen geschrieben: @HL dG (z) ──────── = ∩ * (z * G (z) - G (z)) dt <==> @HL dG (z) ──────── = ∩ * G (z) * (z - 1) dt @HBDie Trennung der Variablen ergibt: @HL dG (z) ──────── = ∩ * (z - 1) * dt G (z) @HBEs gilt allgemein: @HBa) @HBb) @HL1 @HL⌠ f' (x) (ln x)' = ─── @HL│ ──────── = ln |f (x)| x @HL⌡ f (x) @HBc) @HLn n-1 (const * x )' = const * n * x @HBDeshalb erhält man nach der Integration @HL ln G (z) = ∩ * (z - 1) * t + c @HB Da G (1) = 1 und ln 1 = 0 ist, muß c = 0 sein. Als Ergebnis erhält man daher (nach Entlogarithmisierung) @HL ∩ * (z - 1) * t G (z) = e ∩zt -∩t = e * e @HBDie Lösung muß man mit dem Ansatz vergleichen (Rücktransformation) Ansatz gefundene Lösung @HL ∞ n -∩t ∩zt G (z) = Σ Pn [t] * z G (z) = e * e n=0 @HB Umformung der gefundenen Lösung (um sie mit dem Ansatz zu vergleichen) @HL n x ∞ x mit e = Σ ──── gilt n=0 n! n -∩t ∞ (∩ * t * z) G (z) = e * Σ ────────────── <==> @HB(siehe nächste Seite) @HLn=0 n! @HL n ∞ -∩t (∩ * t) n G (z) = Σ e * ───────── * z n=0 n! @HB Man sieht aus dem Koeffizientenvergleich @HL n -∩t (∩ * t) Pn [t] = e * ────────── n! @HBDiese Gleichung stellt die @HL n @HBPoisson-Verteilung dar. Sie gibt an, @HL (∩ * t) -∩t @HBwie groß die Wahrscheinlichkeit ist, @HL = ────────── * e @HBdaß im Zeitraum [0, t] genau n Ankünfte @HL n! @HBvon Kunden stattfinden. Der Ankunftsprozeß ist, unter den gemachten (plausiblen und naheliegenden) Annahmen , @HPPoisson @HBverteilt. @HEHerleitung der Verteilung der Zwischenankunftszeiten @HBFrage: Wie groß ist die Wahrscheinlichkeit, daß die Zwischenankunftszeit a kleiner oder gleich t ist ? Das entgegengesetzte Ereignis zu dem aus der Frage ist, daß die Zwischenankunftszeit a größer als t ist. In diesem Fall darf in der Zeit [0, t] kein Kunde ankommen. Aus der Poisson-Verteilung läßt sich aber sofort angeben, wie groß die Wahrscheinlichkeit dafür ist (nämlich Po [t]). Die beiden Ereignisse schließen sich aus, bilden zusammen aber ein sicheres Ereignis, das heißt @HL P [a ≤ t] + P [a > t] = 1 <==> P [a ≤ t] = 1 - P [a > t] ==> P [a ≤ t] = 1 - Po [t] <==> @HB(siehe nächste Seite) @HBmit @HL 0 (∩ * t) -∩t Po [t] = ────────── * e 0! @HB gilt@HL P [a ≤ t] = 1 - Po [t] <==> -∩t P [a ≤ t] = 1 - e @HBDiese Gleichung stellt die Exponentialverteilung dar. Die Zwischenankunftszeiten sind unter der Annahme, daß der Ankunfts- prozeß eine Poisson-Verteilung ist, @HPexponential @HBverteilt. @HB weiter mit ⌐Bedienprozeß@BS___2¬ AHBAA #!!# Bedienprozeß @HEBedienrate: @HBWenn in T Zeiteinheiten N Kunden bedient werden, so sagt man, sie werden mit der Bedienrate µ bedient. @AO ╔═════════╗ @HB @AO ║ N ║ @HB @AO ║ µ = ─── ║ @HB @AO ║ T ║ @HB @AO ╚═════════╝ @HB @HEBedienzeit: @HBDie mittlere Zeit, mit der die N Kunden in T Zeiteinheiten bedient @AO ╔═══════════════╗ @HB @AO ║ T 1 ║ @HB @HBwerden, nennt man ⌐Bedienzeit@BS2¬ B @AO ║ B = ─── = ─── ║ @HB @AO ║ N µ ║ @HB @AO ╚═══════════════╝ @HB @HB siehe auch ⌐Queue-Theory@BS___2¬ @HBFür den Bedienprozeß werden die gleichen (plausiblen und naheliegenden) Annahmen gemacht wie beim Ankunftsprozeß: 1) Die Kunden sollen unabhängig voneinander bedient werden. 2) Die Kunden müssen zufallsmäßig verteilt bedient werden. 3) Es dürfen nicht zwei oder mehr Kunden gleichzeitig bedient werden. Für die Verteilung der Bedienzeit gilt: @HL -µt B (0 ≤ t) = 1 - e @HB Die Gleichung stellt die Exponentialverteilung dar. Sie gibt die Wahrscheinlichkeit dafür an, daß die Bedienzeit eines Kunden kleiner oder gleich t ist. Andsers ausgedrückt: Die Wahrscheinlichkeit, daß in der Zeit [0, t] mindestens ein Kunde bedient wird und die ⌐Bedieneinheit@BS2¬ wieder verläßt. @HBAnmerkung: Während für die Zwischenankunftszeiten eine Exponentialverteilung durchaus realistisch ist, trifft dies für die Bedienzeiten meist nicht so gut zu. Man bleibt jedoch bei dieser Annahme, weil die mathematischen Berechnungen dann besonders einfach sind. weiter mit ⌐Markov-Eigenschaft@BS___2¬ AHBAA #!!# Markov-Eigenschaft @HEMarkov-Eigenschaft der Poisson-Verteilung @HBDie Markov-Eigenschaft besagt, daß die Verteilung @HPkein Gedächtnis@HB hat. Ausgangspunkt ist die Frage: Wird die Wahrscheinlichkeit eines Ereignisses größer, je länger man auf das Ereignis wartet ? Die Wahrscheinlichkeit, daß ein Ereignis frühestens nach dem Zeitraum [0, T] eintritt, ist P [x > t] = Po [t]. Bei der Poisson- -∩T Verteilung ist P [x > T] = e . Es wird angenommen, daß während der Zeit [0, T] kein Ereignis eingetreten ist. Gefragt wird nun nach der Wahrscheinlichkeit, daß in den nächsten t Zeiteinheiten auch kein Ereignis eintritt. Dies entspricht der Frage nach der bedingten Wahrscheinlichkeit P [x > T+t | x > T]. @HL -∩(T+t) e -∩T - ∩t + ∩T -∩t P [x > T+t | x > T] = ────────── = e = e = P [x > t] -∩T e @HB Man sieht, daß die Wartezeit von 0 bis T die Wahrscheinlichkeit für das Ereignis nicht erhöht hat. Man sagt, die Poisson-Verteilung hat kein Gedächtnis, bzw. sie hat die Markov-Eigenschaft (memoryless property). weiter mit ⌐Poisson, Mittelwert@BS___2¬ AHBAA #!!# Poisson, Mittelwert @HEMittelwert einer diskreten Verteilung: @HL _ ∞ E [x] = x = Σ x * pn x=0 @HB Bei der Poisson-Verteilung ist @HL n ∞ (∩ * t) -∩t pn (t) = Σ ────────── * e n=0 n! ==> n _ ∞ (∩ * t) -∩t n = Σ n * ────────── * e n=0 n! @HL n _ -∩t ∞ (∩ * t) n = e * Σ ────────── * n n=0 n! n -∩t ∞ (∩ * t) = e * Σ ────────── n=0 (n-1)! ┌ n-1 ┐ -∩t │ ∞ (∩ * t) │ = e * │ Σ ──────────── │ * ∩ * t │ n=1 (n-1)! │ └ ┘ @HL ┌ n ┐ n _ -∩t │ ∞ (∩ * t) │ x ∞ x n = e * │ Σ ────────── │ * ∩ * t mit e = Σ ──── ==> │ n=0 n! │ n=0 n! └ ┘ -∩t ∩t = e * e * ∩ * t _ n = ∩ * t @HB N @HL_ @HBmit ∩ = ─── : @HLn = N @HB(das heißt im Mittel kommen N Kunden an) t Bei der Poisson-Verteilung sind der Mittelwert und die ⌐Varianz@BS2¬ gleich. weiter mit ⌐Modellkennzeichnung@BS___2¬ AHBAA #!!# Modellkennzeichnung @HEKennzeichnung der Modelle @HBDie Notation von Modelltypen ist wie folgt aufgebaut: @HP A / B / C / D / E @HB wobei die Buchstaben folgende Merkmale kennzeichnen: A: Verhalten des Ankunftsprozesses B: Verhalten des Bedienprozesses C: Anzahl der Bedieneinheiten D: Größe des Speichers, ausgedrückt in aufnehmbarer Kundenkapazität E: Anzahl der Kunden in einem (geschlossenen) System @HBFür A und B verwendet man wiederum bestimmte Buchstaben zur Benennung der Verteilfunktion: M : Exponentialverteilung (@HPM@HBarkov-Eigenschaft) Er: @HPr@HB-stufige @HPEr@HBlang-Verteilung Hr: @HPr@HB-stufige @HPH@HByperexponential-Verteilung D : @HPd@HBeterministisch, das heißt, alle Zwischenankunftszeiten bzw. Bedienzeiten sind gleich groß G : @HPG@HBeneral (die Verteilung ist beliebig) weiter mit ⌐offenes System@BS___2¬ AHBAA #!!# offenes System @HBEin offenes System ist meist ein Ausschnitt aus einem größeren (oft nicht offenen) System. Es können beliebig viele Kunden kommen, die nach ihrer Abfertigung in einer Bedieneinheit (oder in einer von mehreren) das System verlassen. @HE┌───────────────┐ @HB∩ @HP┌┬┬┬┬┬┬┬┬┬┬┐ @HBµ @HE│ │ @HBΦ @HA─────────>@HP│││@HBQueue@HP│││├@HA──────────────>@HE│ @HBBedieneinheit @HE├@HA────────> @HP└┴┴┴┴┴┴┴┴┴┴┘ @HE│ │ └───────────────┘ @HBFragestellung: Wie groß ist die Wahrscheinlichkeit, daß sich bei bekanntem Verhalten von Ankunftsrate ∩ und Bedienrate µ genau n Kunden im System befinden ? Lösung: @HLn P [genau n Kunden im System] = (1-δ) * δ @HB(geometrische Verteilung) bei stationärem Zustand des Systems (also ∩ und µ etwa konstant) @HEHerleitung @HBAnsatz (genau wie beim Ankunftsprozeß): Es wird angenommen, daß die Verhältnisse im System zum Zeitpunkt t bekannt sind. Was passiert in der Zeit [t, t + dt] ? Wenn zum Zeitpunkt t + dt genau n Kunden im System sein sollen, dann gibt es 4 Fälle, die zu unterscheiden sind: a) Zum Zeitpunkt t sind n Kunden im System, - keiner neu hinzugekommen, - keiner fertiggeworden: @HL(1 - ∩ * dt) * (1 - µ * dt)@HB b) Zum Zeitpunkt t sind n - 1 Kunden im System, - 1 neu hinzugekommen - keiner fertiggeworden @HL(∩ * dt) * ( 1 - µ * dt) @HBc) Zum Zeitpunkt t sind n + 1 Kunden im System, - keiner neu hinzugekommen - 1 fertig geworden @HL(1 - ∩ * dt) * (µ * dt)@HB d) Zum Zeitpunkt t sind n Kunden im System, - 1 neu hinzugekommen - 1 fertig geworden @HL(∩ * dt) * (µ * dt)@HB Man erhält also für Pn [t + dt]: @HL Pn [t + dt] = Pn [t] * (1 - ∩ * dt) * (1 - µ * dt) + Pn-1 [t] * (∩ * dt) * (1 - µ * dt) + Pn+1 [t] * (1 - ∩ * dt) * (µ * dt) + Pn [t] * (∩ * dt) * (µ * dt) mit n ≥ 1 @HBUmformungen: Ausmultiplizieren @HLPn [t + dt] = (1 - ∩dt - µdt + ∩µ(dt)²) * Pn [t] + ( ∩dt - ∩µ(dt)²) * Pn-1 [t] + ( µdt - ∩µ(dt)²) * Pn+1 [t] + ( ∩µ(dt)²) * Pn [t] mit n ≥ 1 @HBDie Terme mit (dt)² weglassen (wegen dt -> 0 ???) @HLPn [t + dt] = (1 - ∩dt - µdt) * Pn [t] + ( ∩dt ) * Pn-1 [t] + ( µdt) * Pn+1 [t] mit n ≥ 1 @HBUmordnen und Division durch dt @HL Pn [t + dt] - Pn [t] ────────────────────── = -(∩ + µ) * Pn [t] + ∩ * Pn-1 [t] + µ * Pn+1 [t] dt = ∩ * Pn-1 [t] - (∩ + µ) * Pn [t] + µ * Pn+1 [t] @HBDifferential-Quotienten-Gleichung (also dt -> 0) @HL dPn [t] ───────── = ∩ * Pn-1 [t] - (∩ + µ) * Pn [t] + µ * Pn+1 [t] dt @HBWenn man festlegt, daß es keine negative Anzahl von Kunden im System gibt, so erhält man für @HL dPo [t] ───────── = - ∩ * Po [t] + µ * P1 [t] dt @HBDen Term µ * Po [t] konnte man weglassen, da wenn keiner im System ist, auch keiner in der Bedieneinheit sein kann. @HBDas Verhalten des Systems soll innerhalb des angegebenen Modells @HE┌───────────────┐ @HB∩ @HP┌┬┬┬┬┬┬┬┬┬┬┐ @HBµ @HE│ │ @HBΦ @HA─────────>@HP│││@HBQueue@HP│││├@HA──────────────>@HE│ @HBBedieneinheit @HE├@HA────────> @HP└┴┴┴┴┴┴┴┴┴┴┘ @HE│ │ └───────────────┘ @HBinsbesondere als Funktion von ∩ und µ untersucht werden. Dabei ist nur das stationäre Systemverhalten interessant, das heißt für feste Werte von ∩ und µ. Es ist uninteressant, wie sich das System beim Hochfahren (siehe ⌐Urstart@BS1¬) bzw. Auslaufen, den Fällen in denen sich ∩ und µ zeitlich ändern, verhält. Ein stationäres Systemverhalten liegt vor, wenn die Prozesse stationär sind. Ein ⌐Prozeß@BS1¬, der einen zeitlichen Verlauf hat, heißt stationär, falls der Verlauf zu beliebig gewählten Zeitpunkten t1, t2, ... sich wahr- scheinlichkeitsmäßig kaum von dem Verlauf unterscheidet, zu den um eine willkürliche Zeitspanne h verschobenen Zeitpunkten t1 + h, t2 + h, ... . @HBIn unserem Modell bedeutet dies, daß sich die Werte für ∩ und µ kaum ändern. Die Wahrscheinlichkeit, daß n Kunden im System sind, bleibt also nahezu konstant. @HLPn [t1] ≈ Pn [t1 + h]@HB Wenn die Wahrscheinlichkeit konstant bleibt, so ist ihre Ableitung 0: @HL dPn [t] ───────── = 0 (t -> ∞) dt @HB Für die Differentialgleichung ergibt sich demnach: @HL dPn [t] ───────── = ∩ * Pn-1 [t] - (∩ + µ) * Pn [t] + µ * Pn+1 [t] = 0 dt (t -> ∞) @HBFür verschiedene Wertebereiche von n gilt: a) @HLn < 0 : Pn [t] = 0@HB b) @HLn = 0 : -∩ * Po [t] + µ * P1 [t] = 0@HB c) @HLn > 0 : ∩ * Pn-1 [t] - (∩ + µ) * Pn [t] + µ * Pn+1 [t] = 0@HB Aus diesen drei Gleichungen kann man ein homogenes Gleichungssystem erstellen. Löst man es, so erhält man einen Ausdruck, mit dem man Pn [t] berechnen kann. @HEHomogenes Gleichungssystem: @HA Po P1 P2 P3 P4 ... Pn @HA I @HP -∩ µ 0 0 0 ... 0 = 0 @HAn = 0 @HA II @HP ∩ -(∩+µ) µ 0 0 ... 0 = 0 @HAn = 1 @HA III @HP 0 ∩ -(∩+µ) µ 0 ... 0 = 0 @HAn = 2 @HA : @HA : @HB(Bei Pn kann die Abhängigkeit von t weggelassen werden, da stationärer Zustand vorliegt, t -> ∞) @HELösen des Gleichungssystems @HA Po P1 P2 P3 P4 ... Pn @HA I @HP -∩ µ 0 0 0 ... 0 = 0 @HAn = 0 @HA II + I = II' @HP ∩ -∩ µ 0 0 ... 0 = 0 @HAn = 1 @HA III + II'= III' @HP 0 ∩ -∩ µ 0 ... 0 = 0 @HAn = 2 @HA : : @HBMan sieht, daß gilt: @HL-∩ * Pn + µ * Pn+1 = 0 @HEUmformungen @HL -∩ * Pn + µ * Pn+1 = 0 µ * Pn+1 = ∩ * Pn ∩ ∩ Pn+1 = ─── * Pn mit Auslastung δ = ─── ==> µ µ Pn+1 = δ * Pn @HEBestimmung von Pn @HL Po = Po P1 = δ * Po P2 = δ * P1 = δ * δ * Po P3 = δ * P2 = δ * δ * δ * Po : : n Pn = δ * Pn-1 = δ * Po mit Po = 1 - δ @HB(siehe nächste Seite) @HL @AO ╔═════════════════╗ @HB @AO ║ n ║ @HB @AO ║ Pn = δ * (1-δ) ║ @HB @AO ╚═════════════════╝ @HB @HEBestimmung von Po @HL ∞ n Σ Pn = 1 mit Pn = δ * Po ==> n=0 ∞ n Σ δ * Po = 1 n=0 <==> ∞ n ∞ x-1 c Po * Σ δ = 1 Es gilt: Σ c * q = ─── für q < 1 ==> n=0 x=1 1-q 1 @AO ╔════════════╗ @HL Po * ─── = 1 <==> @AO ║ Po = 1 - δ ║ @HL 1-δ @AO ╚════════════╝ @HB @HEErgebnisse @HLPo = 1 - δ @HBDie Wahrscheinlichkeit, daß das System leer ist (also nicht arbeitet), ∩ ist 1 - δ (δ = Auslastung = ───) µ @HLδ = 1 - Po @HBDie Auslastung δ des Systems wird angegeben durch Wahrscheinlichkeit, daß das System beschäftigt ist. @HL n @HLPn = δ * (1 - δ) @HBDie Wahrscheinlichkeit, daß im stationären Zustand n Kunden im System sind, ist geometrisch verteilt. @HL δ 1 - Po @HLE [n] = ─── = ──────── @HL 1-δ Po @HB Der ⌐Erwartungswert@BS2¬ für die mittlere Anzahl von Kunden im System entspricht dem Quotienten aus der Wahrscheinlichkeit, daß das System beschäftigt ist (nicht leer ist) und der Wahrscheinlichkeit, daß das System nicht beschäftigt ist (also leer ist). @HERechnung für E [n] @HBallgemein gilt @HL ∞ E [n] = Σ n * f (n) n=0 @HBhier gilt dann @HL ∞ n E [n] = Σ n * δ * (1-δ) <==> n=0 ∞ n = (1-δ) Σ N * δ ==> @HBBegründung auf den@HL n=0 @HBnächsten 2 Seiten@HL δ = (1-δ) * ──────── <==> (1-δ)² @AO ╔══════════════╗ @HB @AO ║ δ ║ @HB @AO ║ E [n] = ─── ║ @HB @AO ║ 1-δ ║ @HB @AO ╚══════════════╝ @HB @HEBegründung für den Schritt der vorigen Seite @HBEs gilt: @HL ∞ n 1 Σ δ = ─── für δ < 1 ==> n=0 1-δ ┌ ┐' ┌ ┐' │ ∞ n │ │ 1 │ 1 │ Σ δ │ = │ ─── │ = ──────── │ n=0 │ │ 1-δ │ (1-δ)² └ ┘ └ ┘ @HBAußerdem gilt @HL ┌ ┐' ∞ n ∞ n-1 │ ∞ n │ Σ n * δ = δ * Σ n * δ = δ * │ Σ δ │ ==> n=0 n=1 │ n=1 │ └ ┘ ∞ n 1 Σ n * δ = δ * ──────── @HBq. e. d.@HL n=0 (1-δ)² @HBweiter mit ⌐Little@BS___2¬ AHBAA #!!# Little @HESatz von Little @HBDie mittlere Anzahl von Kunden im System E [N] = L ist proportional zu der Ankunftsrate ∩ und der mittleren Verweilzeit eines Kunden im System E [V] = T. @AO ╔═══════════╗ @HB @AO ║ L = ∩ * T ║ @HB @AO ╚═══════════╝ @HB Diese Gleichung ist gültig für alle Systeme, wenn sie sich im stationären Zustand befinden. Sie beschreibt die Tatsache, daß ein neu ankommender Kunde genau so viele Kunden im System vorfindet (E [N]), wie er bei seiner Beendigung zurückläßt (∩ * E [V]). @HEHerleitung @HB - Im Mittel sind E [N] Kunden im System. - Also findet ein neu ankommender Kunde E [N] = L Kunden im System vor. - Er ist nach E [V] = T Zeiteinheiten fertig. - Während dieser Zeit sind, bei einer Ankunftsrate ∩, genau ∩ * E [V] Kunden angekommen. - Da stationärer Zustand vorliegt, gilt: @HL∩ * E [V] = E [N],@HB das heißt er läßt im Mittel E [N] Kunden auch wieder im System hinter sich zurück. @HEVerweilzeit im System @HBInteressanter als die Frage nach der mittleren Anzahl von Kunden im System ist die Frage nach der mittleren ⌐Verweilzeit@BS2¬ von Kunden im System. Zur Beantwortung der Frage braucht man nur den Satz von Little umzustellen: @HL L = ∩ * T L E [N] ==> T = ─── = ─────── ∩ ∩ @HBfür offene Systeme gilt dann: @HL δ 1 ∩ T = ─── * ─── mit δ = ─── ==> 1-δ ∩ µ 1 ∩ 1 = ─── * ─── * ─── <==> 1-δ µ ∩ @HBMittlere Verweilzeit T in einem offenen System: @AO ╔═══════════════╗ @HB @AO ║ 1 1 ║ @HB @AO ║ T = ─── * ─── ║ @HB @AO ║ µ 1-δ ║ @HB @AO ╚═══════════════╝ @HB @HEVerweilzeit in der Schlange @HL E [N] T = ─────── @HBim System@HL ∩ E [nq] Tq = ──────── @HBin der Queue@HL ∩ 1 TQ = T - ─── @HB(Zeit im System minus Bedienzeit)@HL µ @HEAnzahl Kunden in der Schlange @HL E [N] = ∩ * T im System E [Nq] = ∩ * Tq in der Schlange = E [N] - E [Nbe] = E [N] - (1 - Po) = E [N] - δ δ δ δ * (1-δ) δ² = ─── - δ = ─── - ─────────── = ─── = E [N] * δ 1-δ 1-δ (1-δ) 1-δ @HBEs gilt also: @AO ╔════════════════════╗ @HB @AO ║ E [Nq] = δ * E [N] ║ @HB @AO ╚════════════════════╝ @HB @HEDie Abgangsrate @HBLittle's Satz sagt aus, daß ein neu ankommender Kunde im System genau so viele Kunden im System vorfindet, wie er beim Verlassen des Systems darin hinterläßt. In einem offenen System kann außerdem nicht plötzlich ein neuer Kunde entstehen oder gar verschwinden. Die Anzahl von Kunden, die während der ⌐Verweilzeit@BS2¬ eines Kunden im System neu ankommen, muß also gleich der Anzahl von Kunden sein, die während dieser Zeit das System verlassen, das heißt @HL Abgangsrate = Ankunftsrate ∩ Φ = ∩ mit ─── = δ = 1 - Po ==> µ Φ = µ * δ = µ * (1 - Po) @HBweiter mit ⌐Systemkonfiguration@BS___2¬ AHBAA #!!# Systemkonfiguration @HBDem Rechenzentrum muß daran gelegen sein, daß der Rechner gut ausgelastet ist, damit sich die hohen Investitionen lohnen. Das bedeutet, daß @HPδ -> 1@HB gehen muß. Das hätte aber eine katastrophale Auswirkung auf die Kunden, weil dann die mittlere Anzahl von Kunden im System und ihre mittlere ⌐Verweilzeit@BS2¬ beliebig groß werden können. Man will den Kunden aber eine angemessene, möglichst kurze Verweilzeit anbieten, was nur bei geringer Belastung des Systems, also bei @HPδ -> 0@HB möglich ist. Zur Erinnerung: @HL ∩ δ 1 1 δ = 1 - Po = ───, E [N] = ───, E [V] = ─── * ─── µ 1-δ µ 1-δ @HBMan sieht, daß die beiden Forderungen nicht gleichzeitig erfüllt werden können. @HEM / M / 1 - Beispiele @HBDie Beispiele dienen zum Vergleich von verschiedenen Systemkonfigurationen. 1) verschiedene Auslastungen @HL 0,8 1 1 1 a) δ = 0,8 : E [N] = ─────── = 4 E [V] = ─── * ─────── = ─── * 5 1-0,8 µ 1-0,8 µ 0,9 1 1 1 b) δ = 0,9 : E [N] = ─────── = 9 E [V] = ─── * ─────── = ─── * 10 1-0,9 µ 1-0,9 µ @HB2) die Betriebseinheit arbeitet mit doppelter Geschwindigkeit @HL µ' = 2 * µ ==> δ' = 0,4 0,4 2 E [N]' = ─────── = ─── ≈ 0,67 1-0,4 3 1 1 1 1 E [V'] = ──── * ─────── = ──── * 1,667 = ─── * 0,83 µ' 1-0,4 µ' µ @HBVerringert man die Auslastung um die Hälfte, indem man die Betriebs- einheit mit doppelter Geschwindigkeit arbeiten läßt, so beträgt die Verweilzeit nur noch ein sechstel der der ursprünglichen Zeit. @HB3) man verwendet zwei Betriebseinheiten und verteilt die Kunden gleichmäßig auf beide @HE┌───────────────┐ @HB∩' = ∩/2 @HP┌┬┬┬┬┬┬┬┬┬┬┐ @HBµ @HE│ │ @HA─────────>@HP│││@HBQueue@HP│││├@HA──────>@HE│ @HBBedieneinheit @HE├@HA────> @HA/ @HP└┴┴┴┴┴┴┴┴┴┴┘ @HE│ @HB1 @HE│ @HA\ @HB∩ @HA/ @HE└───────────────┘ @HA\ @HA──────> ──────> @HA\ @HE┌───────────────┐ @HA/ @HA\ @HB∩' = ∩/2 @HP┌┬┬┬┬┬┬┬┬┬┬┐ @HBµ @HE│ │ @HA/ @HA─────────>@HP│││@HBQueue@HP│││├@HA──────>@HE│ @HBBedieneinheit @HE├@HA────> @HP└┴┴┴┴┴┴┴┴┴┴┘ @HE│ @HB2 @HE│ @HE└───────────────┘ @HL ∩ δ ∩' = ─── ==> δ' = ─── : 2 2 δ' 0,4 E [N]' = ────── = ───── = 0,67 1-δ' 0,6 1 1 1 1 1 E [V]' = ─── * ────── = ─── * ───── = ─── * 1,67 µ 1-δ' µ 0,6 µ @HEErgebnis aus den Beispielen @HBEine Änderung von ∩ hat nicht so starke Auswirkungen wie eine Änderung von µ um den gleichen Faktor, bezogen auf die mittlere Verweilzeit im System E [V]. @HBweiter mit ⌐allg. Lösung@BS___2¬ AHBAA #!!# allg. Lösung @HEDie allgemeine, stationäre Lösung @HBBei der bisher gefundenen Lösung für Pn hat man vereinfachend ange- nommen, daß die Ankunftsrate ∩ und die Bedienrate µ unabhängig von der Anzahl der Kunden im System sind. Das muß nicht immer der Fall sein, denn eine ⌐Warteschlange@BS2¬ (z. B. beim Einkaufen) kann einen anziehenden oder aber einen abweisenden Charakter haben, je nach der Anzahl der Kunden in der Warteschlange (und der angebotenen Dienstleistung). @HP ∩k : Ankunftsrate, wenn k Kunden im System sind µk : Bedienrate, wenn k Kunden im System sind @HBBeim vereinfachten (∩k = ∩), stationären Fall lautet die Differentialgleichung (siehe ⌐offenes System@BS___2¬)@HL dPn [t] ───────── = ∩ * Pn-1 [t] - (∩ + µ) * Pn [t] + µ * Pn+1 [t] = 0 mit n > 0 dt = -∩ * Po [t] + µ * P1 [t] = 0 mit n = 0 @HB Da t -> ∞ geht, darf man auch schreiben:@HL ∩ * Pn-1 - (∩ + µ) * Pn + µ * Pn+1 = 0 mit n > 0 -∩ * Po + µ * P1 = 0 mit n = 0 @HBIm allgemeinen, stationären Fall muß es also heißen:@HL ∩n-1 * Pn-1 - (∩n + µn) * Pn + µn+1 * Pn+1 = 0 mit n > 0 -∩0 * Po + µ1 * P1 = 0 mit n = 0 @HB @HEVeranschaulichung mit Hilfe eines Zustandsdiagrammes (state-transition-reate-diagram): @DB @HB @DB @DA∩0 ∩1 ∩2 ∩n-1 ∩n @HB @DB @DP┌────>─── ┌────>─── ┌────>─...─>───┌────>─ @HB @DB @DP│ │ │ │ @HB @DB @DA0 1 2 n @HB n = Anzahl von Kunden @DB @DP│ │ │ │ @HB im System @DB @DP────<────┘────<────┘────<─...─<─── ────<─ @HB @DB @DAµ1 µ2 µ3 µn µn+1 @HB @DB @HB @HBAus dem Diagramm und den Gleichungen sieht man, daß im stationären Fall der Fluß in den Zustand n gleich dem Fluß aus dem Zustand n ist: @HL Fluß in Zustand n = Fluß aus Zustand n ∩n-1 * Pn-1 + µn+1 * Pn+1 = ∩n * Pn + µn * Pn @HB Die Lösung für Pn erhält man wie beim vereinfachten, stationären Fall, indem wiederum - ein lineares Gleichungssystem aufgestellt wird, - die Gleichungen umgeformt (zur Gleichung II addiert man die Gleichung I, zur Gleichung III die neue Gleichung II, usw.) und - aus den so erhaltenen Gleichungen für Pn abliest. @HBSie lautet:@HL ∩n-1 Pn = ────── * Pn-1 für n > 0 µn @HB ∞ Po muß man noch extra berechnen und zwar mit Σ Pn = 1 n=0 weiter mit ⌐geschlossenes System@BS___2¬ AHBAA #!!# geschlossenes System Ein geschlossenes System ist das einfachste Modell eines Time-Sharing Systems. @HA ┌─────────────────────<──────────────────────────────────┐ @HA │ │ @HA ├─>─@HB1@HA──>─┐ @HE┌───────────────┐ @HBx @HA ├─>─@HB2@HA──>─┤ @HB∩ @HP┌┬┬┬┬┬┬┬┬┬┬┐ @HBµ @HE│ │ @HBΦ @HA │ @HA ├─>─@HB3@HA──>─┼────>@HP│││@HBQueue@HP│││├@HA──────>@HE│ @HBBedieneinheit @HE├@HA────>─┘ @HA │ @HB:@HA │ @HP└┴┴┴┴┴┴┴┴┴┴┘ @HE│ @HE│ @HA └─>─@HBN@HA──>─┘ @HE└───────────────┘ @HB Denkzeit Wartezeit Bedienzeit @HO «────────»«──────────────────────»«────────────────» @HB Antwortzeit @HO «────────────────────────────────────────» @HB Umlaufzeit @HO «──────────────────────────────────────────────────» @HBU: @HPDenkzeit@HB am Terminal (user-time), ist eine Zufallsgröße mit dem 1 Mittelwert ─── ∩ R: @HPAntwortzeit@HB (response-time), setzt sich zusammen aus - der Zeit in der Queue und 1 - der Bedienzeit ─── µ T: @HPUmlaufzeit@HB (turn-around-time), setzt sich zusammen aus - der Denkzeit und - der Antwortzeit @HESystemablauf @HBN Kunden stellen (am Terminal) Aufgaben an den Rechner mit einer Ankunftsrate ∩. Wenn die Aufgabe abgeschickt ist, bewirbt sich der Kunde damit um die Bedieneinheit. Ist diese schon besetzt, muß er so lange in der Queue warten, bis er ausgewählt wird und die Bedieneinheit benutzen darf. Nach Abarbeitung des Auftrags, was im Mittel 1/µ Zeiteinheiten dauert, kann er wieder am Terminal aktiv werden. Solange ein Kunde sich in der ⌐Warteschlange@BS2¬ oder Bedieneinheit befindet, kann er am Terminal keine neue Aufgabe stellen. Wichtig: - N Kunden im System - Ankunftsrate ∩ 1 - mittlere Bedienzeit ─── µ @HEDer Idealfall @HB Der Idealfall in einem Time-Sharing-System liegt dann vor, wenn N Kunden im System sind und keiner etwas vom anderen merkt, das heißt er meint, er wäre allein im System. Das bedeutet, die Response-Time besteht nur aus der Bedienzeit. Die Wartezeit in der Schlange fällt weg. Dies ist dann möglich, wenn man annimmt, daß 1. die Denkzeit U und die Response-Time R für alle N Kunden gleich groß sind und 2. die Denkzeit U größer oder gleich (N-1)mal der Response-Time ist. @HBAnnahme: U, R gleich groß für alle Kunden @HB 1. Kunde @HO├────@HAU@HO────┼─@HAR@HO─┼────@HAU@HO────┼─@HAR@HO─┤ @HBWenn einer rechnet, @HB 2. Kunde @HO ...├────@HAU@HO────┼─@HAR@HO─┤... @HBsind die anderen @HBgerade am "denken". @HB 3. Kunde @HO ...├─────@HAU@HO───┼─@HAR@HO─┤... @HB 4. Kunde @HO ...├─────@HAU@HO───┼─@HAR@HO─┤... @HEErgebnisse@HB 1 - ideale Antwortzeit Ri = ─── µ - keiner merkt etwas vom anderen - jeder weitere Kunde geht auf Kosten der Antwortzeit der anderen @HEHerleitung der Response-Time für den Normalfall @HBIdee: Man schneidet das System hinter der Bedieneinheit auf (an der Stelle x im Bild des geschlossenen Systems), so daß prinzipiell wieder ein offenes System vorliegt. Nun beobachtet man, was an der Schnittstelle passiert. @HE1. Feststellung @HPAnkunftsrate = Abgangsrate@HB Begründung siehe ⌐Little@BS___2¬ Den Satz von Little (E [N] = ∩ * T) darauf angewendet ergibt:@HL N = Φ * T @HBEine notwendige Annahme für die Gültigkeit der @AO ╔═════════════════╗ @HB Gleichung ist stationäres Verhalten. Verteilungen @AO ║ N = Φ * (U + R) ║ @HB von U und R sind uninteressant, können also @AO ╚═════════════════╝ @HB beliebig sein. @HE2. Feststellung @AO ╔══════════════════╗ @HB @AO ║ Φ = (1 - Po) * µ ║ @HB @AO ╚══════════════════╝ @HB Herleitung: @HL ∩ (1 - Po) = δ = ─── mit Φ = ∩ ==> µ (1 - Po) * µ = Φ @HBInterpretation: Die Abgangsrate ist proportional zur Bedienrate µ und der Wahrschein- lichkeit, daß die Betriebseinheit arbeitet. Nur wenn die Betriebseinheit arbeitet können auch Kunden das (offene) System verlassen. @HBAus den beiden Feststellungen folgt: @HL N ───────── = (1-Po) * µ (U + R) @HBAuflösen nach Antwortzeit R:@HL N ──────────── = U + R <==> (1-Po) * µ @HBResponse-Time: normierte Response-Time @AO ╔════════════════════════╗ @HB @AO ╔══════════════════════════╗ @HB @AO ║ N 1 ║ @HB @AO ║ N ║ @HB @AO ║ R = ──────── * ─── - U ║ @HB @AO ║ µ * R = ──────── - U * µ ║ @HB @AO ║ (1-Po) µ ║ @HB @AO ║ (1-Po) ║ @HB @AO ╚════════════════════════╝ @HB @AO ╚══════════════════════════╝ @HB @HBDie Gleichung für die Response-Time gilt nahezu ohne Einschränkung. Die Gleichung bleibt von der Art der Verteilung von Bedienzeit und Denkzeit unbeeinflußt, lediglich Po ist davon abhängig. Es wird nur noch stationäres Verhalten vorausgesetzt. Die Response-Time R wird normiert, weil nur die Response-Time allein wenig aussagt. @HL 1 @HL ─── @HBist die ideale Response-Time @HL µ @HL 1 @HB tatsächliche @HL µ * R = R : ─── @HBist ────────────── Response-Time @HL µ @HB ideale @HEDie Response-Time R in Abhängigkeit von der Anzahl der Kunden N @HAR @HP/│\ @HLo@HO* @HP│ @HLo@HO* @HP│ @HLo @HO* @HP│ @HLo @HO* @HP│ @HLo @HO* @HP│ @HLo @HO* @HO* @HB: theoretisch @HP│ @HLo @HO* @HLo @HB: praktisch @HP│ @HLo @HO* @HP│ @HLo o oo @HO* @HA1@HP┤@HO* * * * * * * * * * ** @HP│ @HP└───┬─────────────────┬───────────────────────────────────> @HAN @HA1 N° = U * µ + 1 @HB Die Denkzeit U sei konstant für alle Kunden n. Bis N° ist die Wartezeit gleich Null, ab N° ist sie größer Null, daher steigt die Antwortzeit R. @HEHerleitung für N° @HBBis zu einer Zahl N° der Kunden ist die Wartezeit gleich Null. N° ergibt sich aus dem Verhältnis von Denkzeit U und Antwortzeit R. (Siehe dazu auch das Bild mit den 4 Kunden von oben.) @HL U N° = ──── + 1 Ri @HBWeil die Auslastung hier gleich 1 ist @HL (1-Po) = 1 @HBund @HL 1 1 Ri = ─── ==> µ = ──── ==> N° = U * µ + 1 µ Ri @HEHerleitung von Po @HB Für die Herleitung von Po muß man Angaben über die Verteilung der Ankunfts- und Bedienzeit machen. Annahme: @HPM / M / 1 / N - System@HB das heißt: - Ankünfte sind Poisson verteilt Denkzeiten demnach Exponential verteilt - Bedienrate ist Poisson verteilt Bedienzeiten demnach Exponential verteilt - 1 Bedieneinheit - endlich viele Kunden im System : N siehe auch ⌐Modellkennzeichnung@BS___2¬ @HEa) Berechnung von Po mit Hilfe des Zustandsdiagramms @HB Alle Kunden kommen mit der Ankunftsrate ∩ und werden mit @DB @HB der Rate µ bedient (siehe Bild @DB @DAN*∩ (N-1)*∩ (N-2)*∩ ∩ @HB des geschlossenen Systems am @DB @DP┌────>─── ┌────>─── ┌────>─...─>───┐ @HB Anfang des Kapitels). @DB @DP│ │ │ │ @HB Wenn die Betriebseinheit leer @DB @DA0 1 2 N @HB ist, können N Kunden ihre Auf- @DB @DP│ │ │ │ @HB gabe absenden, also N * ∩ Auf- @DB @DP────<────┘────<────┘────<─...─<───┘ @HB gaben sich um die Betriebs- @DB @DAµ µ µ µ @HB einheit bewerben. @DB @HB Wenn in der Betriebseinheit und Warteschlange zusammen ein Kunde ist, dann sind noch (N-1) Kunden an den Terminals und können eine Aufgabe abschicken. @HBWenn alle Kunden in der Betriebseinheit oder ⌐Warteschlange@BS2¬ sind, kann von den Terminals keine neue Aufgabe mehr abgeschickt werden. Es gilt auch hier die im allgemeinen, stationären Fall aufgestellte Gleichung für Pk@HL ∩k-1 @HBwobei@HL ∩k = (N - K) * ∩ Pk = ────── * Pk-1 µk µk = µ ∞ @HBMit Hilfe der Summengleichung @HLΣ Pk = 1 @HBläßt sich dann Po bestimmen @HLk=0 @HB(siehe das folgende Beispiel). @HEb) Numerische Berechnung für Po durch Rekursionsformel @HL Po [0] = 1 1 ∩ 1 ──────── = 1 + N * ─── * ───────── Po [N] µ Po [N-1] @HB Die Formel hat den Vorteil, daß man bei der Berechnung von Po [N] für N = k außerdem noch Po [N] für N < k erhält. Auch für die normierte Antwortzeit gibt es eine Rekursionsformel, die eine einfache numerische Berechnung erlaubt: @HL µ * R (1) = 1 (µ/∩) * (N-1) µ * R (N) = N - ───────────────────── µ * R (N-1) + (µ/∩) @HEBeispiele für die Berechnung der Response-Time @HB 1 1 gegeben : N = 5, Denkzeit : ─── = 5 sec, Bedienzeit : ─── = 0,5 sec ∩ µ gesucht : R (5), also die Antwortzeit, wenn 5 Kunden im System sind Rechnung: @HL∩0 = 5 * ∩ ∩1 = 4 * ∩ ∩2 = 3 * ∩ ∩3 = 2 * ∩ ∩4 = ∩ ∩k = 0 für alle k ≥ 5 @HB(weiter mit der Berechnung von Po auf der nächsten Seite) @HBBerechnung von Po des Beispiels @HBRekursionsformel:@HL ∩k-1 ∩ 0,2 Pk = ────── * Pk-1 mit ─── = ───── = 0,1 µk µ 2 @HBEinsetzen ergibt:@HL P1 = 5 * ∩/µ * Po = 0,5 * Po P2 = 4 * ∩/µ * P1 = 0,4 * P1 = 0,2 * Po P3 = 3 * ∩/µ * P2 = 0,3 * P2 = 0,06 * Po P4 = 2 * ∩/µ * P3 = 0,2 * P3 = 0,012 * Po P5 = ∩/µ * P4 = 0,1 * P4 = 0,0012 * Po @HL 5 5 Σ Pk = Po + Σ Pk = Po + 0,7732 * Po = 1 ==> k=0 k=1 1 @HB(1-Po) ≈ 44 %@HL Po = ──────── = 0,563952 @HBder Rechner arbeitet also@HL 1,7732 @HBin 44 % der Zeit@HL N @HBEs gilt:@HL µ * R = ────── - U * µ 1-Po @HBWerte einsetzen:@HL 5 1 1,468 µ * R = ─────────── - ───── = 1,468 ==> R = ─────── = 0,734 sec 1 - 0,564 0,1 µ @HBErgebnis: R (5) = 0,734 sec @HEResponse-Time in Abhängigkeit von µ bzw. ∩@HB a) Beispiel wie gesehen: 1 1 gegeben: N = 5, Denkzeit : ─── = 5 sec, Bedienzeit : ─── = 0,5 sec ∩ µ @HL ∩ 0,2 ─── = ───── = 0,1 µ 2 N @HBEs gilt:@HL µ * R = ────── - U * µ 1-Po µ * R = 1,468 R = 0,734 sec @HBb) die Bedienzeit wird halbiert 1 ──── = 0,25 µ' @HL ∩ ──── = 0,05 µ' µ' * R' = 1,2186 R' = 0,305 sec @HB Ergebnis: Eine doppelt schnelle CPU halbiert (in dem Beispiel) die Antwortzeit (Verbesserung um 50 %) @HBc) die Denkzeit wird verdoppelt 1 ──── = 10 sec ∩' @HL ∩' ──── = 0,05 µ µ * R'' = 1,2186 R'' = 0,61 sec @HB Ergebnis: Die Antwortzeit verkürzt sich nur um 12 %. @HEFazit @HBDie Antwortzeit (Response-Time) reagiert auf Änderungen der Bedienzeiten weit empfindlicher als auf Änderungen der Denkzeit. Erklärung: Ein Vergleich der beiden Parameter ∩ und µ ist nur dann sinnvoll, wenn die Auslastung δ (δ = ∩/µ) bei der Änderung von ∩ die gleiche wie bei der Änderung von µ ist. Ist δ in beiden Fällen gleich, so auch Po, µ/∩ und letztlich auch die normierten Antwortzeiten. Um die tatsächliche Antwortzeit zu erhalten, dividiert man ja zum Schluß noch die normierte Antwortzeit durch die Bedienrate µ. Damit ist also klar, warum eine Änderung von µ sich wesentlich stärker bemerkbar macht als die von ∩. @HEDie normierte Response-Time in Abhängigkeit von N und der Auslastung δ @HBa) @HAµ * R @HP/│\ @HK+ @HLo@HO* @HP│ @HK+ @HLo@HO* @HP│ @HK+ @HLo @HO* @HP│ @HK+ @HLo @HO* @HP│ @HK+ @HLo @HO* @HP│ @HK+ @HLo @HO* @HO* @HB: theoretisch @HP│ @HK+ @HLo @HO* @HLo @HB: δ = 0,05 @HP│ @HK+ + @HLo @HO* @HK+ @HB: δ = 1,0 @HP│ @HLo o oo @HO* @HA1@HP┤@HO* * * * * * * * * * ** @HP│ @HP└───┬─────────────────┬───────────────────────────────────> @HAN @HA1 N° = U * µ + 1 @HBJe mehr Kunden im System sind, desto größer wird die Antwortzeit. Sie steigt schneller und eher, je größer die Auslastung ist. @HEDie normierte Response-Time in Abhängigkeit von N und der Auslastung δ @HBb) @HAµ * R @HP/│\ @HK+ @HLo @HP│ @HK+ @HLo @HP│ @HK+ @HLo @HP│ @HK+ @HLo @HP│ @HK+ @HLo @HO* @HP│ @HK+ @HLo @HO* @HP│ @HK+ @HLo @HO* @HP│ @HK+ @HLo @HO* @HK+ @HB: N = 10 @HP│@HK+ @HLo @HO* @HLo @HB: N = 4 @HA1@HP┤@HK+@HLo@HO* @HO* @HB: N = 2 @HP│ @HP└──┬───────────┬──────────────┬─────────────────────> @HAδ @HA0,1 0,5 1 @HBDie Antwortzeit steigt, bis die Auslastung 100 % beträgt. Sie steigt um so schneller je größer die Anahl der Kunden im System ist. weiter mit ⌐M/G/1-System@BS___2¬ AHBAA #!!# M/G/1-System #!!# PK-Gleichung Bei einem M/G/1-System gilt: - Ankunftsprozeß : Poisson verteilt - Bedienprozeß : Verteilung beliebig - Bedieneinheiten : eine (siehe auch ⌐Modellkennzeichnung@BS___2¬) Man betrachtet das System nur zu bestimmten Zeitpunkten, nämlich immer dann wenn ein Kunde die Bedieneinheit verläßt. @HE1.Fall: Während der Bedienzeit des n-ten Kunden Cn kommt ein neuer Kunde Cn+1 in das System @AH qn+1 = qn - 1 + vn+1 @HB Cn Cn+1 @HP│ @HO/│\ /│\ @HP└ Cn+1 selbst @HO│ │ @HBBE @HA════════════════════════@HOo@HA═════════════════@HO■@HA══ @HO/│\ /│\ @HPo : sieht qn @HO│@HL«───────────»@HO│@HL«───────────────» @HPhinter sich @HO│ @HBXn @HO│ @HBXn+1 @HO│@HBCn @HO│@HBCn+1 @HP■ : sieht qn+1 @HBQueue @HA═════════════════════════════════════════════ @HPhinter sich @HO/│\ @HO/│\ @HO│ │ @HL└────────┬────────┘ @HPXn : Bedienzeit @HBCn Cn+1 vn+1 @HPvon Cn qn : Anzahl der Kunden, die Cn hinter sich im System läßt vn : Anzahl der Ankünfte weiterer Kunden, während der Bedienzeit von Cn @HE2.Fall: Während der Bedienzeit des n-ten Kunden Cn kommt kein neuer Kunde Cn+1 in das System. Erst danach kommt Cn+1 an. @AH qn+1 = vn+1 | qn = 0 @HB Cn Cn+1 @HO/│\ /│\ @HO│ │ @HBBE @HA════════════════════════@HOo@HA═════════════════@HO■@HA══ @HO/│\ /│\ @HPo : sieht qn @HO│@HL«───────────» @HO│@HL«───────────» @HPhinter sich @HO│ @HBXn @HO│ @HBXn+1 @HO│@HBCn @HO│@HBCn+1 @HP■ : sieht qn+1 @HBQueue @HA═════════════════════════════════════════════ @HPhinter sich @HO/│\ @HO/│\ @HO│ │@HL @HPXn : Bedienzeit @HBCn Cn+1 @HPvon Cn @HL└──────┬──────┘ @HBvn+1 @HBAus den beiden Fällen ergibt sich für die Anzahl der Kunden, die ein Kunde Cn+1 hinter sich läßt: @HL ┌ qn - 1 + vn+1 für qn > 0 qn+1 = ┤ └ vn+1 für qn = 0 @HB Um die beiden Gleichungen zu einer zusammenfassen zu können, bedient man sich der Sprungfunktion delta_k (dk) @HL ┌ 1 für k = 1, 2, 3, ... dk = ┤ └ 0 für k = 0 @HB Damit ergibt sich: I: @HLqn+1 = qn - dk + vn+1 @HEHerleitung des ⌐Erwartungswert@BS2¬es E [qn] @HB1. Ansatz: Bilden des Erwartungswertes @HL E [qn+1] = E [qn] - E [dqn] + E [vn+1] @HB Da n -> ∞ folgt │ Es gilt: lim E [qn+1] = E [qn] @HL _ @HB│ n->∞ @HL E [q] = E [q] - E [dq] + E [v] @HB│ @HL _ @HB│ Bei der Suche nach der _ @HL 0 = - E [dq] + E [v] @HB│ Sprungfunktion muß man jetzt q @HL _ @HB│ als Index nehmen, weil es q∞ @HL E [v] = E [dq] @HB│ nicht gibt. Diese Gleichung halten wir fest: @HL_ @HBII:@HL E [v] = E [dq] @HB _ Berechnung von E [dq]: @HL _ ∞ E [dq] = Σ dk * P [q=k] k=0 = d0 * P [q=0] + d1 * P [q=1] + d2 * P [q=2] + ... = 0 + 1 * P [q=1] + P [q=2] + ... = P [q > 0] = @HBIII:@HL 1 - P [q=0] = δ @HB Man erhält also für E [v]: @HL _ _ E [v] = δ = ∩ * x mit x = mittlere Bedienzeit @HBDer Ansatz führte nicht zu dem gesuchten Erwartungswert für qn. @HB2. Ansatz zur Ermittlung von E [qn]: Man quadriert die Gleichung I:@HL (qn+1)² = (qn - dqn + vn+1)² = (qn)² + (dqn)² + (vn+1)² - 2dqn*vn+1 - 2qn*dqn + 2qn*vn+1 = (qn)² + dqn + (vn+1)² - 2dqn*vn+1 - 2qn + 2qn*vn+1 @HB Erwartungswerte bilden und n -> ∞: @HL _ _ E [q²] = E [q²] + E [v²] + E [dq] - E [2dq*v] - E [2q] + E [2q*v] _ _ 0 = E [v²] + E [dq] - 2E [dq]*E [v] - 2E [q] + 2E [q]*E[v] = E [v²] + δ - 2δ * δ - 2E [q] + 2E [q]* δ = E [v²] + δ - 2δ² - E [q] (2 - 2δ) <==> @HB(nächste Seite) @HL E [q] (2 - 2δ) = E [v²] + δ - 2δ² + δ - δ = E [v²] - δ + 2δ - 2δ² = E [v²] - δ + δ * (2 - 2δ) E [v²] - δ E [q] = ──────────── + δ 2 * (1-δ) E [v²] - E [v] = δ + ──────────────── mit δ < 1 2 * (1-δ) @HB Unbekannt in dem Term ist nur E [v²], denn: @HL _ E [v] = δ @HBund@HL δ = ∩ * x @HBAber mit Hilfe der Z-Transformation (hier geht die Voraussetzung ein, daß der Ankunftsprozeß Poisson verteilt ist) erhält man: @HL __ @HB __ @HL E [v²] - E [v] = ∩² * x² @HB│ ┌ k ┐ k @HB│ E │ y │ = y @HB│ └ n ┘ Oben eingesetzt ergibt sich die │ │ (das k-te Moment) @HEPollaczek-Klinchin (PK-) Gleichung @HL __ __ ∩² * x² _ ∩² * x² E [q] = δ + ─────────── = ∩ * x + ─────────── für δ < 1 2 * (1-δ) 2 * (1-δ) @HBDie PK-Gleichung, die die mittlere Anzahl von Kunden im System angibt, ist im wesentlichen nur von den ersten beiden Momenten der Bedienzeit- Verteilung abhängig. _ _ 1. Moment: x in δ = ∩ * x __ 2. Moment: x² @HL__ _ @HLvar x² - (x)² @HBFührt man noch @HLC² = ───── = ─────────── @HBein und setzt den Wert in @HL_ _ (x)² (x)² @HBdie PK-Gleichung ein, so erhält man: @AO ╔════════════════════════════╗ @HB @AO ║ 1 + C² ║ @HB @AO ║ E [q] = δ + δ² (─────────) ║ @HB @AO ║ 2 (1-δ) ║ @HB @AO ╚════════════════════════════╝ @HB @HEBemerkungen zur PK-Gleichung@HB - E [q] steigt linear mit C². - E [q] ist am kleinsten, wenn C² = 0, das heißt die Varianz = 0 ist, es also keine Abweichungen vom Mittelwert gibt. Dies bedeutet, daß die Bedienzeiten für alle Kunden gleich sind. ==> M/D/1-System (D = deterministisch = fest) δ - Für C² = 1 gilt: E [q] = ─── ==> M/M/1-System 1-δ @HEAnwendungen der PK-Gleichung @HB 1) M/D/1-System Ankunftsprozeß : Poisson verteilt Bedienzeit : deterministisch, für alle Kunden gleich Bedieneinheit : eine Da die Bedienzeiten alle gleich sind für alle Kunden, ist ihre Varianz gleich 0 und somit auch C² = 0. Die PK-Gleichung lautet dann: @HL 1 δ E [q] = δ + δ² ───────── = δ (1 + ─────────) 2 (1-δ) 2 (1-δ) <==> @HB(weiter auf nächster Seite) @HL 2 - 2δ + δ 2 - δ 2δ - δ² E [q] = δ (────────────) = δ (─────────) = ───────── 2 (1-δ) 2 (1-δ) 2 (1-δ) @HBFür ein M/D/1-System gilt also: @HL δ δ² E [q] = ─── - ───────── 1-δ 2 (1-δ) @HB2) M/M/1-System _ 1 1. Moment: x = ─── ┐ µ ├ ==> C² = 1 __ ┘ 2. Moment: x² = ??? @HL 2 δ (1-δ) + δ² δ - δ² + δ² E [q] = δ + δ² ───────── = ────────────── - ───────────── 2 (1-δ) 1-δ 1-δ δ E [q] = ─── 1-δ @HB δ² Das M/D/1- System hat also im Mittel ───────── Kunden im System weniger 2 (1-δ) als das M/M/1-System. @HBweiter mit ⌐Jackson-Netz@BS___2¬ AHBAA #!!# Jackson-Netz @HEGraphische Darstellung eines Jackson-Netzes @HJ┌────────────────────@HBJackson-Netz@HJ─────────────────────────┐ @HJ│ @HAr_ki r_ij @HJ│ @HJ│ @HA: @HO╔═══@HBKnoten_i@HO═══════════════╗ @HA┌───> @HBKnoten_j @HJ│ @HJ│ @HA: @HO║ @HAµ_i @HO║ @HA│ @HJ│ @HJ│ @HA\│/ @HO║ @HA┌───> @HEBE_1 @HA┐ @HO║ @HA│ @HJ│ @HAτ_i @HJ│ @HA│ @HO║ @HA∩_i @HA│µ_i │ @HO║ @HA│ @HJ│ @HA────>────┼────────> @HPQueue @HA─┼───> @HEBE_2 @HA┼───>─┼─────────────────────> @HJ│ @HA│ @HO║ @HA│µ_i │ @HO║ @HA│ N @HJ│ @HJ│ @HA/│\ @HO║ @HA└───> @HEBE_mi@HA┘ @HO║ @HA│ 1 - Σ r_is @HJ│ @HJ│ @HA│ @HO║ ║ @HA│ s=1 @HJ│ @HJ│ @HA│ @HO╚══════════════════════════╝ @HA│ @HJ│ @HJ│ @HA│ r_ii │ @HJ│ @HJ│ @HA└─────────────<────────────────────┘ @HJ│ @HJ│ │ └─────────────────────────────────────────────────────────┘ @HBEin @HPJackson-Netz@HB besteht aus N Knoten. Für N=1 entspricht das Netz einem M/M/m-System. Daten über den i-ten Knoten: - @HPmi @HB: Bedieneinheiten - @HPµi @HB: Bedienrate, Poisson verteilt - @HPrij @HB: Wahrscheinlichkeit, daß ein Kunde nach Verlassen des Knotens i zum Knoten j geht, rii > 0 (wieder in den Knoten i) ist erlaubt. @HPN@HB - @HP1 - Σ rij @HB: Wahrscheinlichkeit, daß ein Kunde nach Verlassen des @HPj=1 @HBKnotens i das Netz verläßt. - @HPτi @HB: Ankunftsrate des Knotens i von Kunden von außerhalb des Netzes, Poisson verteilt - @HP∩i@HB : gesamte Ankunftsrate für den Knoten i N ∩i = τi + Σ ∩j * rji für ∩i < mi * µi j=1 @HETheorem von Jackson @HBIn jedem Knoten i seien Ki Kunden. Dann gilt:@HL N p [(K1, K2, ..., KN)] = p1 [K1] * p [K2] * ... * p [KN] = π pi [Ki] i=1 @HBDas bedeutet, jeder Knoten kann wie ein unabhängiges M/M/m-System betrachtet werden (weil pi [Ki] aus dem M/M/m-System berechnet werden kann) mit einer Ankunftsrate ∩i, Poisson verteilt, auch wenn τi nicht Poisson verteilt ist. @HP (K1, K2, ..., KN) @HB: Zustandsvariable für Netz mit N Knoten @HP p [(K1, K2, ..., KN)] @HB: Wahrscheinlichkeit des Zustandes @HP pi [Ki] @HB: Wahrscheinlichkeit, daß sich Ki Kunden im Knoten i befinden @HEGordon/Newell Netz @HB Das von Gordon und Newell entwickelte Netz ist eine Modifikation des Jackson-Netzes. Ihr Netz ist geschlossen, das heißt: a) Es gibt eine feste Anzahl von Kunden im Netz, K. b) Kein weiterer Kunde kann in das Netz gelangen, τi = 0 für alle i. N c) Keiner der K Kunden kann das Netz verlassen, Σ rij = 1 für alle i. j=1 @HBFolgerungen: - Die Elemente Ki eines Zustandes sind untereinander abhängig. N Σ Ki = K i=1 @HB - Es gibt eine begrenzte Anzahl von Zuständen im Netz, nämlich genau so viele, wie es Möglichkeiten gibt, K Kunden auf N Knoten zu verteilen. Permutationen N verschiedener Knoten, jedesmal K Kunden verteilt ohne Berücksichtigung der Anordnung mit Wiederholung: @HP ┌ ┐ ┌ ┐ │ N + K - 1 │ │ N + K - 1 │ │ │ = │ │ │ K │ │ N - 1 │ └ ┘ └ ┘ @HB - p [K1, K2, ..., KN] läßt sich nicht aus dem Produkt der Einzelwahr- scheinlichkeiten berechnen. @HEBeispiele für die Auslastung einzelner Knoten des Netzes: @HB a und b sind Bedienraten @HBA) @HE┌─────────┐ ┌─────────┐ @HP┌┬┬┬┬┬┬┬┬┬┐ @HBa @HE│ │ @HP┌┬┬┬┬┬┬┬┬┬┐ @HBb @HE│ │ @HA┌────>@HP│││@HBQueue@HP││├@HA─────>@HE│ @HBC P U @HE├@HA─────>@HP│││@HBQueue@HP││├@HA─────>@HE│ @HBI/O @HE├@HA──┐ @HA│ @HP└┴┴┴┴┴┴┴┴┴┘ @HE│ │ @HP└┴┴┴┴┴┴┴┴┴┘ @HE│ │ @HA│ @HA│ @HE└─────────┘ └─────────┘ @HA│ @HA└───────────────────────────────────<─────────────────────────────────┘ @HBB) @HE┌─────────┐ ┌─────────┐ @HP┌┬┬┬┬┬┬┬┬┬┐ @HBa @HE│ │ @HP┌┬┬┬┬┬┬┬┬┬┐ @HB2*b @HE│ │ @HA┌────>@HP│││@HBQueue@HP││├@HA─────>@HE│ @HBC P U @HE├@HA─────>@HP│││@HBQueue@HP││├@HA─────>@HE│ @HBI/O @HE├@HA──┐ @HA│ @HP└┴┴┴┴┴┴┴┴┴┘ @HE│ │ @HP└┴┴┴┴┴┴┴┴┴┘ @HE│ │ @HA│ @HA│ @HE└─────────┘ └─────────┘ @HA│ @HA└───────────────────────────────────<─────────────────────────────────┘ @HBC) @HP┌┬┬┬┬┬┬┬┬┬┐ @HBb @HE┌─────────┐ @HE┌─────────┬@HA─────>@HP│││@HBQueue@HP││├@HA─────>@HE│ @HBI/O @HE├@HA─┐ @HP┌┬┬┬┬┬┬┬┬┬┐ @HBa @HE│ │ @HP└┴┴┴┴┴┴┴┴┴┘ @HE└─────────┘ @HA│ @HA┌───>@HP│││@HBQueue@HP││├@HA─────>@HE│ @HBC P U @HE│ @HA├─┐ @HA│ @HP└┴┴┴┴┴┴┴┴┴┘ @HE│ │ @HP┌┬┬┬┬┬┬┬┬┬┐ @HBb @HE┌─────────┐ @HA│ │ @HA│ @HE└─────────┴@HA─────>@HP│││@HBQueue@HP││├@HA─────>@HE│ @HBI/O @HE├@HA─┘ │ @HA│ @HP└┴┴┴┴┴┴┴┴┴┘ @HE└─────────┘ @HA│ @HA└───────────────────────────────────<─────────────────────────────────┘ @HBD) @HBb @HE┌─────────┐ @HE┌─────────┐ @HA┌──>@HE│ @HBI/O @HE├@HA─┐ @HP┌┬┬┬┬┬┬┬┬┬┐ @HBa @HE│ │ @HP┌┬┬┬┬┬┬┬┬┬┐ @HA│ @HE└─────────┘ @HA│ @HA┌───>@HP│││@HBQueue@HP││├@HA─────>@HE│ @HBC P U @HE├@HA─────>@HP│││@HBQueue@HP││├@HA─>@HA│ ├─┐ @HA│ @HP└┴┴┴┴┴┴┴┴┴┘ @HE│ │ @HP└┴┴┴┴┴┴┴┴┴┘ @HA│ @HBb @HE┌─────────┐ @HA│ │ @HA│ @HE└─────────┘ @HA└──>@HE│ @HBI/O @HE├@HA─┘ │ @HA│ @HE└─────────┘ @HA│ @HA└───────────────────────────────────<─────────────────────────────────┘ @HEUntersuchung der Auslastung der vier Beispiele @HB1. Die CPU ist 3 mal so schnell wie die I/O-Einheit. @HACPU δ @HP/│\ @HL+ @HB: A @HP┤ @HO* @HB: B @HA1,0 @HP┤ @HN# @HB: C @HP┤ @HKo @HB: D @HP┤ @HP┤ @HB2b @HP┤ @HO* * * *@HKo@HO*@HKo@HO*@HKo@HO*@HKo@HO*@HKo@HO*@HKo@HO*@HKo@HO*@HN#@HKo@HO*@HN# @HB──── = 0,6 @HA0,5 @HP┤ @HO* @HKo @HN# @HBa @HP┤ @HO* @HKo @HN# @HBb @HP┤ @HO* @HKo @HN# @HL+ + + + + + + + + + + + + @HB ─── = 0,3 @HP┤@HO* @HKo @HN#@HL+ @HBa @HP┤@HL+@HN# @HP└─────────────────────────────────────────────────────> @HAAnzahl der Kunden K @HBFalls die CPU 3 mal so schnell ist wie die I/O-Einheit kann man beobachten, daß - im @HPFall A @HBeine stärkere Auslastung als 30 % nicht zu erreichen ist, egal wieviele Kunden im System sind. - im @HPFall B @HBeine doppelt so schnelle I/O-Einheit (die CPU ist also nur noch 1,5 mal so schnell) eine doppelt so hohe Auslastung der CPU zur Folge hat. - im @HPFall C und D @HB2 I/O-Einheiten gegenüber einer zunächst doppelt so schnell sind. Erst später (bei mehr Kunden) wird die gleiche CPU-Auslastung erreicht. Verwendet man jedoch 2 I/O-Einheiten, so ist es besser, dafür eine gemeinsame Warteschlange zu benutzen, als für jede I/O-Einheit eine eigene. Fazit: Der Engpaß bei der CPU-Auslastung ist die langsame I/O-Einheit. @HEUntersuchung der Auslastung der vier Beispiele @HB2. Die I/O-Einheit ist mindestens so schnell wie die CPU. @HA CPU δ @HP/│\ @HO* * * * * @HKo@HO* *@HKo@HO* *@HKo@HO* *@HKo@HO* *@HKo@HO* @HN#@HKo@HO* @HP┤ @HO* @HKo @HN# @HL+@HA 1,0 @HP┤ @HO* @HKo @HN# @HL+ @HP┤ @HO* @HKo @HN# @HL+ @HP┤ @HO* @HKo @HN# @HL+ @HP┤ @HO* @HKo @HN# @HL+ @HP┤ @HO* @HKo @HN# @HL+ @HA 0,5 @HP┤ @HO* @HKo @HN# @HL+ @HL+ @HB: A @HP┤ @HO*@HKo @HN# @HL+ @HO* @HB: B @HP┤ @HO*@HKo@HN# @HL+ @HN# @HB: C @HP┤@HO*@HKo@HN#@HL+ @HKo @HB: D @HP┤@HO*@HL+ @HP└─────────────────────────────────────────────────────────────> @HAAnzahl der Kunden K @HBFalls die I/O-Einheit mindestens so schnell ist wie die CPU, ergibt sich in allen vier Fällen eine Auslastung der CPU von 100 %. Die volle Aus- lastung wird jedoch bei einer unterschiedlichen Anzahl von Kunden im System erreicht. Ist die I/O-Einheit genügend schnell (mindestens so schnell wie die CPU), so entsteht der Engpaß bei der CPU selbst. weiter mit "Synchronisation paralleler Prozesse": ⌐Parallelität@BS___3¬