Zum Inhalt springen

Shortest-Job-Next

aus Wikipedia, der freien Enzyklopädie

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.<ref name="ostep-1">{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau|Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau: }}{{#if:|{{#if:Operating Systems: Three Easy Pieces|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Operating Systems: Three Easy Pieces}}]{{#if:PDF; 116 kB| (PDF; 116 kB)}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Operating Systems: Three Easy Pieces}}}}|[{{#invoke:URLutil|getNormalized|1=https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Operating Systems: Three Easy Pieces}}}}]}}{{#if:PDF; 116 kB| (PDF; 116 kB{{#if:Arpaci-Dusseau Books2014{{#if: 2021-01-09 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}} 

          | )
          | {{#if:{{#ifeq:de|de||{{#if:|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf}}%7C%7C}}}}{{#if:Operating Systems: Three Easy Pieces|{{#if:{{#invoke:WLink|isValidLinktext|1=Operating Systems: Three Easy Pieces|lines=0}}||}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: Arpaci-Dusseau Books| Arpaci-Dusseau Books{{#if: 2014|,|{{#if: 2021-01-09 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: 2014| {{#if:{{#invoke:DateTime|format|2014|noerror=1}}
            |{{#invoke:DateTime|format|2014|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=2014|class=Zitationswartung}} }}{{#if: |,|{{#if: 2021-01-09 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2021-01-09 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:2014Arpaci-Dusseau Books|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:51417||(?)}}}}}}{{#if: 2021-01-09|;}}}}{{#if: 2021-01-09| {{#if:2014Arpaci-Dusseau Books{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2021-01-09 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2021-01-09|class=Zitationswartung}} }} {{#invoke:DateTime|format|2021-01-09|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de|de||{{#if:|1}}}}|{{#if:Arpaci-Dusseau Books2014{{#if: 2021-01-09 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if:PDF; 116 kB | |  (}}
       }}{{#ifeq:{{#if:de|de|de}}|de||
          {{#invoke:Multilingual|format|{{{sprache}}}|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: 2014{{#if: 2021-01-09 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}} 

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref>

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

Prozess Ankunftszeit Dauer
A 0 4
B 2 7
C 3 6
D 9 2
E 16 1
Datei:Spn.svg
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 />

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Shortest-Job-Next&oldid=51417“