Betriebssystemtheorie/ Scheduling/ Algorithmen

Zurück zu Ressourcen und Ressourcenverwaltung | Hoch zum Scheduling

Einleitung

Es gibt eine Reihe von möglichen Kriterien, nach denen die Scheduling-Strategie gewählt wird. Einige typische Kriterien sind:

• Fairness: Jeder Job erhält einen gerechten Anteil an der Ressource.
• Effizienz: Die Ressource ist immer vollständig ausgelastet.
• Antwortzeit: Die Antwortzeit für die interaktiv arbeitenden Benutzer wird minimiert.
• Wartezeit: Die Wartezeit auf die Ausgaben von Stapelaufträgen (d.h. Rechenaufträgen, die einmal abgegeben werden, im Hintergrund laufen und deren Ergebnisse irgendwann abgeholt werden) wird minimiert.
• Durchsatz: Die Anzahl der Jobs, die in einem bestimmten Zeitintervall ausgeführt werden, wird maximiert.

Einige dieser Ziele widersprechen sich. Um zum Beispiel die Antwortzeit zu minimieren, sollten möglichst gar keine Stapelaufträge bearbeitet werden, beziehungsweise nur nachts, wenn alle interaktiven Benutzer schlafen. Das erhöht natürlich die Wartezeit auf die Ausgaben der Stapelaufträge.

Es gibt daher keine optimale Scheduling-Strategie, die alle Kriterien gleichzeitig erfüllt. Je nachdem, welche dieser Kriterien höhere Priorität erhalten sollen, sind bestimmte Strategien geeigneter und andere ungeeigneter. Die einfachste Strategie war in den früheren Batch-Systemen implementiert: run to completion - ein Job verfügt über eine Ressource, bis er beendet ist, erst dann kann ein neuer Job mit dieser Ressource gestartet werden. Im Gegensatz dazu werden Strategien, die die zeitweilige Unterbrechung laufender Jobs erlauben oder benötigen, als preemptives Scheduling bezeichnet. In diesem Fall muss sichergestellt werden, dass die Ressourcen unterbrochener Jobs nicht vom laufenden Job gestört werden können. Mehr dazu im Kapitel Ressourcen und Ressourcenverwaltung.

Prozessor

Statische Prioritäten

Eine statische Priorität wird einem Job einmal zugewiesen und verändert sich dann nicht mehr.

Rate Monotonic Scheduling

Das Rate Monotonic Scheduling (RMS) weist jedem Job eine Priorität zu, entsprechend der Periodenlänge des Jobs. Je kürzer dabei die Periode ist, desto höher ist die Priorität.

RMS ist nicht optimal.

Deadline Monotonic Scheduling

Beim Deadline Monotonic Scheduling (DMS) wird die Priorität eines Jobs durch seine Deadline bestimmt. Je näher die Deadline ist, desto höher ist die Priorität des Jobs.

Dynamische Prioritäten

Algorithmen, die mit dynamischen Prioritäten arbeiten, weisen jedem Job eine Priorität, relativ zu den anderen im System vorhandenen Jobs, zu. Diese Priorität kann sich während der Ausführung des Scheduling-Plans ändern.

Earliest Deadline First

Der Algorithmus Earliest Deadline First (EDF) sortiert alle Jobs im System aufsteigend nach ihrer Deadline. EDF ist optimal, falls folgendes gilt:

Das System enthält nur einen Prozessor.

Bei mehr als einem Prozessor kann es sein, dass EDF die Jobs falsch auf die Prozessoren verteilt. Beispielsweise gibt es in einem System 2 Prozessoren P₁ und P₂ sowie 3 Jobs J₁ 1 (0, 1), J₂ 1 (0, 2) und J₃ 5 (0, 5). EDF führt am Zeitpunkt 0 J₁ auf P₁ aus und J₂ auf P₂. Am Zeitpunkt 1 ist J₁ fertig und EDF führt J₃ auf P₁ aus. Da J₃ seine Deadline bei 5 hat, aber erst bei 6 fertig wird, kann EDF im Mehr-Prozessor-Fall nicht optimal sein. Eine korrekte Lösung wäre gewesen, J₁ und J₂ auf P₁ auszuführen und J₃ auf P₂.

Alle Ressourcen sind preemptierbar.

