Process Scheduling
CPU Scheduling Algorithms
Operating Systems | Computer Science
A complete guide for quick understanding
240280107027 – Dave krisha N .
240280107057 – Kachhatiya Paras V.
240280107059 – Kalariya Dhruvi M.
240280107062 – Kanzariya Amit B.
240280107064 – Katharotiya Prem A.
Introduction
🖥️ What is an OS? ⚙️ What is a Process?
• Operating System manages hardware & software • A program in execution
• Acts as bridge between user & hardware • Has its own memory space & resources
• Handles memory, files, devices & CPU • Can be Running, Ready, or Waiting
🔄 Process Life Cycle
• New → Ready → Running → Waiting → Terminated
• CPU can run only ONE process at a time
• Scheduling decides which process gets CPU next
CPU Scheduling
📌 Definition
• The process of deciding which process in the Ready Queue gets the CPU
• Handled by the Short-Term Scheduler (Dispatcher)
❓ Why Needed? 🎯 Goals
• CPU must be kept busy at all times • Max CPU utilization
• Maximize throughput & minimize wait time • Max throughput
• Ensure fairness among all processes • Min turnaround, wait & response time
Key Terms
AT Arrival Time TAT Turnaround Time
Time when process enters Ready Queue TAT = CT − AT (total time in system)
BT Burst Time WT Waiting Time
Total CPU time required by the process WT = TAT − BT (time spent waiting)
CT Completion Time RT Response Time
Time when process finishes execution Time from arrival to first CPU allocation
Types of Scheduling
🔴 Non-Preemptive 🟢 Preemptive
• Process holds CPU until it finishes or blocks • CPU can be taken away from running process
• No forceful removal from CPU • OS forcefully switches to higher-priority task
• Simple to implement • Better response time
• Can cause long waiting times • More overhead due to context switching
• Examples: FCFS, SJF (non-preemptive) • Examples: SRTF, Round Robin, Priority
VS
FCFS — First Come First Serve
📋 Key Points 📊 Example
• Simplest scheduling algorithm Process AT BT CT WT
• Non-preemptive
• Process served in arrival order P1 0 4 4 0
• Easy to implement using a Queue
P2 1 3 7 3
P3 2 5 12 5
Gantt Chart: | P1 (0–4) | P2 (4–7) | P3 (7–12) |
✅ Advantages ❌ Disadvantages
• Simple & easy to implement • Convoy effect — short jobs wait behind long ones
• No starvation (fair order) • High average waiting time
SJF — Shortest Job First
📋 Key Points ⚡ Example
• Process with shortest burst time runs first • P1: BT=6, P2: BT=2, P3: BT=4
• Can be preemptive (SRTF) or non-preemptive • Order: P2 → P3 → P1
• Gives minimum average waiting time • Avg WT = (0+1+3)/3 = 1.33 ms
• Requires knowledge of burst time in advance
✅ Advantages ⚠️ Starvation
• Minimum average waiting time • Long processes may never get CPU
• Optimal for batch systems • Solution: Aging — gradually increase priority of
waiting processes
Round Robin (RR)
📋 Key Points
• Each process gets a fixed time slice called Time Quantum (TQ)
• Preemptive — after TQ expires, process goes back to end of ready queue
• Designed for time-sharing systems
• Best for equal priority processes
⚡ Example (TQ = 2) ⚖️ Time Quantum Effect
• P1: BT=5, P2: BT=3, P3: BT=2 • Small TQ → High context switching overhead
• P1(2) → P2(2) → P3(2) → P1(2) → P2(1) → P1(1) • Large TQ → Behaves like FCFS
• Avg WT = (4+5+2)/3 = 3.67 ms • Ideal TQ: 10–100 ms in practice
✅
• Fair — every process gets equal CPU share | No starvation
Priority Scheduling
📋 How It Works
• Each process is assigned a priority number
• CPU always goes to the highest-priority process (lower number = higher priority in most systems)
• Can be preemptive or non-preemptive
📊 Example ⚠️ Starvation Problem
• P1: Priority 3, P2: Priority 1, P3: Priority 2 • Low-priority processes may never execute
• Order: P2 → P3 → P1 • Example: high-priority jobs keep coming in
🛡️ Solution: Aging
Gradually increase the priority of processes that wait too long → prevents starvation
Low priority processes may stay in the ready queue
indefinitely if higher priority jobs keep arriving.
0 The Solution: AGING
Gradually increase the priority of processes that
High Priority Process wait in the system for a long time.
Algorithm Comparison
Algorithm Type Overhead Starvation Fairness Best For
FCFS Non-Pre Low No Yes Simple batch
SJF Both Low Yes No Min wait time
SRTF Preemptive Medium Yes No Optimal wait
Round Robin Preemptive High No Yes Time-sharing
Priority Both Medium Yes No Real-time OS
Priority+Aging Both Medium No Yes General use
PROCESS CONTROL BLOCK (PCB)
The Repository of Info
Each process is represented in the OS by
a PCB. It stores all data needed to restart
a process after it's been interrupted.
Process ID (PID): Unique identifier.
Memory Limits: Base/Limit registers.
Problem: Convoy Effect
When a long CPU-bound process blocks several
short processes, leading to poor device
utilization and high wait times.
Efficiency drops significantly as shown in the
throughput trend when P1 burst is very large.
OPTIMAL WAIT: SJF ANALYSIS
Conclusion
1 CPU Scheduling — Ensures efficient use of CPU & fair process execution
2 FCFS — Simple but can cause high waiting times (Convoy Effect)
3 SJF — Optimal average wait time but can starve long processes
4 Round Robin — Best for time-sharing; fair but has context-switch overhead
5 Priority Scheduling — Useful for real-time tasks; use Aging to prevent starvation