Process Scheduling: Algorithms & Trade-offs

At 10:00:00 AM on tatkal opening day, IRCTC's booking servers do not receive one request — they receive hundreds of thousands within the same second, each one a separate process: parse passenger details, lock a berth, debit the wallet, print a PNR. A modern server has dozens of CPU cores, but at any instant a single core can execute exactly one instruction stream. If a core has thirty processes ready to run and one core, something has to decide which process gets the core next, for how long, and what happens to the twenty-nine that wait. That decision — made tens of thousands of times per second, by a few hundred lines of kernel code called the CPU scheduler — is the entire subject of this chapter. Get it wrong and IRCTC's servers spend more time deciding who runs than actually running anyone; get it right and the system stays both fast on average and fair to every request.

The setup: states, queues, and what "scheduling" even means

Every process the OS manages moves through a small set of states: New (created, not yet admitted), Ready (loaded in memory, waiting only for a CPU), Running (currently executing on a core), Waiting (blocked on I/O or an event — a disk read, a network reply, a lock), and Terminated. The kernel keeps one Process Control Block (PCB) per process — its saved registers, program counter, memory bounds, open files — and the PCBs of every Ready process sit in a data structure called the ready queue. Swapping which PCB occupies the CPU's registers is a context switch: save the outgoing process's register state to its PCB, load the incoming process's saved state, jump to its program counter. This is pure overhead — no user instruction executes during a switch — and its cost (typically a few microseconds) matters later in this chapter.

A scheduling algorithm is simply the rule the dispatcher uses to pick the next PCB out of the ready queue. Every algorithm in this chapter shares the exact same mechanism — admit, queue, dispatch, run, then either block, get preempted, or terminate — and differs only in how the ready queue is ordered. That single idea is the throughline of everything below, and it is exactly what the diagram makes explicit.

Non-preemptive scheduling: FCFS and the convoy effect

First-Come, First-Served (FCFS) orders the ready queue purely by arrival time and never interrupts a running process. It is the simplest possible rule and it is exactly what a single unmanaged checkout line does. Consider four processes on one core (times in milliseconds, all figures below are exact hand-derived arithmetic, not estimates):

Under FCFS, P1 starts at 0 and runs uninterrupted to 8 (nothing else has arrived yet at t=0, so it must go first regardless of length). Then P2 runs 8→12, P3 runs 12→21, P4 runs 21→26. Waiting time is start time minus arrival time: P1 = 0, P2 = 8−1 = 7, P3 = 12−2 = 10, P4 = 21−3 = 18. Average waiting time = (0+7+10+18)/4 = 35/4 = 8.75 ms. Turnaround time (completion minus arrival) averages (8+11+19+23)/4 = 61/4 = 15.25 ms. Notice what happened: P2, P3, and P4 each needed only 4, 9, or 5 ms of CPU but sat behind P1's 8 ms burst simply because P1 arrived first. This is the convoy effect — a handful of long processes at the head of the queue block a trail of short ones behind them, dragging down the average wait for everyone even though most individual processes are short. It is the single biggest weakness of FCFS and the direct motivation for the next algorithm.

Shortest Job First and why it is provably optimal

SJF always dispatches whichever ready process has the smallest remaining CPU burst. When every process is already in the ready queue at time 0, this ordering is not just intuitively good — it minimizes the average waiting time exactly, and the proof is a direct application of the rearrangement inequality you already use in JEE algebra. If n jobs are scheduled in some order and job at position k (1-indexed, all arrived at t=0) has burst b, its waiting time equals the sum of every burst scheduled before it. Summing over all positions, total waiting time = Σ (n−k)·b_{σ(k)}, a sum of products between the fixed decreasing weight sequence (n−1, n−2, …, 0) and a permutation of the bursts. The rearrangement inequality says a sum of products of two sequences is minimized when the largest weight is paired with the smallest value — so the earliest slot (largest weight, n−1) must get the smallest burst. That is precisely "shortest job first." No other ordering of the same multiset of bursts can beat it.

