CPU Scheduling Algorithms Explained: A Beginner's Guide to FCFS, SJF, and Round Robin

Understanding CPU Scheduling Fundamentals and Process States

Welcome to the engine room of the Operating System. As a Senior Architect, I cannot stress this enough: the CPU is the most expensive resource in your machine. If it sits idle, you are losing money. If it is inefficiently managed, your system grinds to a halt.

CPU scheduling is the art of deciding which process gets the CPU, when, and for how long. To master this, we must first understand the lifecycle of a process. A process is not a static block of code; it is a dynamic entity that changes state constantly.

The Anatomy of a Process: The PCB

How does the OS keep track of all these moving parts? It uses a data structure called the Process Control Block (PCB). Think of the PCB as the "ID card" and "medical record" of a process combined. Every time the CPU switches tasks (a context switch), it saves the current state into the PCB and loads the next one.

Here is how a PCB might look defined in C++. Notice the mix of data types required to manage a running program.

// Process Control Block Structure
struct PCB {
    int pid;                  // Process ID
    int state;                // 0: New, 1: Ready, 2: Running, 3: Waiting
    int priority;             // Scheduling priority
    void *program_counter;    // Pointer to next instruction
    void *cpu_registers;      // Saved register context
    long long cpu_time_used;  // Total CPU time consumed
    long long arrival_time;   // When process entered Ready queue
};
    

The Cost of Switching

Context switching is powerful, but it is not free. The CPU spends time saving the old state and loading the new one instead of executing user code. This is known as overhead.

If we denote $T_{exec}$ as the pure execution time and $T_{overhead}$ as the context switch time, the total time $T_{total}$ required to complete a task is:

Where $N$ is the number of context switches. This is why aggressive scheduling (switching too often) can actually degrade performance. For a deeper dive into specific strategies, check out our guide on Demystifying Round Robin Scheduling.

Key Takeaways

• Dynamic Nature: Processes are not static; they transition between states (Ready, Running, Waiting) based on events.
• The PCB: The Process Control Block is the critical data structure that allows the OS to pause and resume processes seamlessly.
• Overhead Matters: Every context switch incurs a cost. Efficient scheduling minimizes this overhead while maximizing CPU utilization.

First-Come-First-Served (FCFS) Scheduling: Mechanics and Limitations

Imagine a line at a coffee shop. The person who steps up to the counter first gets their latte first. No cutting in line, no prioritizing the person with the complicated order. This is the essence of First-Come-First-Served (FCFS) scheduling.

While it sounds rudimentary, FCFS is the foundational logic upon which more complex algorithms are built. However, in the world of Operating Systems, simplicity often comes at a steep performance cost.

The Mechanics: A FIFO Queue

FCFS is non-preemptive. Once a process enters the CPU, it holds it until it terminates or switches to a waiting state. The OS maintains a Ready Queue (typically implemented as a FIFO queue).

• 1. Arrival: A process enters the ready queue and is appended to the tail.
• 2. Selection: The scheduler picks the process at the head of the queue.
• 3. Execution: The process runs until completion.

The Convoy Effect: Why FCFS Fails Interactive Systems

The biggest flaw in FCFS is the Convoy Effect. Imagine a slow truck (a CPU-bound process) driving on a single-lane road. All the fast sports cars (I/O-bound processes) are stuck behind it, even though they could be zipping around if the road allowed it.

In an OS, if a large process grabs the CPU, smaller, interactive processes (like your mouse clicks or UI rendering) must wait. This leads to poor Response Time, which is critical for user experience. For a deeper dive into how we solve this, look into Round Robin Scheduling.

def calculate_fcfs(processes):
    """
    Calculates waiting time and turnaround time for FCFS.
    processes: List of dictionaries with 'id' and 'burst_time'.
    """
    n = len(processes)
    waiting_time = [0] * n
    turnaround_time = [0] * n

    # First process always has 0 waiting time
    waiting_time[0] = 0

    # Calculate waiting time for remaining processes
    for i in range(1, n):
        # Wait time = Previous process wait + Previous process burst
        waiting_time[i] = (waiting_time[i - 1] + 
                           processes[i - 1]['burst_time'])

    # Calculate Turnaround Time (Wait + Burst)
    for i in range(n):
        turnaround_time[i] = (waiting_time[i] + 
                              processes[i]['burst_time'])

    return waiting_time, turnaround_time

