Shortest-Job-Next
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 Burstgeschätzt(n + 1) = α · Burstgemessen(n) + (1 − α) · Burstgeschä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.
Beispiel
[Bearbeiten | Quelltext bearbeiten]| Prozess | Ankunftszeit | Dauer |
| A | 0 | 4 |
| B | 2 | 7 |
| C | 3 | 6 |
| D | 9 | 2 |
| E | 16 | 1 |
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.
Einzelnachweise
[Bearbeiten | Quelltext bearbeiten]- ↑ 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.