Shortest Job First (SJF): Präventives, nicht präventives Beispiel

Was ist „Shortest Job First Scheduling“?

Kürzester Job zuerst (SJF) ist ein Algorithmus, bei dem der Prozess mit der kürzesten Ausführungszeit für die nächste Ausführung ausgewählt wird. Diese Planungsmethode kann präventiv oder nicht präemptiv sein. Dadurch wird die durchschnittliche Wartezeit für andere Prozesse, die auf die Ausführung warten, erheblich verkürzt. Die vollständige Form von SJF ist Shortest Job First.

Grundsätzlich gibt es zwei Arten von SJF-Methoden:

  • Nichtpräventives SJF
  • Präventives SJF

Merkmale der SJF-Planung

  • Sie ist jedem Auftrag als Zeiteinheit für die Fertigstellung zugeordnet.
  • Diese Algorithmusmethode ist hilfreich für die Stapelverarbeitung, bei der das Warten auf den Abschluss von Aufträgen nicht kritisch ist.
  • Es kann den Prozessdurchsatz verbessern, indem sichergestellt wird, dass kürzere Jobs zuerst ausgeführt werden und daher möglicherweise eine kurze Bearbeitungszeit haben.
  • Es verbessert die Auftragsleistung, indem es kürzere Aufträge anbietet, die zuerst ausgeführt werden sollten und meist eine kürzere Bearbeitungszeit haben.

Nichtpräventives SJF

Bei der nicht präventiven Planung hält der Prozess den CPU-Zyklus, sobald er einem Prozess zugewiesen wurde, bis er einen Wartezustand erreicht oder beendet wird.

Betrachten Sie Folgendeswing Fünf Prozesse, von denen jeder seine eigene einzigartige Burst- und Ankunftszeit hat.

Warteschlange verarbeiten Burst-Zeit Ankunftszeit
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Schritt 0) Zum Zeitpunkt = 0 trifft P4 ein und beginnt mit der Ausführung.

Nichtpräventives SJF

Schritt 1) Zum Zeitpunkt = 1 kommt Prozess P3 an. Für den Abschluss benötigt P4 jedoch noch zwei Ausführungseinheiten. Die Ausführung wird fortgesetzt.

Nichtpräventives SJF

Schritt 2) Zum Zeitpunkt =2 trifft Prozess P1 ein und wird zur Warteschlange hinzugefügt. P4 wird die Ausführung fortsetzen.

Nichtpräventives SJF

Schritt 3) Zum Zeitpunkt = 3 beendet Prozess P4 seine Ausführung. Die Burst-Zeit von P3 und P1 wird verglichen. Prozess P1 wird ausgeführt, da seine Burst-Zeit im Vergleich zu P3 kürzer ist.

Nichtpräventives SJF

Schritt 4) Zum Zeitpunkt = 4 trifft Prozess P5 ein und wird zur Warteschlange hinzugefügt. P1 setzt die Ausführung fort.

Nichtpräventives SJF

Schritt 5) Zum Zeitpunkt = 5 trifft Prozess P2 ein und wird zur Warteschlange hinzugefügt. P1 setzt die Ausführung fort.

Nichtpräventives SJF

Schritt 6) Zum Zeitpunkt = 9 beendet Prozess P1 seine Ausführung. Die Burst-Zeit von P3, P5 und P2 wird verglichen. Prozess P2 wird ausgeführt, weil seine Burst-Zeit am niedrigsten ist.

Nichtpräventives SJF

Schritt 7) Zum Zeitpunkt = 10 wird P2 ausgeführt und P3 und P5 befinden sich in der Warteschlange.

Nichtpräventives SJF

Schritt 8) Zum Zeitpunkt = 11 beendet Prozess P2 seine Ausführung. Die Burst-Zeit von P3 und P5 wird verglichen. Prozess P5 wird ausgeführt, da seine Burst-Zeit geringer ist.

Nichtpräventives SJF

Schritt 9) Zum Zeitpunkt = 15 beendet Prozess P5 seine Ausführung.