# Example Usage
procs = [
    {'id': 'P1', 'burst_time': 24},
    {'id': 'P2', 'burst_time': 3},
    {'id': 'P3', 'burst_time': 3}
]

w_times, t_times = calculate_fcfs(procs)
print(f"{'Process':<10} {'Wait':<10} {'Turnaround':<10}")
for i in range(len(procs)):
    print(f"{procs[i]['id']:<10} {w_times[i]:<10} {t_times[i]:<10}")
        

Pros and Cons Analysis

Shortest Job First (SJF) Scheduling: Optimizing Turnaround Time

Imagine you are at a coffee shop. The barista has three orders: a complex latte art (10 mins), a simple black coffee (2 mins), and a cold brew (5 mins). If they make the latte first, the other two customers wait 10 minutes. If they make the black coffee first, the average wait time drops dramatically.

This is the essence of Shortest Job First (SJF). It is a scheduling algorithm that selects the waiting process with the smallest execution time (burst time) to execute next. In the world of OS architecture, this is the "greedy" approach to minimizing average waiting time.

The Critical Distinction: Non-Preemptive vs. Preemptive

SJF comes in two flavors. Understanding the difference is vital for system design.

The Math Behind the Magic

Why do we care about SJF? Because it mathematically minimizes the average waiting time. The formula for Turnaround Time ($T_{turnaround}$) is:

And the Average Waiting Time ($W_{avg}$) is simply the sum of individual waiting times divided by the number of processes ($n$):

This optimization logic is similar to how database engines optimize queries. Just as an optimizer chooses the execution path with the lowest cost, SJF chooses the path with the lowest time cost. You can see similar optimization logic in SQL execution plans.

Python Simulation: Calculating Waiting Times

Let's implement a basic Non-Preemptive SJF scheduler in Python. This script sorts processes by burst time to calculate the optimal waiting time.

def calculate_sjf(processes):
    """
    Calculates waiting time and turnaround time for Non-Preemptive SJF.
    processes: List of tuples (Process_ID, Arrival_Time, Burst_Time)
    """
    n = len(processes)
    
    # Create a copy to sort without modifying original arrival order
    # We sort by Burst Time (index 2)
    sorted_processes = sorted(processes, key=lambda x: x[2])
    
    completion_time = 0
    total_waiting_time = 0
    total_turnaround_time = 0
    
    print(f"{'PID':<5} {'Arrival':<10} {'Burst':<10} {'Wait':<10} {'Turnaround':<12}")
    print("-" * 55)
    
    for p in sorted_processes:
        pid, arrival, burst = p
        
        # If the CPU is idle, it waits for the process to arrive
        if completion_time < arrival:
            completion_time = arrival
            
        # Waiting time = Start Time - Arrival Time
        # Start Time is effectively the current completion_time of previous tasks
        waiting_time = completion_time - arrival
        turnaround_time = waiting_time + burst
        
        # Update completion time
        completion_time += burst
        
        total_waiting_time += waiting_time
        total_turnaround_time += turnaround_time
        
        print(f"{pid:<5} {arrival:<10} {burst:<10} {waiting_time:<10} {turnaround_time:<12}")
        
    avg_wait = total_waiting_time / n
    avg_turn = total_turnaround_time / n
    
    print("-" * 55)
    print(f"Avg Waiting Time: {avg_wait:.2f}")
    print(f"Avg Turnaround Time: {avg_turn:.2f}")

# Example Usage
# P1 arrives at 0, takes 10ms. P2 arrives at 1, takes 1ms.
# SJF will run P2 first (even though P1 arrived first) because 1 < 10.
procs = [(1, 0, 10), (2, 1, 1), (3, 2, 2)]
calculate_sjf(procs)
    

Round Robin Scheduling: Balancing Fairness and Response Time

The Core Mechanism: The Time Quantum

