Shortest-Job-Next (SJN) oder Shortest-Job-First (SJF) ist ein nonpräemptives Scheduling-Verfahren, das eingesetzt wird, um rechenwillige Threads oder/und Prozesse auf die physischen Prozessoren des Rechners zu verteilen.^[1]

Abwandlungen dieses Scheduling-Verfahrens sind

• Shortest-Processing-Time (SPT) auch bekannt als Shortest-Remaining-Time-Next (SRTN)

Dabei handelt es sich um eine präemptive Version von SJF

• Shortest-Process-Next (SPN)

Für interaktive Prozesse

Die Grundlage des SJF-Verfahrens ist eine Rangliste, ähnlich dem FIFO-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. Demgegenüber steht der große Nachteil, dass das Verfahren praktisch nicht implementierbar ist, da die CPU-Burstlängen in der Regel unbekannt sind. Allerdings sind näherungsweise Implementierungen möglich.

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 ein Thread in der Vergangenheit verhalten hat, in der Hoffnung, er wird sich in der Zukunft ähnlich verhalten.

Dabei ist Burst_geschätzt(n + 1) = α · Burst_gemessen(n) + (1 − α) · Burst_geschätzt(n) 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 (dieser Algorithmus wird Shortest Remaining Time Next genannt) 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) bzw. durch Ablauf der Lebensbedingung des Threads oder/und Prozesses stattfindet. D. h., es findet keine automatische Unterbrechung wie z. B. bei Round-Robin-Verfahren statt.

SJF kann auch für interaktive Prozesse abgewandelt werden. Man spricht dann vom Shortest-Process-Next. Als Alternative gibt es das präemptive Shortest-Remaing-Time, das auf Shortest-Process-Next basiert.

Beim fünften Abarbeitungsschritt ist Prozess A abgeschlossen und es stehen Prozess B und C zur Auswahl bereit. Da C nur 6 Schritte, B jedoch 7 Schritte zur Fertigstellung benötigt, wird C zuerst ausgeführt.

Zu Zeitpunkt 11 wird der nur 2 Schritte lange Prozess D dem 7 Schritte Prozess B vorgezogen.

Zu Zeitpunkt 13 sind Prozesse A, C und D abgearbeitet. Prozess E gibt es noch nicht, so dass Prozess B ausgeführt werden kann.

1. ↑ Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau: Operating Systems: Three Easy Pieces. (PDF; 116 kB) Arpaci-Dusseau Books, 2014, abgerufen am 9. Januar 2021.