Shortest-Job-First

SJF ist ein Schedulingverfahren, das vom Scheduler eingesetzt wird, um rechenwillige Threads auf die physikalischen Prozessoren des Rechners zu verteilen.

Die Grundlage des SJF-Verfahrens ist eine Rangliste, ähnlich dem FCFS-Verfahren. Hierbei wird die Länge des CPU-Bursts (Rechenzeit) zur Bestimmung der Rangfolge herangezogen. Threads mit einer kurzen Burstlänge werden den längeren vorgezogen. Folglich kann es zu dem Problem führen, dass ein Thread mit einem langen CPU-Burst fast nie zum Zuge kommt. Allerdings stößt man leicht auf derartige Probleme, sobald man Prioritäten bildet. Sind mehrere CPU-Bursts gleich lang, kommt es dem FCFS-Verfahren gleich.

Gegenüber dem FCFS-Verfahren hat SJF den Vorteil, dass es den nachteiligen Konvoi-Effekt vermeidet. Weiterhin lässt es sich beweisen, dass SJF die Wartezeit auf ein Optimum bringt. Dem gegenüber steht ein großer Nachteil; es ist praktisch nicht implementierbar, da die CPU-Burstlängen unbekannt sind. Man ist allerdings in der Lage eine Annäherung zu implementieren.

Hinter der Approximation des SJF Verfahrens steckt eine simple Idee. Da die Länge des künftigen CPU-Bursts nicht bekannt ist, kann man beobachten wie sich der Thread in der Vergangenheit verhalten hat, in der Hoffnung er wird sich in der Zukunft ähnlich verhalten.

Dabei ist Mit der Veränderlichen α lässt sich die Gewichtung der vergangenen Messungen festlegen. Werte nahe der 1 weisen der Vergangenheit einen geringen Stellenwert zu.

SJF lässt sich präemptiv und nicht präemptiv implementieren. Wobei bei der nicht präemptiven Implementierung der Threadwechsel erst nach einer freiwilligen Abgabe durch den Thread selber oder nach einer blockierenden Operation (z.B. E/A) stattfindet.