Nichtpräventives SJF

Schritt 10) Zum Zeitpunkt = 23 beendet Prozess P3 seine Ausführung.

Nichtpräventives SJF

Schritt 11) Berechnen wir die durchschnittliche Wartezeit für das obige Beispiel.

Wait time 
P4= 0-0=0
P1=  3-2=1
P2= 9-5=4
P5= 11-4=7
P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2

Präventives SJF

Bei der präventiven SJF-Planung werden Aufträge bei Eingang in die Bereitschaftswarteschlange gestellt. Ein Prozess mit der kürzesten Burst-Zeit beginnt mit der Ausführung. Wenn ein Prozess mit noch kürzerer Burst-Zeit eintrifft, wird der aktuelle Prozess entfernt oder von der Ausführung ausgeschlossen und dem kürzeren Job wird der CPU-Zyklus zugewiesen.

Betrachten Sie Folgendeswing fünf Prozess:

Warteschlange verarbeiten Burst-Zeit Ankunftszeit
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Schritt 0) Zum Zeitpunkt = 0 trifft P4 ein und beginnt mit der Ausführung.

Warteschlange verarbeiten Burst-Zeit Ankunftszeit
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Präventives SJF

Schritt 1) Zum Zeitpunkt = 1 kommt Prozess P3 an. P4 hat jedoch eine kürzere Burst-Zeit. Die Ausführung wird fortgesetzt.

Präventives SJF

Schritt 2) Zum Zeitpunkt = 2 kommt Prozess P1 mit Burst-Zeit = 6 an. Die Burst-Zeit ist länger als die von P4. Daher wird P4 die Ausführung fortsetzen.

Präventives SJF

Schritt 3) Zum Zeitpunkt = 3 beendet Prozess P4 seine Ausführung. Die Burst-Zeit von P3 und P1 wird verglichen. Prozess P1 wird ausgeführt, da seine Burst-Zeit geringer ist.

Präventives SJF

Schritt 4) Zum Zeitpunkt = 4 kommt der Prozess P5. Die Burst-Zeit von P3, P5 und P1 wird verglichen. Prozess P5 wird ausgeführt, weil seine Burst-Zeit am niedrigsten ist. Prozess P1 wird vorbelegt.

Warteschlange verarbeiten Burst-Zeit Ankunftszeit
P1 5 von 6 sind übrig 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Präventives SJF

Schritt 5) Zum Zeitpunkt = 5 kommt Prozess P2. Die Burst-Zeit von P1, P2, P3 und P5 wird verglichen. Prozess P2 wird ausgeführt, weil seine Burst-Zeit am kürzesten ist. Prozess P5 wird vorgezogen.

Warteschlange verarbeiten Burst-Zeit Ankunftszeit
P1 5 von 6 sind übrig 2
P2 2 5
P3 8 1
P4 3 0
P5 3 von 4 sind übrig 4

Präventives SJF

Schritt 6) Zum Zeitpunkt =6 wird P2 ausgeführt.

Präventives SJF

Schritt 7) Zum Zeitpunkt =7 beendet P2 seine Ausführung. Die Burst-Zeit von P1, P3 und P5 wird verglichen. Prozess P5 wird ausgeführt, da seine Burst-Zeit kürzer ist.

Warteschlange verarbeiten Burst-Zeit Ankunftszeit
P1 5 von 6 sind übrig 2
P2 2 5
P3 8 1
P4 3 0
P5 3 von 4 sind übrig 4

Präventives SJF

Schritt 8) Zum Zeitpunkt =10 beendet P5 seine Ausführung. Die Burst-Zeit von P1 und P3 wird verglichen. Prozess P1 wird ausgeführt, da seine Burst-Zeit kürzer ist.

Präventives SJF

Schritt 9) Zum Zeitpunkt =15 beendet P1 seine Ausführung. P3 ist der einzige verbleibende Prozess. Die Ausführung wird gestartet.

Präventives SJF

Schritt 10) Zum Zeitpunkt =23 beendet P3 seine Ausführung.

Präventives SJF

