Shortest Job First (SJF): Präventives, nicht präventives Beispiel
Nathaniel Brooks
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 die folgenden fünf Prozesse, von denen jeder seine eigene Burst-Zeit 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.
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.
Schritt 2) Zum Zeitpunkt =2 trifft Prozess P1 ein und wird zur Warteschlange hinzugefügt. P4 wird die Ausführung fortsetzen.
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.
Schritt 4) Zum Zeitpunkt = 4 trifft Prozess P5 ein und wird zur Warteschlange hinzugefügt. P1 setzt die Ausführung fort.
Schritt 5) Zum Zeitpunkt = 5 trifft Prozess P2 ein und wird zur Warteschlange hinzugefügt. P1 setzt die Ausführung fort.
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.
Schritt 7) Zum Zeitpunkt = 10 wird P2 ausgeführt und P3 und P5 befinden sich in der Warteschlange.
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.
Schritt 9) Zum Zeitpunkt = 15 beendet Prozess P5 seine Ausführung.
Schritt 10) Zum Zeitpunkt = 23 beendet Prozess P3 seine Ausführung.
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 die folgenden fünf Prozesse:
| 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 |
Schritt 1) Zum Zeitpunkt = 1 kommt Prozess P3 an. P4 hat jedoch eine kürzere Burst-Zeit. Die Ausführung wird fortgesetzt.
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.
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.
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 |
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 |
Schritt 6) Zum Zeitpunkt =6 wird P2 ausgeführt.
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 |
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.
Schritt 9) Zum Zeitpunkt =15 beendet P1 seine Ausführung. P3 ist der einzige verbleibende Prozess. Die Ausführung wird gestartet.
Schritt 10) Zum Zeitpunkt =23 beendet P3 seine Ausführung.
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.
