Scheduling algorithms

When you open a browser, stream music, and download a file simultaneously, your laptop's OS is quietly juggling all three — and the machinery that makes this feel seamless is what this lesson demystifies. Understanding processes, the PCB, context switching, and IPC is not just GATE syllabus; it is the foundation of everything that happens when a computer runs software.

Definition: A process is a program in execution — an active entity with its own memory space, register values, program counter, and state. A program is merely the passive set of instructions sitting on disk; it becomes a process only when the OS loads and begins running it.

Definition: The Process Control Block (PCB) is the kernel data structure that stores a complete snapshot of a process — PID, state, program counter, saved registers, memory-management pointers, open file table, and accounting data.

Why a program becomes a process

Think of a recipe (program) versus a cook actually making the dish (process). The recipe can be photocopied a thousand times; a hundred cooks can run the same recipe simultaneously. Each cook has their own workspace, their own state (which step they are at), and their own set of pots. In the same way, a single .exe or binary on disk can launch as many independent processes, each with a completely separate memory image and execution state.

The five-state process model

The OS tracks every process through five states:

[New] ──→ [Ready] ⇌ [Running] ──→ [Terminated]
                        ↕
                  [Waiting / Blocked]

• New: the process is being created — resources are being allocated, the PCB is initialised.
• Ready: the process is loaded into memory and waiting for the CPU. The OS keeps a ready queue of these.
• Running: the process owns a CPU core and is executing instructions. On a single-core machine, only one process is ever in this state at a time.
• Waiting / Blocked: the process issued an I/O request (read a disk file, wait for a keyboard input, open a socket) and cannot proceed until that I/O completes. It vacates the CPU voluntarily.
• Terminated: execution finished (or the process was killed). Resources are being reclaimed.

Key transitions (memorise the direction and trigger):

Transition	Cause
New → Ready	OS finishes loading the process
Ready → Running	Scheduler dispatches the process (gives it CPU)
Running → Ready	Time slice expires (preemption)
Running → Waiting	Process requests I/O or waits for an event
Waiting → Ready	I/O completes or event occurs
Running → Terminated	Process calls exit() or is killed

Why it matters: These transitions are drawn in GATE diagrams and appear as MCQs ("after a time-slice expires, a process moves from __ to __"). Getting the direction right is the whole question.

The Process Control Block in depth

The PCB is the kernel's "resume card" for a process. Its fields:

• PID (Process ID): unique integer identifier.
• Process state: one of the five states above.
• Program counter (PC): address of the next instruction to execute.
• CPU registers: all general-purpose registers, stack pointer, base pointer — saved exactly so execution can resume as if it never stopped.
• CPU scheduling info: priority value, pointer to scheduling queue.
• Memory management info: page tables or segment descriptors that describe the process's address space.
• I/O status: list of open files and devices, pending I/O requests.
• Accounting data: CPU time consumed, wall-clock time, number of context switches.

Real-world example: Open Linux's /proc/<PID>/status or Windows Task Manager's details tab — every row you see (PID, state, virtual memory, open handles) maps directly to a field in the PCB.

Context switching — the cost of multitasking

A context switch is the act of saving one process's state into its PCB and loading another process's state from its PCB so the CPU can run the second process. During the switch itself, no user code runs — it is pure overhead.

Steps in a context switch:

1. The running process is interrupted (timer interrupt or voluntary yield).
2. The OS saves the process's PC, registers, and flags into its PCB.
3. The OS selects the next process from the ready queue (scheduling decision).
4. The OS loads that process's PC, registers, and flags from its PCB.
5. On architectures with virtual memory, the OS flushes or selectively invalidates the TLB (Translation Lookaside Buffer), because the new process has different virtual-to-physical address mappings.
6. Pipeline state and branch-predictor state may reset, adding a few extra cycles.

Modern OSes do this hundreds to thousands of times per second. Each switch costs ~1–10 microseconds, but if switches are too frequent, the overhead eats into throughput — a phenomenon called thrashing the scheduler.

Common misconception: Students say "context switch creates a new process." No — a context switch only swaps which process is on the CPU. No new process is created.

Unix process creation: fork, exec, wait

Unix and Linux create processes with three system calls:

fork() — creates a child process that is an almost-exact copy of the parent:

