1. Introduction
Scheduling criteria are the performance metrics used to evaluate, compare, and design CPU scheduling algorithms. Since multiple processes compete for CPU time, the operating system must determine how to allocate this limited resource in a way that achieves specific system objectives.
Different scheduling algorithms prioritize different goals. Some algorithms focus on maximizing CPU utilization, while others emphasize responsiveness, fairness, or throughput. Because these objectives often conflict with one another, no single scheduling algorithm can simultaneously optimize all performance metrics.
For this reason, operating systems rely on scheduling criteria to measure effectiveness and analyze trade-offs between competing design goals.
Scheduling criteria help answer questions such as:
Is the CPU being utilized efficiently?
Are processes completing quickly?
Are users receiving fast responses?
Are processes being treated fairly?
Is the system achieving high throughput?
A thorough understanding of scheduling criteria is essential before studying specific scheduling algorithms because these metrics provide the basis for evaluating their performance.
2. Purpose of Scheduling Criteria
Scheduling criteria provide a quantitative framework for assessing CPU scheduling performance.
They are used to:
Evaluate Scheduling Algorithms
Determine whether an algorithm performs efficiently under specific workloads.
Example:
FCFS
SJF
Round Robin
can be compared using scheduling metrics.
Compare System Performance
Measure how different scheduling strategies affect:
CPU usage
Waiting time
Response time
Throughput
Design Scheduling Policies
Operating system designers use scheduling criteria to create algorithms that satisfy desired objectives.
Examples:
Interactive systems prioritize response time.
Batch systems prioritize throughput.
Balance Conflicting Objectives
Scheduling often involves trade-offs.
For example:
Improving response time may increase context switching overhead.
Maximizing throughput may increase waiting time.
Scheduling criteria help analyze these trade-offs systematically.
3. Primary Scheduling Criteria
The five most important scheduling criteria are:
CPU Utilization
Throughput
Turnaround Time
Waiting Time
Response Time
These metrics are widely used to evaluate scheduling algorithms.
3.1 CPU Utilization
Definition
CPU Utilization measures the percentage of time the CPU is actively executing processes rather than remaining idle.
Mathematically:
CPU utilization is typically expressed as a percentage.
Objective
The primary goal is:
Maximize CPU utilization
An efficient operating system attempts to keep the CPU busy whenever possible.
Example
Suppose:
CPU busy for 90 seconds
Total observation time = 100 seconds
Then:
CPU Utilization = 90%
This indicates efficient CPU usage.
Importance
Higher CPU utilization generally indicates:
Better resource utilization
Less idle time
Improved efficiency
Important Insight
High CPU utilization is desirable, but it should not be achieved at the expense of user experience.
For example:
CPU Utilization = 99%
Response Time = Very Poor
Although utilization is high, the system may feel unresponsive.
Therefore:
CPU utilization alone is not sufficient to judge scheduling quality.
3.2 Throughput
Definition
Throughput represents the number of processes completed per unit time.
Mathematically:
Objective
The goal is:
Maximize throughput
A higher throughput means the system completes more work within a given period.
Example
Suppose:
100 processes completed
Total time = 50 seconds
Then:
Throughput = 2 Processes/Second
Importance
Throughput measures:
Overall productivity
System efficiency
Work completed
Where Throughput Matters Most
Batch Systems
Batch systems prioritize:
Large job completion
Maximum productivity
Therefore throughput becomes a primary metric.
Example
Payroll processing systems focus on:
Maximum Jobs Completed
rather than immediate responsiveness.
Important Insight
A scheduling algorithm that maximizes throughput may not provide the best response time.
3.3 Turnaround Time
Definition
Turnaround Time is the total time required for a process to complete after submission.
Mathematically:
Objective
The goal is:
Minimize turnaround time
Processes should complete as quickly as possible.
Example
Suppose:
Arrival Time = 2 sec
Completion Time = 12 sec
Then:
Turnaround Time = 10 sec
Components of Turnaround Time
Turnaround time includes:
Waiting time
CPU execution time
I/O waiting time
Thus:
Process Submission
↓
Waiting
↓
Execution
↓
I/O
↓
Completion
All contribute to turnaround time.
Importance
Turnaround time is especially important in:
Batch systems
Scientific computing
Large computational workloads
Users often care about:
When the job finishes
rather than how quickly it starts.
3.4 Waiting Time
Definition
Waiting Time is the total time a process spends waiting in the Ready Queue before receiving CPU service.
Mathematically:
Objective
The goal is:
Minimize waiting time
Processes should spend as little time as possible waiting for CPU allocation.
Example
Suppose:
Turnaround Time = 15 sec
CPU Burst Time = 5 sec
Then:
Waiting Time = 10 sec
Importance
Waiting time directly reflects scheduling efficiency.
Large waiting times indicate:
Poor scheduling decisions
Long ready queues
Resource contention
Impact on Users
Excessive waiting time may cause:
Slow application startup
Delayed execution
Reduced system responsiveness
3.5 Response Time
Definition
Response Time measures the interval between process arrival and the first time it receives CPU service.
Mathematically:
Objective
The goal is:
Minimize response time
Processes should begin execution as quickly as possible.
Example
Suppose:
Arrival Time = 0 sec
First CPU Allocation = 2 sec
Then:
Response Time = 2 sec
Important Distinction
Response time measures:
Time until first response
not:
Time until completion
A process may respond quickly while still taking a long time to finish.
Importance
Response time is critical in:
Interactive systems
Web applications
GUI environments
Users generally notice response time more than turnaround time.
Example:
When clicking a button:
Immediate Feedback → Good UX
Even if final completion occurs later.
4. Visual Understanding of Time Metrics
Consider the following process timeline:
Arrival First CPU Completion
| | |
v v v
---Waiting---|--Execution--|--I/O--|
Response Time
Arrival → First CPU Allocation
Waiting Time
Total Time in Ready Queue
Turnaround Time
Arrival → Completion
CPU Utilization
CPU Busy Time / Total Time
Throughput
Completed Processes / Unit Time
5. Relationships Between Metrics
Scheduling metrics are closely interconnected.
Turnaround Time Relationship
Turnaround time consists of:
Waiting Time
+ CPU Execution Time
+ I/O Time
Therefore:
Reducing Waiting Time
↓
Reduces Turnaround Time
Response Time Relationship
Improving response time often requires:
Frequent scheduling
Smaller time quanta
This may increase:
Context switching overhead
Throughput Relationship
Higher throughput generally requires:
Efficient CPU utilization
Reduced idle time
These relationships mean improving one metric may affect others.
6. Trade-offs Between Criteria
Scheduling algorithms must balance competing objectives.
| Criterion | Goal | Possible Conflict |
|---|---|---|
| CPU Utilization | Maximize | May reduce responsiveness |
| Throughput | Maximize | May increase waiting time |
| Turnaround Time | Minimize | May affect fairness |
| Waiting Time | Minimize | May cause starvation |
| Response Time | Minimize | May increase context switching |
Example Trade-Off
Suppose very short jobs are always prioritized.
Benefits:
Low waiting time
Low turnaround time
Problem:
Long jobs may starve
Thus:
Efficiency ↑
Fairness ↓
Operating system design involves balancing these competing objectives.
7. Practical Examples
Different operating systems prioritize different scheduling criteria depending on their workload.
Batch Systems
Examples:
Payroll processing
Scientific computation
Large-scale data processing
Primary goals:
High throughput
High CPU utilization
Focus:
Maximum Work Completed
Interactive Systems
Examples:
Desktop computers
Mobile devices
Web applications
Primary goals:
Low response time
Fairness
Focus:
Fast User Feedback
Real-Time Systems
Examples:
Aircraft control systems
Medical monitoring systems
Industrial automation
Primary goals:
Predictability
Deadline satisfaction
Focus:
Correct Timing
rather than maximum throughput.
Summary of Scheduling Criteria
| Criterion | Objective |
|---|---|
| CPU Utilization | Maximize CPU usage |
| Throughput | Maximize completed processes |
| Turnaround Time | Minimize total completion time |
| Waiting Time | Minimize ready queue delay |
| Response Time | Minimize first response delay |