Knowledge & Learning

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

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

Wrap

Text File | 1992-03-09 | 53.9 KB | 1,341 lines

YCPAA #!!# - Scheduling - @CEInhalt @CPDas Thema von BS___5 ist das Scheduling. Start mit ⌐Scheduling II@BS___5¬ AHBAA #!!# Scheduling II @HEEinführung @HBFalls mehrere Prozesse gleichzeitig auf ein bestimmtes ⌐Betriebsmittel@BS1¬ zugreifen möchten, muß man entscheiden, welchem dieser Prozesse das Betriebsmittel als nächstes zugeteilt wird. Man bezeichnet das Verfahren der Auswahl des zu bedienenden Prozesses als ⌐Scheduling@BS1¬ und das Programm, das diese Auswahl trifft, als ⌐Scheduler@BS1¬. Von besonderer Bedeutung ist die Verplanung der CPU (siehe ⌐Rechnerkern@BS1¬). Beim Scheduling unterscheidet man zwei prinzipiell verschiedene Vorgehensweisen: @HEa) deterministisches Scheduling @HBSind die Ausführungszeiten der einzelnen Prozesse schon vorher bekannt (deterministisch), kann man diese zeitlich so anordnen, daß sich ein gewünschtes Systemverhalten ergibt. In der Praxis sind die Voraussetzungen für deterministisches Scheduling aber meistens nicht gegeben. @HEb) probabilistisches Scheduling @HBSind nur Erwartungswerte und Wahrscheinlichkeits-Verteilungen für die Rechenzeiten bzw. die Ankunftszeiten der Prozesse bekannt, so muß man das Verhalten der einzelnen Scheduling-Algorithmen durch charakteristische Größen (z. B. ⌐Wartezeit@BS1¬, ⌐Verweilzeit@BS2¬) beschreiben. @HEZiele des Schedulings @HBDie Ziele des Schedulings, welches Systemverhalten erzielt werden soll bzw. welche charakteristischen Größen eines bestimmten Verhaltens optimiert werden sollen, sind je nach Typ des ⌐Betriebssystem@BS1¬s verschieden: - Batch-System : hoher ⌐Durchsatz@BS1¬ - Time-Sharing-System : kurze ⌐Antwortzeit@BS1¬en - Real-Time-System : Antworten innerhalb festgelegter garantierter Zeiten Je nach Ziel muß eine unterschiedliche Verplanung vorgenommen werden. @HB weiter mit ⌐probabil. Scheduling@BS___5¬ AHBAA #!!# probabil. Scheduling @HEgegebene Einschränkung @HBEs sind nur Erwartungswerte und Wahrscheinlichkeits-Verteilungen für die Bedienzeiten bzw. die Ankunftszeiten der Prozesse bekannt. Die verschiedenen Verfahren lassen sich unterscheiden: - nach dem Verfahren der Prioritätszuteilung an konkurrierende Prozesse - in statische / dynamische Prioritätsvergabe - in Verfahren mit / ohne Preemption (siehe ⌐Deadlock II@BS___4¬) Als Modell dient hier das einfache Warteschlangen-Modell mit ⌐Warteschlange@BS2¬ (Queue) und ⌐Bedieneinheit@BS2¬. Kann eine Anforderung an die Bedieneinheit nicht sofort bearbeitet werden, so wird sie in die Warteschlange eingereiht. siehe auch ⌐SET-Modell@BS1¬ @EH1. Verfahren: @HEFCFS (first come first served) @HBVerfahren ohne Preemption In diesem, auch als FIFO bezeichneten Verfahren, werden die einzelnen Prozesse streng in der Reihenfolge des Eintreffens ihrer Anforderungen bedient. @HEWie groß ist die mittlere Wartezeit der Aufträge ? @HBGegeben sei ein M/M/1-System: @HLWartezeit = Gesamtzeit im System - ⌐Bedienzeit@BS1¬ <==> 1 1 1 W = ─── * ─── - ─── <==> µ 1-δ µ 1 δ = ─── * ─── @HBsiehe ⌐Little@BS___2¬@HL µ 1-δ @HBInterpretation: Die ⌐Wartezeit@BS1¬ ist unabhängig von der (individuellen) ⌐Rechenzeit@BS2¬ der Prozesse. Das heißt im Mittel ist die Wartezeit für lange und kurze Jobs gleich lang. Die ⌐Auslastung@BS1¬ hat einen sehr starken Einfluß auf die Wartezeit. Um die Wartezeit zu verkürzen, kann der Benutzer beim FCFS eine @HPAntistrategie@HB anwenden, indem er mehrere kleinere Prozesse zu einem größeren zusammenfaßt. Diese Aussagen gelten auch für die Vefahren LCFS und RANDOM. Unterschiede gibt es aber in der ⌐Varianz@BS1¬ der Wartezeiten (FCFS: geringe Varianz, RANDOM: sehr starke Varianz). Festhalten sollte man auch, daß die mittlere Wartezeit kein geeignetes Kriterium für die Güte der Algorithmen ist, da bei gleichen Wartezeiten die Varianz ganz anders sein kann. @HEMittlere Verweilzeit im System (= Gesamtzeit im System) @HLMittlere Verweilzeit = Wartezeit + Bedienzeit <==> 1 δ 1 V = ─── * ─── + ─── <==> µ 1-δ µ 1 1 = ─── * ─── µ 1-δ @HEE [N] = mittlerer Anzahl Kunden im System @HL δ E [N] = ─── 1-δ @EH2. Verfahren: @HELCFS (last come first served) @HBVerfahren mit Preemption Bei diesem, auch als LIFO bezeichnetem Verfahren, behält der zuletzt ein- getroffene Prozeß die ⌐Bedieneinheit@BS2¬ (CPU) so lange, bis er entweder vollständig bearbeitet wurde oder durch einen neu ankommenden ⌐Prozeß@BS1¬ aus der Bedieneinheit verdrängt und an das Ende der ⌐Warteschlange@BS2¬ zur späteren Weiterbearbeitung eingereiht wird. @HA┌────────────────────────┐ │ │ \│/ @HE┌───────┴───────┐ @HBAnfang@HP┌┬┬┬┬┬┬┬┬┬┬┐@HBEnde @HE│ │ @HP│││@HBQueue@HP│││├@HA──────────────>@HE│ @HBBedieneinheit @HE├@HA────────> @HP└┴┴┴┴┴┴┴┴┴┴┘ @HE│ │ @HA─────────────────────────────>@HE└───────────────┘ @HBneuer Prozeß @HEWie groß ist die mittlere Wartezeit W ? @HL 1 δ W = ─── * ─── @HB(wie bei FCFS)@HL µ 1-δ @HBDie Wartezeiten bei FCFS, LCFS und Round Robin sind gleich. Richter sagt jedoch, daß die Varianz der Wartezeiten bei LCFS größer als bei Round Robin ist. @EH3. Verfahren: @HESJF (shortest job first) @HBVerfahren ohne Preemption Bei diesem Verfahren wird jeweils der Prozeß mit der kürzesten ⌐Rechenzeit@BS2¬ als nächster ausgewählt. Man muß also die Rechenzeiten der Prozesse schon im voraus wissen, um sie in die Queue einsortieren zu können. (Wieso gehört das Verfahren dann zu den probabilistischen ???) Kurze Prozesse sollen schnell bearbeitet werden, damit die Anzahl der Prozesse im System möglichst gering ist und somit die Antwortzeiten kurz sind. @HEWie groß ist die mittlere Wartezeit W ? @HL __ x ∩ * x² ⌠ W (x) = ──────────────── mit g (x) = ∩ * │ t * dB (t) @HB│@HL 2 (1 - g (x))² ⌡ @HB│ @HB│@HL t=0 @HB└Dichte der @HB└angenommene Bedienverteilung Rechenzeit des Prozesses Zum Vergleich die Mittlere Wartezeit bei FCFS mit M/M/1: @HL 1 δ W = ─── * ─── µ 1-δ @HEVergleich der SJF- und FCFS-Wartezeiten @HBInterpretation: @HAw (x) @HO* * * * @HBBei FCFS ist die Wartezeit @HP/│\ @HO* @HASJF @HBfür lange Prozesse genauso @HP│ @HO* @HBgroß wie für kurze. @HP│ @HO* @HP│ @HO* @HBBei SJF ist die Wartezeit @HP│ @HO* @HBfür lange Prozesse wesentlich @HP│ @HO* @HBgrößer als für kurze. @HP│ @HO* @HP│ @HO* @HP│ @HO* @HAFCFS @HP│@HO───*─────────────────────── @HP│@HO** @HP└─────────────────────────────> @HAx @EH4. Verfahren: @HERR (round robin) @HBVerfahren mit Preemption Bei diesem ⌐Zeitscheibenverfahren@BS2¬ werden die neu ankommenden Prozesse nach FCFS in die Queue eingereiht. Ist ein Prozeß an der Reihe, so wird ihm die Bedieneinheit für ein bestimmtes Quantum Q an ⌐Rechenzeit@BS2¬ (Zeitscheibe von 100-500ms) zugeteilt. Alle Zeitscheiben sind gleich groß. Ist ein Prozeß nach Ablauf einer Zeitscheibe fertig, so verläßt er das System. Andernfalls wird er wieder an den Anfang der Queue eingereiht. @HA┌──────────────────────────────────────┐ │ │ │ @HE┌───────┴───────┐ @HA└──>@HP┌┬┬┬┬┬┬┬┬┬┬┐ @HE│ │ @HP│││@HBQueue@HP│││├@HA──────────────>@HE│ @HBBedieneinheit @HE├@HA────────> @HA────────────>@HP└┴┴┴┴┴┴┴┴┴┴┘ @HE│ │ @HBneuer Prozeß @HE└───────────────┘ @HEHerleitung der Wahrscheinlichkeit gk, daß die Rechenzeit eines Prozesses zwischen to und t1 liegt, also k Zeitscheiben benötigt. @HB Bedienzeitverteilung: @HL -µt B (t) = P [x ≤ t] = 1 - e @HAB (t) @HP/│\ @HP│ @HA1 @HP┤ @HB┐@HO* * * * @HP│ @HO* @HB| ├ @HAgk = ? @HP│ @HB_@HO*@HB_ _ _ _ _ | ┘ @HP│ @HO* @HB| | @HP│ @HO* @HB| | @HP│ @HO* @HB| | @HP│@HO* @HB| | @HP└──────────┬────────────┬───────────> @HAto t1 @HEHerleitung von gk @HL -µ * (k-1) * Q to = (k-1) * Q ==> B (to) = 1 - e -µ * k * Q t1 = k * Q ==> B (t1) = 1 - e gk = P [to ≤ x ≤ t1] = P [x ≤ t1] - P [x < to] = ... k-1 -µQ = s * (1 - s) mit 0 < s = e < 1 @HERechnung @HL gk = P [to ≤ x ≤ t1] = P [x ≤ t1] - P [x < to] -µkQ -µ(k-1)Q = (1 - e ) - (1 - e ) -µ(k-1)Q -µkQ = e - e -µ(k-1)Q -µQ = e * (1 - e ) k-1 -µQ = s * (1 - s) mit 0 < s = e < 1 @HBgk ist geometrisch verteilt, dem diskreten Gegenstück zur Poisson-Verteilung. @HEGrenzfälle beim RR-Verfahren @HBa) @HPQ -> ∞ @HB In diesem Extremfall verhält sich das Verfahren wie FCFS ohne Preemption. @HBb) @HPQ -> 0 @HBIn diesem Extremfall erhält man das Processor-Sharing-Scheduling (PS-Scheduling). @HPPS-Scheduling@HB erhält man, wenn man während eines Zeitraumes die Bedieneinheit sehr oft zwischen Prozessen umschaltet, d. h. Q -> 0. Der Benutzer hat das Gefühl, ihm alleine stünde die Bedieneinheit zur Verfügung, weil "immer" jeder Prozeß rechnet. Er rechnet aber nur mit einem Bruchteil der Geschwindigkeit, die er ohne das Umschalten hätte. Man betrachtet oft den @HPOverhead@HB (die Zeit zum Umschalten) als vernachlässigbar, wenn der Overhead noch erheblich kürzer ist, als die Zeit, in der ein Prozeß die Bedieneinheit ohne Unterbrechung besitzt. @HEWie groß ist die mittlere Wartezeit bei RR ? @HBBeim Round Robin Verfahren hängt die ⌐Antwortzeit@BS1¬ T, also auch die ⌐Wartezeit@BS1¬ W, von der Länge der gewünschten ⌐Bedienzeit@BS1¬ x ab und ist gegeben durch @HL 1 δ 1 T (x) = x * ─── @HBnach Little:@HL T = ─── * ─── 1-δ 1-δ ∩ @HBT = Verweilzeit@HL 1 ∩ 1 = ─── * ─── * ─── @HB1 _@HL 1-δ µ ∩ @HB─── = x@HL @HBµ@HL 1 = ─── * x 1-δ @HL δ W (x) = x * ─── @HBW = Wartezeit@HL 1-δ @HBwegen@HL T (x) = W (x) + x <==> W (x) = T (x) - x @HB Eigenschaften des Round Robin Verfahrens: a) Die Diskriminierung eines Benutzers ist linear, das heißt, die Antwortzeit wächst linear mit der benötigten Rechenzeit. b) Die Bestrafung aller Prozesse, ob groß oder klein, ist konstant, das heißt die Wartezeit, die je nach Bedienzeit als "Strafe" aufer- legt wird, ist konstant. @HL W (x) δ@HB Bestrafungsfunktion: @HL ─────── = ─── ==> @HL x 1-δ@HB Faire Verplanung, der Benutzer kann keine Antistrategie entwickeln. @HEVergleich der Bestrafungsfunktionen @HAW (x) @HP/│\ @HM─ @HB: RR @HA───── @HP│ @HO* @HB: FB @HAx @HP│ @HK+ @HLo @HB: SRR @HP│ @HLo @HK+ @HB: FCFS @HP│ @HK+ @HP│ @HLo @HO* * @HP│ @HK+ @HO* * @HP│ @HK+@HLo @HO* * @HP│ @HK+@HLo@HO* * * * * @HAδ @HP│ @HO* @HK+ @HLo @HA─── @HP┤@HM───────@HO*@HM─────@HK+@HM──@HLo@HM───────────────────────────────────── @HA1-δ @HP│ @HO* @HK+ @HLo @HP│ @HO* @HK+ @HLo o o o o o o o o o o @HP│@HO* @HK+ + + + + + + @HA1 @HP└────────────────────────────────────────────────────────> @HAx = ─── @HAµ @EH5. Verfahren: @HESRR (selfish round robin) @HBVerfahren mit Preemption und mit dynamischer Vergabe von Prioritäten Bei diesem Verfahren wird die Queue durch eine Trennlinie in zwei Teile getrennt. (selfish = egoistisch) @HA┌────────────────────────┐ @HA\│/ │ @HBTrennlinie@HA<─@HM║@HA│ @HE┌────┴────┐ @HB∩ @HP┌┬┬┬┬┬┬┬┬┬┬┬@HM║@HP┬┬┬┬┬┬┬┬┬┬┬┐ @HE│ @HBBedien- @HE│ @HA───>@HP││ @HBlinks @HP│││@HM║@HP│ @HBrechts @HP││├@HA───────>@HE│ ├@HA──> @HP└┴┴┴┴┴┴┴┴┴┴┴@HM║@HP┴┴┴┴┴┴┴┴┴┴┴┘ @HE│ @HBeinheit @HE│ @HM║ @HE└─────────┘ @HO├───────────┼───────────────────────────────┤ @HBäußeres, inneres System @HBNeu ankommende Prozesse werden in den linken Teil der Queue aufgenommen und erhalten die Priorität 0. Die Priorität wächst dann mit der Zeit linear um den Faktor α ≥ 0. Im rechten Teil der Queue befinden sich Prozesse, die schon bedient wurden (sie haben schon Rechenzeit aufgenommen), aber noch nicht fertig sind und Prozesse aus dem linken Teil, wenn sie eine bestimmte Priorität erreicht haben. Diese neuen Prozesse im rechten Teil werden durch Verschieben der Trennlinie darin aufgenommen. Die Priorität in dem rechten Teil der Queue wächst linear um den Faktor ß. Es gilt dabei α ≥ ß ≥ 0. Alle Prozesse haben im rechten Teil der Queue die gleiche Priorität. Ein Prozeß wechselt vom linken Teil der Queue in den rechten, wenn er die Priorität der Prozesse im rechten Teil erreicht hat. @HEHerleitung der Übergangsrate ∩' in den rechten Teil der Queue @HAPriorität @HP/│\ @HO* @HP│ @HO*@HA: @HB┐ @HBα und ß sind @HP│ @HBWechsel vom @HO* *@HA: @HB│ @HBdie Winkel bzw. @HP│ @HBrechten in den @HO* * @HA: @HB├ y @HBSteigungen @HP│ @HBlinken Teil @HO* * @HA: @HB│ @HP│ @HBder Queue──┐ @HO* @HBß @HO* @HBα @HA: @HB│ @HP│ @HO*@HA...............@HO*@HA....:.@HB┘@HA.......... @HP│ @HO*@HA: @HO* @HA: @HP│ @HO* @HA: @HO* @HA: @HP│ @HBProzeß i@HO* @HA: @HBProzeß i+1@HO* @HA: @HP│ @HO* @HA: @HO* @HA: @HP│ @HO* @HBα @HA: @HO* @HBα @HA: @HP└──────@HO*@HP───────────────@HO*@HP─────────────────────────────────────> @HAt @HB├──────1/∩──────┤ ├────────1/∩'────────┤ @HEHerleitung der Übergangsrate ∩' @HL y ß = ────── = y * ∩' ==> y = ß * 1/∩' 1/∩' y α = ──────────── ==> y = α * (1/∩' - 1/∩) 1/∩' - 1/∩ ==> α * (1/∩' - 1/∩) = ß * 1/∩' @HBgesucht ∩'@HL 1/∩' * α - 1/∩ * α = 1/∩' * ß 1/∩' - 1/∩' * ß = 1/∩ * α 1/∩' * (α - ß) = 1/∩ * α @HB* ∩ * ∩'@HL @HL ∩ (α - ß) = ∩' * α α - ß ∩ ─────── = ∩' α @HBÜbergangsrate beim SRR-Verfahren: @AO ╔══════════════════╗ @HB @AO ║ ß ║ @HB @AO ║ ∩' = ∩ (1 - ───) ║ @HB @AO ║ α ║ @HB @AO ╚══════════════════╝ @HB Ergebnis: Die Übergangsrate ∩' von Prozessen aus dem linken Teil der Queue in den rechten Teil der Queue ist abhängig von den Parametern α und ß. Diese können vom Operator festgelegt werden. Er hat also einen direkten Einfluß auf das Verhalten des Systems. @HEGrenzfälle bei der Festlegung für α und ß @HB1) @HPα = ß > 0 : Systemverhalten FCFS@HB α = ß bedeutet, daß die Prioritäten im linken und rechten Teil der Queue um den gleichen Faktor wachsen. Findet ein Prozeß ein leeres System vor, so rutscht er direkt durch in die Bedieneinheit. Nach Ablauf einer Zeitscheibe verläßt er sie und seine Priorität wird erhöht, dann belegt er sofort wieder die Bedien- einheit. Kommt ein zweiter Prozeß, so erhöht sich dessen Priorität in gleichen Abständen und um den gleichen Faktor wie die des ersten Prozesses. Er kann die Priorität des ersten Prozesses deshalb nie erreichen. Also muß er solange in dem linken Teil der Queue warten, bis der erste Prozeß das System verläßt. Es kann sich immer nur ein Prozeß im inneren System aufhalten. Dieser wird komplett bedient und verläßt dann das System. Jetzt kann der nächste Prozeß ins innere System gelangen. ==> FCFS-Verfahren. 2) @HPα = ß = 0 : Systemverhalten RR@HB α = ß = 0 bedeutet, daß ohne Prioritäten gearbeitet wird. Neu an- kommende Prozesse kommen sofort ins innere System, das heißt es besteht kein linker Teil der Queue. Man erhält also das normale RR-Verfahren. @HAW (x) @HL─ @HB: FCFS @HP/│\ @HO* @HKo @HBα = ß > 0 @HP│ @HO* @HKo @HP│ @HO* @HKo @HO* @HB: RR @HP│ @HO* @HKo @HBα = ß = 0 @HP│ @HO* @HKo @HP│ @HO* @HKo @HKo @HB: SRR @HP│@HL──@HO*@HKo@HL───────────────────── @HBDie Gerade liegt irgendwo @HP│@HKo@HO* @HBzwischen den beiden anderen. @HP│@HO* @HP└──────────────────────────> @HAx @HBBemerkungen: - Im inneren System kann man jeden beliebigen Scheduling-Algorithmus anwenden. - Durch geschickte Wahl der Variablen α und ß sind die beiden Grenzfälle einzustellen: a) FCFS bei α = ß > 0 b) der Scheduling-Algorithmus des inneren Systems bei α = ß = 0 - Je nach Beobachtung des Systems kann der Operateur α und ß verändern, um die Wirkung eines anderen Scheduling-Algorithmusses einzustellen (Bevorzugung von kurzen bzw. langen Prozessen, Batch Betrieb (FCFS) oder Time-Sharing-Betrieb (RR)). @EH6. Verfahren: @HEFB (foreground background) @HBVerfahren mit Preemption und dynamischer Vergabe der Prioritäten Bei diesem Verfahren wird jeweils der Prozeß bedient, der bisher am wenigsten Rechenzeit aufgenommen hat. Man benutzt mehrere Warteschlangen. @HESystem 1 (ursprüngliches Modell)@HB Alle neu ankommenden Prozesse werden in die 1. Warteschlange aufgenommen und nach dem FCFS-Verfahren bedient. Nach der Aufnahme des ersten Bedienquantums (BQ) an Rechenzeit wird ein noch nicht vollständig abgearbeiteter Prozeß an den Anfang der 2. Warte- schlange eingereiht und nach dem RR-Verfahren weiter behandelt. Die Prozesse in der 2. Warteschlange werden nur dann bedient, wenn die 1. Warteschlange leer ist. @HB Trifft ein neuer Prozeß @HA┌────────────────────────────────┐ @HBwährend der Bearbeitung @HA│ @HBniedrige Priorität @HA│ @HBeines Prozesses aus der @HA│ @HP┌┬┬┬┬┬┬┬┬┬┬┬┬┐ @HE┌────┴────┐ @HB2. Warteschlange ein, so @HA└──>@HP││ @HB2. Queue @HP│├@HA─────────>@HE│ │ @HBwird der bearbeitete aus @HP└┴┴┴┴┴┴┴┴┴┴┴┴┘ @HE│ @HBBedien- @HE│ @HBder Bedieneinheit ver- @HE│ ├@HA─────> @HBdrängt, wieder an den @HP┌┬┬┬┬┬┬┬┬┬┬┬┬┐ @HE│ @HBeinheit @HE│ @HBAnfang der 2. Warte- @HA───>@HP││ @HB1. Queue @HP│├@HA─────────>@HE│ │ @HBschlange eingereiht und @HP└┴┴┴┴┴┴┴┴┴┴┴┴┘ @HE└─────────┘ @HBder neu angekommene hohe Priorität Prozeß bearbeitet. Man bezeichnet die Prozesse aus der 1. Warteschlange deshalb auch als Foreground Process (in der Hoffnung, daß sie höchstens 1 BQ benötigen) und die aus der 2. Warte- schlange als Background Process (weil sie mehr BQ benötigen und als Hintergrundoperation betrachtet werden). Ein neu ankommender Prozeß kann gegenüber den Prozessen aus der 2. Warteschlange maximal 1 BQ an Rechenzeit aufholen. @HESystem 2@HB Erweitert man das System 1 auf den Fall des PS-Verfahrens (BQ -> 0, siehe oben "Grenzfälle beim RR-Verfahren") und nimmt man eine größere Anzahl von Warteschlangen, so ist der Ablauf folgender: Trifft zu irgendeinem Zeitpunkt ein neuer Prozeß ein, so wird er so lange exklusiv und mit voller Prozessor-Kapazität 1 sec Bedienzeit (BZ) (───────────────────────) bedient, bis er genauso viel Rechenzeit 1 sec Echtzeit (EZ) aufgenommen hat, wie der mit der bisher geringsten aufgenommenen Rechen- zeit. Er wird anschließend in die selbe Warteschlange wie dieser einge- reiht. Die Prozesse aus dieser Warteschlange werden abwechselnd weiter bearbeitet, bis sie den Rückstand zum nächsten Prozeß aufgeholt haben und anschließend in diese Warteschlange eingereiht. Von dort rücken sie dann in die nächste Warteschlange auf, usw. @HA┌──────────────────────────────────────┐ │ @HP┌┬┬┬┬┬┬┬┬┬┬┬┬┐ @HA│ ├──>@HP││ @HBN. Queue @HP│├@HA──┐ @HBniedrigste @HA│ │ @HP└┴┴┴┴┴┴┴┴┴┴┴┴┘ @HA│ @HBPriorität @HA│ │ │ │ │ @HP┌┬┬┬┬┬┬┬┬┬┬┬┬┐ @HA│ │ ├──>@HP│ @HBN-1. Queue @HP├@HA──┤ │ │ @HP└┴┴┴┴┴┴┴┴┴┴┴┴┘ @HA│ @HE┌────┴────┐ @HA│ : ├────────────>@HE│ @HBBedien- @HE│ @HA│ : │ @HE│ ├@HA───> │ : │ ┌─────>@HE│ @HBeinheit @HE│ @HA│ @HP┌┬┬┬┬┬┬┬┬┬┬┬┬┐ @HA│ │ @HE└─────────┘ @HA└──>@HP││ @HB2. Queue @HP│├@HA──┘ │ @HP└┴┴┴┴┴┴┴┴┴┴┴┴┘ @HA│ │ @HP┌┬┬┬┬┬┬┬┬┬┬┬┬┐ @HA│ @HBhöchste @HA───>@HP││ @HB1. Queue @HP│├@HA─────────┘ @HBPriorität @HP└┴┴┴┴┴┴┴┴┴┴┴┴┘ @HBBeispiel: @HACPU Kapazität @HP/│\ @HA1 @HP┼──────────────────┬─────────┬─────────┬───────┬────────── @HP│ │ │ │ @HBP2 @HP│ @HBP1 @HP│ │ │ │ ├────────── @HA½ @HP┤ @HBP1 @HP│ @HBP2 @HP│ @HBP3 @HP├───────┤ @HBP2 @HP│ │ │ │ ├────────── @HP│ │ │ │ @HBP3 @HP│ @HBP3 @HP├──────────────────┼─────────┼─────────┼───────┼──────────> @HAt @HAto ta tb tc td @HB Prozeß P1 betritt leeres System und wird mit 1 sec BZ / sec EZ 8 BQ lang bedient, bis zum Zeitpunkt ta. Zum Zeitpunkt ta trifft Prozeß P2 ein, der P1 in die Queue mit Priorität 8 verdrängt (1 = höchste, N = niedrigste Priorität). P2 wird mit 1 sec BZ / sec EZ bis zum Zeitpunkt tb bedient. @HB Zum Zeitpunkt tb trifft Prozeß P3 ein, der P2 in die Queue mit der Priorität 5 verdrängt. Wenn bis zum Zeitpunkt ta + 2 (tb - ta) = tc kein neuer Prozeß ins System kommt, wird P3 für (tb - ta) Zeitein- heiten (= 5 BQ) nach seiner Ankunft exklusiv und mit voller Prozessor- Kapazität bedient. Zum Zeitpunkt tc = 2tb - ta haben P2 und P3 die gleiche Anzahl BQ's auf- genommen und werden jetzt abwechselnd bzw. gleichzeitig mit halber Prozessor-Kapazität 1 sec BZ / 2 sec EZ weiterbearbeitet. Trifft zu irgendeinem späteren Zeitpunkt als tc ein weiterer Prozeß ein, so wird dieser wieder solange exklusiv und mit voller Prozessor- Kapazität bedient, bis er den Rückstand zu P2 und P3 aufgeholt hat. Sie werden dann gemeinsam mit 1/3 Prozessorkapazität solange weiter- bearbeitet, bis sie den Rückstand zu P1 aufgeholt haben. Dann werden alle vier gleichzeitig weiterbearbeitet. siehe auch ⌐SET-Modell@BS1¬ @HEBerechnung der mittleren Antwortzeit bei FB @HB Bei der Berechnung der mittleren Antwortzeit geht man von folgenden Über- legungen aus: Wenn ein markierter "Job" (= Prozeß, dient der Identifizierung), der x sec Bedienzeit (BZ) benötigt, das System betritt, findet er andere Jobs im System vor. Von den anderen Jobs haben einige weniger und einige mehr als x sec BZ bereits aufgenommen. Es ist offensichtlich, daß alle Jobs, mit einer bereits aufgenommenen BZ größer oder gleich x sec, den markierten Job nicht stören. Vom Standpunkt des markierten Jobs aus könnte jeder Job, der mehr als x sec BZ benötigt, das System bereits verlassen, wenn er x sec oder mehr BZ aufgenommen hat. Jedem Job mit einer bisher aufgenommenen BZ kleiner als x sec wird er- laubt, bis zu x sec aufzunehmen, aber nicht zu überschreiten, bevor der markierte Job seine x sec BZ aufgenommen hat. @HBSo kommt man zu der Verteilungsfunktion Bx (t): @HL ┌ │ B (t), für t < x Bx (t) = ┤ │ 1, für t ≥ x └ @HB Die Wahrscheinlichkeit, daß die mittlere BZ eines Jobs kleiner oder gleich einer festgelegten Zeit t ist, ist B (t), wenn t kleiner als die benötigte BZ x des "markierten" Jobs ist. Die Wahrscheinlichkeit für das Ereignis ist sicher, das heißt gleich 1, wenn t größer oder gleich der benötigten BZ x des markierten Jobs ist. (???) @HEVerteilungsfunktion Bx (t) @HAB (t) @HP/│\ @HP│ @HP┤@HA·······························@HO* * * * * * * * * * * @HBBx (t) @HP│ @HO* @HP│ @HO* @HP│ @HO* @HA: @HP│ @HO* @HA: @HP│ @HO* @HA: @HP│ @HO* @HA: @HP│ @HO* @HA: @HP│ @HO* @HA: @HP│@HO* @HA: @HP└───────────────────────────────┬────────────────────> @HAt @HAx @HBDer @HPMittelwert für die Bedienzeit@HB in Abhängigkeit von x beträgt: @HL x __ ⌠ Xx = │ t dB (t) + x * (1 - B (x)) ⌡ 0 @HB Die @HPAuslastung@HB in Abhängigkeit von x des markierten Jobs beträgt: @HL __ δx = ∩ * Xx @HB Die @HPPK-Gleichung@HB lautet dann: (siehe ⌐M/G/1-System@BS___2¬) @HL _____ ∩² * (Xx)² E [N] = δx + ──────────── = E [N (BE)] + E [N (Q)] 2 (1-δx) @HBMit dem Satz von ⌐Little@BS___2¬ (E [N] = ∩ * E [T]) erhält man für die @HPWartezeit@HB:@HL Ex [Na] Ex [Ta] = ───────── @HBund@HL Ex [T] = Wx ∩ _____ @HBInterpretation von Wx:@HL ∩² * (Xx)² Wx = (────────────) / ∩ @HBWx ist, vom markierten Job aus@HL 2 (1-δx) @HBbetrachtet, die Zeit, während der@HL @HBdas System noch Arbeit verrichten@HL _____ @HBmuß, ehe er selbst dran kommt.@HL ∩ * (Xx)² = (───────────) 2 (1-δx) @HBFür die @HPVerweilzeit Tx (x)@HB ergibt sich: Neue Jobs, die ankommen, während der └───────┬─────────┘ markierte Job im System ist.@HL __ @HBDer markierte Job kommt erst@HL Tx (x) = Wx + x + ∩ * Tx (x) * Xx @HBwieder dran, wenn alle neuen@HL __ @HBsoviel Zeit aufgenommen@HL <==> Wx + x = Tx (x) - ∩ * Tx (x) * Xx @HBnommen haben, wie er selbst.@HL __ <==> = Tx (x) * (1 - ∩ * Xx) <==> = Tx (x) * (1 - δx) Wx + x <==> Tx (x) = ──────── 1 - δx @HB Bemerkungen: - Ein Job mit verschwindend geringer benötigter Bedienzeit hat eine Antwortzeit nahe 1. - Ein langer Job muß mit seiner Fertigstellung so lange warten, bis alle während seiner Bedienung eingetroffenen Jobs die gleiche BZ aufgenommen haben, wie er selbst. Das heißt die Antwortzeitrate entspricht dem LCFS-Verfahren (aber ohne die unerwünschte große Varianz). @EH6. Weitere probabilistische Algorithmen @HB - @HPHRN@HB (highest response ratio next) Verfahren ohne Preemption und dynamischer Vergabe der Prioritäten Idee: Es wird versucht, das Reaktionsverhältnis @HL W (x) + x W (x) C = ─────────── = ─────── + 1 x x @HB dadurch konstant zu halten, daß jedem Prozeß als Priorität dieses Verhältnis (mit W (x) = aktuelle Wartezeit) zugeordnet wird. Dadurch haben kurze Prozesse eine hohe Priorität, aber lange Prozesse werden nicht so sehr verzögert wie beim SJF-Verfahren. - @HPSET@HB (shortest elapsed time) kürzeste aufgenommene Bedienzeit - @HPSRT@HB (shortest remaning time) kürzeste noch benötigte Rechenzeit - @HPSHST@HB (shortest attained service first) kürzeste erreichte Bedienzeit zuerst (???) weiter mit ⌐determin. Scheduling@BS___5¬ AHBAA #!!# determin. Scheduling Beim deterministischen Scheduling sind, im Gegensatz zum probabilistischen Scheduling, die Ausführungszeiten der einzelnen Prozesse schon im voraus bekannt (deterministisch). @HEDefinitionen @HPSchedule@HB Ein Schedule S für - m Prozessoren und - eine vorgegebene Menge an Tasks (Prozessen) mit gegebenen Abhängigkeiten ist eine Beschreibung der Arbeit, die jeder Prozessor zu jedem Zeitpunkt zu verrichten hat. @HPPräzedenz-Graph@HB Der Präzedenz-Graph beschreibt die Abhängigkeiten der Prozesse unter- einander. Ein Pfeil vom Prozeß Ti zum Prozeß Tj bedeutet, daß Ti beendet sein muß, bevor Tj beginnen darf. @HPGantt-Diagramm@HB Ein Gantt-Diagramm ist eine Zeitachse mit der Angabe der Prozessor/Prozeß- Zuordnungen, die Schedules darstellen. Ein @HPSchedule@HB muß die folgenden Bedingungen erfüllen: - Berücksichtigung der Abhängigkeiten der Prozesse voneinander (Präzedenz-Relationen). - Zu jeder Zeit steht einem Prozeß höchstens ein Prozessor zur Verfügung. - Einem fordernden Prozeß wird immer die gesamte geforderte Rechenzeit auf einmal zugewiesen. @HBGesucht wird immer die Länge des Scheduls, sei es die optimale oder die schlechteste. @HPLänge eines Scheduls@HB Die Länge t (S) eines Scheduls S ist die Zeit, zu der der letzte Prozeß von S fertig wird. @HPFreiheit von Prozessoren@HB Ein Prozessor wird als frei (idle) bezeichnet, wenn ihm in irgendeinem Teilintervall von [0, t (S)] kein Prozeß zugewiesen ist. Bemerkung: Ein Schedule kann eventuell kürzer werden, wenn ein Prozessor zeitweise frei ist. @HEAllgemeines Beispiel zur Einführung: @HBPräzedenz-Graph: @HO█ @HLT1,1 @HO█ @HLT2,2 @HP│ │ @HB│ └──geforderte Rechenzeiteinheiten @HP└────┬────┘ @HB└────Prozeß-Nummer @HP\│/ @HO█ @HLT3,2 @HO█ @HLT4,1 @HP│ ┌┴┐ @HP└────┬───┘ └───┐ \│/ \│/ @HO█ @HLT5,2 @HO█ @HLT6,3 @HBGrantt-Diagramm: @HAt: 0 1 2 3 4 5 6 7 8 @HP┌────┬────┬─────────┬─────────┬────┬────┬──── @HAProzessor 1 @HP│ @HLT1@HP │ │ @HLT3@HP │ @HLT5@HP │ │ │ @HAS: @HP├────┴────┼────┬────┴─────────┼────┼────┼──── @HAProzessor 2 @HP│ @HLT2@HP │ @HLT4@HP │ @HLT6@HP │ │ │ @HBt (S) = 6 @HP└─────────┴────┴──────────────┴────┴────┴──── @HB weiter mit ⌐optimales Scheduling@BS___5¬ siehe auch ⌐Scheduling@BS1¬ ⌐Scheduler@BS1¬ ⌐Scheduling II@BS___5¬ ⌐probabil. Scheduling@BS___5¬ AHBAA #!!# optimales Scheduling @HPOptimales Scheduling@HB liegt vor, wenn die Länge des Scheduls minimal ist. siehe auch ⌐determin. Scheduling@BS___5¬ Minimale Schedules kann man im Prinzip durch Vergleichen aller möglichen Schedules finden. Dieses Verfahren ist jedoch viel zu aufwendig, da die Anzahl der möglichen Schedules exponentiell mit der Anzahl der Prozesse wächst. Man kann im Augenblick nur für einige spezielle Fälle einen optimalen Scheduling-Algorithmus angeben. @EH Optimales Scheduling von Doppelprozessoren (m=2) @HB Für diesen Spezialfall sind die Voraussetzungen, daß - die Anzahl der Proessoren m = 2 ist und - die Ausführungszeiten (Rechenzeiten) für alle Prozesse gleich sind. Idee: Durch eine geeignete Durchnumerierung der Prozesse erhält man eine lineare Anordnung gemäß ihrer Abhängigkeiten. @HBDefinition: Für zwei streng monoton fallende Folgen natürlicher Zahlen @HP N = (n1, ..., nt) @HBund@HP N' = (n'1, ..., n't')@HB, das heißt@HP für alle i mit ni ε N @HBund@HP für alle j mit nj ε N' @HBund@HP für alle j < t' mit n'j > n'j+1 @HBgilt:@HP N < N', @HBwenn entweder a) @HPfür alle i : ni < n'i AND ??? @HBoder b) @HPt < t' AND für alle j ≤ t : nj = n'j @HBBeispiele: @HAN = (7, 5, 3, 2) N' = (7, 5, 4, 1) ==> N < N' @HBBedingung a) erfüllt @HAN = (4, 3, 1) N' = (5, 1) ==> N < N' @HBBedingung a) erfüllt @HAN = (7, 2) N' = (7, 2, 1) ==> N < N' @HBBedingung b) erfüllt @HBHilfe: Die Zahlen als Kommazahlen lesen: @HA 0,7532 < 0,7541 0,431 < 0,51 0,72 < 0,721 @HENumerierungsalgorithmus @HB @HPgegeben:@HB Präzedenz-Graph G, Menge aller unmittelbaren Nachfolger von Prozeß T, S (T) @HPZiel@HB Jedem der n Prozesse soll eine natürliche Zahl a (T) ε {1, ..., n} zugeordnet werden. @HPDie einzelnen Schritte: @HB 1) Wähle einen beliebigen Prozeß To, der keinen Nachfolger hat, das heißt für To gilt: S (To) = {}, und setze a (To) = 1. 2) Numeriere alle anderen Prozesse ohne Nachfolger fortlaufend, beginnend mit der Zahl 2. 3) Seien alle Zahlen j < k für k ≤ n vergeben. Für jeden Prozeß T, @XE@HPdessen unmittelbare Nachfolger alle schon eine Zahl zugeordnet bekommen haben, bezeichnet N (T) eine monoton fallende Folge von ganzen Zahlen,@XA@HB die aus der Menge {a (T') | T' ε S (T)} gebildet wird. (Monotonie erhält man durch Umordnen der Menge). Für wenigstens einen Prozeß T", für den das hervorgehobene zutrifft, muß gelten N (T") ≤ N (T) für alle Prozesse T, für die das hervorge- hobene gilt. Wähle einen dieser Prozesse T" und setze a (T") = k. 4) Wiederhole Schritt 3 so lange, bis allen Prozessen eine Nummer zugeordnet ist. @HEAlgorithmus A (Scheduling Algorithmus) @HB Wenn ein Prozessor frei wird, weise ihm den Prozeß zu, dessen sämliche Vorgänger ausgeführt sind und der unter allen noch nicht ausgeführten Prozessen die höchste Nummer a hat. @HEBeispiel @HB In dem folgenden Beispiel ist die Anzahl der Prozessoren m = 2 und alle Prozesse haben die gleiche Rechenzeit. Die Pfeile der Kanten in dem Präzedenzgraph wurden "aus drucktechnischen Gründen" weggelassen. Die gerichteten Kanten verlaufen aber in jedem Fall von oben nach unten. @HEPräzedenzgraph @HL20 @HO█ @HL21 @HO█ @HL22 @HO█ @HBNumerierung: @HP└─────────┼─────────┘ @HB1. Schritt: 1 @HL19 @HO█ @HB2. Schritt: 2, 3, ..., 6 @HP│ @HB3. Schritt: 7, 8, ..., 22 @HL18 @HO█ @HP┌─────────┴─────────┐ @HO█ @HL17 @HO█ @HL16 @HP├─────────┐ │ @HO█ @HL14 @HO█ @HL13 @HP└─────────@HO█ @HL15 @HP┌────┴───┐┌────┘ ┌───────┬─────────┴─────────┐ @HL1 @HO█ @HL10@HP└@HO█@HP──────┘ @HL11 @HO█@HP @HL12 @HO█ @HP└──────┬───────┴─────────┬─────────┘ @HL7 @HO█ @HL9 @HO█ @HP│ ┌─────────┼──────────────┐ @HL2 @HO█@HP───────┘ @HL8 @HO█ @HL3 @HO█ @HP┌─────────┴─────────┐ @HL4 @HO█ @HL5 @HO█ @HL6 @HO█ @HESchedule S @HAt: 0 1 2 3 4 5 6 7 8 9 10 11 12 @HP┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬───@HA P1 @HP│ @HL22 @HP│ @HL20 @HP│ @HL19 @HP│ @HL18 @HP│ @HL17 @HP│ @HL15 @HP│ @HL12 @HP│ @HL10 @HP│ @HL9 @HP│ @HL8 @HP│ @HL5 @HP│ @HL2 @HP│ frei . @HAS: @HP├────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┴───@HA P2 @HP│ @HL21 @HP│ @HL14 @HP│ @HL6 @HP│ @HL1 @HP│ @HL16 @HP│ @HL13 @HP│ @HL11 @HP│frei│ @HL7 @HP│ @HL3 @HP│ @HL4 @HP│ frei @HP└────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴──────── @HBt (S) = 12 Eigenschaften der Numerierung: - Falls im Präzedenz-Graph T auf einer höheren Ebene liegt als T', dann ist a (T) > a (T'). (tiefste Ebene = Knoten ohne Nachfolger, höhere Ebene = Knoten mit Nachfolger) @HB - Falls S (T') eine echte Teilmenge von S (T) ist, dann ist a (T) > a (T'). - Falls t (T) und t (T') die Anfangszeiten von T und T' sind, und falls T auf dem Prozessor P1 ausgeführt wird, gilt: t (T) < t (T') ==> a (T) > a (T'). - P1 ist während des gesamten Schedules nie frei. Bemerkung: Bei Abweichungen von den genannten Voraussetzungen braucht der Schedule nicht mehr optimal zu sein, wie die Beispiele a) und b) zeigen. Hinweis: Die Numerierung der Prozesse erfolgt von jetzt ab immer in genau der umgekehrten Reihenfolge, wie im Numerierungsalgorithmus von oben. Dadurch ändert sich aber am Prinzip gar nichts. @HBBeispiel a) verschiedene Ausführungszeiten anstelle gleicher @HO█ @HLT1,1 @HO█ @HLT2,1 @HO█ @HLT 3,2 @HP└────┬────┴────┬────┘ @HO█ @HLT4,1 @HO█ @HLT5,1 @HAt: 0 1 2 3 4 @HP┌────┬─────────┬────┬──── @HAP1 @HP│ @HLT1 @HP│ @HLT3 @HP│ @HLT5 @HP│ frei @HBA-Schedule @HAS: @HP├────┼────┬────┴────┴──── @HAP2 @HP│ @HLT2 @HP│ @HLT4 @HP│ frei @HBt (S) = 4 @HP└────┴────┴────────────── @HAt: 0 1 2 3 @HP┌─────────┬────┬───────── @HAP1 @HP│ @HLT3 @HP│ @HLT4 @HP│ frei @HBOptimales-Schedule @HAS: @HP├────┬────┼────┼───────── @HAP2 @HP│ @HLT1 @HP│ @HLT2 @HP│ @HLT5 @HP│ frei @HBt (S) = 3 @HP└────┴────┴────┴───────── @HBBeispiel b) 3 Prozessoren anstatt 2 @HO█ @HLT1 @HO█ @HLT2 @HO█ @HLT3 @HO█ @HLT5 @HP└─────────┼─────────┘ ┌─────┬─────┬──┴──┬─────┬─────┐ @HO█ @HLT4 @HO█ @HLT7 @HO█ @HLT8 @HO█ @HLT9 @HO█ @HLT10 @HO█ @HLT11 @HO█ @HLT12 @HP│ @HO█ @HLT6 @HBA-Schedule: @HAt: 0 1 2 3 4 5 @HP┌────┬────┬────┬────┬────┬──── @HAP1 @HP│ @HLT1 @HP│ @HLT4 @HP│ @HLT6 @HP│ @HLT9 @HP│ @HLT12@HP│ frei @HP├────┼────┼────┼────┼────┴──── @HAS: P2 @HP│ @HLT2 @HP│ @HLT5 @HP│ @HLT7 @HP│ @HLT10@HP│ frei @HP├────┼────┼────┼────┼───────── @HAP3 @HP│ @HLT3 @HP│frei│ @HLT8 @HP│ @HLT11@HP│ frei @HP└────┴────┴────┴────┴───────── @HBt (S) = 5 @HB Optimales-Schedule: @HAt: 0 1 2 3 4 @HP┌────┬────┬────┬────┬───────── @HAP1 @HP│ @HLT1 @HP│ @HLT3 @HP│ @HLT4 @HP│ @HLT6 @HP│ frei @HP├────┼────┼────┼────┼───────── @HAS: P2 @HP│ @HLT2 @HP│ @HLT7 @HP│ @HLT9 @HP│ @HLT11@HP│ frei @HP├────┼────┼────┼────┼───────── @HAP3 @HP│ @HLT3 @HP│ @HLT8 @HP│ @HLT10@HP│ @HLT12@HP│ frei @HP└────┴────┴────┴────┴───────── @HBt (S) = 4 @EH Optimales Scheduling von Präzedenz-Bäumen @HB Man kann eine Menge von Prozessen mit gleichen Ausführungszeiten auf m ≥ 2 Prozessoren optimal schedulen, wenn ihr Präzedenz-Graph eine Baumstruktur hat (@HPPräzedenz-Baum@HB). @HENumerierungsalgorithmus @HB Ordne jedem Prozeß T eine Nummer L (T), zu. L (T) entspricht der Ebene, auf der sich T befindet. L (T) ist die Länge, das heißt die Anzahl der Teilstrecken - 1, des längsten Weges im Präzedenz-Baum von dem Prozeß T zum Terminalprozeß T~. Ein Prozeß T~ ohne Nachfolger heißt @HPTerminalprozeß@HB. Für ihn gilt: L(T~) = 1. Ein Prozeß ohne Vorgänger heißt @HPInitialprozeß@HB. @HEAlgorithmus B (Scheduling Algorithmus) @HB Wenn ein Prozessor frei wird, weise ihm den Prozeß zu, dessen sämliche Vorgänger ausgeführt sind und der unter allen noch nicht ausgeführten Prozessen die höchste Ebene hat. (größte L (T)-Nummer) @HEBeispiel @HB In dem folgenden Beispiel ist die Anzahl der Prozessoren m = 3 und alle Prozesse haben die gleiche Rechenzeit. @HEPräzedenzgraph @HC╔══╗ @HBkönnen gleichzeitig @HC╔═══════════════════════╗ @HC╚══╝ @HBausgeführt werden @HC║ @HO█ @HLT1 @HK5 @HO█ @HLT2 @HK5 @HC║ @HAEbene 5 @HC║ @HP└────┬────┘ @HC║ @HC╔═════════════════════════════╩══════@HP│@HC═══════╗ ║ @HC║ @HO█ @HLT3 @HK4 @HC║ @HO█ @HLT4 @HK4 @HC║ @HAEbene 4 @HC║ @HP└────┬────┘ @HC║ @HC║ ╔══════════════════════@HP│@HC══╩═══╦════╝ @HC║ @HO█ @HLT5 @HK3 @HO█ @HLT6 @HK3 @HC║ @HO█ @HLT7 @HK3 @HO█ @HLT8 @HK3 @HO█ @HLT9 @HK3 @HC║ @HAEbene 3 @HC║ @HP└─────────┼─────────┘ @HP└────┬────┘ @HC║ @HC╚═════════╦═@HP│@HC══════╩═════════════════@HP│@HC@HC═══════╦═══╝ @HC║ @HO█ @HLT10 @HK2 @HO█ @HLT11 @HK2 @HC║ @HAEbene 2 @HC║ @HP└────────────┬───────────┘ @HC║ @HC╚════════════╦═@HP│@HC══════╦════════════╝ @HC║ @HO█ @HLT12 @HK1@HC║ @HAEbene 1 @HKx @HB: L (T) @HC╚════════╝ @HB B-Schedule @HAt: 0 1 2 3 4 5 @HP┌────┬────┬────┬────┬────┬──── @HAP1 @HP│ @HLT1 @HP│ @HLT3 @HP│ @HLT7 @HP│ @HLT10@HP│ @HLT12@HP│ frei @HP├────┼────┼────┼────┼────┴──── @HAS: P2 @HP│ @HLT2 @HP│ @HLT5 @HP│ @HLT8 @HP│ @HLT11@HP│ frei @HP├────┼────┼────┼────┴───────── @HAP3 @HP│ @HLT4 @HP│ @HLT6 @HP│ @HLT9 @HP│ frei @HP└────┴────┴────┴────────────── @HBt (S) = 5 weiter mit ⌐LPT Scheduling@BS___5¬ AHBAA #!!# LPT Scheduling @HEScheduling unabhängiger Tasks @HB Für den Fall, daß die Anzahl der verfügbaren Prozessoren beliebig und die Ausführungszeiten der Prozesse verschieden und sie völlig unabhängig von- einander sind, läßt sich (nach heutigem Wissensstand) kein optimaler Scheduling-Algorithmus mit akzeptablem Zeitverhalten angeben. Wegen der Bedeutung des Problems "Scheduling unabhängiger Tasks" sei ein Algorithmus angegeben, der vielleicht die einfachste und eindeutigste Heuristik für Scheduling unabhängiger Prozesse ist, der @HPLPT Algorithmus@HB (largest processing time). @HELPT Scheduling Algorithmus @HB Wenn ein Prozessor frei ist, ordne ihm den Prozeß zu, der von allen noch nicht ausgeführten Prozessen die längste Ausführungszeit hat. Da der LPT Algorithmus im allgemeinen nicht optimal ist, versucht man die Frage zu beantworten, wie gut der LPT Schedule im Vergleich zum optimalen Schedule ist. Als obere Schranke hat man herausgefunden: @HP t (S_LPT) 4 1 ──────────── ≤ ─── - ─────── @HBm = Anzahl der Prozessoren@HP t (S_Opti) 3 3 * m ≤ 1 für m = 1 ≤ 1,17 für m = 2 ≤ 1,22 für m = 3 : : @HBBeispiel: @HLT1=16 T2=13 T3=12 T4=8 T5=6 T6=5 T7=5 T8=2 @HAt: 0 4 8 12 16 20 24 @HP┌───────────────────┬────┬───────── @HAP1 @HP│ @HLT1 @HP│ @HLT6 @HP│ frei @HP├───────────────┬───┴───┬┴────┬──── @HBS_LPT @HAP2 @HP│ @HLT2 @HP│ @HLT5 @HP│ @HLT7 @HP│ frei @HP├──────────────┬┴───────┴┬──┬─┴──── @HAP3 @HP│ @HLT3 @HP│ @HLT4 @HP│@HLT8@HP│ frei @HBt (S_LPT) = 24 @HP└──────────────┴─────────┴──┴────── @HAt: 0 4 8 12 16 20 23 @HP┌───────────────────┬────┬───────── @HAP1 @HP│ @HLT1 @HP│ @HLT6 @HP│ frei @HP├───────────────┬───┴────┴┬──┬───── @HBS_Opti @HAP2 @HP│ @HLT2 @HP│ @HLT4 @HP│@HLT8@HP│ frei @HP├──────────────┬┴──────┬──┴──┼───── @HAP3 @HP│ @HLT3 @HP│ @HLT5 @HP│ @HLT7 @HP│ frei @HBt (S_Opti) = 23 @HP└──────────────┴───────┴─────┴───── @HBAbweichung vom optimalen Schedule @HA t (S_LPT) 24 ──────────── = ──── = 1,04 @HBalso: 4 % Abweichung vom@HA t (S_Opti) 23 @HBoptimalen Scheduling _ Mittlere Verweilzeit T aus der Benutzersicht:@HA _ 1 T_LPT = ─── (16 + (16 + 5) + 13 + (13 + 6) + (13 + 6 + 5) 8 + 12 + (12 + 8) + (12 + 8 + 2)) = 18,375 _ _ T_Opti = 18,375 = T_LPT @HBWürde man an Stelle von LPT den @HPSPT Algorithmus@HB (shortest processing time) nehmen, so käme man zu folgenden Ergebnissen: @HA t (S_SPT) = 29 _ T_SPT = 12,5 @HB weiter mit ⌐Prioritätslisten@BS___5¬ AHBAA #!!# Prioritätslisten @HEScheduling nach Prioritätslisten @HB In dem Fall, daß die Ausführungszeiten der einzelnen Prozesse im voraus bekannt sind, muß der Scheduler Prozesse allein nach den Informationen des Präzedenz-Graphen auswählen. Da diese Informationen nur eine teilweise Ordnung in der Liste der Prozesse festlegen, müssen sie noch nach einem externen Prioritätskriterium geordnet werden. Wenn ein Prozessor frei wird, so wird ihm der Prozeß aus der Liste zuge- ordnet, dessen sämliche Vorgänger ausgeführt sind und der von allen noch nicht ausgeführten Prozessen der nächste in der Liste ist. Auch die Scheduling-Algorithmen, die bis jetzt behandelt wurden (siehe ⌐optimales Scheduling@BS___5¬), kann man als Scheduling nach Prioritätslisten ansehen. Beim Algorithmus A zum Beispiel ist die Prioritätsliste, die Liste der Nummern der Prozesse. Beim ⌐LPT Scheduling@BS___5¬ Algorithmus erhält man die Ordnung der Prioritätenliste aus der Länge der Ausführungszeiten. @HBDie Länge des Scheduls hängt ab von: - der Anzahl m der Prozessoren, - den Ausführungszeiten der Prozesse, - den Einschränkungen durch den Präzedenz-Graphen und - der Reihenfolge der Prozesse in den Prioritätslisten. Beim Scheduling nach Prioritätslisten interessiert man sich besonders für die auftretenden Anomalien. So führt die Aufhebung oder Abschwächung der oben genannten Einflüsse nicht unbedingt zu einer Verkürzung, sondern kann unter Umständen sogar eine Verlängerung des erzeugten Scheduls bewirken. @HBBeispiel: @HO█ @HLT1,3 @HO█ @HLT2,2 @HO█ @HLT3,2 @HO█ @HLT4,2 @HP│ ┌─────────┬────┴────┬─────────┐ @HO█ @HLT9,9 @HO█ @HLT5,4 @HO█ @HLT6,4 @HO█ @HLT7,4 @HO█ @HLT8,4 @HBPrioritätsliste: @HAL = {T1, T2, T3, T4, T5, T6, T7, T8, T9} @HBm = 3 @HAt: 0 2 4 6 8 10 12 @HP┌────────┬──────────────────────────┬───── @HAP1 @HP│ @HLT1 @HP│ @HLT9 @HP│ frei @HP├─────┬──┴──┬───────────┬───────────┼───── @HAS: P2 @HP│ @HLT2 @HP│ @HLT4 @HP│ @HLT5 @HP│ @HLT7 @HP│ frei @HP├─────┼─────┼───────────┼───────────┼───── @HAP3 @HP│ @HLT3 @HP│ frei│ @HLT6 @HP│ @HLT8 @HP│ frei @HBt (S) = 12 @HP└─────┴─────┴───────────┴───────────┴───── @HE"Verbesserungen" @HB a) Erhöhung der Prozessorzahl um einen Prozessor @HAt: 0 2 4 6 8 10 12 14 15 @HP┌────────┬───────────┬────────────────────────── @HAP1 @HP│ @HLT1 @HP│ @HLT8 @HP│ frei @HP├─────┬──┴────────┬──┴───────────────────────┬── @HAP2 @HP│ @HLT2 @HP│ @HLT5 @HP│ @HLT9 @HP│ @HAS: @HP├─────┼───────────┼──────────────────────────┴── @HAP3 @HP│ @HLT3 @HP│ @HLT6 @HP│ frei @HP├─────┼───────────┼───────────────────────────── @HAP4 @HP│ @HLT4 @HP│ @HLT7 @HP│ frei @HP└─────┴───────────┴───────────────────────────── @HBt (S) = 15 (!) @HB b) Verkürzung der Ausführungszeiten bei allen Prozessen um eine Einheit @HAt: 0 2 4 6 8 10 12 13 @HP┌─────┬────────┬────────┬─────────────────── @HAP1 @HP│ @HLT1 @HP│ @HLT5 @HP│ @HLT8 @HP│ frei @HP├──┬──┼────────┼────────┴──────────────┬──── @HAS: P2 @HP│@HLT2@HP│@HLT4@HP│ @HLT6 @HP│ @HLT9 @HP│ frei @HP├──┼──┼────────┼───────────────────────┴──── @HAP3 @HP│@HLT3@HP@HP│ @HP│ @HLT7 @HP│ frei @HP└──┴──┴────────┴──────────────────────────── @HBt (S) = 13 (!) c) Änderung des Präzedenz-Graphen @HO█ @HLT1,3 @HO█ @HLT2,2 @HO█ @HLT3,2 @HO█ @HLT4,2 @HP│ └────┬─────────┐ @HO█ @HLT9,9 @HO█ @HLT5,4 @HO█ @HLT6,4 @HO█ @HLT7,4 @HO█ @HLT8,4 @HAt: 0 2 4 6 8 10 12 14 16 @HP┌────────┬───────────┬──────────────────────────┬─── @HAP1 @HP│ @HLT1 @HP│ @HLT6 @HP│ @HLT9 @HP│ frei @HP├─────┬──┴──┬────────┴──┬───────────────────────┴─── @HAS: P2 @HP│ @HLT2 @HP│ @HLT4 @HP│ @HLT7 @HP│ frei @HP├─────┼─────┴─────┬─────┴─────┬───────────────────── @HAP3 @HP│ @HLT3 @HP│ @HLT5 @HP│ @HLT8 @HP│ frei @HP└─────┴───────────┴───────────┴───────────────────── @HBt (S) = 16 (!) @HB d) Änderung der Prioritätenliste alte @HAL = {T1, T2, T3, T4, T5, T6, T7, T8, T9} @HBneue @HAL = {T1, T2, T4, T5, T6, T3, T9, T7, T8} @HAt: 0 2 4 6 8 10 12 14 16 @HP┌────────┬─────┬──────────────────────────┬───────── @HAP1 @HP│ @HLT1 @HP│ @HLT3 @HP│ @HLT9 @HP│ frei @HP├─────┬──┴─────┴──┬───────────┬───────────┴───────── @HAS: P2 @HP│ @HLT2 @HP│ @HLT5 @HP│ @HLT7 @HP│ frei @HP├─────┼───────────┼───────────┼───────────────────── @HAP3 @HP│ @HLT4 @HP│ @HLT6 @HP│ @HLT8 @HP│ frei @HP└─────┴───────────┴───────────┴───────────────────── @HBt (S) = 14 (!) @HB weiter mit ⌐Rechnernetz@BS___6¬