Shortest-Processing-Time

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.

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. Dem gegenü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 nennt sich dann Shortest Remaining Time Next) 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 preämtive Shortest-Remaing-Time, das auf Shortest-Process-Next basiert.

Beispiel

Prozess	Ankunftszeit	Dauer
A	0	4
B	2	7
C	3	6
D	9	2
E	16	1

Shortest Process Next, Beispiel

Beim fünften Abarbeitungsschritt stehen Prozess B und C 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.