What are the FCFS, SJF, Round Robin and Priority CPU scheduling algorithms, and how do you calculate waiting time?
FCFS runs processes in arrival order, SJF picks the shortest job next and gives the lowest average waiting time, Round Robin gives each process a fixed time slice in turn for fair response, and Priority runs the most important process first but can starve low-priority ones unless aging is used.
Explain it simply
Picture a railway ticket counter with one clerk (the CPU) and a queue of people (processes).
- FCFS (First Come, First Served): serve people in the order they arrived. Fair, but if the first person is booking tickets for a whole wedding party, everyone behind waits a long time.
- SJF (Shortest Job First): serve whoever needs the least time. Quick tasks finish fast, so the average wait drops, but you must know how long each job takes.
- Round Robin: each person gets two minutes, then goes to the back of the line if not done. Nobody waits forever.
- Priority: senior citizens or emergency quota first. Good for important work, but low-priority people may keep getting pushed back (starvation).
Example
Four processes (times in milliseconds):
| Process | Arrival | Burst |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 1 | 3 |
| P3 | 2 | 8 |
| P4 | 3 | 6 |
Formulas: Turnaround time = Completion − Arrival, Waiting time = Turnaround − Burst.
FCFS
| P1 | P2 | P3 | P4 |
0 5 8 16 22| Process | Completion | Turnaround | Waiting |
|---|---|---|---|
| P1 | 5 | 5 | 0 |
| P2 | 8 | 7 | 4 |
| P3 | 16 | 14 | 6 |
| P4 | 22 | 19 | 13 |
Average waiting = 23 / 4 = 5.75 ms. Average turnaround = 45 / 4 = 11.25 ms.
SJF (non-preemptive)
At time 0 only P1 has arrived, so it runs to 5. Then the shortest waiting job is P2 (3), then P4 (6), then P3 (8).
| P1 | P2 | P4 | P3 |
0 5 8 14 22| Process | Completion | Turnaround | Waiting |
|---|---|---|---|
| P1 | 5 | 5 | 0 |
| P2 | 8 | 7 | 4 |
| P3 | 22 | 20 | 12 |
| P4 | 14 | 11 | 5 |
Average waiting = 21 / 4 = 5.25 ms. Average turnaround = 43 / 4 = 10.75 ms.
Round Robin (time quantum = 2)
Convention: a newly arrived process joins the queue before the process that was just preempted.
| P1 | P2 | P3 | P1 | P4 | P2 | P3 | P1 | P4 | P3 | P4 | P3 |
0 2 4 6 8 10 11 13 14 16 18 20 22| Process | Completion | Turnaround | Waiting |
|---|---|---|---|
| P1 | 14 | 14 | 9 |
| P2 | 11 | 10 | 7 |
| P3 | 22 | 20 | 12 |
| P4 | 20 | 17 | 11 |
Average waiting = 39 / 4 = 9.75 ms. Average turnaround = 61 / 4 = 15.25 ms. Round Robin has higher averages here, but every process got its first turn on the CPU within 5 ms of arriving, which is what makes a system feel responsive.
How it works
- Preemptive vs non-preemptive: in non-preemptive scheduling a process keeps the CPU until it finishes or blocks. In preemptive scheduling the OS can take the CPU away, for example when a time slice ends or a shorter or higher-priority job arrives. The preemptive version of SJF is called SRTF (Shortest Remaining Time First).
- FCFS suffers from the convoy effect: one long job holds up many short ones.
- SJF is provably optimal for average waiting time, but the OS cannot know burst times in advance, so real systems estimate them from past bursts.
- Round Robin depends on the quantum. Too large and it behaves like FCFS; too small and the CPU wastes time on context switches.
- Priority scheduling fixes starvation with aging: a process's priority slowly increases the longer it waits.
Real-world use
Real operating systems mix these ideas. Linux's scheduler aims to give each runnable task a fair share of CPU time, with nice values acting as priorities. Interactive programs get quick response, and batch jobs still make progress. Multilevel feedback queues, used in many textbook and classic systems, move jobs between Round Robin queues of different priority based on how they behave.
Common mistakes
- Using Waiting = Start − Arrival for preemptive algorithms. It ignores time spent waiting after being preempted; use Turnaround − Burst.
- Forgetting arrival times and scheduling a job that has not arrived yet.
- Getting the Round Robin queue order wrong when an arrival and a preemption happen at the same moment. State your convention.
What to say in the interview
"FCFS runs processes in arrival order; it is simple but suffers from the convoy effect. SJF runs the shortest burst first and gives the minimum average waiting time, but needs burst estimates and can starve long jobs; its preemptive form is SRTF. Round Robin gives each process a fixed quantum in a circular queue, which gives good response time for interactive systems, and its performance depends on the quantum size. Priority scheduling runs the highest-priority process first and uses aging to prevent starvation. I calculate turnaround as completion minus arrival and waiting as turnaround minus burst."
Follow-up questions
- Solve the same example with preemptive SJF (SRTF).
- What happens to Round Robin if the time quantum is very large or very small?
- What is a multilevel feedback queue?
- What is the difference between throughput, turnaround time and response time?