Three-Level-Scheduling
aus Wikipedia, der freien Enzyklopädie
Three-Level-Scheduling (TLS) TLS unterteilt den Scheduling Prozess in 3 Teilprozesse:
- Admission Scheduler
- Memory Scheduler
- CPU Scheduler
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 entscheided welcher Job ins weitere System (genauer gesagt in den Speicher) kommt. Die anderen Jobs verbleiben in dem 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 werden längeren vorgezogen. Der Admission Scheduler kann dabei auch Jobs welche später kommen 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. Nachdem 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, wieviele 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 das der Job auf die HD ausgelagert wurde?
- Wieviel 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.