Applying SJF to the same four processes, but now respecting arrival times (this is the non-preemptive version — once a process starts, it runs to completion): at t=0 only P1 has arrived, so it must run first regardless of length — SJF does not fully escape the convoy effect when the queue starts empty. P1 runs 0→8. At t=8, P2 (burst 4), P3 (burst 9), and P4 (burst 5) have all arrived; SJF picks the shortest, P2, running 8→12. At t=12, P3 (9) and P4 (5) remain; P4 runs 12→17. Finally P3 runs 17→26.

Waiting times: P1 = 0, P2 = 8−1 = 7, P4 = 12−3 = 9, P3 = 17−2 = 15. Average = (0+7+9+15)/4 = 31/4 = 7.75 ms — a full millisecond better than FCFS's 8.75. Average turnaround = (8+11+14+24)/4 = 57/4 = 14.25 ms, also better. The cost SJF pays for this is practical, not theoretical: the scheduler must know each process's next burst length in advance, which in a real OS is only ever an estimate (usually an exponentially-weighted average of past bursts), and a steady stream of short arrivals can starve a long process indefinitely, since it is always the last one picked.

Round Robin: trading average waiting time for fairness

Round Robin (RR) keeps FCFS's simple arrival-order queue but adds preemption: each process gets a fixed slice, the time quantum q, and if it hasn't finished by then, it is preempted and sent to the back of the queue. Run the same four processes with q = 4, tracking the ready queue at every step (new arrivals are enqueued before the just-preempted process re-joins the back):

t=0 : queue=[P1]                run P1 for 4  → t=4,  P1 rem=4
       (P2 arrives t=1, P3 t=2, P4 t=3, enqueued in order)
t=4 : queue=[P2,P3,P4,P1]       run P2 for 4  → t=8,  P2 DONE (rem=0)
t=8 : queue=[P3,P4,P1]          run P3 for 4  → t=12, P3 rem=5
t=12: queue=[P4,P1,P3]          run P4 for 4  → t=16, P4 rem=1
t=16: queue=[P1,P3,P4]          run P1 for 4  → t=20, P1 DONE (rem=0)
t=20: queue=[P3,P4]             run P3 for 4  → t=24, P3 rem=1
t=24: queue=[P4,P3]             run P4 for 1  → t=25, P4 DONE (rem=0)
t=25: queue=[P3]                run P3 for 1  → t=26, P3 DONE (rem=0)

Completion times: P2=8, P1=20, P4=25, P3=26. Turnaround = completion − arrival: P1=20, P2=7, P3=24, P4=22, averaging 73/4 = 18.25 ms. Waiting = turnaround − burst: P1=12, P2=3, P3=15, P4=17, averaging 47/4 = 11.75 ms — worse than both FCFS and SJF on this metric. But look at response time (time of first dispatch minus arrival), the metric that matters for an interactive system where a user is watching the screen: P1 first runs at t=0 (response 0), P2 at t=4 (response 3), P3 at t=8 (response 6), P4 at t=12 (response 9); average = 18/4 = 4.5 ms. Under FCFS, response time equals waiting time for every process (each runs exactly once), so FCFS's average response time is the full 8.75 ms computed earlier — nearly double RR's.

This table is the whole chapter in miniature: SJF wins on throughput-style averages, RR wins on responsiveness and fairness (no process ever waits behind an arbitrarily long one for more than roughly n·q), and there is no algorithm here that dominates on every metric at once — scheduling is a genuine trade-off, not a search for one "best" answer.

Priority scheduling and starvation

Priority scheduling generalizes SJF by dispatching whichever ready process has the best priority number (in most OS conventions, numerically smaller = more urgent), independent of burst length; it can be preemptive or non-preemptive exactly like SJF/SRTF. Its failure mode is the same one SJF has, in sharper form: a continuous stream of high-priority arrivals can starve a low-priority process forever. The standard fix is aging — the scheduler periodically raises the effective priority of any process that has been waiting, so its priority number eventually becomes best-in-queue and it is guaranteed to run no matter how many new high-priority processes keep appearing.

