Kapitel 5 - Scheduling
|
Inhalt
|
- 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.
|
|
|
|
|
| Kapitel 1 | Einleitung |
|
Ebenen- oder Schichtenmodell, Aufgaben...
|
| Kapitel 2 | Modelle |
|
Schichtenmodell, Betriebsmittel, Instanzen...
|
| Kapitel 3 | Aktivitäten |
|
Token, Multitasking, Prozesse,Timesharing...
|
| Kapitel 4 | Kritischer Abschnitt |
|
Gegenseitiger Ausschluss,Peterson,Semaphore...
|
| Kapitel 5 | Scheduling |
|
Prozessorzuteilung, Prioritätsscheduling, RR...
|
| Kapitel 6 | Speichermanagment |
|
Freispeicherverwaltung, Segmentierung, Paging...
|
| Kapitel 7 | Seitenersetzung |
|
NRU, FiFo, Second Chance, LRU, NFU, Aging...
|
| Kapitel 8 | Deadlocks |
|
Bedingungen, Erkennung und Auflösung...
|
| Kapitel 9 | Dateisysteme |
|
Freispeicherverwaltung, Festplattenscheduling...
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
Home 
