· 

First Come First Served (FCFS)

1. Einführung

"Wer zuerst kommt, mahlt zuerst", "Der frühe Vogel fängt den Wurm" und "Wer zu spät kommt, den bestraft das Leben" sind Sprüche, die alle zum Scheduling-Verfahren First Come First Served (FCFS) passen. Dieses zählt zur Klasse der nicht-präemptiven Scheduling-Verfahren, die es Prozessen erlauben, dass sie die CPU für die gewünschte Zeit zur Abarbeitung ihres Tasks am Stück verwenden können. Diese Zeit nennt man CPU Burst. Die Bedienzeit (also die Zeit, in der ein Prozess die CPU am Stück erhält) entspricht bei nicht-präemptiven (also unterbrechungsfreien)  Schedulingverfahren dem CPU Burst.


2. Der Algorithmus

Alle CPU-anfordernden Prozesse \(P_1, P_2, ..., P_n\) werden zunächst ihrer Ankunftszeit entsprechend in eine Warteschlange (Queue) gepackt. Das Prinzip, nach dem dieser Algorithmus arbeitet, ist denkbar einfach: Der erste Prozess, der in einer Queue eingetroffen ist (in diesem Fall \(P_1\)), ist auch der Prozess, der zuerst abgearbeitet wird. Egal wie lange die Bearbeitungszeit von \(P_1\) auch sein mag: erst, wenn \(P_1\) abgearbeitet ist, ist \(P_2\) dran.

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} $$ Zuerst kommt \(P_1\), dann \(P_2\), dann \(P_3\), dann \(P_4\) und zum Schluss \(P_5\) in der Queue an. Da \(P_1\) zuerst in der Queue angekommen ist, wird ihm eine Bedienzeit von \(42\) Sekunden auf der CPU gewährt. Erst danach ist \(P_2\) mit \(5\) Sekunden dran, obwohl dieser Prozess weitaus weniger Zeit benötigt als \(P_1\). Im Anschluss an \(P_2\) erhält \(P_3\) für \(8\) Sekunden die CPU. Danach ist zuerst \(P_4\) mit \(10\) Sekunden und abschließend \(P_5\) mit \(6\) Sekunden dran. Wie du siehst, ist der Algorithmus sehr einfach und lässt sich daher auch sehr leicht implementieren. Prozesse, die nur sehr kurz die CPU benötigen (das sind oft Prozesse, die interaktiv sind und eigentlich bevorzugt werden müssten), werden gegenüber lange laufenden Prozessen benachteiligt, wenngleich sie nicht verhungern (irgendwann werden sie nämlich drankommen).

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. Für unser Beispiel ergibt sich also:
  • \(P_1\Longrightarrow 0s\)
  • \(P_2\Longrightarrow (0+42)s=42s\)
  • \(P_3\Longrightarrow (42+5)s=47s\)
  • \(P_4\Longrightarrow (47+8)s=55s\)
  • \(P_5\Longrightarrow (55+10)s=65s\)
Daraus folgt für die durchschnittliche Wartezeit also: $$ \frac{(0+42+47+55+65)s}{5}=41.8s $$ Das ist eine ziemlich hohe durchschnittliche Wartezeit, die vor allem durch die hohe Wartezeit am Anfang entsteht.

5. Vor- und Nachteile

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

Vorteile

  • Der Algorithmus ist sehr einfach und kann dementsprechend leicht implementiert werden.
  • Der Scheduler muss die  Prozesse im Zustand Ready in einer einfachen Queue verwalten und kann diese in konstanter Zeit O(1) nach dem FIFO-Prinzip (First In First Out) der CPU zuteilen. Das Verfahren ist algorithmisch betrachtet sehr effizient, da der Verwaltungsaufwand und die Laufzeiten sehr gering sind.
  • Der Algorithmus ist fair, da alle Prozesse ihrer Ankunftszeit entsprechend die CPU erhalten. Niemand wird bevorzugt.

Der Vorteil, dass kein Prozess bevorzugt wird, kann jedoch auch als Nachteil ausgelegt werden.

Nachteile

  • Dieses Verfahren ist I/O-lastigen Prozessen nicht zumutbar. Insbesondere bei Dialoganwendungen muss schnell auf Benutzereingaben reagiert werden. So kann es passieren, dass während ein Prozess, der nur kurze CPU-Bursts besitzt und auf eine Benutzereingabe wartet, ein anderer Prozess mit einer sehr langen Bedienzeit in der Warteschlange ankommt und dann zuerst abgearbeitet wird.