Three-Level-Scheduling

Three-Level-Scheduling (TLS) TLS unterteilt den Scheduling-Prozess in 3 Teilprozesse:

• Admission Scheduler
• Memory Scheduler
• CPU Scheduler

Three Level Scheduling

Am Beginn dieses Schedulingverfahrens steht ein Input Queue. Dabei handelt es sich lediglich um eine Datenstruktur ähnlich einer Liste, in welcher die neu ankommenden "Jobs" zwischengespeichert werden.

Nun kommt der Admission Scheduler (in Folge AS genannt) ins Spiel. Der AS entscheidet, welcher Job ins weitere System (genauer gesagt in den Speicher) kommt. Die anderen Jobs verbleiben im Input Queue. Grundsätzlich wird versucht, einen guten Mix aus Compute-Bound Jobs (meist lange Abarbeitezeit) und IO-Bound Jobs (Input/Output - kurze Abarbeitezeit) zu finden und/oder kürzere Jobs längeren vorzuziehen. Der Admission Scheduler kann dabei auch Jobs, welche später hinzutreten, denen in der Input Queue vorziehen. Man kann den AS also als Vorfilter betrachten.

Vom Admission Scheduler werden die Jobs dann weiter in den Arbeitsspeicher geladen. Hier beginnt nun die Arbeit des Memory Scheduler. Da jeder Job im Speicher Platz benötigt und es durchaus vorkommen kann, dass mehrere Jobs im Speicher vorhanden sind, entscheidet der Memory Scheduler, welcher Job im Hauptspeicher verbleibt und welcher auf die Festplatte ausgelagert wird (Swap). Dabei wird das "Degree of Multiprogramming" herangezogen, um zu entscheiden, wie viele Jobs im Hauptspeicher belassen werden. Das "Degree of Multiprogramming" beschreibt die Anzahl von Prozessen, welche ein Prozessor, abhängig von Hauptspeicherauslastung und Prozessorgeschwindigkeit, effizient verarbeiten kann. Wird auf eine Ressource von mehreren Prozessen gemeinsam zugegriffen, so kann dies das "Degree of Multiprogramming" beeinflussen. Um eine optimale Performance zu gewährleisten, muss regelmäßig entschieden werden, wie viele Jobs im Speicher abgelegt werden. Es wird versucht, eine möglichst hohe CPU-Auslastung zu erreichen, wobei der Rest auf die Festplatte ausgelagert wird. Das Ein-/Auslagern ist teuer, da es vermehrt Systemressourcen beansprucht und Festplattenzugriffe verhältnismäßig langsam sind. Kriterien des Ein-/Auslagerns:

• Wie lange ist es her, dass der Job auf die Festplatte ausgelagert wurde?
• Wie viel CPU-Zeit hat der Job kürzlich erhalten?
• Wie groß ist der Job? (kleinere Jobs werden überhaupt nicht ausgelagert, da Auslagern teuer ist)
• Wie wichtig ist der Job?

Der CPU Scheduler entnimmt nun aus dem Speicher einen Job und arbeitet diesen ab (bzw. arbeitet weiter daran). Hierzu wird eines der anderen Scheduling-Verfahren (meist aber Shortest-Process-Next) verwendet.

Quellen

• Andrew S. Tanenbaum: Modern Operating Systems - Second Edition ISBN 0-13-092641-8