• Returns 0 inside the child.
• Returns the child's PID inside the parent.
• Returns −1 if it fails (out of memory, process-table full).

Both processes continue running from the line after fork(), which is why the return value is the only way they can tell each other apart. Internally, modern OSes use copy-on-write (COW): the child's pages are marked read-only and share the parent's physical frames until one of them writes — only then is the physical page copied. This makes fork() cheap even for large processes.

exec() family — replaces the current process's memory image with a new program loaded from a file. It does not create a new process; the same PID continues, but now running entirely new code. The fork() + exec() pattern is "spawn a new program."

wait() / waitpid() — lets the parent block until a child finishes, collecting the child's exit status and letting the kernel clean up the child's PCB.

Zombie process: a child that has finished (exit()ed) but whose parent has not yet called wait(). The process is dead, but its PCB entry remains so the parent can collect the exit status. If many zombies accumulate, the process table fills up.

Orphan process: a child whose parent exits first. The OS reassigns it to init (PID 1, or systemd) as its new parent, which periodically calls wait() to reap orphans.

Threads versus processes

Definition: A thread is a lightweight unit of execution within a process. All threads in a process share the same code, heap, and global data, but each has its own stack and register set.

User-level threads are managed by a library (e.g., POSIX pthreads at user level); the kernel is unaware — switching is fast, but a blocking system call blocks all threads. Kernel-level threads are OS-aware; one can block while others run, but creation is expensive. Modern OSes (Linux, Windows) use a 1:1 model: each user thread maps to exactly one kernel thread.

Inter-Process Communication (IPC)

Separate processes need to share data or coordinate. IPC mechanisms:

1. Shared memory — processes map the same physical region into their address spaces. It is the fastest IPC (no kernel copy), but requires explicit synchronisation (semaphores or mutexes) to avoid race conditions.
2. Pipes — a unidirectional byte stream between a parent and child. | in the shell is a pipe.
3. Named pipes (FIFOs) — like pipes, but accessible by any two processes that know the name.
4. Message queues — a kernel-maintained list of typed messages; any process can send/receive.
5. Sockets — work across machines via TCP/IP, not just within one OS.
6. Signals — asynchronous notifications: SIGKILL (9) forcibly terminates; SIGTERM (15) asks gracefully; SIGINT is Ctrl+C; SIGSEGV fires on a segmentation fault.

Synchronisation and critical sections

When multiple processes or threads access shared mutable data, the result can depend on the exact timing of interleaved instructions — a race condition. The segment of code that reads or modifies the shared resource is the critical section. Mutual exclusion (only one thread in the critical section at a time) is enforced by semaphores, mutexes, and monitors — detailed in the synchronisation lesson.

Key scheduling metrics

• Turnaround time = completion time − arrival time
• Waiting time = turnaround time − CPU burst time
• Response time = time from arrival to first CPU allocation

Worked example:

Question: Two processes arrive at t = 0. P1 has burst 5 ms, P2 has burst 3 ms. FCFS order P1 then P2. Calculate waiting times.

Solution:

• Step 1: P1 starts at 0, finishes at 5 ms. Waiting time = 5 − 0 − 5 = 0 ms.
• Step 2: P2 starts at 5, finishes at 8 ms. Waiting time = 8 − 0 − 3 = 5 ms.
• Conclusion: Average waiting time = (0 + 5) / 2 = 2.5 ms.

Every modern operating system must decide which process gets to run next — the wrong choice can waste milliseconds that add up to a sluggish system, while the right choice keeps users happy and CPUs busy. CPU scheduling algorithms are the set of rules the OS uses to make that decision, and understanding why each one was invented tells you exactly when to use it.

Definition: CPU scheduling is the mechanism by which the OS selects, from the ready queue, which process will be loaded onto the CPU next.

Definition: Preemptive scheduling means the OS can forcibly remove a running process from the CPU before it finishes; non-preemptive means a process keeps the CPU until it voluntarily releases it (I/O wait or termination).

Definition: Burst time is the amount of CPU time a process needs to complete its current CPU phase.

First-Come-First-Served (FCFS)

FCFS is the simplest possible policy: treat the ready queue like a queue at a bus stop — whoever arrived first boards first. It is strictly non-preemptive.

Why it matters: FCFS is easy to implement and fair in the sense that no process is permanently ignored, but its performance degrades badly when a long job arrives first.