Common misconception: "a smaller time quantum is always better"

Students meeting Round Robin for the first time often reason: shorter quantum → processes get switched back to sooner → the system feels more responsive → therefore smaller is strictly better. This ignores the one cost RR alone among these algorithms pays repeatedly: every preemption is a context switch, and every context switch is pure overhead — CPU cycles spent saving and restoring PCBs, doing zero useful work. Shrink the quantum enough and the overhead can dominate the useful work entirely.

Make this precise with three processes, all arriving at t=0, each needing exactly 3 ms of CPU, and assume (purely for illustration, to make the effect visible by hand) a context-switch cost of 1 ms — real switches cost microseconds, but the ratio between quantum and switch cost is what drives the result, so an exaggerated but proportionate example makes the mechanism visible without a computer.

Quantum = 3 (each process finishes inside one slice, so this degenerates to FCFS with a switch after each): P1 runs 0→3, switch 3→4, P2 runs 4→7, switch 7→8, P3 runs 8→11. Completions: 3, 7, 11. Waiting (completion − burst, since all arrived at 0) = 0, 4, 8. Average waiting = 4.0 ms. Total elapsed time = 11 ms for 9 ms of real work → 2 ms overhead (18%).

Quantum = 1: the scheduler now cycles P1, P2, P3 one millisecond at a time, paying the 1 ms switch cost between every single slice:

0-1 P1  1-2 sw  2-3 P2  3-4 sw  4-5 P3  5-6 sw
6-7 P1  7-8 sw  8-9 P2  9-10 sw 10-11 P3 11-12 sw
12-13 P1(done)  13-14 sw  14-15 P2(done)  15-16 sw  16-17 P3(done)

Completions: P1=13, P2=15, P3=17. Waiting = completion − burst = 10, 12, 14. Average waiting = 12.0 ms — three times worse than quantum = 3 — and total elapsed time is 17 ms for the same 9 ms of real work, 47% overhead. The smaller quantum did shrink each individual wait-for-turn interval, but it multiplied the number of switches so much that total wall-clock time for every process got worse, not better. The correct mental model is a balance point, not a monotonic "smaller is better" rule: choose q large enough that most CPU bursts finish within one or two quanta (so the system behaves close to SJF-like efficiency) while keeping q at least an order of magnitude above the actual context-switch cost, so switching stays a rounding error rather than a tax. Textbooks' common rule of thumb — pick q so 70–80% of bursts complete in a single quantum — is exactly this balance.

Verifying the arithmetic in code

The FCFS numbers above can be checked mechanically rather than trusted by hand. Here is a direct trace of a short Python function against the P1–P4 data:

def fcfs_waiting_times(arrivals, bursts):
    n = len(arrivals)
    order = sorted(range(n), key=lambda i: arrivals[i])
    completion = [0] * n
    t = 0
    for i in order:
        start = max(t, arrivals[i])
        completion[i] = start + bursts[i]
        t = completion[i]
    return [completion[i] - arrivals[i] - bursts[i] for i in range(n)]

arrivals = [0, 1, 2, 3]     # P1..P4
bursts   = [8, 4, 9, 5]
print(fcfs_waiting_times(arrivals, bursts))

Tracing it: order = [0,1,2,3] (already arrival-sorted). i=0: start=max(0,0)=0, completion[0]=8, t=8. i=1: start=max(8,1)=8, completion[1]=12, t=12. i=2: start=max(12,2)=12, completion[2]=21, t=21. i=3: start=max(21,3)=21, completion[3]=26, t=26. Waiting = [8−0−8, 12−1−4, 21−2−9, 26−3−5] = [0, 7, 10, 18], matching the hand-derivation exactly, average 8.75.

