CPU Scheduling

CPU Scheduling is the process of determining which process will own the CPU for execution while another process is on hold. It is a fundamental function of the operating system.

Why CPU Scheduling?

• Processes alternate between CPU bursts and I/O bursts
• While one process waits for I/O, CPU can execute another process
• Maximizes CPU utilization and system throughput
• Ensures fair resource allocation among processes

Important Terminology

Scheduling Objectives

1. Maximize CPU Utilization – Keep CPU as busy as possible
2. Maximize Throughput – Complete more processes per time unit
3. Minimize Turnaround Time – Reduce total time for process execution
4. Minimize Waiting Time – Reduce time spent in ready queue
5. Minimize Response Time – Quick response for interactive systems
6. Fairness – Each process gets fair share of CPU

Types of Process Schedulers

Operating systems use three distinct types of schedulers to manage process lifecycle and resource utilization across storage, memory, and CPU:

1. Long-Term Scheduler (Job Scheduler)

• Primary Role: Selects processes from the Job Pool on secondary storage (disk) and loads them into Main Memory (Ready Queue).
• Execution Frequency: Executes relatively infrequently (seconds or minutes).
• Controls Degree of Multiprogramming: Directly sets the total number of active processes residing in main memory at any given time.
• Mix Balancing: Ensures a stable balance between:
  • I/O-Bound Processes: Spend more time doing I/O than computations (e.g., file transfer, interactive UI).
  • CPU-Bound Processes: Spend more time performing heavy caculations (e.g., matrix multiplication, video encoding).
  • If all jobs are CPU-bound: I/O queue sits idle, device utilization drops.
  • If all jobs are I/O-bound: Ready queue is empty, CPU sits idle.
• Modern OS Status: Minimal or absent in modern time-sharing OS (like Linux or Windows), where new processes are immediately placed into memory upon creation.

2. Short-Term Scheduler (CPU Scheduler)

• Primary Role: Selects a process from the Ready Queue in main memory and allocates the CPU for execution.
• Execution Frequency: Executes extremely frequently (every 10–100 milliseconds).
• Speed Requirement: Must be blazing fast ($\approx$ microseconds) to minimize CPU scheduling overhead and prevent CPU starvation.
• Working with the Dispatcher:
  • While the scheduler selects which process runs next, the Dispatcher gives actual control of the CPU to that selected process.
  • Dispatcher responsibilities:
    1. Saving old process context and restoring new process context (Context Switch).
    2. Switching mode from kernel mode to user mode.
    3. Jumping to the appropriate location in the user program to restart it.
  • Dispatch Latency: The time taken by the dispatcher to stop one process and start another.

3. Medium-Term Scheduler (Swapper)

• Primary Role: Removes processes temporarily from main memory to secondary storage (Swap Out) and brings them back (Swap In).
• Execution Frequency: Executes at intermediate frequency (when memory pressure or thrashing occurs).
• Reduces Degree of Multiprogramming: Temporarily lowers memory contention when physical RAM is overloaded.
• Handles Suspended States:
  • Suspend Ready: Process was ready to run but swapped out to disk due to memory pressure.
  • Suspend Blocked: Process was waiting for an event/I/O and swapped out to disk.
• Benefit: Frees up contiguous RAM pages for active processes, dramatically reducing page faults and preventing system thrashing.

Comparison of Schedulers

Types of Scheduling

Preemptive Scheduling

• Running process can be interrupted and moved to ready queue
• CPU can be taken away from a process
• Examples: Round Robin, SRTF, Priority (Preemptive)
• Better for time-sharing systems

Non-Preemptive Scheduling

• Once CPU is allocated, process runs until completion or I/O wait
• CPU cannot be taken away from running process
• Examples: FCFS, SJF, Priority (Non-Preemptive)
• Simpler to implement

CPU Scheduling Algorithms

1. First Come First Serve (FCFS)

Concept: Processes are executed in the order they arrive.
Characteristics:

• Non-preemptive
• Simple to implement using FIFO queue
• Poor average waiting time (especially if long process arrives first)
• Convoy Effect: Short processes wait behind long ones
  Example:

  Process	AT	BT
  P1	0	24
  P2	1	3
  P3	2	3
  Gantt Chart: `	P1 (0-24)	P2 (24-27)
  Calculations:

• P1: TAT = 24-0 = 24, WT = 24-24 = 0
• P2: TAT = 27-1 = 26, WT = 26-3 = 23
• P3: TAT = 30-2 = 28, WT = 28-3 = 25
• Average WT = (0+23+25)/3 = 16

2. Shortest Job First (SJF)

Concept: Process with smallest burst time executes first.
Characteristics:

• Non-preemptive
• Optimal average waiting time for non-preemptive algorithms
• Difficult to know burst time in advance
• May cause starvation for longer processes
  Example:

  Process	AT	BT
  P1	0	7
  P2	2	4
  P3	4	1
  P4	5	4
  Execution Order (after P1): P3 → P2 → P4

3. Shortest Remaining Time First (SRTF)

Concept: Preemptive version of SJF. Process with shortest remaining time executes.
Characteristics:

• Preemptive
• Most optimal algorithm (minimum average WT)
• High context switching overhead
• Starvation possible for long processes
  Example:

  Process	AT	BT
  P1	0	8
  P2	1	4
  P3	2	2
  P4	3	1
  Gantt Chart: `	P1(0-1)	P2(1-2)

