Knowledge & Learning

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

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

Wrap

Text File | 1992-03-19 | 57.5 KB | 2,203 lines

95 BS___2 Diplomprüfung Informatik Teilprüfung Betriebssysteme Themen: Modellbildung und Systemanalyse zusammengestellt von Andreas Smoor Das Programm soll der Kontrolle, nicht der Erarbeitung des Stoffes für die Diplomprüfung Betriebssysteme dienen. Die Fragen wurden mit Hilfe eines Vorlesungsscripts von Martin Kohnen an der UNI Koblenz erstellt. WARNUNG: Der Autor übernimmt keine Haftung für das Auftreten einer Nasenschleimhautentzündung in Folge der Benutzung dieses Lernprogramms. Januar 1992 Was versteht man ganz Der Durchsatz ist ein Maß allgemein unter dem für die Wirksamkeit eines Rechners. Durchsatz ? Anzahl Jobs Durchsatz = ───────────── Zeiteinheit 2 Systemanalyse 0 1 Durchsatz - 1 10000001 Was versteht man unter Als Verweilzeit bezeichnet man die Zeit von Beginn der ersten Ausführung eines Jobs Verweilzeit ? bis zur Ausgabe des Ergebnisses. 2 Systemanalyse 0 1 Verweilzeit - 1 10000002 Seit etwa 1967 versucht man, Das Verhalten eines Betriebs- das Verhalten von Betriebs- systems ist abhängig von: systemen durch Modellbildung - Benutzerverhalten mathematisch zu beschreiben. - Hardware-Konfiguration Von welchen drei Größen - Systemparameter, die das hängt das Verhalten eines Scheduling beeinflussen Betriebssystems immer ab ? 2 Systemanalyse 0 1 Modellbildung 31000097 Was sollte der Benutzer Zeitverhalten: von einem Betriebssystem - Antwortzeit ist voraus- in bezug auf dessen sagbar Zeitverhalten bei der - Antwortzeit steht in Bearbeitung eines Programms linearem Verhältnis zur erwarten können ? Komplexität des Programms 2 Systemanalyse 0 1 Zeitverhalten 31000098 Was versteht man unter der Die Antwortzeit ist die Zeitspanne, zwischen dem Ende einer Benutzereingabe Antwortzeit ? und dem Vorliegen der vollständigen Antwort darauf. 2 Systemanalyse 0 1 Antwortzeit - 1 31000099 Wann spricht man vom Die eintreffenden Arbeiten müssen vollständig vorliegen Stapel- oder auch und werden vor ihrer Abarbei- tung zuerst in einen Stapel Batchbetrieb eines Systems ? (Keller) abgelegt. Während der Abarbeitung kann man keinen Einfluß nehmen. 2 Systemanalyse 0 1 Stapelbetrieb 31000100 Was wird als Als Dialogbetrieb bezeichnet man eine Betriebsart (meist im Zeitscheibensystem) Dialogbetrieb bei der die Benutzer mit dem DV-System korrespondieren (im Gegensatz zum bezeichnet ? Stapelbetrieb). 2 Systemanalyse 0 1 Dialogbetrieb 31000101 Was versteht man unter Transaktion = einzelner Aufruf einer einer Systemfunktion Transaktion ? Z.B. Löschen, Ersetzen oder Modifizieren eines Nennen Sie ein Beispiel. Datenfeldes 2 Systemanalyse 0 1 Transaktion 31000102 Der Durchsatz ist für Stapelbetrieb: Stapel- und Dialogbetrieb Durchsatz = unterschiedlich definiert. Aufträge / Zeiteinheit Wie ? Dialogbetrieb: Durchsatz = Transaktion / Zeiteinheit 2 Systemanalyse 0 1 Durchsatz - 2 31000103 Definieren Sie den Begriff Unter Auslastung einer Funk- tionseinheit versteht man das Auslastung. Verhältnis von in einem Zeit- raum erbrachter Leistung zu ( utilization, der in diesem Zeitraum relative throughput ) maximal erbringbaren Leistung. 2 Systemanalyse 0 1 Auslastung 31000104 Was meint man mit dem Begriff Das Verhalten eines Systems "Engpass" (bottleneck) und wird wesentlich von dem Gerät welche Rolle spielt er beim bestimmt, das am ehesten voll Verhalten eines Systems ? ausgelastet ist. Es ist also wichtig zu wissen, wo bottlenecks auftreten. 2 Systemanalyse 0 1 Engpässe 31000105 Skizzieren Sie ein ┌───────┐ ∩ ┌─────┐ µ │Bedien-│ Φ einfaches --> │Queue│ ---> │einheit│ -> └─────┘ └───────┘ Warteschlangenmodell. ∩ = Ankunftsrate µ = Bedienrate Φ = Abgangsrate 2 Queue-Theory 0 1 Warteschlangen - 1 31000106 Was versteht man unter der Wenn in T Zeiteinheiten N Kunden kommen, so sagt man sie kommen mit der Ankunftsrate ? N Ankunftsrate ∩ = ─── T 2 Ankunftsprozeß 0 1 Ankunftsrate 31000107 Erklären Sie den Begriff Den mittleren zeitlichen Abstand mit dem die N Kunden in T Zeiteinheiten ankommen nennt man Zwischenankunftszeit ! T Zwischenankunftszeit a = ─── N 2 Ankunftsprozeß 0 1 Zwischenankunftszeit - 1 31000108 Um statistische Aussagen - Kunden kommen unabhängig über den Ankunftsprozeß voneinander an machen zu können, müssen - Kunden kommen zufallsmäßig einige plausible Annahmen verteilt an (unabhängig von gemacht werden. äußeren Umständen) - Es kommt immer höchstens Nennen Sie derer drei. ein Kunde zur gleichen Zeit 2 Ankunftsprozeß 0 1 Ankunftsprozeß - 1 31000109 Zur Beschreibung des zeit- t : Ankunftszeit eines Kunden lichen Verhaltens in einem a : Zwischenankunftszeit Warteschlangensystem werden W : Wartezeit in der Queue verschiedene Zeitbegriffe B : Bedienzeit definiert. V = Verweilzeit = W + B Nennen Sie 5 davon. 2 Queue-Theory 0 1 Warteschlangen - 2 31000110 Wie groß ist die Wahrschein- Poisson-Verteilung: lichkeit, daß in n (∩*t) -∩t t-Zeiteinheiten genau Pn (t) = ──────── * e n! n Kunden eintreffen ? ∩ = Ankunftsrate 2 Ankunftsprozeß 0 1 Ankunftsprozeß - 2 31000111 Wie groß ist die P [a <= t] = 1 - P [a > t] = 1 - Po (t) Wahrscheinlichkeit, daß die -∩t Zwischenankunftszeit a = 1 - e kleiner oder gleich t ist ? also Exponentialverteilung 2 Ankunftsprozeß 0 1 Zwischenankunftszeit - 2 31000112 Definieren Sie den Begriff Wenn in T Zeiteinheiten N Kunden bedient werden, so sagt man sie werden mit der Bedienrate. Bedienrate N µ = ─── T 2 Bedienprozeß 0 1 Bedienrate 31000113 Definieren Sie den Begriff Die mittlere Zeit, mit der die N Kunden in T Zeiteinheiten bedient Bedienzeit. werden, nennt man Bedienzeit 1 B = ─── µ 2 Bedienprozeß 0 1 Bedienzeit - 1 31000114 Wie groß ist die Die Wahrscheinlichkeit, daß (theoretische) Wahrschein- in dem Zeitintervall (0, t) lichkeit, daß die Bedienzeit mindestens ein Kunde bedient eines Kunden kleiner oder wird und die Bedieneinheit gleich t ist ? wieder verläßt, ist -µt B (t) = 1 - e 2 Bedienprozeß 0 1 Bedienzeit - 2 31000115 Was bedeutet es, wenn eine Die Markov-Eigenschaft besagt, daß die Verteilung Verteilung die kein Gedächtnis hat. Die Wahrscheinlichkeit eines Markov-Eigenschaft Ereignisses wird nicht größer, je länger man auf besitzt ? dieses Ereignis wartet. 2 Markov-Eigenschaft 1 1 Markov-Eigenschaft - 1 31000116 Welche Verteilungen besitzen Sowohl die Poisson- als auch die Exponential- die Markov-Eigenschaft ? verteilung besitzt die Markov-Eigenschaft (memoryless property). 2 Markov-Eigenschaft 1 1 Markov-Eigenschaft - 2 31000117 Es gilt, Mittelwert einer Mittelwert der _ diskreten Verteilung Poisson-Verteilung n = ∩ * t, _ ∞ N _ E [x] = x = Σ n * p (n) mit ∩ = ─── ==> n = N n=0 t Was gilt für den Mittelwert (im Mittel kommen der Poisson Verteilung ? N Kunden an) 2 Poisson, Mittelwert 1 1 Poisson-Verteilung 31000118 Wann wird ein System als Ein offenes System ist meist ein Ausschnitt aus einem größeren (oft nicht offenen) offenes System System. In ein offenes System können beliebig viele Kunden kommen und nach ihrer Bedie- bezeichnet ? nung auch wieder gehen. 2 offenes System 1 1 Offenes System 31000119 Wie groß ist bei einem Beim stationärem Zustand in offenen System die Wahr- einem offenen System ist scheinlichkeit, daß sich in P [genau n Kunden im System] einem stationären Zustand des n ∩ Systems genau n Kunden = (1 - δ) * δ mit δ = ─── im System befinden ? µ geometrische Verteilung 2 offenes System 1 1 Kundenzahl 31000121 Wann spricht man vom Wenn sich die Werte für Ankunftsrate ∩ und stationären Verhalten Bedienrate µ zeitlich kaum ändern, so zeigt ein System eines Systems ? stationäres Verhalten. 2 offenes System 0 1 stationäres Verhalten 31000120 Wie groß ist die Wahrschein- Die Wahrscheinlichkeit für ein Faulenzen des Systems ist lichkeit, daß ein System ∩ leer ist, also nicht Po = 1 - δ mit δ = ─── µ arbeitet ? 2 offenes System 1 1 Faulenzen des Systems - 1 31000122 Wie ist die Die Auslastung δ des Systems wird angegeben durch die Auslastung Wahrscheinlichkeit, daß das System beschäftigt ist. des Systems definiert ? δ = 1 - Po 2 offenes System 1 1 Auslastung - 1 31000123 Wie ergibt sich der E [n] = Quotient aus den Erwartungswert E [n] für die Wahrscheinlichkeiten für die mittlere Anzahl von Kunden, Beschäftigung und die Nicht- die sich im System befinden ? Beschäftigung des System δ 1-Po E [n] = ─── = ──── 1-δ Po 2 offenes System 1 1 Erwartungswert Anzahl Kunden 31000124 Wie lautet der Die mittlere Anzahl von Kunden im System E [n] = L Satz von Little ist proportional zu der Ankunftsrate ∩ und der für Systeme im stationären mittleren Verweilzeit eines Kunden im System E [V] = T. Zustand ? Also: L = ∩ * T 2 Little 0 1 Little - 1 31000125 Leiten Sie aus dem Satz von Satz von Little: L = ∩ * T E [n] Little die mittlere => T = ───── offene Systeme: ∩ Verweilzeit von Kunden im δ 1 1 1 => T = ─── * ─── = ─── * ─── System ab ! 1-δ ∩ µ 1-δ 2 Little 1 1 Little - 2 31000126 Aus dem Satz von Little Verweilzeit in der Schlange ergibt sich die Verweilzeit ist gleich Zeit im System im System minus Bedienzeit: E [n] T = ─────. Wie groß ist die 1 ∩ Tq = T - ─── Verweilzeit in der Queue ? µ 2 Little 1 1 Verweilzeit in der Schlange 31000127 Wie läßt sich die mittlere E [nq] = ∩ * Tq = E [n] - E [nBE] Anzahl der Kunden in der = E [n] - (1 - Po) = E [n] - δ Schlange berechnen ? δ = ─── - δ = ... = E [n] * δ 1-δ 2 Little 1 1 Kunden in der Queue 31000128 Was besagt der Satz von Ein neu ankommender Kunde findet im System genau so Little über die Beziehung von viele Kunden vor, wie er bei seiner Beendigung zurückläßt. Abgangsrate Φ und Abgangsrate = Ankunftsrate Ankunftsrate ∩ ? Φ = ∩ 2 Little 0 1 Little - 3 31000129 In welcher Beziehung steht Abgangsrate Φ = ∩ die Abgangsrate Φ zu ∩ mit ─── = δ = 1 - Po ==> zu Bedienrate µ und µ Auslastung δ eines Systems ? Φ = µ * δ = µ * (1 - Po) 2 Little 0 1 Abgangsrate - 1 31000130 Damit sich die Hardware- Rechner augelastet ==> δ -> 1 Investitionen lohnen, muß der Es gilt: 1 1 Rechner gut ausgelastet sein. T = ─── * ─── Welche Konsequenzen ergeben 1-δ µ sich dadurch für die mittlere Verweilzeit T der Wenn δ -> 1, dann wird T Kunden im System ? beliebig groß ! 2 Systemkonfiguration 0 1 Auslastung - 2 31000131 Bei einer Steigerung der Antwort: Auslastung δ des Systems vergrößert sich die Gar nicht. mittlere Verweilzeit der Kunden T. Entweder man macht ab und zu Wie wird dieses Dilemma in Kaffeepause oder man ärgert der Praxis gelöst ? sich grün und blau. 2 Systemkonfiguration 0 1 Verweilzeit - 2 31000132 Was ergibt sich für die 1 1 1 E [T] = ─── * ─── = B * ─── mittlere Verweilzeit T, wenn µ 1-δ 1-δ die Auslastung δ von 0,8 auf δ = 0,8 ==> E [T] = B * 5 0,9 gesteigert wird ? δ = 0,9 ==> E [T] = B * 10 2 auch B ist abhängig von δ ! ==> Verhältnis 4/9, \(5/10) ? Systemkonfiguration 0 1 Systemkonfiguration - 1 31000133 Was ergibt sich für die δ mittlere Anzahl der Kunden E [n] = ─── im System E [n], wenn die 1-δ Auslastung von 0,8 auf 0,9 gesteigert wird ? δ = 0,8 ==> E [n] = 4 δ = 0,9 ==> E [n] = 9 2 Systemkonfiguration 1 1 Systemkonfiguration - 2 31000134 Sei die Auslastung des Es wird dann µ' = 2 * µ ==> Systems δ = 0,8. δ' = 0,4. Es gilt Welche Auswirkung hätte die δ Verdoppelung der Geschwindig- E [n] = ─── keit der Bedieneinheit BE 1-δ auf die mittlere Anzahl der δ = 0,8 ==> E [n] = 4 Kunden im System ? δ = 0,4 ==> E [n] = 0,67 2 Systemkonfiguration 0 1 Systemkonfiguration - 3 31000135 Sei die Auslastung des Es wird dann µ' = 2 * µ ==> Systems δ = 0,8. δ' = 0,4. Es gilt Welche Auswirkung hätte die 1 1 1 Verdoppelung der Geschwindig- E [T] = ─── * ─── = B * ─── keit der Bedieneinheit BE µ 1-δ 1-δ auf die mittlere Verweilzeit δ = 0,8 ==> E [T] = B * 5 der Kunden im System T ? δ = 0,4 ==> E [T] = B * 0,83 2 Aufpassen mit B und B'. Systemkonfiguration 1 1 Systemkonfiguration - 4 31000136 Welche Auswirkung hätte Bei Hinzunahme einer zweiten die Verwendung einer zweiten BE halbiert sich die Betriebseinheit auf die zu Ankunftsrate ∩ ==> erwartende mittlere Zahl der δ Kunden im System, falls δ' = ─── ==> E [n]' = 0,67 die Auslastung δ vorher 2 0,8 betrug ? E [n] = 4 2 Systemkonfiguration 1 1 Systemkonfiguration - 5 31000137 Welche Auswirkung hätte die Die Ankunftsrate ∩ halbiert Verwendung einer zweiten sich. ==> δ' = ½ δ = 0,4 ==> Betriebseinheit auf die zu 1 1 erwartende mittlere Verweil- E [T]' = ─── * ─── = B * 1,67 zeit der Kunden im System, µ 1-δ' wenn die Auslastung δ vorher 0,8 betrug ? für δ = 0,8 war E [T] = B * 5 2 Systemkonfiguration 1 1 Systemkonfiguration - 6 31000138 Eine Firma möchte die mitt- 1 1 lere Verweilzeit im System E [T] = ─── * ─── verkürzen. Sei δ = 0,8. Ist µ 1-δ es günstiger a) einen zweiten δ = 0,8 ==> E [T] = B * 5 gleichstarken oder b) nur ei- Lösung b) ist besser, denn nen aber doppelt so schnellen a) ∩'=½∩ ==> E [T] = B * 1,67 Prozessor einzusetzen ? b) µ'=2µ ==> E [T] = B * 0,83 2 Systemkonfiguration 0 1 Systemkonfiguration - 7 31000139 Im vereinfachten stationären Im vereinfachten stationären Modell geht man davon aus, Modell sind ∩ und µ unab- daß die Ankunftsrate ∩ und hängig von der Anzahl der die Bedienrate µ unabhängig Kunden im System. Im allge- von ... meinen stationären Modell läßt man diese Voraussetzung Ergänzen Sie den Satz. fallen. 2 allg. Lösung 0 1 allgemeines stationäres Modell 31000140 Skizzieren Sie ein ┌───────────<───────────────┐ geschlossenes System mit │ ┌────┐ │ N Kunden. ├>1─>┐ ∩ ┌─────┐ µ │ │ Φ │ ├>2─>┼──>│Queue│──>│ BE │──>┘ U = Denkzeit am Terminal │ : │ └─────┘ │ │ BZ = Bedienzeit └>N─>┘ └────┘ ├─U──┼──Wartezeit──┼─BZ─┤ 2 geschlossenes System 0 1 geschlossenes System 32000141 Die Denkzeit am Terminal U Die user-time U hat den (user-time) ist eine Zufallsgröße mit welchem 1 Mittelwert ? Mittelwert ───. ∩ 2 geschlossenes System 1 1 user-time 32000142 Die Umlaufzeit T Die Umlaufzeit T setzt sich (turn-around-time) zusammen aus setzt sich zusammen aus ... - der Denkzeit U und - der Antwortzeit R. 2 geschlossenes System 0 1 Umlaufzeit 32000143 Wie lange dauert im Mittel Im Mittel dauert die Abarbeitung eines Auftrags die Abarbeitung eines durch die Bedieneinheit Auftrags durch die 1 ─── Zeiteinheiten. Bedieneinheit ? µ 2 geschlossenes System 1 1 Bedienzeit - 3 32000144 Was gilt im Idealfall Im Idealfall besteht die Antwortzeit R nur aus der Bedienzeit. Es gilt dann eines Time- Sharing-Systems ? 1 R (ideal) = ─── . µ 2 geschlossenes System 1 1 Idealfall 32000145 Wie groß ist die Tatsächliche Antwortzeit: tatsächliche Antwortzeit N 1 R (tat) = ──── * ─── - U in einem geschlossenen 1-Po µ System ? 2 geschlossenes System 0 1 Antwortzeit, tatsächliche - 2 32000150 Da die tatsächliche Sie ist definiert als Antwortzeit eines tatsächliche geteilt durch geschlossenen Systems wenig ideale Antwortzeit. Also aussagt, wird diese normiert. Wie ist die normierte tatsächliche Antwortzeit R (norm) = µ * R (tat) definiert ? 2 geschlossenes System 1 1 Antwortzeit, normierte 32000151 Zur Ermittlung der Satz von Little: N = µ * T Abgangsrate Φ in einem mit µ = Φ ==> N = Φ * T geschlossenen System schnei- mit T = U + R ==> det man das System hinter der N = Φ * (U + R) ==> BE auf und beobachtet was N dort passiert. Φ = ───── Tun Sie genau das. (U+R) 2 geschlossenes System 1 1 Abgangsrate - 2 32000146 Wie läßt sich die ∩ Abgangsrate Φ mit Hilfe der (1-Po) = δ = ─── Wahrscheinlichkeit für das µ Arbeiten des System (1-Po) ausdrücken ? mit Φ = ∩ ==> Φ = (1-Po) * µ 2 geschlossenes System 0 1 Abgangsrate - 3 32000147 Leiten Sie die tatsächliche N Φ = ─── = (1-Po) * µ ==> Antwortzeit in einem U+R N 1 geschlossenen System ab. R (tat) = ──── * ─── - U 1-Po µ 2 geschlossenes System 0 1 Antwortzeit, tatsächliche - 1 32000148 Die Gleichungen für die Bei den Gleichungen für die Antwortzeit in einem Antwortzeit in geschlossenen geschlossenen System sind von Systemen wird der Verteilung der Bedienzeit und Denkzeit unabhängig. stationäres Verhalten Was wird aber vorausgesetzt ? vorausgesetzt. 2 geschlossenes System 0 1 Antwortzeit - 2 32000149 Interpretieren Sie die Die tatsächliche Antwortzeit Formel für die Antwortzeit in im geschlossenen System ist einem geschlossenen System: eine lineare Funktion der Zahl der Benutzer N. N 1 R = ──── * ─── - U (stationäres Verhalten 1-Po µ vorausgesetzt) 2 geschlossenes System 0 1 Antwortzeit, tatsächliche - 3 32000152 Bis zu einer gewissen Zahl N 1 der Kunden N° beträgt die R = ──── * ─── - U Wartezeit im geschlossenen 1-Po µ System 0. Ab der Zahl N° Wartezeit > 0 ==> (1-Po) = 1 steigt die Wartezeit dann 1 linear an. µ = ─────── ==> N° = U * µ +1 Berechnen Sie N° ! R(ideal) 2 geschlossenes System 0 1 kritische Benutzerzahl 32000153 Was ist mit einem M / M / 1 / N - System : - Ankünfte Poisson verteilt M / M / 1 / N - System ==> Denkzeiten exponentiell - Bedienrate Poisson gemeint ? ==> Bedienzeit exponentiell - 1 Bedieneinheit - endlich viele Kunden N 2 geschlossenes System 0 1 M / M / 1 / N - System 32000154 Ist es in einem Modell für Nein, solange ein Auftrag ein geschlossenes System noch nicht beendet wurde, erlaubt, daß ein Kunde mehr kann kein zweiter Auftrag des als einen Auftrag gleich- gleichen Kunden abgeschickt zeitig an die Betriebseinheit werden. schickt ? 2 geschlossenes System 0 1 Kunden im System - 1 32000155 Was besagt die folgende Sie stellt die rekursive Gleichung ? Formel für die Wahrschein- lichkeit von K Kunden im ∩ (K-1) System dar. Also K Kunden P (K) = ─────── * P (K-1) befinden sich entweder in µ (K) der Queue oder in der mit ∩ (K) = (N-K) * ∩ Betriebseinheit. 2 geschlossenes System 0 1 Faulenzen des Systems - 2 32000156 Wie erhält man anschaulich Die Formel ergibt sich über das Zustandsdiagramm. die Formel für Wahrschein- N*∩ (N-1)*∩ ∩ ┌───>── ┌───>── ┌─>... ── lichkeit von K Kunden im 0 1 2 N ───<───┘───<───┘──...<──┘ offenen System P (K) ? µ µ µ 2 geschlossenes System 0 1 Kunden im System - 2 32000157 Wie läßt sich die Wahrschein- Mit Hilfe der Summenformel lichkeit für ein Faulenzen im offenen System Po mit ∞ Hilfe der Rekursionsformel Σ P (K) = 1 für die Wahrscheinlichkeit K=0 von K Kunden im System berechnen ? läßt sich Po berechnen. 2 geschlossenes System 1 1 Faulenzen des Systems - 3 32000158 Es sei Denkzeit U = 5 sec Bei den gegebenen Werten und Bedienzeit B = 0,5 sec in einem geschlossenen Anzahl der Kunden N = 5 System wird sich bei Halbierung der Bedienzeit Wie wirkt sich eine auch die Antwortzeit in etwa Halbierung der Bedienzeit auf halbieren. die Antwortzeit R (tat) aus ? (Rekursionsformel für Po) 2 geschlossenes System 0 1 Antwortzeit - 4 32000161 µ * R (1) = 1 Es handelt sich um die Rekursionsformel für die (µ/∩) * (N-1) normierte Antwortzeit R in µ * R (N) = ──────────────── einem geschlossen System in µ*R(N-1) + (µ/∩) Abhängigkeit von der Anzahl der Kunden N im stationären Was ist das ? Zustand. 2 geschlossenes System 0 1 Antwortzeit - 3 32000160 Es sei Denkzeit U = 5 sec Bei den gegebenen Werten in und Bedienzeit B = 0,5 sec einem geschlossenen System Anzahl der Kunden N = 5. wird sich bei Verdoppelung der Denkzeit die Wie wirkt sich eine Antwortzeit nur um 12 % Verdoppelung der Denkzeit auf verkürzen. die Antwortzeit R (tat) aus ? (Rekursionsformel für Po) 2 geschlossenes System 0 1 Antwortzeit - 5 32000162 Warum macht sich eine Beim sinnvollen Vergleich ist Änderung der Bedienrate µ die Auslastung δ und damit im bezug auf die tatsächliche auch die normierte Antwortzeit R (tat) stärker Antwortzeit R (norm) in bemerkbar als eine Änderung beiden Fällen gleich. Um aber der Ankunftsrate ∩ ? R (tat) zu erhalten wird R (norm) noch durch µ geteilt 2 geschlossenes System 1 1 Antwortzeit - 6 32000163 Was gilt bei einem Im M / G / 1 - System gilt: - Ankunftsprozeß: M / G / 1 - System ? Poisson verteilt - Bedienprozeß: Verteilung beliebig (general) - Anzahl Bedieneinheiten = 1 2 M/G/1-System 1 1 M / G / 1 - System 33000164 Erläutern Sie die rekursive Wenn Kunde C (n+1) das System Gleichung verläßt, dann befinden sich im System die Kunden, die q (n+1) = q (n) - 1 + v (n+1) auch bei C (n) da waren, minus C (n+1) selbst und plus für die Anzahl der Kunden im die Kunden, die dazu kamen, M/G/1-System mit q (n) > 0. während C (n+1) in der BE war 2 M/G/1-System 0 1 Kunden im System - 3 33000165 Welche Voraussetzungen Falls im M/G/1-System sich müssen für die Gültigkeit während der Bedienzeit des der Gleichung Kunden C (n) kein anderer Kunde im System befindet, und q (n+1) = v (n+1) C (n+1) erst danach eintrifft, gilt die gegeben sein ? Gleichung. Also: q (n) = 0. 2 M/G/1-System 0 1 Kunden im System - 4 33000166 Die Pollaczek-Klinchin (PK) Die erste rekursive Gleichung Gleichung gibt die mittlere für Anzahl der Kunden q Anzahl der Kunden in einem quadrieren, Erwartungswerte M/G/1-System an. bilden, nach E [q] auflösen, E [v²] mit Z-Transformation Wie erhält man sie ? ersetzen und C² für die Varianz einführen. Fertig ! 2 M/G/1-System 1 1 Pollaczek-Klinchin - 1 33000167 Die Varianz der Bedienzeiten PK-Gleichung: sei __ _² var x² - x C² = ─── = ──────── 1 + C² _² _² E [q] = δ + δ² * ─────────── x x 2 * (1 - δ) Wie lautet die PK-Gleichung ? 2 M/G/1-System 0 1 Pollaczek-Klinchin - 2 33000168 Interpretieren Sie die E [q] steigt linear mit C². E [q] ist am kleinsten, wenn Pollaczek-Klinchin Gleichung. die Bedienzeiten für alle Kunden gleich sind (M/D/1). δ Für C² = 1 gilt: E [q] = ─── 1-δ (==> M/M/1) 2 M/G/1-System 0 1 Pollaczek-Klinchin - 3 33000169 Was gilt in einem M / D / 1 - System: M / D / 1 - System ? - Ankunftsprozeß Poisson verteilt - Bedienzeit deterministisch für alle Kunden gleich - eine Bedieneinheit 2 M/G/1-System 0 1 M / D / 1 - System 33000170 Leiten Sie mit Hilfe der Bedienzeiten alle gleich ==> PK-Gleichung den Erwartungs- Varianz = 0 = C² ==> ... ==> wert für die Zahl der Kunden in einem M/D/1-System ab. δ δ² E [q] = ─── - ───────── 1-δ 2 * (1-δ) 2 M/G/1-System 0 1 Pollaczek-Klinchin - 4 33000171 Vergleichen Sie die Das M/D/1-System hat im Erwartungswerte für die Zahl Mittel der Kunden für ein δ² M/M/1-System und ein ───────── M/D/1-System ! 2 * (1-δ) weniger Kunden im System als das M/M/1-System. 2 M/G/1-System 0 1 Kunden im System - 5 33000172 Das von Jackson entwickelte Jackson-Netz: Netz von Warteschlangen- - m (i) = Zahl der Bedienein- Systemen besteht aus heiten N Knoten. Was bedeuten die - µ (i) = Bedienrate, Parameter Poisson verteilt m (i) und µ (i) eines Knotens i ? 2 Jackson-Netz 1 1 Jackson Netz - 1 33000173 Was bedeutet die Angabe von Jackson Netz: r (i,j) = Wahrscheinlichkeit, r (i,j) daß ein Kunde nach Verlassen des Knotens i zum Knoten j für ein Jackson Netz ? geht. r (i,i) > 0, in den Knoten i zurück gehen ist erlaubt. 2 Jackson-Netz 1 1 Jackson Netz - 2 33000174 Was drückt Die Summenformel gibt die Wahrscheinlichkeit für ein N Jackson Netz an, daß ein 1 - Σ r (i,j) Kunde nach Verlassen des j=1 Knotens i das gesamte Netz verläßt. für ein Jackson Netz aus ? 2 Jackson-Netz 1 1 Jackson Netz - 3 33000175 Welche Verteilung ergibt sich Die Ankunftsrate Y (i) für den Knoten i von Kunden für die Ankunftsrate Y (i) außerhalb des Netzes ist des Knoten i von Kunden von Poisson verteilt. außerhalb des Netzes ? 2 Jackson-Netz 1 1 Jackson Netz - 4 33000176 Wie lautet die Formel für die In einem Jackson Netz ist die gesamte Ankunftsrate für den gesamte Ankunftsrate ∩ (i) Knoten i ∩ (i) = eines Knoten i in einem N Y (i) + Σ ∩ (j) * r (j, i) Jackson Netz ? j=1 2 Jackson-Netz 0 1 Jackson Netz - 5 33000177 Was wird aus einem Ein Jackson Netz aus nur Jackson Netz, wenn es nur einem Knoten entspricht einen Knoten enthält ? einem M/M/m-System. 2 Jackson-Netz 0 1 Jackson Netz - 6 33000178 Es sei pi (Ki) die Wahr- Die Wahrscheinlichkeit scheinlichkeit für ein p (K1, K2, ..., KN) Jackson Netz, daß sich im = p1 (K1) * p2 (K2) * Knoten i Ki Kunden befinden. ... * pN (KN) N Was lautet das = π pi (Ki) Jackson-Theorem ? i=1 2 Jackson-Netz 0 1 Theorem von Jackson - 1 33000179 Interpretieren Sie das Jeder Knoten in einem Jackson Netz kann wie ein Theorem von Jackson. unabhängiges M/M/m-System betrachtet werden. Die Einzelzustände sind unabhängig voneinander. 2 Jackson-Netz 0 1 Theorem von Jackson - 2 33000180 Das Gordon / Newell Netz ist Das Netz ist geschlossen: eine Modifikation des - feste Anzahl Kunden im Netz Jackson Netzes. - kein weiterer Kunde kann in das Netz gelangen, Y(i) = 0 Welchen Einschränkungen - keiner der K Kunden kann unterliegt es ? das Netz verlassen 2 Jackson-Netz 0 1 Gordon / Newell Netz - 1 33000181 Wie kann man die Bedingung Im Gordon / Newell Netz gilt: eines Gordon / Newell Netzes, daß kein Kunde das Netz N verlassen kann, formal Σ r (i,j) = 1 ausdrücken ? j=1 für alle i 2 Jackson-Netz 0 1 Gordon / Newell Netz - 2 33000182 Da die Zahl der Kunden im Man kann K Kunden auf Gordon / Newell Netz konstant N Knoten verteilen wie folgt: ist, ist sie insbesondere nach oben beschränkt. Deshalb ┌ ┐ ┌ ┐ ist die Anzahl der Zustände │N + K - 1│ = │N + K - 1│ des Systems endlich. │ K │ │ N - 1 │ Wie groß ist diese Anzahl ? └ ┘ └ ┘ 2 Jackson-Netz 0 1 Gordon / Newell Netz - 3 33000183 Gilt das Jackson Theorem Nein, p(K1, K2, ..., KN) läßt sich im Gordon / Newell auch für ein Netz nicht aus dem Produkt der Einzelwahrscheinlich- Gordon / Newell Netz ? keiten pi (Ki) berechnen. 2 Jackson-Netz 1 1 Gordon / Newell Netz - 4 33000184 Die Funktion der Wahrschein- Ansatz: lichkeit, daß im Zeitraum (0, t + dt) genau n Kunden ∞ n ankommen erhält man mit Hilfe G (z) = Σ Pn (t) * z einer erzeugenden Funktion. n=0 Wie lautet der Ansatz ? 2 Ankunftsprozeß 1 1 z-Transformation 31000998 Wie erhält man die Verteilung Aus der Poisson-Verteilung des Ankunftsprozesses ergibt der Zwischenankunftszeit ? sich -∩t Po (t) = e mit P (a≤t) = 1 - Po (t) ==> -∩t P (a≤t) = 1 - e 2 Ankunftsprozeß 1 1 Zwischenankunftszeit - 3 31000999 Die Notation von Modellkennzeichnung: Modelltypen ist wie folgt A: Verhalten Ankunftsprozeß aufgebaut: B: Verhalten Bedienprozeß C: Anzahl Bedieneinheiten A / B / C / D / E D: Größe des Speichers E: Anzahl Kunden in einem Wofür stehen die Buchstaben ? (geschlossenen) System 2 Modellkennzeichnung 1 1 Modellkennzeichnung - 1 31000996 Bei der Modellkennzeichnung M : Markov-Eigenschaft verwendet man für die ersten Er: r-stufige Erlang Verteil. beiden Stellen Buchstaben zur Hr: r-stufige Hyperexponen- Kennzeichnung der Verteil- tialverteilung funktion. D : Zwischenankunftszeit Was bedeuten dabei M, Er, Hr, deterministisch D und G ? G : Verteilung beliebig 2 Modellkennzeichnung 1 1 Modellkennzeichnung - 2 31000997 Die Wahrscheinlichkeit, daß Annahme: Verhältnisse bei t genau n Kunden im offenen sind bekannt. System sind ist n - 4 Fälle für Zeit (t, t+dt) Pn = (1-δ) δ . - 4 Gleichungen für Pn (t+dt) - Gleichungssystem auflösen Wie kommt man darauf ? - Differentialgleichung dt->0 lösen 2 offenes System 0 1 Kunden im System 31000995 Welche Voraussetzungen Damit die ideale 1 müssen in einem geschlossenen Response-Time R (ideal) = ─── System für die Denkzeit U µ und die Response-Time R erreicht werden kann, muß gelten, damit die ideale gelten, daß 1. U und R für Response-Time R (ideal) alle Kunden gleich und erreicht werden kann ? 2. U ≥ (N-1) * R 2 geschlossenes System 1 1 ideale Antwortzeit 32000999