Session 2.2: Process Scheduling
Understanding CPU scheduling algorithms and their characteristics
Learning Objectives
By the end of this session, you will be able to:
- Explain the CPU-I/O burst cycle
- Understand scheduling terminology and metrics
- Analyze FCFS, SJF, Round Robin, and Priority scheduling
- Calculate performance metrics for each algorithm
- Compare algorithms and select appropriate ones
- Understand multilevel queue concepts
Key Concept
CPU scheduling algorithms determine which process gets CPU time and when, directly impacting system performance, response time, and resource utilization.
CPU-I/O Burst Cycle
Process execution consists of alternating sequences of CPU execution and I/O waits. Understanding this cycle is crucial for effective scheduling.
CPU Burst
Period when process executes instructions on the CPU. Duration varies widely but typically follows a pattern with many short bursts and fewer long ones.
I/O Burst
Period when process waits for I/O operations to complete. Process is blocked and CPU can be allocated to other processes.
Process Characteristics
I/O-bound processes:
- Many short CPU bursts
- Frequent I/O operations
- Interactive applications
- Need quick response times
CPU-bound processes:
- Fewer, longer CPU bursts
- Minimal I/O operations
- Computational applications
- Focus on throughput
Scheduling Terminology
Essential Formulas (Remember These!)
Turnaround Time (TAT):
TAT = Completion Time - Arrival Time
Waiting Time (WT):
WT = Turnaround Time - Burst Time
Response Time (RT):
RT = Start Time - Arrival Time
Average Metrics:
Avg = Sum of all values ÷ Number of processes
Time-Related Terms:
- Arrival Time (AT): When process enters ready queue
- Burst Time (BT): Total CPU time required
- Start Time (ST): When process first gets CPU
- Completion Time (CT): When process finishes
Performance Metrics:
- CPU Utilization: Percentage of time CPU is busy
- Throughput: Processes completed per unit time
- Fairness: Equal treatment of processes
- Starvation: Process waiting indefinitely
First-Come, First-Served (FCFS)
Algorithm Logic:
- Processes served in order of arrival (FIFO queue)
- Once process starts, runs to completion
- No preemption allowed
- Fair but can cause long waiting times
Example Problem:
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
Advantages
- Simple to implement
- No starvation
- Fair (first come, first served)
- Low overhead
Disadvantages
- Long average waiting time
- Convoy effect
- Poor for interactive systems
- No priority consideration
FCFS Gantt Chart:
Convoy Effect
When short processes wait for a long process to complete, causing poor average waiting time. Like being stuck behind a slow truck on a single-lane road.
Shortest Job First (SJF)
Optimality Property
SJF is provably optimal for minimizing average waiting time when all processes arrive simultaneously.
Non-Preemptive SJF:
- Select process with shortest burst time
- Once started, runs to completion
- New arrivals wait until current process finishes
- Ties broken by arrival time (FCFS)
Non-Preemptive SJF:
Preemptive SJF (SRTF):
- Check remaining time vs new arrivals
- Preempt if shorter remaining time arrives
- Resume preempted process later
- More context switches than non-preemptive
Preemptive SJF (SRTF):
Advantages
- Optimal average waiting time
- Good for batch systems
- Efficient resource utilization
Disadvantages
- Difficult to predict burst times
- Starvation of long processes
- Not suitable for interactive systems
Starvation Problem
Long processes may wait indefinitely if shorter processes keep arriving. Solution: Aging - gradually increase priority of waiting processes.
Round Robin (RR)
Algorithm Logic:
- Each process gets fixed time quantum (Q)
- If process completes within Q → remove from queue
- If process uses full Q → move to queue end
- New arrivals added to queue end
- Circular queue structure
Example with Time Quantum = 4:
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 24 |
| P2 | 0 | 3 |
| P3 | 0 | 3 |
Time Quantum Selection
Too Small: High overhead from context switches
Too Large: Becomes FCFS
Optimal: 10-100 milliseconds
Round Robin Gantt Chart (Q=4):
Queue Management
Track queue state at each time quantum:
- Time 0: Queue = [P1, P2, P3], P1 runs
- Time 4: Queue = [P2, P3, P1], P2 runs
- Time 7: Queue = [P3, P1], P3 runs (P2 completed)
- Time 10: Queue = [P1], P1 runs (P3 completed)
Advantages
- Fair allocation of CPU time
- Good response time
- No starvation
- Suitable for time-sharing systems
Disadvantages
- Higher average waiting time than SJF
- Context switch overhead
- Performance depends on quantum size
- Not optimal for any metric
Priority Scheduling
Priority Convention
In this course: Lower number = Higher priority
Priority 1 > Priority 2 > Priority 3 (Priority 1 is highest)
Priority Assignment:
Internal Priorities:
- Time limits
- Memory requirements
- File usage
- CPU vs I/O ratio
External Priorities:
- Process importance
- User type (system vs user)
- Payment/resource allocation
- Administrative policies
Example Problem:
| Process | AT | BT | Priority |
|---|---|---|---|
| P1 | 0 | 10 | 3 |
| P2 | 1 | 1 | 1 |
| P3 | 2 | 2 | 4 |
| P4 | 3 | 1 | 5 |
| P5 | 4 | 5 | 2 |
Non-Preemptive Priority:
Preemptive Priority:
Starvation and Aging
Problem: Low-priority processes may wait indefinitely
Solution - Aging: Gradually increase priority of waiting processes
Example: Increase priority by 1 every 15 minutes of waiting
Special Case
SJF is actually a special case of priority scheduling where priority = 1/burst_time (shorter jobs have higher priority)
Multilevel Queue Scheduling
Multilevel Queue:
- Processes partitioned into separate queues
- Each queue has its own scheduling algorithm
- Fixed-priority preemptive scheduling between queues
- Processes cannot move between queues
Typical Queue Structure:
Advantages
- Different algorithms for different process types
- System processes get priority
- Flexible scheduling policies
Disadvantages
- Starvation of lower queues
- Inflexible - no queue movement
- Complex implementation
Multilevel Feedback Queue:
Key Improvement
Processes can move between queues based on behavior:
- CPU-intensive processes: Move to lower-priority queues
- I/O-bound processes: Stay in higher-priority queues
- Aging: Processes waiting too long move to higher-priority queues
- Configurable parameters: Number of queues, scheduling algorithms, upgrade/downgrade criteria
Most General Algorithm
Multilevel Feedback Queue is the most general and complex scheduling algorithm. It can be configured to behave like any other scheduling algorithm by adjusting its parameters.
Algorithm Comparison
| Algorithm | Preemptive | Avg WT | Response Time | Starvation | Complexity | Best Use Case |
|---|---|---|---|---|---|---|
| FCFS | No | Poor | Poor | No | Low | Batch systems |
| SJF | No | Optimal | Good | Yes | Medium | Batch systems (known burst times) |
| SRTF | Yes | Optimal | Good | Yes | High | Systems with predictable workloads |
| Round Robin | Yes | Fair | Good | No | Medium | Time-sharing, interactive systems |
| Priority | Both | Variable | Variable | Yes* | Medium | Real-time, system processes |
| Multilevel | Yes | Variable | Good | Yes* | High | Complex systems with mixed workloads |
Selection Guidelines
- Batch Systems: FCFS or SJF
- Interactive Systems: Round Robin
- Real-time Systems: Priority Scheduling
- General Purpose: Multilevel Feedback Queue
Performance Trade-offs
- Throughput vs Response Time: Often inversely related
- Fairness vs Efficiency: Fair algorithms may not be optimal
- Simplicity vs Performance: Complex algorithms perform better
- Predictability vs Adaptability: Static vs dynamic policies
Session Summary
Key Takeaways:
- CPU scheduling algorithms determine process execution order and timing
- Each algorithm has trade-offs between different performance metrics
- FCFS is simple but can cause convoy effect
- SJF is optimal for average waiting time but may cause starvation
- Round Robin provides fairness and good response time
- Priority scheduling handles different process importance levels
- Multilevel queues provide flexibility for mixed workloads
Important Formulas:
TAT = CT - AT (Turnaround Time)
WT = TAT - BT (Waiting Time)
RT = ST - AT (Response Time)
Average = Sum ÷ Number of processes
Next Session
Session 2.3: Operations on Processes
Process creation, termination, hierarchy, and interprocess communication introduction
Study Tips:
- Practice calculating TAT, WT, and RT for different algorithms
- Draw Gantt charts step-by-step for each algorithm
- Understand when to use each algorithm based on system requirements
- Remember the trade-offs: optimal vs fair, simple vs complex
- Practice identifying process characteristics (CPU-bound vs I/O-bound)