imported>Esther Phalcard: nicht präemptiv vs nicht-präemptiv verdeutlicht

2025-10-13T16:25:55Z

nicht präemptiv vs nicht-präemptiv verdeutlicht

Neue Seite

'''Shortest-Job-Next''' (SJN) oder '''Shortest-Job-First''' (SJF) ist ein [[Scheduling#Präemptive und nicht-präemptive Verfahren|nonpräemptives]] [[Prozess-Scheduler|Scheduling]]-Verfahren, das eingesetzt wird, um rechenwillige [[Thread (Informatik)|Threads]] oder/und [[Prozess (Informatik)|Prozesse]] auf die physischen [[Prozessor]]en des [[Computer|Rechners]] zu verteilen.<ref name="ostep-1">{{Internetquelle |autor=Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau |url=https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf |titel=Operating Systems: Three Easy Pieces |hrsg=Arpaci-Dusseau Books |datum=2014 |abruf=2021-01-09 |format=PDF; 116 kB}}</ref>

Abwandlungen dieses Scheduling-Verfahrens sind
* Shortest-Processing-Time ('''SPT''') auch bekannt als Shortest-Remaining-Time-Next ('''SRTN''')
::Dabei handelt es sich um eine [[Scheduling#Präemptive und nicht-präemptive Verfahren|präemptive]] Version von SJF
* Shortest-Process-Next ('''SPN''')
::Für interaktive Prozesse

Die Grundlage des SJF-Verfahrens ist eine Rangliste, ähnlich dem [[First In – First Out|FIFO]]-Verfahren. Hierbei wird die Länge des [[CPU-Burst]]s (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 [[First In – First Out|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äemptives Multitasking|präemptiv]] (dieser [[Algorithmus]] wird Shortest Remaining Time Next genannt) und nicht-präemptiv [[Implementierung|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 (Informatik)|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 ==

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

[[Datei:Spn.svg|links|mini|250px|Shortest Process Next, Beispiel]]

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 ==
<references />

[[Kategorie:Betriebssystemtheorie]]

Shortest-Job-Next - Versionsgeschichte

imported>Esther Phalcard: nicht präemptiv vs nicht-präemptiv verdeutlicht