Process Scheduling

Process scheduling is the operating system's answer to a brutal constraint: one CPU, many runnable processes. The scheduler decides, at every decision point, which ready process gets the CPU next. This lesson runs one fixed four-process workload through three classic policies — FCFS, SJF, and Round Robin — so the same jobs produce three directly comparable Gantt charts.

Picture a grocery store with a single cashier. Four customers walk in over four minutes, carts of different sizes, and the store's only real choice is the line discipline: serve in arrival order, wave the small baskets ahead, or ring up two items per customer and send everyone to the back for another turn. Same customers, wildly different experiences. The cashier is the CPU; the line discipline is the policy. Keep the analogy — it pays rent all the way down.

How Process Scheduling Works

Three structures carry the whole picture. The ready queue holds processes that have arrived and want the CPU — the checkout line. The CPU runs exactly one process at a time — the cashier. The Gantt chart is the receipt tape: a timeline of which process held the CPU during each stretch.

Every policy is a rule for one moment, the dispatch: who leaves the ready queue for the CPU?

FCFS (First-Come, First-Served) takes the front of the queue — strict arrival order — and runs it until its burst is exhausted. No interruptions, ever.

SJF (Shortest Job First) dispatches the ready process with the smallest remaining burst, then also runs it to completion. This is the non-preemptive variant: a long job already on the CPU keeps it even if a tiny job arrives mid-run. Ties on burst go to the earlier arrival.

Round Robin takes the front of the queue but caps the run at one quantum (here, 2 time units; the slider goes 1 to 4). A job that finishes within its slice completes; otherwise it is preempted — pushed to the back of the queue — and the next job gets the cashier. A process that arrived during the slice joins the queue before the preempted one re-enters.

Two numbers grade each process. Turnaround time is completion minus arrival: door to door. Waiting time is turnaround minus burst: time standing in line, the part everyone resents. Averaging each over all four processes grades the policy.

The fixed workload: P1 arrives at t = 0 with burst 5, P2 at t = 1 with burst 3, P3 at t = 2 with burst 1, P4 at t = 3 with burst 2. One big cart first, three small baskets behind it — that ordering is the setup for the punchline.

Process Scheduling Step by Step

The default policy is FCFS, so press play and you get arrival order, no mercy.

At t = 0 only P1 has arrived, so it is dispatched and runs its full burst of 5: the Gantt's first bar grows across [0, 5]. While it runs, P2 arrives at t = 1, P3 at t = 2, P4 at t = 3 — all three pile up in the ready queue. P1 completes at t = 5 with turnaround 5 − 0 = 5 and wait 5 − 5 = 0. It never waited a single tick.

P2 is now at the front, so it runs [5, 8] and completes at t = 8: turnaround 8 − 1 = 7, wait 7 − 3 = 4. P3 runs [8, 9] — it needed exactly one unit of CPU but completes at t = 9 with turnaround 7 and wait 6. P4 runs [9, 11], completing at t = 11 with turnaround 8 and wait 6.

Final FCFS Gantt: P1[0,5] P2[5,8] P3[8,9] P4[9,11]. Average waiting time (0 + 4 + 6 + 6) / 4 = 4.00; average turnaround (5 + 7 + 7 + 8) / 4 = 6.75. P3's score is the scandal: one unit of work, six units of queueing. Three small baskets stuck behind one full cart — that is the convoy effect, and FCFS manufactures it by design.

Switch the selector to SJF and the chart reorders itself after P1. At t = 5 the ready queue holds P2 (burst 3), P3 (burst 1), P4 (burst 2); the scheduler waves the smallest basket through first. Gantt: P1[0,5] P3[5,6] P4[6,8] P2[8,11]. P3 now waits only 3, P4 waits 3, and P2 — the longest of the latecomers — absorbs the wait of 7. Average wait drops to 3.25, average turnaround to 6.00.

Switch to Round Robin with quantum 2 and the chart fractures into seven slices: P1[0,2] P2[2,4] P3[4,5] P1[5,7] P4[7,9] P2[9,10] P1[10,11]. Watch the t = 2 boundary closely: P3 arrives at the exact instant P1's quantum expires, and P3 enters the queue before the preempted P1 re-joins. P3 completes at t = 5 (wait 2), P4 at t = 9 (wait 4), P2 at t = 10 (wait 6), and P1 — chopped into three slices — limps home last at t = 11 (wait 6). Average wait climbs to 4.50, average turnaround to 7.25, but every process got CPU time within the first 7 units.

On the canvas, each process keeps one identity color from queue to CPU to Gantt bar, so you can follow a single job through the whole machine. Per-process wait counters climb in real time while a job queues — under FCFS, watch P3's counter grind upward while P1's bar stretches across the chart. Under Round Robin, the CPU box shows a quantum meter draining toward the next preemption.

Which Scheduling Policy Wins?

Wrong question — and that is the lesson. On this workload: FCFS averages wait 4.00 / turnaround 6.75; SJF averages 3.25 / 6.00; Round Robin averages 4.50 / 7.25.

SJF wins the averages, and not by luck: when all jobs are available together and their bursts are known, non-preemptive shortest-first order minimizes average waiting time. With staggered arrivals, that theorem does not make every greedy, non-preemptive SJF schedule globally optimal. The catch is that it requires knowing burst lengths in advance — real systems can only estimate — and a steady stream of small baskets can starve the full cart indefinitely.

Round Robin posts the worst averages here, yet it is the closest to what real systems run. It buys responsiveness: every customer gets rung up within a bounded delay, no clairvoyance required, no starvation. Interactive systems happily pay a higher average wait for that guarantee. FCFS is what you get when you optimize for nothing: fair in one narrow sense, and one long burst away from a convoy.

Edge Cases

• Idle CPU. If the queue is empty but a process arrives later, the clock jumps to that arrival and the Gantt records a hatched idle gap. The default workload never goes idle.
• Completion exactly at a quantum boundary. A Round Robin job whose remaining work equals the quantum completes on that slice — it is not preempted and pointlessly re-queued.
• Arrival at the instant of preemption. When an arrival coincides with a quantum expiry (P3 at t = 2), the arrival enters the queue first, the preempted job behind it. Textbook conventions vary; this is what the animation simulates.
• SJF ties. Equal remaining bursts go to the earlier arrival.

Common Mistakes

• Confusing waiting time with turnaround time. Turnaround includes the running time; waiting excludes it. P3 under FCFS: turnaround 7, wait 6 — the gap is its burst of 1.
• Believing SJF is simply best. It improves the averages here and is optimal under the simultaneous-availability assumption, but it needs burst lengths up front and can starve long jobs. Optimal-on-paper is not deployable-as-is.
• Assuming a smaller quantum is strictly better. Tiny quanta sharpen response time but multiply context switches, and this model charges zero per switch. Real hardware charges plenty; set quantum 1 and watch the slice count explode.

A Note on Simplification

The model on screen is one CPU running CPU-bound jobs, with zero-cost context switches and burst lengths known in advance — the cleanest stage on which the scheduling decision itself is visible. Production systems pay real time for every switch, never see bursts up front, and layer multi-level feedback queues, priority with aging, and per-core balancing on top. This lesson isolates the one decision all of that machinery builds on.