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

⚡ Intelligente Zusammenfassung

Shortest Job First (SJF) ist ein CPU-Scheduling-Algorithmus, der den Prozess mit der kürzesten Ausführungszeit als nächsten auswählt. Er kann präemptiv oder nicht-präemptiv sein und reduziert die durchschnittliche Wartezeit für Prozesse erheblich.

️ Definition: Für die nächste Ausführung wird der Prozess mit der kürzesten Ausführungszeit ausgewählt.
🔀 Zwei Arten: SJF kann nicht-präemptiv oder präemptiv sein (Shortest Remaining Time First).
📉 Hauptvorteil: Es liefert die niedrigste durchschnittliche Wartezeit für eine gegebene Menge von Prozessen.
🏭 beste Verwendung: Ideal für Batch-Systeme, bei denen die Laufzeiten der Aufträge im Voraus bekannt sind.
❓ Hauptbeschränkung: Die benötigte Zeit für die Impulsabgabe muss im Voraus bekannt sein, was schwer vorherzusagen ist.
⚠️ Risiko: Langfristige Prozesse könnten ins Stocken geraten, wenn ständig kurze Aufträge eingehen.

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.
Dadurch kann der Prozessdurchsatz verbessert werden, indem sichergestellt wird, dass kürzere Aufträge zuerst ausgeführt werden, was möglicherweise zu einer kürzeren Bearbeitungszeit führt.
Es verbessert die Arbeitsleistung, indem es kürzere Aufträge anbietet, die zuerst ausgeführt werden sollen und meist eine kürzere Bearbeitungszeit haben.

Nichtpräventives SJF

Bei der nicht-präemptiven Ablaufplanung behält ein Prozess, sobald ihm ein CPU-Zyklus zugewiesen wurde, diesen so lange, bis er in einen Wartezustand gerät oder beendet wird.

Betrachten Sie die folgenden fünf Prozesse, von denen jeder seine eigene eindeutige Startzeit 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 t = 0 trifft P4 ein und beginnt mit der Ausführung.

Schritt 1) Zum Zeitpunkt t = 1 trifft Prozess P3 ein. Prozess P4 benötigt jedoch noch 2 Ausführungseinheiten zur Fertigstellung. Die Ausführung wird fortgesetzt.

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

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 t = 10 wird P2 ausgeführt, während sich P3 und P5 in der Warteschlange befinden.

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) Lassen Sie uns die durchschnittliche Wartezeit für das obige Beispiel berechnen.

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äemptiven SJF-Planung werden Aufträge in die Warteschlange gestellt, sobald sie eintreffen. Der Prozess mit der kürzesten Ausführungszeit beginnt. Trifft ein Prozess mit noch kürzerer Ausführungszeit ein, wird der aktuelle Prozess entfernt oder unterbrochen, und dem kürzeren Auftrag wird ein 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 t = 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 t = 1 trifft Prozess P3 ein. Da P4 jedoch eine kürzere Ausführungszeit hat, wird er seine Ausführung fortsetzen.

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 t = 5 trifft Prozess P2 ein. Die Ausführungszeiten von P1, P2, P3 und P5 werden verglichen. Prozess P2 wird ausgeführt, da seine Ausführungszeit am kürzesten ist. Prozess P5 wird unterbrochen.

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 t = 6 wird P2 ausgeführt.

Schritt 7) Zum Zeitpunkt t = 7 beendet Prozess P2 seine Ausführung. Die Ausführungszeiten von P1, P3 und P5 werden verglichen. Prozess P5 wird ausgeführt, da seine Ausführungszeit 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 t = 10 beendet Prozess P5 seine Ausführung. Die Ausführungszeiten von P1 und P3 werden verglichen. Prozess P1 wird ausgeführt, da seine Ausführungszeit kürzer ist.

Schritt 9) Zum Zeitpunkt t = 15 beendet Prozess P1 seine Ausführung. Prozess P3 ist der einzige verbleibende Prozess. Er wird nun mit der Ausführung beginnen.

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

Schritt 11) Lassen Sie uns die durchschnittliche Wartezeit für das obige Beispiel berechnen.

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 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 liefert die niedrigste durchschnittliche Wartezeit für eine bestimmte Menge 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.
Es ist wahrscheinlich hinsichtlich der durchschnittlichen Bearbeitungszeit optimal.

Nachteile/Nachteile von SJF

Hier sind einige 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 für 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 einer Unterversorgung, die die durchschnittliche Bearbeitungszeit nicht verkürzt.
Es ist schwierig, die Länge der bevorstehenden CPU-Anfrage zu bestimmen.
Die verstrichene Zeit sollte protokolliert werden, was zu einer höheren Prozessorlast führt.

Häufig gestellte Fragen

SRTF (Shortest Remaining Time First) ist im Prinzip die präemptive Variante von SJF. Bei SJF wird ein laufender Job beendet, bevor der nächste ausgewählt wird. Bei SRTF kann ein neu eintreffender Job mit kürzerer Restlaufzeit den laufenden Prozess unterbrechen.

SJF bevorzugt stets den kürzesten Prozess. Wenn ständig kurze Prozesse eintreffen, kann es passieren, dass ein langer Prozess nie die CPU erhält und unbegrenzt warten muss. Dies führt zu einer sogenannten „Starvation“. Um dies zu verhindern, wird die Priorität wartender Prozesse schrittweise erhöht.

Ja. SJF ist nachweislich optimal, da es die minimal mögliche durchschnittliche Wartezeit für eine gegebene Menge von Prozessen erzeugt. Dies trifft jedoch nur zu, wenn die Burst-Zeiten im Voraus bekannt sind, was in der Praxis selten möglich ist.

KI und maschinelles Lernen analysieren die Historie, Code-Merkmale und vergangene Ausführungen eines Prozesses, um dessen CPU-Burst-Zeit abzuschätzen. Bessere Vorhersagen machen SJF genauer und reduzieren die Wartezeit im Vergleich zu herkömmlichen Schätzungen mittels exponentieller Mittelwertbildung.

Möglicherweise. SJF hat Schwierigkeiten bei der kurzfristigen Planung, da die Spitzenzeiten unbekannt sind. KI, die Spitzenzeiten in Echtzeit vorhersagt, könnte SJF nutzbar machen, aber der Vorhersageaufwand und die Fehler müssen gering genug sein, damit die Planungsentscheidung sinnvoll bleibt.