· 

Shortest Remaining Time First (SRTF)

1. Einführung

Das Scheduling-Verfahren Shortest Job First (SJF) lässt sich einfach zu einer Strategie für präemptive Systeme erweitern, bei der auch bereits auf der CPU laufende Prozesse vom System unterbrochen werden können. Dieses Verfahren heißt Shortest Remaining Time First.

2. Der Algorithmus

Die grundlegende Idee dieses Verfahrens ist, dass beim Eintreffen eines neuen Prozesses der gerade auf der CPU arbeitende Prozess angehalten wird. Die bis zu diesem Zeitpunkt verbliebene Bedienzeit wird zur neuen Bedienzeit dieses Prozesses. Nun wird (wie der Name dieses Scheduling-Verfahrens bereits vermuten lässt) unter allen bereiten Prozessen derjenige mit der keinsten Bedienzeit ausgewählt. Das kann auch der soeben angehaltene Prozess sein. Wenn mehrere Prozesse dieselbe Zeit bis zur Beendigung ihres Tasks haben, dann gilt das First Come First Served Prinzip (also wer zuerst kommt, mahlt zuerst).

3. Beispiel

Wir betrachten ein System mit fünf Prozessen, die zu unterschiedlichen Zeiten ankommen.

$$ \begin{array}{|c|c|c|c|c|c|}\hline \text{Prozess} &P_1&P_2&P_3&P_4&P_5 \\\hline \text{Ankunftszeit}&0&2&3&5&8 \\\hline \text{CPU-Burst}&8&4&1&6&2 \\\hline \end{array} $$
Zuerst erhält \(P_1\) die CPU. Er arbeitet zwei Sekunden, bis \(P_2\) eintrifft. \(P_1\) wird angehalten. Nun wird geschaut, welcher der aktuell vorhandenen Prozesse die geringste noch verbliebene Bedienzeit hat. Das ist \(P_2\). \(P_2\) erhält für eine Sekunde die CPU. Danach wird er angehalten, weil \(P_3\) ankommt. Von allen vorhandenen Prozessen wird derjenige ausgewählt, der die geringste noch verbleibende Bedienzeit hat. Das ist \(P_3\) mit einer Sekunde. \(P_3\) erhält also für eine Sekunde die CPU und ist danach beendet. Da \(P_2\) mit drei Sekunden die geringste noch verbleibende Bedienzeit hat, wird ihm als nächstes eine Audienz auf der CPU gewährt. Nach einer weiteren Sekunde kommt \(P_4\) hinzu. Da \(P_2\) immer noch die geringste Bedienzeit hat, darf er seine verbliebenen zwei Sekunden abarbeiten. Jetzt sind nur noch \(P_1\) und \(P_4\) übrig. Da beide eine Restzeit von sechs Sekunden haben, wird derjenige ausgewählt, der zuerst kam (FCFS), nämlich \(P_1\). \(P_1\) arbeitet eine Sekunde. Danach kommt \(P_5\) hinzu. Unter \(P_1,P_4\) und \(P_5\) wird nun der Prozess mit der geringsten verbliebenen Bedienzeit ausgewählt, was in diesem Fall \(P_5\) ist. Dieser darf für zwei Sekunden auf der CPU verweilen. Danach erhält \(P_1\) wieder die CPU und arbeitet seine verbliebenen fünf Sekunden ab. Danach ist \(P_4\) dran und auch dieser arbeitet unterbrechungsfrei seinen Task ab.

4. Berechnung der durchschnittlichen Wartezeit

Die durchschnittliche Wartezeit wird berechnet, indem man die Wartezeiten aller Prozesse addiert und dann durch die Anzahl der Prozesse teilt.

  • \(P_1\) darf direkt starten, muss bis zu seiner nächsten Ausführung aber \(5\) Zeiteinheiten warten und danach noch einmal \(2\) Zeiteinheiten. Somit ergibt sich eine Gesamtwartezeit von \(0+5+2=7\) Zeiteinheiten.
  • \(P_2\) kommt erst nach zwei Zeiteinheiten ins System und muss lediglich eine Sekunde warten, bis er nach der Abarbeitung von \(P_3\) wieder starten darf. Somit ergibt sich eine Gesamtwartezeit von \(0+1=1\) Zeiteinheit.
  • \(P_3\) kommt direkt dran und arbeitet seinen kompletten Task ab. Er hat also eine Gesamtwartezeit von \(0\) Zeiteinheiten.
  • \(P_4\) kommt nach fünf Zeiteinheiten an und wartet zehn Zeiteinheiten, bis er starten darf. Er kann seinen Task dann allerdings an einem Stück abarbeiten, woraus sich eine Gesamtwartezeit von \(10\) Zeiteinheiten ergibt.
  • \(P_5\) kommt nach acht Zeiteinheiten an und kann direkt mit der Abarbeitung seines Tasks beginnen. Er wird in einem Rutsch fertig und muss (wie schon \(P_3\)) keine weitere Wartezeit einkalkulieren. Somit liegt auch seine Wartezeit bei \(0\) Zeiteinheiten.
Daraus folgt für die durchschnittliche Wartezeit also: $$ \frac{7+1+0+10+0}{5}=3.6 $$ Das ist eine ziemlich geringe durchschnittliche Wartezeit.

5. Vor- und Nachteile

Fassen wir die Vor- und Nachteile dieses Algorithmus einmal zusammen:

Vorteile

  • Es gibt im Durchschnitt weniger Wartezeiten als bei FCFS und SJF.
  • Die Wartezeiten bei kurzen Prozessen ist relativ gering.
  • Der Convoy-Effekt wird verhindert, d. h. Langläufer kann nicht die gesamte Verarbeitung unterbrechen bzw. verzögern.

Nachteile

  • Wie schon bei SJF ist es schwierig vorherzusehen, wann die Prozesse tatsächlich beendet werden. Man muss ggf. Schätzungen durchführen. 
  • Relativ lange Antwortzeiten für Prozesse mit einer hohen Bedienzeit.
  • Bei langen Prozessen ist es dennoch möglich, dass andere Prozesse verhungern.