· 

Shortest Job First (SJF)

1. Einführung

Insbesondere bei der Kombination von I/O-Prozessen, die für gewöhnlich kurze Bedienzeiten und häufige Auftritte haben, und Langläufern zur Auführung rechenintensiver Aufgaben, ist FCFS ein ineffizientes Verfahren. Schließlich werden dabei Prozesse mit kurzen Bedienzeiten benachteiligt. Eine Lösung für dieses Problem ist der Scheduling-Algorithmus Shortes Job First (SJF), der ebenfalls zu den nicht-präemptiven Scheduling-Verfahren zählt.

2. Der Algorithmus

Alle CPU-anfordernden Prozesse \(P_1, P_2, ..., P_n\) werden zunächst in eine Warteschlange eingeordnet und gemäß ihren Bedienzeiten (geringste Bedienzeit zuerst) sortiert. Wenn zwei oder mehr Prozesse dieselbe Bedienzeit besitzen, kann FCFS angewendet werden. Für die Implementierung kann man bspw. eine sortierte Liste verwenden, bei der die Entnahme des nächsten Prozesses in konstanter Zeit möglich ist. Allerdings muss diese Liste immer wieder neu sortiert werden, was im Falle der Verwendung eines Heaps in logarithmischer Laufzeitkomplexität \(\mathcal{O}(\log (n))\) möglich ist, wobei \(n\in\mathbb{N}\) die Anzahl der Prozesse ist.

3. Beispiel

Nehmen wir als Beispiel die folgenden Prozesse mit den entsprechenden Bedienzeiten bzw. CPU-Bursts: $$ \begin{array}{|c|c|c|c|c|c|c|}\hline \text{Prozess}&P_1&P_2&P_3&P_4&P_5 \\\hline \text{CPU-Burst (s)}&42&5&8&10&6 \\\hline \end{array} $$ Die Prozesse werden gemäß ihren CPU-Bursts aufsteigend sortiert: zuerst kommt \(P_2\), dann \(P_5\), dann \(P_3\), dann \(P_4\) und zum Schluss \(P_1\). \(P_2\) arbeitet seine \(5\) Sekunden ab. Danach ist \(P_5\) mit seinen \(6\) Sekunden an der Reihe. Anschließend folgen noch \(P_3\) mit \(8\) und \(P_4\) mit \(10\) Sekunden. Dem Prozess \(P_1\), der am längsten zur Abarbeitung seines Tasks benötigt, werden abschließend seine \(42\) Sekunden auf der CPU gewährt.

4. Berechnung der durchschnittlichen  Wartezeit

Die durchschnittliche Wartezeit wird berechnet, indem man die Startzeiten der jeweiligen Prozesse addiert und durch die Anzahl der Prozesse teilt. Durch die Sortierung der Prozesse \(P_1\) bis \(P_5\) gemäß ihren CPU-Bursts ergibt sich für die einzelnen Wartezeiten:
  • \(P_2\Longrightarrow 0s\)
  • \(P_5\Longrightarrow (0+5)s=5s\)
  • \(P_3\Longrightarrow (5+6)s=11s\)
  • \(P_4\Longrightarrow (11+8)s=19s\)
  • \(P_1\Longrightarrow (19+10)s=29s\)
Daraus foglt für die durchschnittliche Wartezeit also: $$ \frac{(0+5+11+19+29)s}{5}=12.8s $$ Man kann mathematisch beweisen, dass SJF bei bekannten CPU-Bursts die mittlere Wartezeit der Prozesse minimiert. Das liegt daran, dass bei \(n\) Prozessen die geringste Wartezeit auf \(n-1\) Prozesse, die zweitgeringste auf \(n-2\) Prozesse, die drittgeringste auf \(n-3\) Prozesse und die längste Wartezeit (die des zuletzt ausgeführten Prozesses) gar nicht mehr addiert werden muss.

5. Schätzung der Bedienzeiten

Ein großes Problem bei der Implementierung dieses Verfahrens ist die Bedienzeit. Diese ist nämlich nicht immer bekannt, doch sie ist für den Algorithmus essentiell, da auf ihrer Basis die Priorisierung der einzelnen Tasks erfolgt. Beim Long-Term-Scheduling ist dieses Problem bei immer wieder auftretenden Prozessen mit bekannten Bedienzeiten kein Problem. Wenn die Zeiten allerdings nicht bekannt sind, müssen sie möglichst gut geschätzt werden. Ggf. bleibt einem nur die Option zu ratem. Beim Short-Term Scheduling könnte man als Schätzstrategie verwenden, dass Prozesse, die in der Vergangenheit lange CPU-Bursts hatten, auch in Zukunft lange brauchen werden (analog für kurze CPU-Bursts). Eine Möglichkeit besteht darin, die folgende Formel für die Schätzung zu verwenden: $$\tau_{n+1}=\alpha\cdot t_n+(1-\alpha)\cdot \tau_n$$ Dabei ist \(0\leq \alpha\leq 1\) ein Gewichtungsfaktor, \(t_n\) der tatsächlich gemessene CPU-Burst im Durchang \(n\) und \(\tau_n\) der geschätzte CPU-Burst. Es handelt sich um eine rekursive Formel. Im Fall \(\alpha=1\) werden nur die tatsächlich gemessenen CPU-Bursts berücksichtigt, was eine sehr einfache (und ggf. schlechte) Schätzung ist. \(\alpha\) muss experimentell ermittelt werden.
Mit dem folgenden Programm lässt sich die nächste Bedienzeit für einen Prozess \(P\) auf Basis \(n\) gemessener Bedienzeiten schätzen:
# Calculates the (assumed) CPU burst based on some weighted factor alpha
def cpu_burst(t, tau, alpha):
        result = alpha * t + (1-alpha) * tau
        # Logging
        print(f"{alpha} * {t} + {1-alpha} * {tau} = {result}")
        return result


# Main.
bursts = [4, 4, 4, 4, 6, 8, 10, 12, 12, 12, 12]
# Start assumption
assumption = 6
alpha = 0.75

for burst in bursts:
        assumption = cpu_burst(burst, assumption, alpha)

6. Vor- und Nachteile

Fassen wir noch einmal die Vor- und Nachteile dieses Verfahrens zusammen:

Vorteile

  • Prozesse mit einem kurzen CPU-Burst werden nicht (wie bei FCFS) benachteiligt.
  • Wenn die Dauer des nächsten CPU-Bursts bekannt ist, lässt sich der Algorithmus relativ leicht implementieren. Da er oft nicht bekant ist, muss er ggf. geschätzt werden.
  • Für endlich viele Prozesse mit bekannten Bedienzeiten wird eine minimale Wartezeit sichergestellt.

Nachteile

  • Langläufer müssen ggf. sehr lange warten, bis sie dran sind, da beim Vorhandensein vieler I/O-Prozesse mit geringen CPU-Bursts diese bevorzugt werden.
  • Durch die Bevorzugung von Prozessen mit geringen CPU-Bursts können Langläufer verhungern.
  • Die Dauer des nächsten CPU-Bursts kann oft nur geschätzt werden. Dies ist unter Umständen schwierig, zeitaufwändig und fehleranfällig.
  • Durch die Umsortierung der Prozesse innerhalb der Warteschlange gemäß ihren Bedienzeiten, entsteht (bei Verwendung eines Heaps) ein logarithmischer Verwaltungsaufwand.