Zu Beginn erfolgt eine kurze Übersicht über Programme, Prozesse und Threads und ihren Zusammenhang zur Arbeit des Schedulers.
Ein Programm ist eine Kombination aus Instruktionen und Daten die gemeinsam eine Aufgabe ausführen. Es handelt sich dabei um Maschinencode der sequentiell vom Prozessor abgearbeitet werden kann.
Ein Prozess ist ein laufendes Programm mit zusätzliches Statusinformationen.
Diese umfassen benutzte Variablen, Register und Adressräume sowie den Program
Counter, der den Fortschritt in einem Programm verfolgt
Dies ist der Gegenstand, mit dem sich Scheduler beschäftigen. In pre-emptiven
Betriebssystemen wie Linux, können Prozesse durch andere Prozesse unterbrochen
werden. In diesem Fall wird ein Kontext-Wechsel durchgeführt, beidem sämtliche
Statusinformationen gespeichert werden und die Betriebszustände des unterbrechenden
Prozesses wieder hergestellt werden.
Der Scheduler als solcher ist ein eigenständiger Prozess, der periodisch
ausgeführt wird.
Threads sind nebenläufige Ablauffäden in Programmen. Sie teilen sich
meist gleiche Speicherbereiche, haben jedoch jeweils einen eigenen Program Counter.
Daher werden sie im Linux Scheduler und im Folgenden auch als Prozesse betrachtet,
da sie genauso unterbrochen werden können und verwaltet werden müssen.
Prozesse und Threads können Eltern-Kind-Beziehungen haben, die ihre Abhängigkeit
voneinander ausdrückt. Stirbt ein Elternprozess, werden auch alle seine
Kindprozesse beendet.
Prozesse tendieren dazu entweder E/A lastig oder CPU-fressend zu sein.
Die einen brauchen den Prozesser nur, um Daten von externen Kanälen anzufragen
und verbringe die meiste Laufzeit mit Warten auf die angeforderten Daten. Externe
Kanäle können Festspeicher, Netzwerke oder Eingabegeräte sein.
Die anderen benutzen den Prozessor primär um Berechnungen durchzuführen
und ihn damit auszulasten.
In der Liste der wartenden Prozesse sollten diejenigen bevorzugt werden, die
einerseits nicht lange Rechnen werden und andererseits viel Zeit mit Warten
verbringen. In der Wartezeit können dann Prozesse mit rechenintensiven
Aufgaben ausgeführt werden.
Festplattenzugriffe bewegen sich im milli-Sekunden bereich (10-3s),
wohingehen aktuelle Server- und Workstation Prozessoren im GHz Bereich getaktet
sind (10-9s/tick). Daraus ergibt sich ein Faktor von 1.000.000 oder
ebensoviele CPU-Ticks die in jeder milli-Sekunde Wartezeit von anderen Prozessen
genutzt werden können.