Knowledge & Learning

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

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

Wrap

Text File | 1992-03-20 | 37.9 KB | 1,444 lines

62 BS___5 Diplomprüfung Informatik (Teil 5 von 7) Teilprüfung Betriebssysteme Thema: Scheduling zusammengestellt von Andreas Smoor Hinweis: Eine Themenübsicht kann mit dem Menüpunkt "Inhalt - Lektionen" eingesehen werden. März 1992 Welche Entscheidungen werden Falls mehrere Prozesse gleichzeitig auf ein Betriebsmittel zugreifen beim Scheduling getroffen ? möchten, muß entschieden werden, welcher Prozeß bevorzugt wird. Dieses Verfahren heißt Scheduling. 2 Scheduling II 0 1 Scheduling - 2 51000277 Was ist ein Ein Scheduler ist ein Programm, das die Betriebsmittelvergabe an die Scheduler ? einzelnen Prozesse steuert und durchführt. 2 Scheduling II 1 1 Scheduler 51000278 Was wird unter Scheduling in einem System, in dem die Ausführungszeiten deterministischem Scheduling der Prozesse schon vorher bekannt sind wird als verstanden ? deterministisches Scheduling bezeichnet. 2 Scheduling II 1 1 deterministisches Scheduling 51000279 Was wird unter Sind für die Rechenzeiten der Prozesse nur Erwartungs- probabilistischem Scheduling und Wahrscheinlichkeitswerte bekannt, dann erfolgt die verstanden ? Verteilung der Betriebsmittel durch probabilistisches Scheduling. 2 Scheduling II 1 1 probabilistisches Scheduling 51000280 Die Ziele des Scheduling sind Batch-System: je nach Betriebssystem-Typ hoher Durchsatz verschieden. Nennen Sie die Time-Sharing-System: wichtigsten Ziele für ein kurze Antwortzeiten Batch-, ein Real-Time-System: Time-Sharing- und ein Antworten innerhalb festge- Real-Time-System. legter garantierter Zeiten 2 Scheduling II 1 1 Scheduling, Ziele 51000281 Scheduling-Verfahren lassen - Verfahren der Prioritäts- sich nach verschiedenen zuteilung an die Prozesse Kriterien unterscheiden. - statische / dynamische Prioritätsvergabe Nennen Sie drei solcher - Verfahren mit / ohne Unterscheidungsmerkmale. Preemption 2 probabil. Scheduling 1 1 Unterscheidungs-Kriterien 52000282 Wie erfolgt das Scheduling Beim FIFO-Verfahren werden die einzelnen Prozesse streng beim FIFO-Verfahren ? in der Reihenfolge des Ein- treffens ihrer Anforderungen bedient. 2 probabil. Scheduling 1 1 FCFS - 1 52100283 Wie groß ist die mittlere Mittlere Wartezeit bei FCFS: Wartezeit beim 1 δ W = ─── * ─── FCFS-Scheduling Verfahren ? µ 1-δ 2 probabil. Scheduling 1 1 FCFS - 2 52100284 Interpretieren Sie die Die mittlere Wartezeit W beim FCFS ist unabhängig von der Formel der mittleren (individuellen) Rechenzeit der Prozesse. Im Mittel ist W Wartezeit W beim also für kurze und lange Prozesse gleich groß. FCFS-Scheduling-Verfahren ! 2 probabil. Scheduling 1 1 FCFS - 3 52100285 Beim FCFS-Scheduling ist die Die mittlere Wartezeit ist mittlere Wartezeit unabhängig unabhängig von der Länge von der Länge eines Jobs. eines Jobs bei Für welche Verfahren gilt - FCFS, diese Aussage auch noch ? - LCFS und - RANDOM-Verfahren. 2 probabil. Scheduling 1 1 FCFS - 4 52100286 Vergleichen Sie das Varianz- Beim FCFS-Scheduling ist die Verhalten in Bezug auf die mittlere Wartezeit beim Varianz der Wartezeiten FCFS-Scheduling und RANDOM-Scheduling. wesentlich geringer als beim RANDOM-Verfahren. 2 probabil. Scheduling 1 1 FCFS - 5 52100287 Weshalb ist das LCFS- Ein Prozeß, der gerade von der Bedieneinheit bedient Scheduling-Verfahren ein wird, wird beim LCFS- Scheduling unterbrochen, Verfahren mit Preemption ? sobald ein neuer Prozeß ankommt. 2 probabil. Scheduling 1 1 LCFS 52200288 Zeichnen Sie eine Skizze /│\ W (x) * * * * * * für die mittlere Wartezeit W │ * in Abhängigkeit der Länge │ * eines Jobs x für das FCFS- │ * SJF und das SJF-Scheduling- │ * Verfahren. │─*────────────────────FCFS *────────────────────────> x 2 probabil. Scheduling 1 1 SJF - 1 52300289 Beschreiben Sie das Bei RR werden die Prozesse nach FCFS in die Queue einge- prinzipielle Vorgehen beim reiht. Abwechselnd wird dann jedem Prozeß ein festes Round-Robin-Scheduling (RR). Quantum an Rechenzeit zuge- teilt wonach er wieder an den Anfang der Queue kommt. 2 probabil. Scheduling 1 1 RR - 1 52400290 Wie groß ist beim g = P [to ≤ x ≤ t1] Round-Robin-Scheduling die Wahrscheinlichkeit g, daß die k-1 Rechenzeit x eines Prozesses = s * (1 - s) zwischen to und t1 liegt, also k Zeitscheiben -µQ aufnimmt ? mit 0 < s = e < 1 2 probabil. Scheduling 1 1 RR - 2 52400291 Skizzieren Sie ein Diagramm, 1 ┤ B (t) * * aus dem die Beziehung │ *..┐ zwischen Bedienzeitverteilung │ * : ├ g und g = P [to ≤ x ≤ t1] │ *.......:..┘ für das RR-Scheduling │*: : hervorgeht. └─┬───────┬─────────────> t to t1 2 probabil. Scheduling 0 1 RR - 3 52400292 Wie verhält sich das RR- Falls Q -> ∞ verhält sich Scheduling-Verfahren, wenn das Rechenquantum Q einer das RR-Verfahren wie Zeitscheibe gegen unendlich geht ? FCFS ohne Preemption. 2 probabil. Scheduling 0 1 RR - 4 52400293 Wie verhält sich das RR- Falls Q -> 0 erhält man Scheduling-Verfahren, wenn Processor-Sharing-Scheduling das Rechenquantum Q einer (PS-Scheduling). Zeitscheibe gegen Null geht ? Wichtig ist hierbei der Overhead, also der Aufwand zum Umschalten zwischen den Prozessen. 2 probabil. Scheduling 0 1 RR - 5 52400294 Leiten Sie die mittlere δ 1 nach Little gilt: T = ─── * ─ Verweilzeit T (x) mit 1-δ ∩ <==> _ 1 1 ∩ 1 1 x = ─── für RR ab. T = ─── * ─ * ─ = ─── * x µ 1-δ µ ∩ 1-δ 2 probabil. Scheduling 0 1 RR - 6 52400295 Wie groß ist die mittlere Die mittlere Wartezeit ist beim RR-Verfahren genauso Wartezeit beim groß wie beim FCFS-Verfahren: RR-Scheduling-Verfahren ? δ W (x) = x * ─── 1-δ 2 probabil. Scheduling 0 1 RR - 7 52400296 Stellen Sie den Zusammenhang Es gilt: zwischen Wartezeit W (x) und Verweilzeit T (x) dar, wobei T (x) = W (x) + x x = Bedienzeit eines <==> Prozesses. W (x) = T (x) - x (z. B. für RR-Scheduling) 2 probabil. Scheduling 0 1 RR - 8 52400297 Was läßt sich über die Bei Round-Robin-Scheduling "Bestrafungsfunktion" ist W (x) W (x) δ ─────── für das RR Verfahren ─────── = ─── = konstant x x 1-δ aussagen ? ==> Fairness 2 probabil. Scheduling 0 1 RR - 9 52400298 Was gilt in Bezug auf die Die Bestrafung ist beim "Bestrafungsfunktion" FCFS für kurze Prozesse relativ größer als für W (x) längere Prozesse. ─────── beim FCFS-Scheduling? x 2 probabil. Scheduling 0 1 FCFS - 6 52100299 Wie könnte eine Antistrategie Wenn man beim FCFS-Scheduling beim FCFS-Scheduling aussehen, die versucht, die mehrere kurze Prozesse zu Wartezeiten für die eigenen Prozesse zu verringern ? einem längeren zusammenfaßt, verkürzt sich die Wartezeit. 2 probabil. Scheduling 1 1 FCFS - 7 52100300 Worin besteht die Die Queue wird bei SRR in einen linken und einen grundsätzliche Idee des rechten Teil mit unterschied- lichen dynamischen SRR-Scheduling-Verfahrens Prioritäten aufgeteilt. (selfish round robin) ? 2 probabil. Scheduling 1 1 SRR - 1 52500301 Wie lautet die Formel für die Übergangsrate ∩' bei SRR: Übergangsrate ∩' von der ß ∩' = ∩ (1 - ───) linken in die rechte Queue α beim SRR-Scheduling ? 2 probabil. Scheduling 1 1 SRR - 3 52500303 Die Prioritäten der linken Beim SRR gilt für die Hälfte der Queue und der Faktoren α und ß der rechten Hälfte wachsen beim Prioritäten immer die SRR um den Faktor α bzw. ß. Beziehung: Welche Beziehung gilt immer α ≥ ß ≥ 0 zwischen α und ß ? 2 probabil. Scheduling 1 1 SRR - 2 52500302 Was könnte eine Erklärung für Wie beim FCFS-Scheduling kann der Benutzer durch eine das "selfish" (egoistisch) Antistrategie die Länge der Wartezeiten für sich im Namen des SRR-Verfahrens verkürzen. Eine solche Strategie geht aber immer sein ? auf Kosten der anderen User. 2 probabil. Scheduling 0 1 SRR - 4 52500304 Mit Hilfe welcher Parameter Durch Veränderung der kann der System-Operateur Faktoren α und ß für die das Scheduling-Verhalten Prioritäten kann der beim SRR-Scheduling Operateur das Verhalten beeinflussen ? des SRR-Algorithmusses steuern. 2 probabil. Scheduling 0 1 SRR - 5 52500305 Wie verhält sich ein Wenn gilt, daß α = ß > 0, SRR-Scheduling-System, wenn dann verhält sich SRR wie man die Parameter α und ß FCFS. so einstellt, daß gilt: (Eine größere Priorität kann α = ß > 0 ? nie eingeholt werden.) 2 probabil. Scheduling 0 1 SRR - 6 52500306 Wie verhält sich ein Wenn gilt, daß α = ß = 0, SRR-Scheduling-System, wenn dann verhält sich SRR wie RR. man die Parameter α und ß so einstellt, daß gilt: (Es gibt keine Prioritäten mehr.) α = ß = 0 ? 2 probabil. Scheduling 1 1 SRR - 7 52500307 Wie erfolgt die Beim FB-Verfahren wird jeweils der Prozeß bedient, Prozeßauswahl beim der bisher am wenigsten Rechenzeit aufgenommen hat. FB (foreground background) Dazu legt man mehrere Warteschlangen für die ver- Scheduling-Verfahren ? schiedenen Prioritäten an. 2 probabil. Scheduling 1 1 FB - 1 52600308 Wie lautet die Formel für Wartezeit Wx bei FB: die Wartezeit Wx beim FB-Scheduling ? _____ ∩ * (Xx)² (x = Rechenzeit eines Wx = ──────────── Prozesses) 2 * (1-δx) 2 probabil. Scheduling 1 1 FB - 2 52600309 Um die Gleichung für die Die Formel für die Wartezeit Wartezeit beim FB-Scheduling beim FB-Scheduling wird zu erhalten, verwendet man abgeleitet mit Hilfe zwei bekannte Gesetze. - der PK-Gleichung und Welche ? - dem Satz von Little. 2 probabil. Scheduling 1 1 FB - 3 52600310 Wie heißt die Formel für die Tx (x) = Wx + x + NeueJobs mit __ Verweilzeit Tx (x) beim NeueJobs = ∩ * Tx (x) * Xx ==> FB-Scheduling und wie Wx + x Tx (x) = ──────── erhält man sie ? 1 - δx 2 probabil. Scheduling 1 1 FB - 4 52600311 Welchen Eindruck gewinnen Diese Jobs müssen immer warten bis alle kürzeren Jobs sehr umfangreiche Jobs beim fertig sind. FB-Scheduling über das Deshalb entspricht das Systemverhalten für sie Systemverhalten ? einem LCFS-Verfahren. 2 probabil. Scheduling 1 1 FB - 5 52600312 Was ist die Idee beim Es wird versucht, das Reaktionsverhältnis C dadurch HRN-Scheduling-Verfahren ? W (x) konstant zu C = ─────── + 1 halten, daß (highest-response ratio next) x jeder Prozeß sein aktuelles C als dynamische Priorität erhält. 2 probabil. Scheduling 1 1 HRN 52600313 Worin besteht der Unterschied Beim deterministischen Scheduling sind, im Gegensatz zwischen probabilistischem zum probabilistischem Scheduling, die und deterministischem Ausführungszeiten der einzel- nen Prozesse schon im voraus Scheduling ? bekannt. 2 determin. Scheduling 1 1 Scheduling - 3 53000314 Ein Schedule S für Ein Schedule S ist eine - m Prozessoren und - eine vorgegebene Menge von Beschreibung der Arbeit, die Tasks mit gegebenen Abhängigkeiten jeder Prozessor zu jedem ist ... Bitte ergänzen ! Zeitpunkt zu verrichten hat. 2 determin. Scheduling 1 1 Schedule - 1 53000315 Welche Information Der Präzedenz-Graph beschreibt die Abhängigkeiten läßt sich aus dem der Prozesse untereinander. Ein Pfeil vom Prozeß Ti zum Präzedenz-Graphen Prozeß Tj bedeutet, daß Ti beendet sein muß, bevor Tj entnehmen ? beginnen darf. 2 determin. Scheduling 1 1 Präzedenz-Graph 53000316 Bei der Analyse determinis- Ein Gantt-Diagramm ist eine tischen Schedulings werden Zeitachse mit der Angabe der Prozessor / Prozeß-Zuordnung. Gantt-Diagramme Ein Gantt-Diagramm stellt verwendet. Was sind das ? einen Schedule anschaulich dar. 2 determin. Scheduling 1 1 Gantt-Diagramm 53000317 Welche Bedingungen muß ein - Präzedenz-Relationen - zu jeder Zeit steht jedem Schedule Prozeß höchstens ein Prozessor zur Verfügung erfüllen ? - die gesamte Rechenzeit für einen Prozeß wird immer auf einmal zugewiesen 2 determin. Scheduling 0 1 Schedule - 2 53000318 Wie ist die Länge t (S) Die Länge t (S) eines Scheduls definiert ? eines Scheduls S ist die Zeit, zu der der letzte Prozeß von S fertig wird. 2 determin. Scheduling 0 1 Schedule, Länge - 1 53000319 Wann wird ein Prozessor im Ein Prozessor wird als frei (idle) bezeichnet, Zusammenhang mit Scheduling wenn ihm in irgendeinem Teilintervall von [0, t (S)] als frei (idle) bezeichnet ? kein Prozeß zugewiesen ist. 2 determin. Scheduling 0 1 frei (idle) 53000320 Was versteht man unter Beim deterministischen Scheduling ist das Scheduling "Optimalem Scheduling". optimal, wenn die Länge des erzeugten Scheduls minimal ist. 2 optimales Scheduling 0 1 Optimales Scheduling - 1 53100321 Optimales Scheduling von Beim Scheduling von Doppel- prozessoren werden genau 2 Doppelprozessoren erhält man Prozessoren vorausgesetzt und man nimmt an, daß die durch zwei Einschränkungen. Ausführungszeiten für alle Prozesse gleich sind. Welche ? 2 optimales Scheduling 1 1 Doppelprozessoren - 1 53110322 Wie werden die Prozesse Ti 1) a (To ohne Nachfolger) = 1 beim Numerierungsalgorithmus 2) a (alle anderen ohne für das optimale Scheduling Nachfolger) = 2..k-1; von Doppelprozessoren durch- 3) a (T" | N (T") ≤ N (Ti) numeriert. für alle i) = k; k = k + 1; 4) IF k < n GOTO 3) 2 optimales Scheduling 1 1 Doppelprozessoren - 3 53110324 Wie lautet die Idee des Wenn ein Prozessor frei wird, Scheduling Algorithmusses A weise ihm den Prozeß mit der beim optimalen Scheduling kleinsten Nummer a von allen von Doppelprozessoren ? Prozessen deren sämtliche Vorgänger bereits ausgeführt sind zu. 2 optimales Scheduling 1 1 Algorithmus A 53110325 Aus dem Präzedenz-Graphen N (T) ist eine monoton ergibt sich die Menge aller fallende Folge, die aus den unmittelbaren Nachfolger Nummern a (Ti), von allen S (T) eines Prozesses T. Nachfolgern Ti von T, gebildet wird. Wie erhält man N (T) ? 2 optimales Scheduling 1 1 Doppelprozessoren - 2 53110323 Falls bei der Numerierung Unter den genannten der Prozesse (beim optimalen Scheduling) t (T) und t (T') Voraussetzungen gilt: die Anfangszeiten von T und T' sind, und T auf dem t (T) < t (T') ==> Prozessor P1 abläuft, gilt a (T) > a (T'). t (T) < t (T') ==> ... ? 2 optimales Scheduling 1 1 Nummerierung A - 1 53110326 Numerierung der Prozesse Falls beim optimalen beim optimalem Scheduling Scheduling möge ergeben, daß S (T') eine echte Teilmenge S (T') eine echte Teilmenge von S (T) ist, dann folgt: von S (T) ist. Was folgt daraus ? a (T) > a (T') 2 optimales Scheduling 1 1 Nummerierung A - 2 53110327 Geben Sie ein Beispiel dafür, Die Antwort ist zu daß der erzeugte Schedule beim optimalen Scheduling umfangreich für diese Karte. nicht mehr minimal sein muß, wenn die Ausführungszeiten Drücken Sie nach dem Piepston der Prozesse unterschiedlich sind ! die Taste "i". 2 optimales Scheduling 1 1 Optimales Scheduling - 2 53110328 Man kann eine Menge von Man kann eine Menge von Prozessen mit gleichen Aus- Prozessen mit gleichen Aus- führungszeiten auf m ≥ 2 Pro- führungszeiten auf m ≥ 2 Pro- zessoren optimal schedulen, zessoren optimal schedulen, wenn ihr Präzedenzgraph ... wenn ihr Präzedenzgraph eine Baumstruktur hat. Ergänzen Sie den Satz ! (Präzedenz-Baum) 2 optimales Scheduling 1 1 Präzedenz-Baum 53120329 Wie würde der Numerierungs- 1) L (T~) = 1 Algorithmus für optimales 2) L (direkter Vorgänger von Scheduling von Präzedenz- T~) = 2 Bäumen vorgehen, falls es nur 3) L (direkter Vorgänger von einen Terminalprozeß T~ ohne direktem Vorgänger von Nachfolger gäbe ? T~) = 3 4) usw. 2 optimales Scheduling 1 1 Nummerierung B 53120330 Wie lautet die Idee des Wenn ein Prozessor frei wird, ordne ihm den Prozeß T zu, optimalen Scheduling der von allen Prozessen, deren sämtliche Vorgänger Algorithmusses B für ausgeführt sind, die größte L (T)-Nummer aufweist. Präzedenz-Bäume ? 2 optimales Scheduling 1 1 Algorithmus B 53120331 Welchen Schedulingalgorithmus Der LPT-Algorithmus kann man verwenden, wenn (largest processing time) - die Zahl der Prozessoren ist ein heuristischer m beliebig, Scheduling Algorithmus, den - die Ausführungszeiten der man auch unter den genannten Tasks verschieden und Bedingungen verwenden kann. - die Tasks unabhängig sind ? 2 LPT Scheduling 1 1 heuristisches Scheduling 53200332 Wie lautet die Idee Wenn ein Prozessor frei wird, ordne ihm den Prozeß zu, der beim LPT Scheduling ? von allen noch nicht ausgeführten Prozessen die längste Ausführungszeit hat. 2 LPT Scheduling 1 1 LPT Scheduling - 1 53200333 Es läßt sich eine obere Die obere Schranke für Schranke angeben, für die m Prozessoren liegt bei: Länge des LPT Scheduls im Vergleich zur Länge des t (S_LPT) 4 1 optimalen Scheduls. ──────────── = ─── - ─────── t (S_Opti) 3 3 * m Wo liegt die Schranke ? 2 LPT Scheduling 1 1 LPT Scheduling - 2 53200334 Welche Funktion erfüllen Durch Prioritätslisten wird eine vollständige Ordnung der Prioritätslisten Prozesse nach einem bestimmten Prioritäts- beim Scheduling ? kriterium gewährleistet. 2 Prioritätslisten 1 1 Prioritätslisten - 1 53300335 Von welchen vier Parametern - Anzahl m der Prozessoren hängt die Länge des Scheduls - Ausführungszeiten der beim Scheduling nach Prozesse Prioritätslisten ab ? - Einschränkungen durch den Präzedenz-Graphen - Reihenfolge der Prozesse in den Prioritätslisten 2 Prioritätslisten 1 1 Schedule, Länge - 2 53300336 Was kann passieren, wenn man Es können Anomalien auf- treten. Beispielsweise kann die Bedingungen für das t (S) größer werden, wenn man mehr Prozessoren zu Scheduling mit Prioritäts- Verfügung stellt oder die Ausführungszeiten der listen scheinbar verbessert ? Prozesse verkürzt. 2 Prioritätslisten 1 1 Prioritätslisten - 2 53300337 Was versteht man unter Scheduling ist ein Verfahren, um dem Rechner die einzelnen in Ausführung befindlichen Scheduling ? Programme abwechselnd zuzu- teilen, so daß diese quasi- gleichzeitig verarbeitet werden. 2 Scheduling II 1 1 Scheduling - 1 50000999