Process Scheduling

Intuition

A single CPU can run only one process at a time, but many processes want to run. The scheduler is the part of the operating system that decides, at every moment, which ready process gets the CPU next. That one decision — repeated over and over — is the entire subject.

Different policies make that decision differently, and the same set of jobs can finish in a very different order depending on which policy you pick. This lesson runs one fixed workload through three classic policies so you can compare them directly:

• FCFS (First-Come, First-Served) — run whoever asked first, to completion.
• SJF (Shortest Job First) — run the job with the least work left, to completion.
• Round Robin — give each job a fixed time slice, then rotate to the next.

The workload is four processes, each with an arrival time (when it shows up) and a burst (how much CPU time it needs):

How It Works

Three structures drive the picture. The ready queue holds processes that have arrived and are waiting. The CPU holds the one process currently running. The Gantt chart at the bottom is the timeline: each colored band records which process held the CPU during that stretch of time.

Each policy is just a rule for the dispatch step — choosing who leaves the ready queue for the CPU:

• FCFS takes the front of the queue (arrival order) and runs it until its burst is exhausted. It never interrupts a running job.
• SJF scans the ready processes and takes the one with the smallest remaining burst, then also runs it to completion (this is the non-preemptive variant).
• Round Robin takes the front of the queue but runs it for at most one quantum. If the job still has work left when the quantum expires, it is preempted — sent to the back of the queue — and the next job runs.

We measure each policy with two numbers per process:

• Turnaround time = completion time − arrival time (how long from showing up to finishing).
• Waiting time = turnaround − burst (time spent ready but not running).

Step By Step

Walking the default FCFS run on the workload above:

1. At t = 0, only P1 has arrived, so it is dispatched and runs its full burst. While it runs, P2 (t=1), P3 (t=2), and P4 (t=3) arrive and pile up in the ready queue behind it.
2. P1 finishes at t = 5. Its waiting time is 0 — it never had to wait.
3. P2 is now at the front, so it runs [5, 8]. It arrived at t=1 but could not start until t=5, so it waited 4.
4. P3 runs [8, 9]. It only needed 1 unit, but waited 6 (arrived at 2, started at 8).
5. P4 runs [9, 11] and waited 6 as well.

The average waiting time is (0 + 4 + 6 + 6) / 4 = 4. Notice the damage P1 does: three short jobs sit behind one long job. That is the convoy effect.

Now switch the policy to SJF. After P1 finishes at t=5, the scheduler picks the shortest job (P3, burst 1), then P4 (burst 2), then P2 (burst 3). The short jobs no longer wait behind P2, and the average waiting time drops to 3.25. SJF is provably optimal for average waiting time — when you know the burst lengths.

Switch to Round Robin with quantum 2 and the chart fractures into seven slices: every job gets CPU time early, so no job is starved of responsiveness, but all the context switching pushes the average waiting time up to 4.5. Round Robin trades a higher average wait for fairness and quick response.

Complexity

Per scheduling decision, FCFS is O(1) (take the front) and SJF is O(n) (scan for the minimum), so a full FCFS/SJF run is O(n) / O(n²) over n processes. Round Robin does one dispatch per quantum, so its number of decisions grows with total burst / quantum. The Gantt chart's total length is the sum of all bursts (plus any idle gaps).

Edge Cases

• Idle CPU. If the queue is empty but a process will arrive later, the CPU sits idle and the clock jumps forward to that arrival (shown as a hatched gap).
• Completion exactly at a quantum boundary. Under Round Robin, if a job's remaining work equals the quantum, it finishes on that slice — it is not preempted and re-queued.
• Ties. When a job arrives at the same instant another's quantum expires, the arriving job enters the queue before the preempted job is re-added. This lesson uses that convention; real systems vary.

Common Mistakes

• Confusing waiting time with turnaround time. Waiting time excludes the time the process is actually running; turnaround includes it.
• Thinking SJF is always best. It minimizes average waiting time, but it needs to know burst lengths in advance (rarely true) and can starve long jobs.
• Thinking a smaller quantum is strictly better. Tiny quanta improve response time but multiply context switches — and in the real world each switch costs time this model ignores.

A Note on Simplification

This is a deliberately small explainer, not a model of a production scheduler. It assumes a single CPU, CPU-bound processes (no I/O waits or blocking), zero context-switch cost, and known burst lengths. Real operating systems use far richer policies (multi-level feedback queues, Linux's CFS, priority and aging, multiprocessor load balancing) and must handle I/O, interrupts, and preemption costs. The goal here is to make the core scheduling decision and the resulting timeline visible — not to substitute for an operating-systems course.