Unlike First-Come-First-Served (FCFS), which can lead to the "Convoy Effect," Round Robin introduces a strict timer called the Time Quantum (or Time Slice), denoted as $q$.

The CPU allocates this fixed time unit to a process. If the process finishes within $q$, it exits. If not, it is preempted and moved to the back of the queue. This creates a circular flow.

The Art of Tuning: The Time Quantum ($q$)

The magic of RR lies entirely in the value of $q$. As a Senior Architect, you must understand the trade-off:

The Sweet Spot: Ideally, 80% of CPU bursts should be shorter than the time quantum. A common rule of thumb is $q \approx 10-100$ milliseconds.

Implementation Logic

In a real-world kernel, this is managed via a Circular Queue. Here is a simplified C implementation of the scheduling logic:

#include <stdio.h>
#include <stdlib.h>

// Process structure
struct Process {
    int pid;
    int burst_time;
    int remaining_time;
};

void roundRobin(struct Process p[], int n, int quantum) {
    int time = 0;
    int completed = 0;

    while (completed != n) {
        for (int i = 0; i < n; i++) {
            // If process has remaining time
            if (p[i].remaining_time > 0) {
                
                // Determine execution time
                if (p[i].remaining_time > quantum) {
                    time += quantum;
                    p[i].remaining_time -= quantum;
                } else {
                    // Process finishes
                    time += p[i].remaining_time;
                    p[i].remaining_time = 0;
                    completed++;
                    printf("Process %d finished at time %d\n", p[i].pid, time);
                }
            }
        }
    }
}

Mathematical Analysis

To evaluate the efficiency of RR, we calculate the Average Waiting Time.

Note that as the number of processes $n$ increases, the waiting time generally increases unless the quantum $q$ is adjusted dynamically.

The Great Scheduling Showdown: FCFS vs. SJF vs. Round Robin

Imagine a busy airport control tower. You have a runway (the CPU) and a line of planes (processes) waiting to land. If you let the biggest planes land first, the small ones wait forever. If you let the closest ones land first, you might miss a critical emergency landing. This is the eternal struggle of the Operating System Scheduler.

As a Senior Architect, you must understand that there is no "perfect" algorithm. There is only the right trade-off for your specific workload. Today, we dissect the three titans of CPU scheduling.

1. First-Come, First-Served (FCFS)

FCFS is the simplest algorithm. It operates exactly like a queue at a coffee shop: the first person in line gets served first. It is non-preemptive, meaning once a process grabs the CPU, it holds it until it finishes or blocks.

The "Convoy Effect": The fatal flaw of FCFS is the Convoy Effect. If a massive process (the "truck") arrives first, all the tiny, interactive processes (the "cars") are stuck behind it. This causes high average waiting time and poor system responsiveness.

2. Shortest Job First (SJF)

If you want to minimize average waiting time mathematically, SJF is the winner. It prioritizes the process with the smallest burst time. It is provably optimal for throughput.

The Risk: Starvation. If short jobs keep arriving, the long jobs may never get a chance to run. This is why modern systems often use Multi-level Feedback Queues to mitigate this.

3. Round Robin (RR)

Round Robin is the standard for time-sharing systems. It assigns a fixed time slice (quantum) to each process. If a process doesn't finish in that time, it is preempted and moved to the back of the queue.

For a deep dive into the mechanics of time slicing and context switching, you should review our guide on Demystifying Round Robin Scheduling.

4. The Metrics: A Mathematical Breakdown

How do we measure success? We look at Average Waiting Time. Let's assume three processes: P1 (24ms), P2 (3ms), P3 (3ms).

Notice the massive difference? SJF reduced the average wait time from 17ms to 3ms simply by reordering the queue.

5. Implementation Logic

Here is a simplified logic flow for a Round Robin scheduler in C-like pseudocode. Note the use of a circular queue structure.