Active recall

Attempt every question before reading its answer.

1. Three processes: A (arrival 0, burst 6), B (arrival 2, burst 2), C (arrival 4, burst 1). Compute the average waiting time under FCFS.
2. Same three processes. Compute the average waiting time under non-preemptive SJF.
3. Same three processes. Compute the average waiting time under preemptive SRTF (Shortest Remaining Time First).
4. Why does SJF/SRTF risk starvation, and what single mechanism fixes it without abandoning the shortest-first idea?
5. In the RR example above, would you always prefer RR over SJF if context switches were free (zero cost)? Justify using the table's numbers.
6. What is the correct heuristic for choosing a Round Robin quantum, and why does the quantum=1 vs quantum=3 example above rule out "as small as possible"?

Answers

1. FCFS runs in arrival order: A runs 0→6. B (arrived 2) runs max(6,2)=6→8. C (arrived 4) runs max(8,4)=8→9. Waiting = start − arrival: A=0, B=6−2=4, C=8−4=4. Average = (0+4+4)/3 = 8/3 ≈ 2.67.

2. At t=0 only A has arrived, so it must run first: 0→6 (SJF cannot start before a process exists, regardless of its length). At t=6, both B (burst 2) and C (burst 1) are ready; SJF picks the shorter, C, running 6→7. Then B runs 7→9. Waiting: A=0, C=6−4=2, B=7−2=5. Average = (0+2+5)/3 = 7/3 ≈ 2.33.

3. SRTF preempts whenever a shorter remaining burst becomes ready. A runs 0→2 (only one ready). At t=2, B arrives with burst 2, tying A's remaining time of 4 — B's remaining (2) is strictly shorter, so B preempts and runs 2→4, finishing exactly as C arrives at t=4. At that instant the choice is between A (remaining 6−2=4) and C (burst 1): C is shorter, runs 4→5. Only A is left, running its remaining 4 units: 5→9. Completions: B=4, C=5, A=9. Waiting = turnaround−burst: B=(4−2)−2=0, C=(5−4)−1=0, A=(9−0)−6=3. Average = (0+0+3)/3 = 1.0 — better than either FCFS or non-preemptive SJF, because preemption let the two short jobs cut in front of A's remaining burst instead of waiting for the whole 6 ms block to finish.

4. A steady stream of newly-arriving short jobs is always preferred over an already-partially-run long job, so the long job can in principle wait forever (in question 3, A came within one preemption of exactly this, and a fourth short arrival at t=5 would have pushed it back again). The fix is aging: raise the effective priority (equivalently, lower the effective remaining-time estimate) of any process the longer it sits in the ready queue, so it eventually outranks every newcomer and is guaranteed to run.

5. No. Even with zero switching cost, RR's average waiting (11.75 ms) and turnaround (18.25 ms) stay worse than SJF's (7.75 ms, 14.25 ms) in the worked example, because RR's ordering rule is arrival order, not burst length — it never prioritizes finishing short jobs early. RR only wins on response time (4.5 ms vs 7.75 ms). The choice is which metric the system cares about — a batch job scheduler wants SJF-like throughput; an interactive system wants RR-like responsiveness — not a strict dominance either way.

6. Choose q large enough that most CPU bursts (rule of thumb: 70–80%) complete within one or two quanta, while keeping q at least an order of magnitude above the real context-switch cost. The quantum=1 example produced triple the average waiting time of quantum=3 (12.0 ms vs 4.0 ms) purely from switching overhead, for identical process data — proving that shrinking q below the point where switch cost stays negligible makes performance worse, not better, so "as small as possible" is not the correct heuristic.

Think About It

Think about this: How would you explain process scheduling: algorithms & trade-offs to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where process scheduling: algorithms & trade-offs is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting process scheduling: algorithms & trade-offs to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind process scheduling: algorithms & trade-offs, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.