Shortest-Job-Next

Shortest-Job-Next

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 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 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 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


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.


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Shortest job next — (SJN) (also known as Shortest Job First (SJF)) is a scheduling policy that selects the waiting process with the smallest execution time to execute next.Shortest job next is advantageous because of its simplicity and because it maximizes process… …   Wikipedia

  • Shortest-Process-Next — 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… …   Deutsch Wikipedia

  • 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… …   Deutsch Wikipedia

  • Shortest remaining time — is a method of CPU scheduling that is a preemptive version of shortest job next scheduling. In this scheduling algorithm, the process with the smallest amount of time remaining until completion is selected to execute. Since the currently… …   Wikipedia

  • 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… …   Deutsch Wikipedia

  • Shortest-Remaining-Time — Ein Prozess Scheduler (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, der die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt. Prozess Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non …   Deutsch Wikipedia

  • Highest response ratio next — (HRRN) scheduling is a non preemptive discipline, similar to Shortest Job Next (SJN), in which the priority of each job is dependent on its estimated run time, and also the amount of time it has spent waiting. Jobs gain higher priority the longer …   Wikipedia

  • Highest Response Ratio Next — Das nicht präemptive Scheduling Verfahren Highest Response Ratio Next (HRRN) weist dem Prozessor immer den Prozess mit der höchsten Response ratio zu. Dieser Quotient berechnet sich wie folgt: Hinweis: Bei den zu verwendenden Zeiten handelt es… …   Deutsch Wikipedia

  • Holland's Next Top Model, Cycle 2 — Infobox Television show name = Holland s Next Top Model, Cycle 2 caption = Promotional photograph of the cast of Cycle 2 of Holland s Next Top Model format = Reality television runtime = 60 minutes creator = Tyra Banks developer = Kenya Barris… …   Wikipedia

  • Australia's Next Top Model, Cycle 4 — Infobox Television show name = Australia s Next Top Model Cycle 4 caption = From left to right: Samantha, Belinda, Emma, Alexandra, Kristy, Rebecca, Alyce, Demelza, Kamila, Alamela, Leiden, Jamie, Caris. picture format = 576i (SDTV) audio format …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”