Angenommen es liegen 2 Jobs im System vor: J₁ 5 (0, 10) und J₂ 1 (1, 2). Zum Zeitpunkt 0 wird J₁ ausgeführt, da J₂ noch nicht bereit ist. Zum Zeitpunkt 1 wird J₂ bereit, kann aber nicht ausgeführt werden, da J₁ nicht preemptiert werden kann. Am Zeitpunkt 5 ist J₁ fertig, aber J₂ hat seine Deadline längst verfehlt. Hätte J₁ an Zeitpunkt 1 preemptiert werden können, wäre J₂ einplanbar.

Es gibt keine Abhängigkeiten zwischen den Jobs.

Es liegen auch hier zwei Jobs J₁ 1 (1, 2) und J₂ 1 (0, 1) vor. J₂ ist von J₁ abhängig. J₂ kann frühestens am Zeitpunkt 1 ausgeführt werden, welcher aber gleichzeitig seine Deadline darstellt. Ohne die Abhängigkeit wären beide Jobs einplanbar.

Least Slack Time First

Bei Least Slack Time First (LST) entscheidet der Scheduler nach der freien Zeit, die jeder Job bis zu seiner Deadline hat. Der Algorithmus wird auch Minimum Laxity First genannt. Genau wie EDF ist er in einem Einzelprozessorsystem optimal.

Slack-time

Der Begriff Slack-time bezeichnet die freie Zeit s, die einem Job bis zum Erreichen seiner Deadline d bleiben. Es gilt s = d - t - x, wobei t die aktuelle Zeit angibt und x die verbleibende Ausführungszeit.

Zur Berechnung der Slack-time der Jobs im System gibt es zwei Varianten. Die strikte Variante berechnet die Slack-time kontinuierlich. Da es sich hier um einigen Aufwand handelt, kann das sehr langsam sein. Die nicht-strikte Variante berechnet die Slack-time nur nach festgelegten Zeitintervallen. Bei beiden Varianten gilt, dass der aktuell berechnete Job vom Prozessor verdrängt wird, falls ein anderer Job eine geringere Slack-time aufweist.

Latest Release Time

Die Idee hinter Latest Release Time (LRT) ist, alle Jobs so spät wie möglich auszuführen. Mit diesem Algorithmus ist es möglich, in einem komplexen System vielen Jobs eine angemessene Rechenzeit zur Verfügung zu stellen. Enthält ein System Hard-, Soft-Real-time-Jobs und Best-Effort-Jobs, können sehr viele davon bedient und trotzdem alle Deadlines eingehalten werden. Aufgrund der Arbeitsweise vom LRT wird es auch als Backwards Scheduling bezeichnet.

Zuerst werden die Hard-Real-time-Jobs berechnet. Der Job mit der spätesten Deadline wird als letzter ausgeführt, direkt vor seiner Deadline. Der vorletzte Job, mit der zweitspätesten Deadline, wird so spät wie möglich ausgeführt, ohne dass er seine Deadline verpasst oder mit dem letzten Job kollidiert. Alle anderen Hard-Real-Time-Jobs werden nach diesem Schema eingefügt.

Falls die Hard-Real-Time-Jobs nicht die gesamte Rechnerzeit benötigen, enthält der Scheduling-Plan Lücken. Diese werden nach dem bereits beschriebenen Schema mit Soft-Real-Time-Jobs aufgefüllt. Der Soft-Real-Time-Job mit der spätesten Deadline wird zuletzt und so spät wie möglich ausgeführt. Der Soft-Real-Time-Job mit der zweitspätesten Deadline wird vor dem letzten Soft-Real-Time-Job ausgeführt und so weiter. Zu Beachten ist hierbei, dass Soft-Real-Time-Jobs nur die ungenutzte Rechenzeit zwischen den Hard-Real-Time-Jobs belegen, aber niemals einen Hard-Real-Time-Job verdrängen. Aufgrund der gelockerten Anforderungen von Soft-Real-Time-Jobs ist es auch möglich die freie Rechenzeit gleichmäßig so zu verteilen, dass alle Jobs die Chance erhalten zu rechnen.

Falls nach dem Scheduling der Soft-Real-Time-Jobs noch Rechenzeit unbenutzt ist, werden zum Schluss noch die Best-Effort-Jobs aufgeteilt.

Shortest Processing Time