4. Round Robin (RR)

Concept: Each process gets a fixed time quantum. After quantum expires, process moves to end of ready queue.
Characteristics:

• Preemptive
• Fair allocation of CPU
• Performance depends on time quantum size
• No starvation
• Higher context switching overhead
  Time Quantum Selection:
• Too small → High context switching overhead
• Too large → Becomes FCFS
• Ideal: 80% of CPU bursts should be shorter than quantum
  Example (Time Quantum = 4):

  Process	AT	BT
  P1	0	5
  P2	1	4
  P3	2	2
  P4	3	1
  Gantt Chart: `	P1(0-4)	P2(4-8)

5. Priority Scheduling

Concept: Each process has a priority. Higher priority processes execute first.
Types:

• Preemptive: Running process can be preempted if higher priority arrives
• Non-Preemptive: Running process completes before higher priority gets CPU
  Priority Assignment:
• Lower number = Higher priority (common convention)
• Can be static or dynamic
  Problem: Starvation
• Low priority processes may never execute
  Solution: Aging
• Gradually increase priority of waiting processes
  Example:

  Process	AT	BT	Priority
  P1	0	10	3
  P2	0	1	1
  P3	0	2	4
  P4	0	1	5
  P5	0	5	2
  Execution Order: P2 → P5 → P1 → P3 → P4

6. Highest Response Ratio Next (HRRN)

Concept: Non-preemptive algorithm that considers both waiting time and burst time.
Response Ratio Formula:

Response Ratio = (Waiting Time + Burst Time) / Burst Time

Characteristics:

• Non-preemptive
• Balances between SJF and FCFS
• Prevents starvation (long waiting increases ratio)
• Fair to both short and long processes

7. Multilevel Queue Scheduling

Concept: Ready queue is divided into multiple separate queues based on process properties (e.g., priority, memory size, process type).

Characteristics:

• Each queue has its own scheduling algorithm.
• Processes stay in their assigned queue permanently (no movement between queues).
• Scheduling between queues is fixed-priority preemptive scheduling (e.g., serve Queue 1 entirely before Queue 2) or time-sliced across queues.

8. Multilevel Feedback Queue Scheduling (MLFQ)

Concept: Processes can dynamically move between queues based on their CPU-burst behavior and aging.

Characteristics:

• Most flexible and general-purpose CPU scheduling algorithm.
• I/O-bound processes stay in high-priority short-quantum queues.
• CPU-intensive processes automatically sink to lower-priority long-quantum/FCFS queues.
• Prevents starvation by upgrading aging processes that wait too long in lower queues.

Key Parameters:

• Number of queues
• Scheduling algorithm for each queue
• Criteria to upgrade a process to a higher queue (Aging)
• Criteria to demote a process to a lower queue
• Method to select entry queue for incoming processes

Algorithm Comparison

Special Scheduling Scenarios

Real-Time Scheduling

Hard Real-Time:

• Deadlines MUST be met
• Used in critical systems (medical, aviation)
  Soft Real-Time:
• Deadlines are preferred but not mandatory
• Used in multimedia, gaming
  Algorithms:
• Rate Monotonic (RM): Static priority based on period
• Earliest Deadline First (EDF): Dynamic priority based on deadline

Thread Scheduling

User-Level Threads:

• Thread library manages scheduling
• OS schedules processes, not threads
  Kernel-Level Threads:
• OS directly schedules threads
• More efficient for multi-core systems

Placement Interview Questions

Q1: Which scheduling algorithm is optimal?

SRTF is optimal for minimizing average waiting time.
Q2: What is convoy effect?
When short processes wait behind a long process in FCFS, leading to poor CPU utilization.
Q3: How to prevent starvation in Priority Scheduling?
Use aging technique - gradually increase priority of waiting processes.
Q4: What is the ideal time quantum for Round Robin?
Should be such that 80% of CPU bursts complete within one quantum.
Q5: Difference between preemptive and non-preemptive scheduling?
Preemptive allows CPU to be taken from running process; non-preemptive doesn't.
Q6: What is turnaround time?
Total time from process arrival to completion (TAT = CT - AT).

Practice Problem

Given:

| Process | AT | BT |
| :--- | :--- | :--- | :--- | :--- |
| P1 | 0 | 5 |
| P2 | 1 | 3 |
| P3 | 2 | 8 |
| P4 | 3 | 6 |

Calculate completion time (CT), turnaround time (TAT), waiting time (WT), and average waiting time for FCFS, SJF (Non-preemptive), and Round Robin ($q=2$).