mibeon
/ Betriebssysteme & Prozesse

FCFS-Wartezeit

Wartezeit eines Prozesses bei First-Come-First-Served: Summe der Bedienzeiten aller vorher eingeplanten Prozesse.

FCFS-Wartezeit
01 · Eingabe

FCFS-Wartezeit berechnen

Wartezeit eines Prozesses bei First-Come-First-Served: Summe der Bedienzeiten aller vorher eingeplanten Prozesse.

Wartezeit = SummeVorherigerBedienzeiten
ms

Worum geht es?

Bei First-Come-First-Served (FCFS, auch FIFO) werden Prozesse in der Reihenfolge ihrer Ankunft bedient — ohne Verdrängung. Die Wartezeit eines Prozesses ist damit schlicht die Summe der Bedienzeiten aller Prozesse, die vor ihm an der Reihe sind.

FCFS ist einfach zu implementieren, leidet aber unter dem Convoy-Effekt: ein langer Prozess am Anfang verzögert alle nachfolgenden kurzen Prozesse.

Die Formel

Formel FCFS-Wartezeit 
Wartezeit = SummeVorherigerBedienzeiten

Die Variablen

SymbolBedeutungEinheitErklärung
SummeVorherigerBedienzeitenSumme vorh. BedienzeitenmsSumme der Bedienzeiten aller vor dem Prozess bedienten Jobs.
WartezeitWartezeitmsWartezeit dieses Prozesses bis zum Start.

Minimal-Beispiel

P3 wartet auf P1 (8 ms) und P2 (4 ms).

Rechnung P3 
Wartezeit(P3) = 8 ms + 4 ms
             = 12 ms

Praxis-Beispiele

Beispiel 1 — Vier Prozesse in Reihenfolge

Bedienzeiten: P1 = 24, P2 = 3, P3 = 3, P4 = 5.

Rechnung Wartezeiten 
Wartezeit(P1) = 0
Wartezeit(P2) = 24
Wartezeit(P3) = 24 + 3 = 27
Wartezeit(P4) = 24 + 3 + 3 = 30

Beispiel 2 — Convoy-Effekt

Ein 100-ms-Job blockiert drei 1-ms-Jobs.

Rechnung Convoy 
Wartezeit(Job 2) = 100
Wartezeit(Job 3) = 101
Wartezeit(Job 4) = 102

Beispiel 3 — Batch-Job am Ende

Bedienzeiten: 5, 8, 12, 3 (ms) — gesucht: Wartezeit des letzten Jobs.

Rechnung Letzter Job 
Wartezeit = 5 + 8 + 12
          = 25 ms