The convoy effect is the defining weakness: imagine a 100-ms process at the head of the queue, followed by five 1-ms processes. All five must wait 100 ms, pushing average waiting time way up.

Worked example — FCFS

Question: Three processes arrive at time 0: P1 (burst 10 ms), P2 (burst 5 ms), P3 (burst 8 ms). Calculate average waiting time under FCFS.

Solution:
Step 1: FCFS order is P1 → P2 → P3.
Step 2: P1 waits 0 ms; P2 waits 10 ms; P3 waits 10 + 5 = 15 ms.
Conclusion: Average waiting time = (0 + 10 + 15) / 3 = 8.33 ms.

Shortest Job First (SJF)

SJF picks the process with the smallest burst time from the ready queue. It is non-preemptive by default.

Why it matters: SJF is mathematically proven to be optimal for minimising average waiting time among all non-preemptive algorithms — you cannot do better with the same set of burst times.

Common misconception: Many students think "shortest" means shortest total program length. It means shortest next CPU burst, not total job length.

Disadvantage — starvation: A continuous stream of short jobs can permanently block a long one. The fix is aging — incrementally raising the effective priority of a process the longer it waits, until it eventually wins the CPU.

Worked example — SJF (compare with FCFS)

Question: Same three processes: P1 (burst 10), P2 (burst 5), P3 (burst 8). All arrive at time 0.

Solution:
Step 1: SJF orders by burst: P2 (5) → P3 (8) → P1 (10).
Step 2: P2 waits 0 ms; P3 waits 5 ms; P1 waits 5 + 8 = 13 ms.
Conclusion: Average = (0 + 5 + 13) / 3 = 6.0 ms — better than FCFS's 8.33 ms.

Real-world example: A hospital triage that always treats the fastest-to-treat patients first would maximise throughput but could leave a complex case waiting indefinitely — the classic starvation trade-off.

Shortest Remaining Time First (SRTF)

SRTF is the preemptive version of SJF: whenever a new process arrives in the ready queue, if its burst time is less than the remaining burst of the currently running process, the OS preempts the current one.

SRTF gives the globally optimal average waiting time across all scheduling algorithms (including preemptive ones), but it requires knowing future burst times — which is impossible in practice. It is used as a theoretical benchmark.

Round Robin (RR)

Round Robin assigns each process a fixed time quantum (also called time slice, typically 10–100 ms), then cycles through the ready queue, giving each process one quantum in turn. It is inherently preemptive.

Why it matters: RR is the standard algorithm for time-sharing systems where responsiveness matters more than raw throughput (desktops, web servers).

Quantum size is critical:

• Too small → context switches dominate; CPU wastes time saving/restoring registers.
• Too large → degrades toward FCFS; processes feel unresponsive.
• Rule of thumb: ~80% of CPU bursts should finish within one quantum.

Real-world example: The Linux CFS (Completely Fair Scheduler) is a weighted Round Robin variant. Each process gets a slice of CPU time proportional to its "nice" value.

Priority Scheduling

Each process is assigned a numeric priority. The CPU always goes to the highest-priority ready process. Can be preemptive (new high-priority process can interrupt) or non-preemptive.

Problem: starvation of low-priority processes. Fix: aging — each second a process waits, its priority value increases by 1. Eventually even the lowest-priority process will accumulate enough seniority to run.

Common misconception: "Higher number = higher priority" is OS-dependent. In many Unix systems, lower numbers mean higher priority (0 = most urgent). Always check the convention in exam questions.

Multilevel Queue Scheduling

The ready queue is split into multiple queues with different scheduling algorithms per queue (e.g., system processes use RR with small quantum; interactive processes use RR with larger quantum; batch jobs use FCFS). Processes are permanently assigned to a queue at birth.

The queues themselves are scheduled by fixed priority — the batch queue does not get CPU time while any interactive process is ready.

Multilevel Feedback Queue (MLFQ)

The most general and most commonly used scheme in real OSes. Like multilevel queue, but processes can move between queues based on their behaviour:

• A CPU-intensive process that consistently uses its full quantum gets demoted to a lower-priority queue.
• A process that often does I/O (interactive behaviour) gets promoted back up.

This means the OS automatically identifies and rewards interactive processes without requiring programmers to label them. Windows, Linux, and macOS all use variants of MLFQ.

Comparison at a Glance