Schritt 11) Berechnen wir die durchschnittliche Wartezeit für das obige Beispiel.

Wait time 
P4= 0-0=0
P1=  (3-2) + 6 =7
P2= 5-5 = 0
P5= 4-4+2 =2
P3= 15-1 = 14
Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6

Vorteile von SJF

Hier sind die Vorteile/Vorteile der Verwendung der SJF-Methode:

  • SJF wird häufig für die langfristige Planung verwendet.
  • Es reduziert die durchschnittliche Wartezeit im Vergleich zum FIFO-Algorithmus (First in First Out).
  • Die SJF-Methode bietet die niedrigste durchschnittliche Wartezeit für eine bestimmte Gruppe von Prozessen.
  • Dies eignet sich für Jobs, die im Stapelbetrieb ausgeführt werden und bei denen die Laufzeiten im Voraus bekannt sind.
  • Für das Batch-System der Langzeitplanung kann eine Schätzung der Burst-Zeit aus der Stellenbeschreibung entnommen werden.
  • Für die kurzfristige Planung müssen wir den Wert des nächsten Burst-Zeitpunkts vorhersagen.
  • Wahrscheinlich optimal im Hinblick auf die durchschnittliche Bearbeitungszeit.

Nachteile/Nachteile von SJF

Hier sind einige Nachteile/Nachteile des SJF-Algorithmus:

  • Der Zeitpunkt der Auftragserfüllung muss früher bekannt sein, ist aber schwer vorherzusagen.
  • Es wird häufig in einem Batch-System für die langfristige Planung verwendet.
  • SJF kann nicht implementiert werden CPU-Planung kurzfristig. Dies liegt daran, dass es keine spezifische Methode zur Vorhersage der Länge des bevorstehenden CPU-Bursts gibt.
  • Dieser Algorithmus kann zu sehr langen Bearbeitungszeiten oder Hunger führen.
  • Erfordert Kenntnisse darüber, wie lange ein Prozess oder Job ausgeführt wird.
  • Dies führt zu einem Mangel, der die durchschnittliche Bearbeitungszeit nicht verkürzt.
  • Es ist schwierig, die Länge der bevorstehenden CPU-Anfrage zu bestimmen.
  • Die verstrichene Zeit sollte aufgezeichnet werden, da dies zu einer höheren Belastung des Prozessors führt.

Zusammenfassung

  • SJF ist ein Algorithmus, bei dem der Prozess mit der kürzesten Ausführungszeit für die nächste Ausführung ausgewählt wird.
  • SJF Scheduling ist jedem Auftrag als Zeiteinheit für die Fertigstellung zugeordnet.
  • Diese Algorithmusmethode ist hilfreich für die Stapelverarbeitung, bei der das Warten auf den Abschluss von Aufträgen nicht kritisch ist.
  • Grundsätzlich gibt es zwei Arten von SJF-Methoden: 1) Nicht-präventives SJF und 2) Präventives SJF.
  • Bei der nicht präventiven Planung hält der Prozess den CPU-Zyklus, sobald er einem Prozess zugewiesen wurde, bis er einen Wartezustand erreicht oder beendet wird.
  • Bei der präventiven SJF-Planung werden Aufträge bei Eingang in die Bereitschaftswarteschlange gestellt.
  • Obwohl ein Prozess mit kurzer Burst-Zeit beginnt, wird der aktuelle Prozess entfernt oder von der Ausführung ausgeschlossen, und der Job, der kürzer ist, wird zuerst ausgeführt.
  • SJF wird häufig für die langfristige Planung verwendet.
  • Es reduziert die durchschnittliche Wartezeit im Vergleich zum FIFO-Algorithmus (First in First Out).
  • Bei der SJF-Planung muss der Zeitpunkt der Auftragserfüllung früher bekannt sein, ist aber schwer vorherzusagen.
  • SJF kann kurzfristig nicht für die CPU-Planung implementiert werden. Dies liegt daran, dass es keine spezifische Methode zur Vorhersage der Länge des bevorstehenden CPU-Bursts gibt.