First Come First Served
Chapter Forty-Seven
Syllabus topic Module 1, "CPU Scheduling - Scheduling Algorithms (FCFS ...)"
Pages 188 to 190 of 452
In one line
The processor goes to whichever ready process asked for it first, and keeps it until that process gives it up.
The rule
The ready queue is a first in, first out queue. A process joining goes to the tail; the scheduler takes the head. It is non-preemptive: once a process has the processor it keeps it until it blocks or finishes.
| Chooses | the process that has been in the ready queue longest |
| Preemptive | no |
| Needs to know | nothing: no burst lengths, no priorities |
| Data structure | one queue |
| Starvation | impossible: every process reaches the head |
It is the only algorithm in this row that needs no information about the processes at all, which is why it is the baseline the others are compared with.
Worked in full
Schedule: first come first served
| Process | Arrival | Burst |
|---|---|---|
| P1 | 0 | 24 |
| P2 | 1 | 3 |
| P3 | 2 | 3 |
| Slice | Process | From | To |
|---|---|---|---|
| 1 | P1 | 0 | 24 |
| 2 | P2 | 24 | 27 |
| 3 | P3 | 27 | 30 |
| Process | Completion | Turnaround | Waiting |
|---|---|---|---|
| P1 | 24 | 24 | 0 |
| P2 | 27 | 26 | 23 |
| P3 | 30 | 28 | 25 |
Average turnaround time: 78 / 3 = 26
Average waiting time: 48 / 3 = 16
Context switches: 2
Two short processes waited more than twenty units each for three units of work.
The convoy effect
Now change nothing except the order in which they arrive. The same three processes with the same bursts, the long one arriving last.
Schedule: first come first served
| Process | Arrival | Burst |
|---|---|---|
| P2 | 0 | 3 |
| P3 | 1 | 3 |
| P1 | 2 | 24 |
| Slice | Process | From | To |
|---|---|---|---|
| 1 | P2 | 0 | 3 |
| 2 | P3 | 3 | 6 |
| 3 | P1 | 6 | 30 |
| Process | Completion | Turnaround | Waiting |
|---|---|---|---|
| P2 | 3 | 3 | 0 |
| P3 | 6 | 5 | 2 |
| P1 | 30 | 28 | 4 |
Average turnaround time: 36 / 3 = 12
Average waiting time: 6 / 3 = 2
Context switches: 2
Average waiting fell from 16 to 2, eight times better, and not one burst changed. The work took thirty units either way; the processor was busy for all thirty either way. All that changed is who waited.
That is the convoy effect, and the name is the explanation: one long process at the front of the queue holds up a convoy of short ones behind it, exactly as one slow lorry holds up the cars on a single track road. The words to use in an answer are that the average waiting time under first come first served varies greatly with the arrival order, and is very poor when a long process arrives first.
The other half of the convoy effect
The version above is about arrival order. The classic statement is about the mixture of Chapter forty three.
One processor bound process and many input and output bound ones. The processor bound process gets the processor and holds it for a long burst. The input and output bound processes finish their tiny bursts, queue for the disk, and are soon all waiting on devices while the processor bound one computes. Then it releases the processor and goes to the disk, and all the little processes now rush through the processor and pile up behind it at the disk. The devices are idle while the processor is busy and the processor is idle while the devices are busy, and the machine achieves far less than it could.
First Come First Served
What it is good for
It is not useless, and a question may ask when it is right.
| Right for | Because |
|---|---|
| a batch system where turnaround per job does not matter | throughput is the same whatever the order |
| the lowest level queue of a feedback scheduler (Chapter fifty four) | processes there are long and nobody is waiting on them |
| any case where predictability matters more than speed | it is completely predictable |
| a system with no way to estimate burst lengths | it needs none |
Distinctions that carry marks
| First come first served | Shortest job first | |
|---|---|---|
| Chooses | the oldest request | the smallest burst |
| Needs to know the burst | no | yes |
| Average waiting time | poor, and depends on the order | the best possible |
| Starvation | impossible | possible |
| Convoy effect | yes | no |
What it does not mean
First come first served is not fair in the useful sense. Everybody is served in order, and a short job behind a long one waits far longer than its own work takes. Fair ordering and fair waiting are different things.
It does not waste the processor. Utilisation is as good as any algorithm's; it is the waiting times that are bad.
The convoy effect is not caused by having too few processors. It is caused by not being allowed to interrupt.
Quick revision
- First come first served gives the processor to the oldest request and is
non-preemptive.
- It needs no information about the processes and cannot starve anybody.
- The convoy effect: one long process at the head of the queue delays every short process
behind it. Measured here, the same three processes gave an average waiting time of 16 in one order and 2 in another.
- In its classic form, one processor bound process and many input and output bound ones
alternately idle the devices and the processor.
- It is right where predictability matters, where nothing is known about burst lengths, and at
the bottom of a multilevel feedback queue.
Test yourself
- State the first come first served rule. The processor is given to the process that
requested it first, and is not taken away until that process blocks or finishes.
First Come First Served
- What does it need to know about the processes? Nothing at all.
- Can it starve a process? No. Every process reaches the head of a first in, first out
queue.
- Explain the convoy effect. A long process at the front of the ready queue makes every
short process behind it wait for the whole of its burst, so the average waiting time is very poor and depends heavily on the arrival order. 5. Three processes with bursts 24, 3 and 3 arrive in that order, then in the reverse order. Compare the average waiting times. 48 / 3 = 16 in the first order and 6 / 3 = 2 in the second: eight times better, with no burst changed. 6. Describe the convoy effect with one processor bound process and several input and output bound ones. The processor bound process holds the processor while the others finish their short bursts and queue at the devices; when it releases the processor they rush through and pile up at the device again, so the processor and the devices take turns at being idle.
- Name a place where first come first served is the right choice. The lowest priority queue
of a multilevel feedback scheduler, or any batch system where per job turnaround does not matter and nothing is known about burst lengths.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.