Scheduler

Der Scheduler (engl.: Disponent, Planer) ist ein elementarer Teil von Betriebssystemen, die Multitasking unterstützen. Werden auf einem Computer mehrere Prozesse gleichzeitig ausgeführt, so muss das Betriebssystem die vorhandenen Ressourcen auf die verschiedenen Prozesse aufteilen. Scheduler kommen aber auch in anderen Bereichen als der Prozessverwaltung zum Einsatz. So müssen etwa auch die Zugriffe auf eine Festplatte möglichst gut organisiert werden, wenn mehrere Lese- oder Schreibaufträge vorliegen. Man spricht dann von einem disk scheduler. Oder es muss entschieden werden, welche Prozesse aus dem Hauptspeicher auf den Hintergrundspeicher verlagert werden - derartige Entscheidungen trifft ein sogenannter Langzeit-Scheduler. Scheduling-Algorithmen lassen sich jedoch häufig in sehr unterschiedlichen Aufgabengebieten anwenden.

Prozess-Scheduler

Prozess-Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non preemptive) aufteilen. Nicht unterbrechende Scheduler lassen einen Prozess, nachdem ihm die CPU einmal zugeteilt wurde, solange laufen, bis dieser diese von sich aus wieder freigibt oder bis er blockiert. Unterbrechende Scheduler teilen die CPU von vornherein nur für eine bestimmte Zeitspanne zu und entziehen dem Prozess diese daraufhin wieder. Man kann verschiedene Systeme unterscheiden, in welchen jeweils verschiedene Anforderungen an den Scheduler gestellt werden:

In Stapelverarbeitungssystemen sieht der Scheduler denkbar einfach aus: Ankommende Aufträge werden in eine Warteschlange eingereiht und jedes Mal, wenn ein Job abgearbeitet ist, kommt der nächste aus der Schlange dran.

Interaktive Systeme stellen höhere Anforderungen: Der Benutzer legt Wert auf kurze Antwortzeit. Wenn er beispielsweise in einem Texteditor eine Tastatureingabe tätigt, sollte der Text sofort erscheinen.

In Echtzeitsystemen gibt es für jeden Job ein Zeitlimit, bis zu dem die Aufgabe erledigt sein muss.

Typische Benutzer-PCs sind interaktive Systeme, auf denen gelegentlich auch Prozesse als so genannte Hintergrundprozesse mit niedrigerer Priorität ablaufen können.

Ziele

Die Zuteilung der CPU an die Prozesse sollte bestmöglich erfolgen, wobei allerdings unterschiedliche Ziele verfolgt werden können:

CPU-Auslastung: Die CPU sollte zu jeder Zeit ausgelastet sein. Es soll nicht vorkommen, dass die CPU sich im Leerlauf befindet, nur weil ein Prozess auf Daten von der Festplatte wartet.
Schnelle Antwortzeiten: Die Wartezeiten des Benutzers (oder anderer Systeme) sollten minimiert werden. Prozesse, die eine Interaktion mit dem Benutzer erfordern, sollten also bevorzugt werden vor solchen, die im Hintergrund stattfinden können.
Durchsatz: Die Anzahl beendeter Aufgaben pro Zeiteinheit sollte maximiert werden. Dies ergibt eine ähnliche Strategie wie die Auslastung, betrachtet aber mehr das tatsächliche Ergebnis.
kurze Turnaroundzeit: Die Zeit, die vom Start eines Prozesses bis zu seiner vollständigen Beendigung vergeht, sollte minimiert werden.
Fairness: Kein Prozess sollte unverhältnismäßig lange warten müssen, während ein anderer bevorzugt wird.
Balance: Die Prozesse sollten der CPU auf eine Weise zugeteilt werden, dass auch andere Ressourcen wie Festplatte, Netzwerk-Schnittstelle u.a. ausgelastet sind.
Deadlines einhalten: Relevant bei Echtzeitsystemen.

Strategien

Das größte Problem des Schedulers ist die Tatsache, dass die benötigten Betriebsmittel für die einzelnen Prozesse nicht im Vorfeld bekannt sind. Es lässt sich also im Allgemeinen keine optimale Planung erstellen, sondern der Scheduler muss dynamisch auf geänderte Anforderungen reagieren. Dabei können (abhänging vom Scheduler) verschiedene Zuteilungsstrategien zum Einsatz kommen:

