Complete visual guide with formulas, memory tricks, and worked examples
What is CPU Scheduling?
Definition
CPU Scheduling is the process of deciding which process gets the CPU next from the ready queue. The OS uses a scheduler (short-term scheduler) to select processes and dispatch them to the CPU.
Why we need it: Multiple processes compete for CPU time. Scheduling ensures fair, efficient use of the CPU — maximizing throughput and minimizing wait time.
Memory Trick: Think of CPU scheduling like a bank queue. Different algorithms = different queue rules. FCFS = normal queue. SJF = "express lane" for quick customers. Round Robin = token system (everyone gets limited time).
Key Terms & Formulas
Arrival Time (AT) = When process enters the ready queue
Burst Time (BT) = CPU time the process needs
Completion Time (CT) = When process finishes execution
Turnaround Time (TAT) = CT − AT
Waiting Time (WT) = TAT − BT
Response Time (RT) = First CPU allocation − AT
Optimization Goals
Maximize CPU Utilization — Keep CPU busy as much as possible
Maximize Throughput — More processes completed per unit time
Minimize Turnaround Time — Less time from submit to finish
Minimize Waiting Time — Less time in ready queue
Minimize Response Time — Faster first response (important for interactive systems)
1. FCFS — First Come First Serve
How it Works
Processes execute in the order of their arrival. Non-preemptive — once started, a process runs to completion.
Advantage: Simple, fair, no starvation Disadvantage:Convoy Effect — short processes wait behind long ones
The process with the shortest burst time executes next. Can be preemptive (SRTF) or non-preemptive.
Advantage: Minimum average waiting time (optimal!) Disadvantage:Starvation — long processes may never execute. Requires knowing burst time in advance (impractical).
Trick: SJF = "Express checkout lane at supermarket" — the person with fewest items goes first. Fair for short tasks, but someone with a full cart might wait forever!
3. Round Robin (RR)
How it Works
Each process gets a fixed time quantum (Q). When it expires, the process is preempted and goes to the back of the queue.
Best for: Time-sharing systems, interactive processes Key factor: Quantum size critically affects performance:
• Small Q → More context switches (overhead)
• Large Q → Degenerates into FCFS
Rule: If Q is too small → too many context switches
Rule: If Q is too large → behaves like FCFS
Ideal: Q > 80% of burst times (common rule of thumb)
4. Priority Scheduling
How it Works
Each process has a priority number. The process with the highest priority (often lowest number) runs first.
Preemptive version: New high-priority process can preempt current process Problem: Starvation of low-priority processes Solution:Aging — gradually increase priority of waiting processes