Gantt Charts and Calculating Metrics

Exam questions often ask for average waiting time or average turnaround time. The method is always:

• Waiting time = start time − arrival time (adjust if process is preempted and re-queued).
• Turnaround time = completion time − arrival time.
• Response time = first time the process gets CPU − arrival time.

Draw a Gantt chart (a timeline showing which process runs when) before computing any metric. It prevents arithmetic mistakes.

Worked example — Round Robin with quantum = 2

Question: P1 arrives at 0 (burst 4), P2 arrives at 0 (burst 3), P3 arrives at 0 (burst 5). Quantum = 2.

Solution:
Step 1: Gantt chart: P1(0-2), P2(2-4), P3(4-6), P1(6-8), P2(8-9), P3(9-11), P3(11-12).
Step 2: Wait times — P1: 4 ms (ran at 6, arrived at 0, already ran 2 ms — use turnaround−burst); compute directly: P1 finishes at 8, burst=4, turnaround=8, wait=4. P2 finishes at 9, burst=3, wait=6. P3 finishes at 12, burst=5, wait=7.
Conclusion: Average wait = (4+6+7)/3 = 5.67 ms.

Cover the answer, recall, then check. 12 cards on CPU scheduling fundamentals for GATE OS.

Q1. Define Turnaround Time (TAT), Waiting Time (WT) and Response Time (RT).
A1. TAT = Completion Time − Arrival Time. WT = TAT − Burst Time. RT = (time of first CPU allocation) − Arrival Time. All three exclude nothing extra; WT and RT differ because RT counts only up to the first dispatch.

Q2. Which criteria do we MAXIMISE vs MINIMISE in scheduling?
A2. Maximise CPU utilisation and throughput; minimise turnaround time, waiting time and response time.

Q3. Preemptive vs non-preemptive scheduling — when does a switch occur?
A3. Non-preemptive: CPU released only on termination or voluntary block (running→wait). Preemptive: CPU can also be taken on interrupt/timer (running→ready) or when a higher-priority process arrives.

Q4. Which scheduling algorithm gives provably minimum average waiting time?
A4. SJF (Shortest Job First) is optimal for minimum average WT among non-preemptive; SRTF (preemptive SJF) is optimal overall. Both are non-implementable exactly because burst length is unknown a priori.

Q5. What is the convoy effect and which algorithm suffers it?
A5. FCFS: one long CPU-bound process holds the CPU while many short processes wait behind it, dragging average waiting time up.

Q6. What causes starvation and one fix?
A6. Priority and SJF/SRTF can starve low-priority / long jobs indefinitely. Fix = aging: gradually raise a waiting process's priority over time.

Q7. Round Robin as time quantum q → ∞ and q → 0?
A7. q → ∞ (larger than every burst): RR degenerates to FCFS. q → 0: behaves like processor sharing but context-switch overhead dominates and throughput collapses.

Q8. Where do the dispatcher and dispatch latency fit in?
A8. The dispatcher gives CPU control to the process the scheduler picked; dispatch latency is the time to stop one process and start another (context switch + mode switch).

Q9. Long-term vs short-term vs medium-term scheduler?
A9. Long-term (job scheduler): controls degree of multiprogramming, runs rarely. Short-term (CPU scheduler): picks next ready process, runs very frequently (ms). Medium-term: swaps processes in/out of memory.

Q10. In a Gantt-chart problem, how do you compute average waiting time?
A10. Draw the Gantt chart, read each process's Completion Time, compute TAT = CT − AT and WT = TAT − BT, then average the WTs. Idle CPU gaps count as no process running.

Q11. Which algorithm minimises response time and why is it used interactively?
A11. Round Robin — every process gets the CPU within (n−1)·q time, bounding response time, which matters for time-sharing/interactive systems.

Q12. CPU-bound vs I/O-bound process — scheduling implication?
A12. I/O-bound processes have short CPU bursts and should be favoured to keep I/O devices busy; CPU-bound processes have long bursts. A good mix maximises overall utilisation.

CPU scheduling decides which ready process gets the CPU next. In GATE, this is a numerical guarantee: expect at least one Gantt-chart problem where you compute average waiting or turnaround time. The scoring skill is drawing the chart correctly and applying the definitions without slips.

Core definitions

