Was ist die kürzeste Job-First-Planung?
Shortest Job First (SJF) ist ein Algorithmus, bei dem der Prozess mit der geringsten Ausführungszeit für die nächste Ausführung ausgewählt wird. Diese Planungsmethode kann präemptiv oder nicht präemptiv sein. Dies reduziert die durchschnittliche Wartezeit für andere Prozesse, die auf die Ausführung warten, erheblich. Die vollständige Form von SJF ist Shortest Job First.
Grundsätzlich gibt es zwei Arten von SJF-Methoden:
- Nicht präventive SJF
- Präventive SJF
In diesem Tutorial zum Betriebssystem lernen Sie:
- Was ist die kürzeste Job-First-Planung?
- Merkmale der SJF-Planung
- Nicht präventive SJF
- Präventive SJF
- Vorteile von SJF
- Nachteile / Nachteile von SJF
Merkmale der SJF-Planung
- Es ist jedem Auftrag als Zeiteinheit zugeordnet.
- Diese Algorithmusmethode ist hilfreich für die Stapelverarbeitung, bei der das Warten auf den Abschluss von Jobs 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 Jobausgabe, indem kürzere Jobs angeboten werden, die zuerst ausgeführt werden sollten und meist eine kürzere Bearbeitungszeit haben.
Nicht präventive SJF
Bei der nicht präemptiven Planung hält der Prozess den CPU-Zyklus, sobald er dem Prozess zugewiesen ist, so lange, bis er einen Wartezustand erreicht oder beendet wird.
Betrachten Sie die folgenden fünf Prozesse, von denen jeder seine eigene eindeutige Burst- und Ankunftszeit hat.
| Prozesswarteschlange | Burst-Zeit | Ankunftszeit |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Schritt 0) Zum Zeitpunkt = 0 kommt P4 an und startet die Ausführung.
Schritt 1) Zum Zeitpunkt = 1 kommt der Prozess P3 an. P4 benötigt jedoch noch 2 Ausführungseinheiten, um abgeschlossen zu werden. Die Ausführung wird fortgesetzt.
Schritt 2) Zum Zeitpunkt = 2 kommt der Prozess P1 an und wird zur Warteschlange hinzugefügt. P4 setzt die Ausführung fort.
Schritt 3) Zum Zeitpunkt = 3 beendet der Prozess P4 seine Ausführung. Die Burst-Zeit von P3 und P1 wird verglichen. Der Prozess P1 wird ausgeführt, weil seine Burst-Zeit im Vergleich zu P3 kürzer ist.
Schritt 4) Zum Zeitpunkt = 4 kommt der Prozess P5 an und wird zur Warteschlange hinzugefügt. P1 setzt die Ausführung fort.
Schritt 5) Zum Zeitpunkt = 5 kommt der Prozess P2 an und wird zur Warteschlange hinzugefügt. P1 setzt die Ausführung fort.
Schritt 6) Zum Zeitpunkt = 9 beendet der Prozess P1 seine Ausführung. Die Burst-Zeit von P3, P5 und P2 wird verglichen. Der 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 der Prozess P2 seine Ausführung. Die Burst-Zeit von P3 und P5 wird verglichen. Der Prozess P5 wird ausgeführt, weil seine Burst-Zeit kürzer ist.
Schritt 9) Zum Zeitpunkt = 15 beendet der Prozess P5 seine Ausführung.
Schritt 10) Zum Zeitpunkt = 23 beendet der Prozess P3 seine Ausführung.
Schritt 11) Berechnen wir die durchschnittliche Wartezeit für das obige Beispiel.
Wait timeP4= 0-0=0P1= 3-2=1P2= 9-5=4P5= 11-4=7P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2
Präventive SJF
In Preemptive SJF Scheduling werden Jobs sofort 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:
| Prozesswarteschlange | Burst-Zeit | Ankunftszeit |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Schritt 0) Zum Zeitpunkt = 0 kommt P4 an und startet die Ausführung.
| Prozesswarteschlange | Burst-Zeit | Ankunftszeit |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Schritt 1) Zum Zeitpunkt = 1 kommt der Prozess P3 an. P4 hat jedoch eine kürzere Burst-Zeit. Die Ausführung wird fortgesetzt.
Schritt 2) Zum Zeitpunkt = 2 kommt der Prozess P1 mit der 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 der Prozess P4 seine Ausführung. Die Burst-Zeit von P3 und P1 wird verglichen. Der Prozess P1 wird ausgeführt, weil seine Burst-Zeit kürzer ist.
Schritt 4) Zum Zeitpunkt = 4 kommt der Prozess P5 an. Die Burst-Zeit von P3, P5 und P1 wird verglichen. Der Prozess P5 wird ausgeführt, weil seine Burst-Zeit am niedrigsten ist. Prozess P1 ist vorbelegt.
| Prozesswarteschlange | Burst-Zeit | Ankunftszeit |
| P1 | 5 von 6 sind noch übrig | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Schritt 5) Zum Zeitpunkt = 5 kommt der Prozess P2 an. Die Burst-Zeit von P1, P2, P3 und P5 wird verglichen. Der Prozess P2 wird ausgeführt, weil seine Burst-Zeit am geringsten ist. Prozess P5 ist ausgeschlossen.
| Prozesswarteschlange | Burst-Zeit | Ankunftszeit |
| P1 | 5 von 6 sind noch übrig | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 von 4 bleiben übrig | 4 |
Schritt 6) Zur Zeit = 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. Der Prozess P5 wird ausgeführt, weil seine Burst-Zeit kürzer ist.
| Prozesswarteschlange | Burst-Zeit | Ankunftszeit |
| P1 | 5 von 6 sind noch übrig | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 von 4 bleiben übrig | 4 |
Schritt 8) Zum Zeitpunkt = 10 beendet P5 seine Ausführung. Die Burst-Zeit von P1 und P3 wird verglichen. Der Prozess P1 wird ausgeführt, weil 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 timeP4= 0-0=0P1= (3-2) + 6 =7P2= 5-5 = 0P5= 4-4+2 =2P3= 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 gegenüber dem FIFO-Algorithmus (First in First Out).
- Die SJF-Methode gibt die niedrigste durchschnittliche Wartezeit für einen bestimmten Satz von Prozessen an.
- Dies ist für Jobs im Batch geeignet, bei denen die Laufzeiten im Voraus bekannt sind.
- Für das Batch-System der Langzeitplanung kann eine Burst-Zeitschätzung aus der Jobbeschreibung erhalten werden.
- Für die kurzfristige Planung müssen wir den Wert der nächsten Burst-Zeit vorhersagen.
- Wahrscheinlich optimal in Bezug auf die durchschnittliche Bearbeitungszeit.
Nachteile / Nachteile von SJF
Hier sind einige Nachteile / Nachteile des SJF-Algorithmus:
- Die Auftragsabschlusszeit muss früher bekannt sein, ist jedoch schwer vorherzusagen.
- Es wird häufig in einem Batch-System für die langfristige Planung verwendet.
- SJF kann kurzfristig nicht für die CPU-Planung implementiert werden. Dies liegt daran, dass es keine spezifische Methode gibt, um die Länge des bevorstehenden CPU-Bursts vorherzusagen.
- Dieser Algorithmus kann sehr lange Durchlaufzeiten oder Hunger verursachen.
- Erfordert Kenntnisse darüber, wie lange ein Prozess oder Job ausgeführt wird.
- Dies führt zu einem Hunger, der die durchschnittliche Bearbeitungszeit nicht verkürzt.
- Es ist schwer, die Länge der bevorstehenden CPU-Anforderung zu kennen.
- Die verstrichene Zeit sollte aufgezeichnet werden, was zu einem höheren Overhead für den Prozessor führt.
Zusammenfassung
- SJF ist ein Algorithmus, bei dem der Prozess mit der kleinsten Ausführungszeit für die nächste Ausführung ausgewählt wird.
- Die SJF-Planung ist jedem Auftrag als Zeiteinheit zugeordnet.
- Diese Algorithmusmethode ist hilfreich für die Stapelverarbeitung, bei der das Warten auf den Abschluss von Jobs 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äemptiven Planung hält der Prozess den CPU-Zyklus, sobald er dem Prozess zugewiesen ist, so lange, bis er einen Wartezustand erreicht oder beendet wird.
- In Preemptive SJF Scheduling werden Jobs sofort 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 kürzere Job wird zuerst ausgeführt.
- SJF wird häufig für die langfristige Planung verwendet.
- Es reduziert die durchschnittliche Wartezeit gegenüber dem FIFO-Algorithmus (First in First Out).
- Bei der SJF-Planung muss die Jobabschlusszeit früher bekannt sein, sie ist jedoch schwer vorherzusagen.
- SJF kann kurzfristig nicht für die CPU-Planung implementiert werden. Dies liegt daran, dass es keine spezifische Methode gibt, um die Länge des bevorstehenden CPU-Bursts vorherzusagen.