Eine weitere Art, Prioritäten zu setzen, ist Shortest Processing Time (SPT), beziehungsweise Shortest Job First. Angenommen, eine Reihe von Prozessen kommt gleichzeitig in die Warteschlange und die Rechenzeiten, die diese Prozesse benötigen, können bereits vorher abgeschätzt werden. Dann wird die Gesamt-Wartezeit aller Prozesse minimiert, wenn man die kürzesten Prozesse zuerst rechnen läßt. Dies funktioniert allerdings nicht für Prozesse, die erst später zur Warteschlange hinzukommen.

Longest Processing Time

Um bei mehreren verschiedenen Prozessen auf mehreren gleichen Maschinen die Gesamtlaufzeit, bis alle Prozesse beendet sind, zu minimieren kann man den Scheduling-Algorithmus Longest Processing Time (LPT) anwenden. Dabei wird der Prozess mit der längsten (erwarteten) Ausführungszeit auf die erste freie Maschine vergeben. Im Vergleich zu einem optimalen Algorithmus dauert es mit LPT höchstens doppelt so lange.

Verbreitete Implementierungen

In vielen verbreiteten Betriebssystemen muss der Scheduler mehrere Kriterien gleichzeitig berücksichtigen. Da die meisten vorgestellten Algorithmen sehr spezialisiert sind und nur in Ausnahmefällen optimale Ergebnisse liefern, werden in der Praxis häufig andere Strategien implementiert.

Round-Robin

Einer der einfachsten, fairsten und verbreitetsten Scheduling-Algorithmen ist Round Robin. Dabei werden alle rechenbereiten Jobs in einer Warteschlange angeordnet. Jeweils der vorderste Job wird aus der Schlange genommen, bekommt ein festes Quantum Prozessorzeit und wird dann, falls er mehr Zeit benötigt, erneut hinten an die Warteschlange angestellt. Neu hinzukommende Jobs werden ebenfalls an das Ende der Schlange gestellt. Das Zeitquantum ist immer gleich groß, typischerweise in Größenordnungen von 10 bis 50 Millisekunden.

Die Wahl eines geeigneten Quantums ist ein Kompromiss: Je kleiner das Quantum, desto größer wird der Zeitanteil, den das System mit der Umschaltung zwischen den Jobs verbringt. Je größer das Quantum, desto länger werden die Antwortzeiten für interaktive Jobs.

Änderung der Zeitscheibe

Ein sehr einfache Idee zur Implementierung von Prioritäten besteht darin, die Länge der Zeitscheiben der Jobs zu ändern. Ein Job normaler Priorität bekommt die normale Länge zugesprochen. Ein nieder-priorisierter Job bekommt eine kürzere Zeitscheibe und ein höher-priorisierter Job eine längere Zeitscheibe. Obwohl (oder auch weil) dieser Algorithmus keine gezielte Strategie zur Optimierung verfolgt, ist er für Desktop-Systeme meist völlig ausreichend. Ein Systemdienst bekommt hier nur eine geringe Priorität zugewiesen und eine Multimedia-Anwendung eine hohe Priorität.

Klassenbasiertes Round-Robin

Alle Jobs mit der selben Priorität bilden eine Scheduling-Klasse. Das Scheduling läuft nun in zwei Schritten ab. Im ersten Schritt bestimmt der Scheduler die Klasse mit der höchsten Priorität, welche rechenbereite Jobs enthält. Im zweiten Schritt werden alle Jobs dieser Klasse im Round-Robin-Verfahren abgearbeitet. Die rechenbereiten Jobs in nieder-priorisierten Klassen werden nicht gerechnet.

Scheduling auf mehreren Ebenen

Bisher sind wir davon ausgegangen, dass alle Prozesse gleichzeitig im Hauptspeicher gehalten werden können. Es kann aber auch sein, dass ein Teil der Prozesse in Sekundärspeicher (etwa auf die Festplatte) ausgelagert werden muss. Dann muss auf zwei Ebenen Scheduling betrieben werden: Auf der oberen Ebene wird entschieden, welche Prozesse gerade in den Hauptspeicher geladen werden. Auf der unteren Ebene wird unter den im Hauptspeicher befindlichen Prozessen jeweils einem der Prozessor zugeteilt. Auf beiden Ebenen können unterschiedliche Strategien (Round Robin, Priority Scheduling, etc.) implementiert sein.