For every process: Turnaround Time (TAT) = Completion Time − Arrival Time, Waiting Time (WT) = TAT − Burst Time, and Response Time (RT) = first CPU allocation − Arrival Time. Averages are taken over all processes.

The algorithms at a glance

Algorithm	Mode	Optimises	Key weakness
FCFS	Non-preemptive	Simple, fair order	Convoy effect, high avg WT
SJF	Non-preemptive	Min avg WT (optimal)	Starvation, burst unknown
SRTF	Preemptive	Min avg WT overall	Starvation, overhead
Priority	Either	Importance ordering	Starvation (fix: aging)
Round Robin	Preemptive	Response time / fairness	q-sensitive; more switches

Scheduling criteria

Maximise CPU utilisation and throughput; minimise turnaround, waiting and response time. Preemptive scheduling switches on interrupts and arrivals; non-preemptive only on termination or a voluntary I/O block.

Exam Tricks & Tips

• 🎯 SJF/SRTF give the minimum average waiting time — if a question asks "which minimises avg WT", the answer is SJF (non-preemptive) or SRTF (preemptive), never FCFS or RR.
• 🎯 RR with q ≥ max burst = FCFS. Setters hide this: if the quantum is larger than every burst, just solve it as FCFS.
• 🎯 Response time = first dispatch − arrival, not completion. A very common trap is to compute WT and label it RT.
• 🎯 Account for CPU idle time in the Gantt chart when no process has arrived yet — forgetting the idle gap shifts every completion time.
• 🎯 Aging cures starvation — the standard one-line answer whenever a question asks how to prevent indefinite blocking under priority/SJF.
• ❌ Common mistake: using WT = CT − BT. It is WT = TAT − BT = (CT − AT) − BT; the arrival time must be subtracted.

Expected exam pattern

1–2 marks: a table of arrival times and burst times, asked for average WT/TAT under a named algorithm, or a conceptual MCQ ("which is starvation-free / optimal / suffers convoy effect"). Tie-breaking rules (equal burst → FCFS by arrival) are frequently the hidden difficulty.

Quick recap

Learn the three time formulas cold, draw the Gantt chart carefully including idle gaps, remember SJF/SRTF are WT-optimal, RR bounds response time, FCFS has the convoy effect, and aging fixes starvation.

Key formulas

• Turnaround time (TAT) = Completion time − Arrival time.
• Waiting time (WT) = TAT − Burst time.
• Response time = First-CPU time − Arrival time.
• Average WT = (Σ WTᵢ)/n; average TAT = (Σ TATᵢ)/n.
• CPU utilisation = busy time / total time.
• Throughput = processes completed / total time.
• SJF/SRTF minimise average waiting time (optimal among non-/pre-emptive).
• Round Robin: response time bounded by (n−1)·q; smaller quantum q ⇒ more context switches.
• Context-switch overhead fraction = context-switch time / (q + context-switch time).

Usage: build the Gantt chart first, then read completion times off it for TAT and WT.

Worked Example

Problem: Three processes have (arrival time, CPU burst): P1 (0, 7), P2 (2, 4), P3 (4, 1). Compute the average waiting time under (a) FCFS and (b) non-preemptive SJF.

Solution:
Turnaround time (TAT) = completion − arrival; waiting time (WT) = TAT − burst.

(a) FCFS runs in arrival order P1, P2, P3:
P1: 0 → 7 (TAT = 7 − 0 = 7, WT = 7 − 7 = 0)
P2: 7 → 11 (TAT = 11 − 2 = 9, WT = 9 − 4 = 5)
P3: 11 → 12 (TAT = 12 − 4 = 8, WT = 8 − 1 = 7)
Average WT = (0 + 5 + 7)/3 = 12/3 = 4.

(b) Non-preemptive SJF: at t = 0 only P1 is present, so it runs 0 → 7. At t = 7 both P2 (burst 4) and P3 (burst 1) are waiting; pick the shorter, P3:
P1: 0 → 7 (WT = 0)
P3: 7 → 8 (TAT = 8 − 4 = 4, WT = 4 − 1 = 3)
P2: 8 → 12 (TAT = 12 − 2 = 10, WT = 10 − 4 = 6)
Average WT = (0 + 3 + 6)/3 = 9/3 = 3.

Answer: FCFS average waiting time = 4; SJF average waiting time = 3 (SJF is better here).