First-Come First-Served (FCFS, oder auch FIFO: First-In First-Out): Hierbei werden alle Prozesse in der Reihenfolge ihres Eingangs bearbeitet. Dabei werden einzelne Prozesse immer komplett verarbeitet, bevor der nächste Prozess an die Reihe kommt. Diese Strategie erzielt eine gute Auslastung bezüglich der CPU, allerdings nicht bezüglich Ressourcen, die längere Zeit für eine Anforderung benötigen können, wie z.B. Ein-/Ausgabe oder Massenspeicher. Für Mehrbenutzersysteme ist die Strategie darüber hinaus wenig geeignet, da einzelne Benutzer so ggf. für längere Zeit (nämlich bei aufwendigen Prozessen anderer Benutzer) ausgeschlossen werden.

Shortest Job First (SJF) ist ein weiteres Verfahren, das nicht für Mehrbenutzersysteme geeignet ist. SJF lässt sich in Fällen einsetzen, in denen die benötigte Rechenzeit für einzelne Aufgaben aus Erfahrungswerten gut vorhergesagt werden kann. Ein Nachteil ist, dass große Prozesse u.U. niemals die CPU zugeteilt bekommen, wenn sich immer kürzere Jobs vordrängeln.

Round Robin (Zeitscheibenverfahren): Einem Prozess wird die CPU für eine bestimmte (kurze) Zeitspanne zugeteilt. Danach wird der Prozess wieder hinten in die Warteschlange eingereiht.

Prioritätsbasiertes Verfahren: Bei dieser Strategie wird jedem Prozess eine Priorität zugeordnet. Die Abarbeitung erfolgt dann in der Reihenfolge der Prioritäten. Da es sich dann (innerhalb der gleichen Prioritäten) um eine Strategie der Eingangsreihenfolge handelt, wird diesem Verfahren meistens noch ein Zeitscheibenverfahren untergeordnet, um trotzdem eine schnelle Antwortzeit zu ermöglichen. Zusätzlich wird in den verbreiteten Schedulern mit dynamischen Prioritäten gearbeitet, wobei sich die Priorität eines Prozesses mit der Zeit erhöht, damit auch niedrig priorisierte Prozesse irgendwann bearbeitet werden und nicht ständig von höher priorisierten Prozessen verdrängt werden.

Terminabhängige Ablaufplanung: Diese Strategie kommt hauptsächlich in Echtzeitsystem vor. Dabei werden die Prozesse bevorzugt verarbeitet, die als erstes beendet sein müssen. Damit ist es möglich, eine definierte Antwortzeit für bestimmte Prozesse zu garantieren.

Festplatten-Scheduler

Festplatte: Wohin soll der Kopf zuerst fahren?

Folgende Techniken werden verwendet, um bestmögliche Ausnutzung der Festplatte zu gewährleisten:

shortest seek first: Dieser Algorithmus ist eine direkte Verbesserung von FCFS. Von einer Menge von Lese-/Schreibaufträgen wird derjenige ausgewählt, der dem Schreib-/Lesekopf der Festplatte am nächsten ist. Ein Vorteil dieser Vorgehensweise ist ihre Einfachheit, ein gravierender Nachteil ist, dass Daten, die am Rand der Festplatte liegen, möglicherweise sehr lange warten müssen, bis sie gelesen bzw. geschrieben werden.

Aufzug-Algorithmus: Der Aufzug-Algorithmus heißt so, weil er sich ähnlich verhält, wie ein Aufzug. Der Arm der Festplatte weiß seinen momentanen Standpunkt und seine Fahrtrichtung. Nach jedem abgeschlossenen Job fährt er in die aktuelle Richtung bis zum nächsten Job weiter, so lange, bis in dieser Richtung kein Job mehr zu erledigen ist. Dann wird die Fahrtrichtung umgekehrt.

Literatur

Tanenbaum, Andrew S.: Moderne Betriebssysteme ISBN 3827370191