Kapitel 5 - Scheduling
- zentral, dezentral und Modelle für Scheduling
- Scheduling Strategien
- Prioritätsscheduling und Round Robin
Scheduling wird notwendig, wenn die Anzahl der gleichzeitig laufenden
Prozesse die Anzahl der physikalischen Prozessoren übersteigt. Die Verwaltung kann
dezentral (Prozesse selbst) oder zentral erfolgen. Es gibt zwei grundlegende
Modelle für zentrale Scheduling-Verwaltung:
- Deterministisches Modell - alle Informationen bekannt (Anzahl
Prozesse/Betriebsmittel/Zeitdauer)
- Probabilistisches Modell - offen (Anzahl Prozesse nicht bekannt) oder
geschlossen (Anzahl Prozesse bekannt, aber Bedienzeiten nicht)
Welche Strategien der Prozessorzuteilung werden unterschieden?
-
Durchsatz (Anzahl bearbeiteter Prozesse pro Zeiteinheit
maximieren)
-
Verweilzeit (Prozess soll so schnell wie möglich abgearbeitet
sein)
-
Wartezeit (Dauer im Zustand "wartend" minimieren)
-
Effizienz (Prozessorleistung maximal ausnutzen)
-
Antwortzeit (möglichst kurze Reaktionszeiten für den Benutzer)
-
Fairness (gerechte Verteilung der Prozessorzeit)
Es ist nicht möglich CPU-Auslastung und Durchsatz zu maximieren und
gleichzeitig Warte- und Antwortzeit zu minimieren. Deshalb müssen alle Scheduling
Algorithmen Kompromisse eingehen.
Nach welchen Kriterium richtet sich das Scheduling Verfahren?
Dies hängt in erster Linie vom Einsatzgebiet des Systems ab:
- Echzeitbetrieb
- Dialogbetrieb
- Stabel- bzw. Batchbetrieb
- Hintergrundbetrieb
Was ist das deterministische Modell?
Bei diesem Modell werden die Schedules vor der Ausführung
berechnet. Dies funktioniert natürlich nicht in interaktiven offenen
Systemen, sondern nur in geschlossenen Systemen mit fester Prozessanahl und
vordefinierter Betriebsmittelnutzung mit statischen Ablauf. In Dialogsystemen wird
deshalb das offene probabilistische System verwendet, da hier Anzahl der Prozesse
und Betriebsmittelnutzung dynamisch erfolgen...
Was ist das probabilistisches Modell?
Die Entscheidung welcher Prozess den Prozessor bekommt, wird dynamisch wärend
der Prozessabarbeitung gefällt. Hierbei gibt es einige wichtige Größen, welche als
stochastische Variablen zur Berechnung herangezogen werden können. Die
Warteschlangentheorie ist wichtiges Mittel für Untersuchungen. (Alle Prozesse
welche den Prozessor fordern werden in eine Warteschlange eingereiht).
Die Abbildung entspricht einem Scheduling ohne Prioritäten und ohne Entzug.
Was ist das Single-Server-Modell?
Eine Warteschlange nimmt Prozesse in einem bestimmten Abstand (A) auf. Der
Scheduler entnimmt nach einer gewissen Wartezeit (W) im Pool einen Prozess und
führt diesen in einer bestimmten Zeit (B) aus .
|
|
mittlere Verweildauer in Warteschlange
|
W
|
|
Zwischenankunftsabstand
|
A
|
|
Prozessorzeit der Teilprozesse
|
B
|
|
Anzahl von Prozessen in Warteschlange
|
Nq (N=Nq+p)
|
|
Verkehrswert
|
p=B/A (Poisson-Prozesse)
|
|
Verweildauer im System
|
V=A*N (Littles Theroem)
|
Weiter Größen wie durchschnittliche Warteschlangellänge oder die Wahrscheinlichkeit
das sich n Prozesse im System befinden, lassen sich mit Poissen-Verteilungen
genauso wie die oben erwähnte mittlere Verweildauer ermitteln.
Wie können Wahrscheinlichkeiten für Prozessgrößen ermittelt werden?
Durch Poisson-Prozesse (Markow) können Erwartungswerte, Mittelwerte und
Varianzen für Zwischenankunftsabstände, Bedienwünsche und Auslastung berechnet
werden. Die Betrachtungen beziehen sich hier auf den stationären Fall
(t->unendlich, also FiFo).
Wie arbeitet First Come First Serve - FCFS?
Ankommende Prozesse werden in eine FIFO Liste eingereiht und sequentiell
abgearbeitet. Somit ist dieses Modell nicht für Timesharing geeignet, da es eher
eine Batchverarbeitung ist.
Kommt ein langer Prozess zuerst, müssen andere winzige Prozesse alle auf die
Beendigung des großen Prozesses warten! Unfair. Bessere Implementationen können
deshalb das Token entziehen.
Durchschnittliche Wartezeit W = (Wartezeit(P1) + Wartezeit(P2) +
... + Wartezeit(Pn)) / n
Ist P1 ein vielfach größerer Prozess als die restlichen, so müssen alle folgenden
Prozesse auf die Beendigung von P1 warten. Dies läßt die durchschnittliche
Wartezeit extrem steigen.
Bsp.:
t(P1) = 24 t(P2) = 3 t(P3) = 3
Bei einer Abarbeitungsfolge von P1 -> P2 -> P3 wäre W =
17.
Bei einer Abarbeitungsfolge von P2 -> P3 -> P1 nur
3!
Was ist Prioritäts-Scheduling?
Hier wird jedem Prozess eine Priorität zugewiesen. Ausgewählt wird vom
Scheduler der ausführbereite Prozess mit der höchsten Priorität. Die Prioritäten
können statisch definiert und dynamisch zugewiesen werden.
Bsp: FEP (Fixed External
Priorities)
Was ist das Problem von Schedulern mit Prioritäten?
Hauptproblem beim Arbeiten mit Prioritäten ist das Aushungern
von Prozessen, welche möglicherweise nie aktiv werden können, da es immer Prozesse
höherer Priorität gibt.
Lösung hierfür ist das Aging. (dynamische Anhebung der Priorität
der älter werdenden Prozesse)
Ein anderes Problem ist die Prioritätenumkehr. Ein hochpriorisierter Prozess wartet
auf ein Betriebsmittel, welches ein niedrigpriorisierter Prozess reserviert hat.
Wie funktioniert Shortest Job First (dynamische Priorität ohne Entzug)?
Es wird der kürzeste Job zur Verarbeitung ausgewählt. Dabei werden die
Durchlauflängen der einzelnen Prozesse protokolliert. Nach jedem Prozesswechsel
wird die "bereit"-Warteschlange anhand der Wartezeiten absteigend neu
sortiert.
Deshalb optimiert Shortest Job First die mittlere Wartezeit. Problem ist hier auch
das Aushungern von Prozessen, was auch durch Aging (Altern) verhindert werden
kann.
SJF ist ohne Entzug (nonpreemtiv). Eine Variante mit Enzug ist
SRTF. Dabei wird der Prozessor entzogen, falls ein Prozess in der
Warteschlange ist, der kürzer als der verbliebene Rest des aktiven Prozesses.
Wie arbeiten Shortest Remaining Time First und Shortest Elapsed Time (dynamisch
mit Entzug)?
Diese beiden Verfahren sind mit Prioritäten und mit Entzug. Sie sind daher
relativ aufwendig, da ein ständiger Abgleich der Prioritätsdaten erfolgen muss. Bei
SET wird Prozessen, welche schon viel Prozessorzeit zugesprochen bekamen, die die
Prozessorzeit entzogen.
Wie arbeitet Highest Response Ratio Next - HRN?
Umso länger ein Prozess wartet, umso höher steigt er in seiner Priorität. So
wird Aushungern verhindert.
Wie funktioniert Round-Robin Scheduling (ohne Prioritäten)?
Das RR ist die verbreitetste Strategie, da sie fair ist und sich auch einfach
implementieren lässt. Das Prinzip ist einfach. Jeder Prozess erhält für eine
konstante Zeit t (Quantum) die Prozessorzeit. Nach Ablauf des
Zeitquantums wird der nächste Prozess aus der Warteschlange entnommen und
bearbeitet. Der zuvor bearbeitete Prozess wird wieder am Anfang der Liste
eingefügt.
Hauptproblem ist eine sinnvolle Zeitspanne für das Quantum zu finden. Da bei jedem
Kontextwechsel Register umgeladen müssen, muss ein gewisser Zeitraum für
Verwaltungsarbeiten eingerechnet werden. Dauert das Umladen der Register 5 ms macht
ein Quantum von 10 ms wenig sinn, da 50% Prozessorzeit verschwendet werden würde.
Wählt man das Quantum aber zu groß (z.B. 500 ms) so ist im Mehrbenutzerbetrieb nur
bedingte Interaktivität möglich. (RR nähert sich somit FCFS an)
Sinnvoll erwiesen sich Quanten von 100 ms.
- Scheduling mit oder ohne Entzug
- Scheduling mit oder ohne Prioritäten
Merktabelle: Scheduling Algorithmen
Was ist Zweistufiges Scheduling?
Angenommen der Arbeitsspeicher reicht nicht aus, um alle Prozesse abzubilden,
müssen diese auf einen Tertiärspeicher ausgelagert werden. Da das Auslagern bzw.
Einlagern eines Prozesses sehr viel Zeit in Anspruch nimmt, werden zwei Stufen
benutzt, um das Scheduling zu realisieren. Die erste Stufe arbeitet nur im
Hauptspeicher, während die zweite Stufe für das Ein- oder Auslagern von Prozessen
verantwortlich ist. Kriterien sind hier dieselben wie oben schon erwähnt.
- Wie lange ist ein Prozess Aus- oder Eingelagert?
- Wieviel Prozessorzeit hat ein Prozess in Anspruch genommen?
- Wie groß ist der Prozess im Speicher?
- Welche Priorität hat der Prozess?
Was steht im Widerspruch zu hohem Durchsatz und guter Auslastung?
Im Widerspruch dazu stehen gutes Antwortzeitverhalten im
Dialog- und Stapelbetrieb. Denn ein hoher Durchsatz und eine gute Auslastung
bedingen viele Prozesse im Rechner, so daß jeder Prozeß nur relativ selten aktiv
werden kann, d.h. das Antwortzeitverhalten schlechter wird. Auch die
Zuteilungsfairness wird dadurch zunehmend schlechter bzw. unfairer.
|
|
|
|
|
|
|
|
|
|
|
Quellen:
|
Andrew S. Tanenbaum
Computerarchitektur
|
Andrew S. Tanenbaum
Moderne Betriebssysteme
|
Petterson
Computer Architectur & Design
|
Christian Märtin
Rechnerarchitekturen
|
Kalfa
Skript und Vorlesung
|
Word Wide Web
Verschiedenste Seiten
|
|
|
|
|
