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. This is the densest topic in Operating Systems for exams, and it is almost entirely mechanical once you can draw a Gantt chart and compute two numbers. Let us do exactly that, on one process set, across every algorithm you need.
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 it costs context switches. Keep that trade-off in mind as the numbers come out.
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 |
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.
Waiting times are 0, 6, 14 and 21, so the average waiting time is 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, 3, 9 and 16, so the average waiting time drops to 28 divided by 4, which is 7.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, the order is 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. Priority scheduling can also starve low-priority processes; 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, 13, 17 and 12, an average of 53 divided by 4, which is 13.25. Round Robin has the highest average waiting time of the four here, because it context-switches the most, but no process waits more than a couple of quanta before getting a slice, which is why it feels responsive for interactive systems.
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 single densest Operating Systems topic in the KnowledgeGate question bank, with about 290 published questions against it, and the subject as a whole carries close to 2,000. GATE questions almost always hand you a process table with arrival and burst times and ask for the average waiting time or turnaround time under a named algorithm, or which algorithm minimises it, or the effect of a particular time quantum. The conceptual variants ask you to identify the convoy effect, spot which algorithms can starve a process, or distinguish preemptive from non-preemptive behaviour. Every one of these is drill-able.
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. Remember the character of each algorithm: FCFS is simple but convoys, SJF is optimal but starves, priority needs aging, and Round Robin trades waiting time for responsiveness.
Practise worked timelines on the CPU scheduling learn module, then test yourself with our operating systems process scheduling MCQs.
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.