// Simplified Round Robin Logic
void round_robin(Process processes[], int n, int quantum) {
    int remaining_time[n];
    int completed = 0;
    int current_time = 0;

    // Initialize remaining times
    for (int i = 0; i < n; i++) {
        remaining_time[i] = processes[i].burst_time;
    }

    while (completed != n) {
        for (int i = 0; i < n; i++) {
            // If process has work left
            if (remaining_time[i] > 0) {
                // Determine execution time
                int exec = (remaining_time[i] > quantum) ? quantum : remaining_time[i];
                
                // Execute
                current_time += exec;
                remaining_time[i] -= exec;

                // Check if finished
                if (remaining_time[i] == 0) {
                    completed++;
                    printf("Process %d finished at %d\n", i, current_time);
                }
            }
        }
    }
}
    

6. The Final Verdict

Choosing the right algorithm depends on your system's goal: Throughput (Batch) or Responsiveness (Interactive).

Multilevel Queue Scheduling: The Static Hierarchy

Imagine a hospital triage system. Critical patients go to the ER, routine checkups to the waiting room, and administrative tasks to the back office. They never mix. This is the essence of Multilevel Queue Scheduling.

The ready queue is partitioned into separate queues based on process properties (e.g., foreground vs. background). Each queue has its own scheduling algorithm.

Multilevel Feedback Queue: The Adaptive Architect

This is the gold standard for modern OSs like Windows and Linux. It solves the static problem by allowing processes to move between queues based on their behavior.

• Demotion (Punishment): If a process uses too much CPU (CPU-bound), it is moved to a lower-priority queue.
• Aging (Reward): If a process waits too long in a low-priority queue, it is promoted to a higher one to prevent starvation.

The Logic of Feedback

The scheduler acts like a smart filter. Interactive processes (short bursts of CPU) stay at the top. CPU-bound processes (long calculations) get pushed down. This creates a self-organizing system.

// Simplified Logic for Multilevel Feedback Queue
void schedule(Process *p) {
    if (p->time_slice_used == p->quantum_limit) {
        // PUNISH: Demote to lower priority queue
        move_to_queue(p, p->current_queue + 1);
        p->time_slice_used = 0;
    } 
    else if (p->wait_time > MAX_WAIT_THRESHOLD) {
        // REWARD: Promote to higher priority (Aging)
        move_to_queue(p, p->current_queue - 1);
    }
    else {
        // Process finished or yielded (I/O)
        if (p->state == BLOCKED) {
            // Keep in same queue for next run (Interactive behavior)
            move_to_queue(p, p->current_queue); 
        }
    }
}
        

Implementation Logic: Pseudocode and Complexity Analysis

As architects, we don't just memorize definitions; we understand the computational cost of our decisions. A scheduler isn't magic—it's a loop, a queue, and a sorting algorithm working in harmony. Let's dissect the logic behind the three giants: FCFS, SJF, and Round Robin.

1. First-Come, First-Served (FCFS)

FCFS is the "dumbest" but most robust algorithm. It requires no sorting, no prediction, and no complex data structures. It simply processes the arrival queue as it stands.

// FCFS Implementation
void scheduleFCFS(List<Process> queue) {
    // No sorting required!
    for (Process p : queue) {
        p.execute();
        // Update waiting time
        current_time += p.burst_time;
    }
}

2. Shortest Job First (SJF)

SJF is the "smartest" for minimizing average waiting time, but it pays a heavy price in overhead. To know which job is shortest, you must look at all available jobs and sort them.

// SJF Implementation
void scheduleSJF(List<Process> queue) {
    // CRITICAL: Sort by burst time
    // This is where the cost lies!
    Collections.sort(queue, (a, b) -> a.burst - b.burst);
    
    for (Process p : queue) {
        p.execute();
    }
}

3. Round Robin (RR)

RR is the "fair" algorithm. It uses a circular queue. The logic is slightly more complex than FCFS because we must handle the Time Quantum—interrupting a process and putting it back at the end of the line.

// RR Implementation
void scheduleRR(Queue<Process> queue, int quantum) {
    while (!queue.isEmpty()) {
        Process p = queue.poll();
        
        if (p.burst > quantum) {
            p.execute(quantum);
            p.burst -= quantum;
            queue.add(p); // Push back to end
        } else {
            p.execute(p.burst);
            p.burst = 0;
        }
    }
}

Algorithmic Decision Flow

Visualizing the control flow helps us see why SJF is computationally heavier than FCFS.