When several processes are ready to run and there is one CPU, the operating system has to choose who goes next. That choice is CPU scheduling, and the algorithm it uses decides how long each process waits and how responsive the system feels. It is also almost entirely mechanical: draw a Gantt chart, read off the completion times, and two subtractions give you everything an exam question asks for. Four processes with burst times of 6, 8, 7 and 3 are scheduled below under FCFS, SJF, priority and Round Robin, and the same two averages come out different every time.
Preemptive vs non-preemptive scheduling
A scheduling decision happens when a process finishes, blocks, or a new process arrives. If the scheduler can only pick a new process when the current one voluntarily gives up the CPU, the scheme is non-preemptive. If it can also stop a running process mid-execution and hand the CPU to another, it is preemptive.
FCFS is always non-preemptive.
SJF has both flavours: non-preemptive SJF and its preemptive form, Shortest Remaining Time First.
Priority scheduling has both non-preemptive and preemptive variants.
Round Robin is always preemptive, using a fixed time quantum.
Preemption improves responsiveness and helps short jobs, but every preemption costs a context switch. Exam arithmetic treats that switch as free, and so does every number below, which flatters the preemptive schemes slightly against a real machine.
The two numbers that matter
For every algorithm you compute two per-process quantities and then average them.
Turnaround time is completion time minus arrival time: the total time the process spent in the system.
Waiting time is turnaround time minus burst time: the time it spent ready but not running.
Take four processes, all arriving at time 0, with these burst times and priorities (a smaller priority number means higher priority):
Process | Burst | Priority |
|---|---|---|
P1 | 6 | 3 |
P2 | 8 | 2 |
P3 | 7 | 4 |
P4 | 3 | 1 |
The same four processes are scheduled four times over, so the only thing that changes is the order in which the CPU serves them. The CPU scheduling learn module works more sets like this one.
FCFS: first come, first served
Processes run in arrival order, here P1, P2, P3, P4. The Gantt chart is a single left-to-right sequence.
Completion times are 6, 14, 21 and 24. All four arrived at time 0, so those are the turnaround times as well, averaging 65 divided by 4, which is 16.25. Subtract each burst and the waiting times are 0, 6, 14 and 21, an average of 41 divided by 4, which is 10.25. FCFS is simple but suffers the convoy effect: one long CPU-bound process at the front makes every short process behind it wait, exactly as P4 waits 21 units here despite needing only 3.
SJF: shortest job first
Non-preemptive SJF runs the ready process with the smallest burst next, giving the order P4, P1, P3, P2. Waiting times become 0 for P4, 3 for P1, 9 for P3 and 16 for P2, so the average waiting time drops to 28 divided by 4, which is 7.0, and turnaround averages 13.0. SJF is provably optimal for average waiting time when all jobs are available together, which is why it is the benchmark every other algorithm is measured against.
Its preemptive form, Shortest Remaining Time First, matters when processes arrive at different times: if a newly arrived process has a shorter remaining time than the running one, it preempts. The cost of both is starvation, a steady stream of short jobs can leave a long job waiting indefinitely.
Priority scheduling
Each process gets a priority and the CPU goes to the highest-priority ready process. Using the priority column above, non-preemptive priority gives the order P4, P2, P1, P3. Waiting times are 0 for P4, 3 for P2, 11 for P1 and 17 for P3, so the average waiting time is 31 divided by 4, which is 7.75, and turnaround averages 13.75. Because all four processes are present at time 0, the preemptive variant produces exactly the same chart here; the two diverge only once a higher-priority process can arrive mid-run. Either variant can starve low-priority processes, and the standard remedy is aging, gradually raising the priority of a process the longer it waits.
Round Robin
Round Robin gives each process a fixed time quantum, then moves it to the back of the ready queue if it is not finished. With a quantum of 4 and the queue order P1, P2, P3, P4, the execution unfolds as follows.
Completion times are P4 at 15, P1 at 17, P2 at 21 and P3 at 24. Since all arrive at 0, those are also the turnaround times, and subtracting bursts gives waiting times of 11 for P1, 13 for P2, 17 for P3 and 12 for P4, an average of 53 divided by 4, which is 13.25. That is the worst of the four, and not because of switching overhead, which this arithmetic ignores. Interleaving simply pushes completions later: only P4, the shortest job, finishes sooner than it did under FCFS, at 15 instead of 24. What Round Robin buys in exchange is a bounded wait for the first slice. With four processes and a quantum of 4, nobody waits longer than three quanta, twelve units, before running, which is why it feels responsive at an interactive terminal even when the queue is long.
Comparing the results
Putting the averages side by side on this one process set:
Algorithm | Average waiting time | Average turnaround time |
|---|---|---|
FCFS | 10.25 | 16.25 |
SJF (non-preemptive) | 7.0 | 13.0 |
Priority (non-preemptive) | 7.75 | 13.75 |
Round Robin (quantum 4) | 13.25 | 19.25 |
SJF wins on average waiting time, as theory predicts. Round Robin trades waiting time for responsiveness. The right choice depends on whether you are optimising throughput, fairness, or interactive feel.
How this is tested in GATE
CPU scheduling is the densest Operating Systems topic in the KnowledgeGate question bank: about 290 questions are tagged to it, out of roughly 2,000 across the subject. GATE questions almost always hand you a process table with arrival and burst times and ask for the average waiting or turnaround time under a named algorithm, or which algorithm minimises it, or what a different time quantum does to the answer. The conceptual variants ask you to identify the convoy effect, spot which algorithms can starve a process, or distinguish preemptive from non-preemptive behaviour. Two traps recur. Non-zero arrival times break the habit of assuming everything is ready at the start, because a shorter job that has not arrived yet cannot be picked. And in Round Robin, when a process is preempted at the same instant another one arrives, the arriving process conventionally joins the ready queue ahead of the preempted one, which changes the entire chart from that point on. Drill both against our operating systems process scheduling MCQs.
The short version
Draw the Gantt chart, read off completion times, then turnaround is completion minus arrival and waiting is turnaround minus burst. Do that until it is automatic. One check catches most arithmetic slips: average turnaround always equals average waiting plus average burst, so with bursts averaging 6 here, every row of the comparison table is exactly 6 apart. Remember the character of each algorithm too. FCFS is simple but convoys, SJF is optimal but starves, priority needs aging, and Round Robin trades waiting time for responsiveness.
The next OS topic students confuse with scheduling is synchronisation, covered in our process synchronization and semaphores deep-dive.
For the full syllabus, GATE Guidance by Sanchit Sir sequences OS with the rest of CS, and more explainers live on the CS Fundamentals category.
