Version [22467]
Dies ist eine alte Version von BSys06Scheduling erstellt von RonnyGertler am 2013-03-26 19:52:55.
Betriebssysteme (Betriebssystemtheorie) - Kapitel 6 - Scheduling
Inhalte von Dr. E. Nadobnyh
6.1. Grundbegriffe
Definition und Eigenschaften
Der Scheduler ist ein Teil des Betriebssystems, welcher über die Prozessorzuteilung entscheidet.
1) Der Scheduler wählt einen Prozess bzw. Thread aus der Menge der ausführbaren (rechenwillige) Prozesse bzw. Threads aus, welcher als nächster den Prozessor (CPU) zugeteilt erhält. Weiter wird der Begriff „Prozesse“ statt „Prozesse bzw. Threads“ verwendet.
2) Das Scheduling (CPU-Scheduling, Prozessorverwaltung) ist die Erstellung eines Zeitplanes.
3) Das Betriebssystem selbst unterliegt nicht dem Scheduling, da es kein Prozess ist.
4) Wir begrenzen uns auf das CPU-Scheduling für das Einprozessorsystem (Uniprozessor-Scheduling).
Grundverfahren
1) Das präemptive (preemptive, verdrängende) Scheduling:
- Die CPU kann einem Prozess entzogen werden, obwohl der Prozess die CPU weiterhin verwenden möchte. Der suspendierte Prozess wird in Zustand „rechenbereit“ zurückgestellt.
b )Ursachen der Verdrängung:
- Ablauf von Zeitscheiben,
- Prozess höherer Priorität wird rechenbereit.
- Dieses Verfahren ist geeignet für Dialog- und Realtime-Systeme.
- Der aktive Prozess verwendet die CPU so lange wie er möchte.
- Dieses Verfahren ist geeignet für Batch–Systeme.
- Es ist nur ein geringer Verwaltungsaufwand nötig.
Verhungern
Es gibt einige Ursachen für das Verhungern (Starvation):
1) Wegen der ungeschickten Synchronisation: Alle Prozesse laufen uneingeschränkt weiter, aber keine Fortschritte machen.
2) Wegen des ungeschickten Schedulings: Ein rechenwilliger Prozess kann nie die CPU zugeteilt bekommen, weil die CPU von anderen Prozessen monopolisiert ist.
Beispiel für präemptives Schduling: ein Prozess mit niedriger Priorität kann ewig auf CPU-Zuteilung warten, da ständig hochprioritäre Prozesse die CPU anfordern.
Beispiel für nicht-präemptives Schduling: ein "unkooperativer" oder fehlerhafter Prozess kann die CPU monopolisieren, z.B. wenn ein fehlerhafter Prozess eine endlose Schleife beginnt.
⇒ Demo 1
Unterbrechung und Verdrängung
1) Das Betriebssystem übernimmt die Kontrolle über dem Rechner bei jeder Unterbrechung.
2) Nicht bei jeder Unterbrechung wird das Scheduling eingeschaltet. Beispiele:
- nach der Unterbrechung wegen einer fehlerhaften I/O-Operation ändern sich die Prozess-Zustände nicht und der unterbrochene Prozess bleibt weiter aktiv.
- Ähnlich reagiert das Betriebssystem auf Unterbrechungen vom Timer. Das Scheduling wird nur zu jeder k-ten Timer-Unterbrechung eingeschaltet, wenn eine Zeitscheibe abläuft.
3) Nicht bei jeder Einschaltung des präemptiven Schedulings wird über eine Verdrängung entschieden.
Begriffsverwirrung: „preemptiv“ kann manchmal als „unterbrechend“ übersetzt werden.
Zeitpunkte für neues Scheduling
1) Erzeugung eines neuen Prozesses.
2) Beendigung eines Prozesses.
3) Blockierung des bis dahin aktiven Prozesses, z.B. wenn ein Prozess eine E/A-Operation beauftragt hat und auf das Ergebnis warten muss.
4) Deblockierung des Prozesses, weil er einen Ereignis erhalten hat, z.B. weil die beauftragte E/A-Operation beendet hat.
5) Ablauf der für aktiven Prozess zugeteilten Zeit und Verdrängung des aktiven Prozesses.
Wegen der Erzeugung oder der Deblockierung eines hochprioritären Prozesses kann der aktive Prozess verdrängt werden.
Warteschlangen im Betriebssystem
6.2. Scheduling-Kriterien
Scheduler-Aufgaben
1) Die Aufgabe eines Schedulers ist die optimale CPU-Zuteilung.
2) Für die Lösung wurden eine Vielzahl von Scheduling-Algorithmen (Scheduling-Strategien) erfunden. Diese Vielzahl kommt daher, dass je nach Ziel unterschiedliche Lösungen optimal sind.
3) Es gibt auch viele Ziele (Kriterien, Anforderungen), die für verschiedene Betriebsarten (Stapel, Dialog, Echtzeit) definiert wurden.
4) Ziele sind widersprüchlich, z.B. Effizienz zu Antwortzeit.
5) Es gibt keinen idealen Scheduling-Algorithmus, der alle Scheduling-Ziele erfüllt.
6) Scheduler kann in einem System mehrere Betriebsarten, z.B. Stapel- und Dialogbetrieb, unabhängig voneinander optimieren.
Einige Scheduling-Kriterien
Gerechtigkeit (Fairness): Jeder Prozess erhält einen gerechten CPU-Anteil.
Effizienz: Die Auslastung der CPU und der übrigen Systemkomponenten soll erhöht werden, möglichst zu 100%.
Durchsatz: Abarbeitung möglichst vieler Aufträge pro Zeiteinheit.
Terminerfüllung: Bereitstellung bestimmter Ergebnisse zu festgelegten Terminen.
Antwortzeit: Die Zeit zwischen einer Eingabe und der Reaktion darauf in interaktiven Systemen soll minimiert und in Echtzeitsystemen garantiert werden.
Durchlaufzeit
Ein der Scheduling-Kriterien ist die Durchlaufzeit, die im Stapelbetrieb verwendet wird. Die durchschnittliche Durchlaufzeit soll minimiert werden.
Die Durchlaufzeit (Verweilzeit) ist die gesamte Zeit, in der sich ein Prozess im System befindet.
Die Durchlaufzeit ergibt sich aus der Summe: Durchlaufzeit = Bedienzeit + Wartezeit.
Eine Wartezeit ist die Summe aller Zeiten in allen Warteschlangen (auch in Bereitwarteschlange), in denen ein Prozess auf die Ausführung warten muss.
Eine Bedienzeit (Servicezeit) ist die Zeit, in der ein Prozess die CPU hält.
Manchmal werden zwei Begriffe: Antwortzeit und Durchlaufzeit als Synonyme verwendet.
6.3. Scheduling-Algorithmen
Klassifikation
Scheduling-Algorithmen können unterschiedlich klassifiziert werden, z.B. nach ihren Eigenschaften oder nach der Betriebsart, in der sie verwenden werden:
1) Kooperatives und präemptives Scheduling.
2) Prioritätsscheduling und Scheduling ohne Prioritäten.
3) Schduling in Batch-, Dialog- und Realtime- Systemen.
Ein Betriebssystem kann in der Regel eine Kombination von Scheduling-Algorithmen verwenden.
Klassische Scheduling-Algorithmen: FIFO, SJF und RR gehören zu dem Scheduling ohne Prioritäten.
FIFO –Algorithmus
Definition: FIFO (First In First Out, FCFS -First Come First Serve) bearbeitet die Aufträge in der Reihenfolge ihres Eintreffens.
Eigenschaften:
1) Es findet keine Verdrängung des aktiven Prozesses statt.
2) Ein Prozess, der nach Blockierung wieder rechenbereit ist, kommt an das Ende der Warteschlange.
Vorteile:
1) Keine Gefahr wegen Verhungern.
2) Geringe Verluste durch Prozesswechsel.
3) Einfache Implementierung.
Nachteil: Convoy–Effect bedeutet, dass ein langer Prozess viele kurze Prozesse verzögern kann.
CategoryBSys
