SJF-Wartezeit
Wartezeit bei Shortest Job First — nach Sortierung nach Bedienzeit identisch zu FCFS: Summe der Bedienzeiten aller kürzeren Prozesse.
SJF-Wartezeit berechnen
Wartezeit bei Shortest Job First — nach Sortierung nach Bedienzeit identisch zu FCFS: Summe der Bedienzeiten aller kürzeren Prozesse.
Worum geht es?
Shortest Job First (SJF) sortiert die Prozesse nach ihrer Bedienzeit aufsteigend und bedient zuerst den kürzesten Job. Nach der Sortierung ist die Berechnung der Wartezeit identisch zu FCFS — nur eben mit den nun geordneten Bedienzeiten.
SJF erreicht nachweislich die minimale durchschnittliche Wartezeit aller nicht-präemptiven Strategien, setzt aber voraus, dass die Bedienzeit im Voraus bekannt (oder gut geschätzt) ist.
Die Formel
Wartezeit = SummeKuerzererJobsDie Variablen
| Symbol | Bedeutung | Einheit | Erklärung |
|---|---|---|---|
| SummeKuerzererJobs | Summe kürzerer Jobs | ms | Summe der Bedienzeiten aller kürzeren Prozesse. |
| Wartezeit | Wartezeit | ms | Wartezeit dieses Prozesses nach Sortierung. |
Minimal-Beispiel
Drei Jobs mit Bedienzeit 3, 5, 8 ms — Wartezeit des längsten Jobs.
Wartezeit = 3 + 5 = 8 msPraxis-Beispiele
Beispiel 1 — Klassisches Schulbuch-Beispiel
Bedienzeiten: P1 = 6, P2 = 8, P3 = 7, P4 = 3 → sortiert: P4, P1, P3, P2.
Wartezeit(P4) = 0
Wartezeit(P1) = 3
Wartezeit(P3) = 3 + 6 = 9
Wartezeit(P2) = 3 + 6 + 7 = 16Beispiel 2 — Vergleich FCFS vs. SJF
Bedienzeiten in Ankunftsreihenfolge: 100, 1, 1, 1.
FCFS: Ø Wartezeit = (0 + 100 + 101 + 102) / 4 = 75,75 ms
SJF: Ø Wartezeit = (0 + 1 + 2 + 3) / 4 = 1,50 msBeispiel 3 — Starvation-Risiko
Lange Jobs können bei kontinuierlich eintreffenden kurzen Jobs verhungern — Aging als Gegenmaßnahme verschiebt sie schrittweise nach vorn.
effektiveBedienzeit = Bedienzeit − Aging · Wartezeit