CPU Scheduling Algorithms: FCFS, SJF, Round Robin Complete Guide

CPU scheduling is a fundamental concept in operating systems that determines how processes are allocated processor time. The CPU scheduler makes decisions about which process should run next when multiple processes are competing for CPU resources. Understanding different scheduling algorithms is crucial for system performance optimization and resource management.

What is CPU Scheduling?

CPU scheduling is the process of selecting which process should be executed by the CPU at any given time. When multiple processes are ready to execute, the operating system must decide the order and duration of execution. This decision-making process is handled by the CPU scheduler, which uses various algorithms to optimize system performance.

Key Scheduling Concepts

• Burst Time: The amount of time a process requires for CPU execution
• Arrival Time: The time when a process arrives in the ready queue
• Completion Time: The time when a process finishes execution
• Turnaround Time: Completion time minus arrival time
• Waiting Time: Time spent waiting in the ready queue
• Response Time: Time from arrival until first CPU allocation

First Come First Served (FCFS) Algorithm

FCFS is the simplest CPU scheduling algorithm where processes are executed in the order they arrive in the ready queue. It follows a non-preemptive approach, meaning once a process starts executing, it continues until completion or until it voluntarily releases the CPU.

FCFS Implementation Example

FCFS Advantages and Disadvantages

Advantages:

• Simple to understand and implement
• No starvation – every process gets executed eventually
• Fair scheduling based on arrival order
• Low overhead for context switching

Disadvantages:

• Convoy effect – short processes wait behind long processes
• High average waiting time
• Not suitable for interactive systems
• CPU utilization may be poor

Shortest Job First (SJF) Algorithm

SJF scheduling selects the process with the shortest burst time for execution next. This algorithm can be implemented in both preemptive and non-preemptive versions. The preemptive version is also known as Shortest Remaining Time First (SRTF).

Non-Preemptive SJF Example

Preemptive SJF (SRTF) vs Non-Preemptive SJF

SJF Advantages and Disadvantages

Advantages:

• Provides minimum average waiting time
• Optimal for batch processing systems
• Efficient CPU utilization
• Better throughput compared to FCFS

Disadvantages:

• Starvation problem for longer processes
• Difficult to predict burst times accurately
• Not suitable for interactive systems
• Requires knowledge of future burst times

Round Robin (RR) Algorithm

Round Robin is a preemptive scheduling algorithm designed specifically for time-sharing systems. Each process is assigned a fixed time slice called a time quantum or time slice. When a process’s time quantum expires, it’s moved to the back of the ready queue, and the next process gets the CPU.

Round Robin Implementation Example

Time Quantum Selection

The choice of time quantum is crucial for Round Robin performance:

• Too Small: High context switching overhead, reduced CPU efficiency
• Too Large: Approaches FCFS behavior, loses time-sharing benefits
• Optimal Range: Typically 10-100 milliseconds, should be larger than context switch time

Round Robin Advantages and Disadvantages

Advantages:

• Fair allocation of CPU time to all processes
• No starvation problem
• Excellent for interactive and time-sharing systems
• Good response time for short processes
• Preemptive nature prevents monopolization

Disadvantages:

• Higher average turnaround time than SJF
• Context switching overhead
• Performance depends heavily on time quantum size
• Not optimal for batch processing

Algorithm Comparison and Performance Analysis

When to Use Each Algorithm

Advanced Concepts and Variations

Priority Scheduling Integration

Real operating systems often combine these basic algorithms with priority-based scheduling:

• Priority + FCFS: Higher priority processes scheduled first, FCFS within same priority
• Priority + Round Robin: Different time quanta for different priority levels
• Multi-level Queue: Separate queues for different process types

Adaptive Algorithms

Modern systems use adaptive approaches:

• Exponential Averaging: Predict next CPU burst based on previous bursts
• Feedback Scheduling: Adjust priority based on past behavior
• Lottery Scheduling: Probabilistic fair scheduling

Implementation Considerations

Data Structures

• FCFS: Simple FIFO queue
• SJF: Priority queue or sorted list
• Round Robin: Circular queue with timer mechanism

Performance Metrics

Real-World Applications

Understanding where each algorithm is applied in practice:

• Linux CFS (Completely Fair Scheduler): Enhanced Round Robin with virtual runtime
• Windows Scheduler: Multi-level feedback queue with aging
• Real-time Systems: Rate Monotonic and Earliest Deadline First
• Cloud Computing: Fair queuing and weighted round robin

Conclusion

CPU scheduling algorithms form the foundation of operating system performance and user experience. FCFS provides simplicity but suffers from the convoy effect. SJF offers optimal average waiting time but faces practical challenges with burst time prediction and starvation issues. Round Robin excels in interactive environments by providing fair CPU sharing and good response times.

The choice of scheduling algorithm depends on system requirements, workload characteristics, and performance objectives. Modern operating systems typically employ hybrid approaches, combining multiple algorithms with dynamic adjustments to optimize performance across diverse scenarios. Understanding these fundamental algorithms provides the groundwork for comprehending more complex scheduling strategies used in contemporary computing environments.

As computing continues to evolve with multi-core processors, cloud computing, and real-time requirements, CPU scheduling algorithms continue to adapt and improve, but the core principles established by FCFS, SJF, and Round Robin remain essential knowledge for system designers and developers.