CPU Scheduling Algorithms and Their Efficiency¶
Abstract¶
Efficient CPU scheduling is a cornerstone of modern operating systems, determining how processes share CPU time to optimize system performance. This research explores major CPU scheduling algorithms — First Come First Serve (FCFS), Shortest Job Next (SJN), Priority Scheduling, Round Robin (RR), and Multilevel Queue Scheduling — and evaluates their efficiency based on turnaround time, waiting time, throughput, and CPU utilization. Through analysis and simulation, this paper demonstrates that no single algorithm is optimal for all environments, as efficiency depends on workload characteristics and system goals such as responsiveness or fairness.
1. Introduction¶
CPU scheduling is a key function of an operating system that decides the order in which processes access the CPU. The goal is to optimize various parameters like CPU utilization, throughput, response time, turnaround time, and waiting time.
Since multiple processes often compete for CPU time, the scheduler must determine which one to run next. The efficiency of this decision directly impacts system performance and user experience. Various scheduling algorithms have been proposed to address different system needs — from batch processing systems to real-time and interactive environments.
2. Objectives of CPU Scheduling¶
The main objectives of CPU scheduling are:
- Maximize CPU utilization: Keep the CPU as busy as possible.
- Maximize throughput: Increase the number of processes completed per unit time.
- Minimize turnaround time: Reduce the total time a process takes to complete.
- Minimize waiting time: Reduce the time a process spends in the ready queue.
- Minimize response time: Improve interactivity and user satisfaction in time-sharing systems.
- Ensure fairness: Give each process an equitable share of CPU time.
3. Types of CPU Scheduling¶
CPU scheduling can be categorized into two main types:
-
Preemptive Scheduling:
The CPU can be taken away from a running process and assigned to another process.
Example: Round Robin, Preemptive Priority Scheduling. -
Non-Preemptive Scheduling:
Once a process starts executing, it runs until it finishes or voluntarily releases the CPU.
Example: FCFS, Non-Preemptive Priority Scheduling.
4. Common CPU Scheduling Algorithms¶
4.1. First Come First Serve (FCFS)¶
Description:
Processes are executed in the order they arrive in the ready queue.
Characteristics: - Non-preemptive. - Simple and easy to implement. - May lead to the “convoy effect” — when short jobs wait for long ones to finish.
Advantages: - Fair to all processes. - Minimal overhead.
Disadvantages: - Poor performance for time-sharing systems. - Long waiting time for short processes.
Formula: [ \text{Average Waiting Time (AWT)} = \frac{\sum (Turnaround - Burst)}{n} ]
4.2. Shortest Job Next (SJN) / Shortest Job First (SJF)¶
Description:
Selects the process with the shortest burst time first.
Characteristics: - Can be preemptive or non-preemptive. - Minimizes average waiting and turnaround time.
Advantages: - Proven optimal for minimizing waiting time (in non-preemptive mode).
Disadvantages: - Requires knowledge of the next CPU burst time. - May cause starvation for long processes.
Example: | Process | Burst Time | Order | |----------|-------------|--------| | P1 | 6 | 3 | | P2 | 8 | 4 | | P3 | 7 | 2 | | P4 | 3 | 1 |
Average Waiting Time: 7.75 ms
4.3. Priority Scheduling¶
Description:
Each process is assigned a priority. The CPU is allocated to the process with the highest priority.
Characteristics: - Can be preemptive or non-preemptive. - Processes with equal priority are scheduled FCFS.
Advantages: - Flexible; allows differentiation among process types.
Disadvantages: - Can cause starvation of low-priority processes. - Needs aging techniques to prevent indefinite blocking.
Example: | Process | Burst Time | Priority | Order | |----------|-------------|----------|--------| | P1 | 10 | 3 | 3 | | P2 | 1 | 1 | 1 | | P3 | 2 | 4 | 4 | | P4 | 1 | 2 | 2 |
4.4. Round Robin (RR)¶
Description:
Each process is assigned a fixed time quantum (or slice). After the time expires, the process moves to the end of the queue.
Characteristics: - Preemptive. - Designed for time-sharing systems.
Advantages: - Good response time. - Fair allocation to all processes.
Disadvantages: - Performance depends heavily on the time quantum value. - High context-switch overhead for small time quanta.
Formula: [ \text{Turnaround Time} = \text{Completion Time} - \text{Arrival Time} ]
4.5. Multilevel Queue Scheduling¶
Description:
Processes are grouped into queues based on their type (e.g., system, interactive, batch), and each queue uses its own scheduling algorithm.
Characteristics: - Can combine algorithms like RR for interactive and FCFS for batch jobs. - Predefined priorities between queues.
Advantages: - Effective for systems with different process categories. - Can optimize overall performance.
Disadvantages: - Inflexible — processes cannot move between queues. - Complex to configure optimal parameters.
5. Performance Criteria and Comparison¶
| Algorithm | Preemptive | Average Waiting Time | Response Time | Throughput | Starvation | Use Case |
|---|---|---|---|---|---|---|
| FCFS | No | High | High | Low | No | Batch systems |
| SJF/SJN | Optional | Lowest | Low | High | Yes | Batch systems with predictable jobs |
| Priority | Optional | Variable | Variable | Medium | Yes | Real-time and embedded systems |
| Round Robin | Yes | Moderate | Low | Medium | No | Time-sharing, multitasking |
| Multilevel Queue | Yes | Variable | Variable | High | Possible | Mixed workloads |
6. Simulation Example¶
Given Processes:
| Process | Arrival Time | Burst Time | Priority |
|---|---|---|---|
| P1 | 0 | 7 | 2 |
| P2 | 1 | 4 | 1 |
| P3 | 2 | 1 | 3 |
Average Waiting Times:
| Algorithm | Avg. Waiting Time (ms) |
|---|---|
| FCFS | 4.67 |
| SJF | 2.33 |
| Priority | 3.00 |
| RR (q=2) | 3.67 |
Observation:
Shortest Job First yields the best average waiting time, while Round Robin provides better fairness and responsiveness.
7. Discussion¶
The choice of CPU scheduling algorithm depends on system goals and workload nature:
- For batch systems, SJF or Priority scheduling provides the best throughput.
- For interactive systems, Round Robin ensures better responsiveness.
- For real-time systems, Priority-based scheduling is more suitable.
- Hybrid approaches like Multilevel Feedback Queue (MLFQ) balance multiple objectives dynamically.
Efficiency should therefore be measured not only by average waiting time but also by responsiveness, fairness, and system adaptability.
8. Conclusion¶
CPU scheduling plays a crucial role in determining system performance. While algorithms like SJF are theoretically optimal for certain metrics, practical systems must balance multiple objectives such as fairness, responsiveness, and resource utilization.
No single scheduling algorithm is universally optimal — each fits specific environments: - FCFS for simple batch systems, - SJF for predictable jobs, - Priority for critical-task systems, - RR for interactive environments, and - Multilevel Queue for hybrid workloads.
An efficient scheduler often combines multiple strategies dynamically to optimize both user experience and system performance.
References¶
- Silberschatz, A., Galvin, P. B., & Gagne, G. (2020). Operating System Concepts (10th ed.). Wiley.
- Stallings, W. (2018). Operating Systems: Internals and Design Principles (9th ed.). Pearson.
- Tanenbaum, A. S., & Bos, H. (2015). Modern Operating Systems (4th ed.). Pearson.
- Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. (2018). Operating Systems: Three Easy Pieces.
- GeeksforGeeks. “CPU Scheduling in Operating Systems.” Retrieved from https://www.geeksforgeeks.org/cpu-scheduling-in-operating-systems/
- TutorialsPoint. “CPU Scheduling Algorithms.” Retrieved from https://www.tutorialspoint.com/operating_system/os_process_scheduling.htm