First Come, First Served (FCFS) Scheduling
I love the idea of first come, first served, because when it comes to lines, I'm always at the front. And let me tell you, I'm going to get a large serving!
What about the people behind you?
-
They can wait!
Some Work to Do
Let's suppose we have five processes as shown below. Each process has a certain amount of time it needs to run, as shown in the table. We'll use these processes to demonstrate how First-Come, First-Served (FCFS) scheduling works.
| Process | Required Time |
|---|
-
I think the “Alice” process needs MORE time!
In fact, the times in the table are randomly chosen (but contrived to always add up to 32 so that our charts always have the same scale and our statistics are comparable). If you like, you can pick a different random seed from the one chosen when the page loaded to pick different times for the processes.
FCFS Scheduling
FCFS scheduling is the simplest scheduling algorithm. It's like waiting in line at the grocery store: the first person in line gets to check out first. Our processes arrived in alphabetical order, so we'll run them in that order.
The chart below shows the schedule for the processes as a timeline:
You can see from the chart that each process is represented by a green rectangle. The length of the rectangle represents the time the process is running. The blue parts of the chart show times when the process is waiting.
At the bottom of the chart, we see a timeline for the CPU, with grey rectangles showing which process the CPU is running at each time point. In this particular chart, the CPU always has something to do.
If you adjust the random seed above, the required times of the processes will change and the chart will change to show a different schedule.
-
I think it's great! I mean, like Alice, I'm always first in line, so I'd always get to run first! No waiting for me! And I'm done before anyone else even gets started! What's not to like?
-
Well, what if you're Eve? You have to wait for everyone else to finish before you even get started.
Exactly. But let's try to actually characterize what's going on.
Response Time, Turnaround Time, and Wait Time
When we run a set of processes, we can measure a few different times for each process:
- Response Time: The time from when the process wants to start running until it first gets the CPU.
- Turnaround Time: The time from when the process wants to start running until it finishes.
- Wait Time: The time the process spends waiting to run.
In our example, the wait time is always the same as the response time, because once a process gets the CPU, it runs to completion and never waits again.
-
That's right. But these statistics are applicable to any scheduling algorithm, not just FCFS.
Here are all the statistics for the processes in this run:
| Process | Response Time | Turnaround Time | Wait Time |
|---|
If you adjust the random seed (which you can also do by selecting and changing the number in the input field below rather than scrolling away), the required times of the processes will change and so the statistics will change, but you may notice that the overall flavor of the statistics remains about the same.
Prof. Melissa ran the simulation one million times and found the response time (and wait time) averaged out to be 12, and the turnaround time averaged out to be 18. The standard deviation for each of these times was about 8.6.
Meh. She has too much time on her hands. She needs to work on her own schedule!
I've gotta wonder, can we do better for these times?
-
Let's have a think about that.
Switch the seed to 123456 and look at the chart. Do you think you can see a different order of running things that would be better?
-
Poor old Eve, all the way at the end. She doesn't even want to do much work, and she's kept waiting for so long!
-
Perhaps that gives us a hint about how we might do better.
(When logged in, completion status appears here.)