Round Robin CPU Scheduling: OS Algorithm Deep Dive

Introduction and Core Concepts

Round robin CPU scheduling is one of the most fundamental and widely deployed preemptive scheduling algorithms in modern operating systems. Designed primarily for time-sharing systems, it ensures fairness by allocating a fixed time slice, known as a time quantum, to each process in a circular order. Every process gets an equal opportunity to execute, preventing starvation and providing responsive interaction for all users. If you have ever wondered how your operating system keeps dozens of applications feeling simultaneously responsive, round robin cpu scheduling is a major part of the answer.

At its core, round robin is a preemptive variant of First-Come, First-Served (FCFS) scheduling. Unlike non-preemptive algorithms where a process runs to completion once dispatched, round robin forcibly preempts a running process when its quantum expires and moves it to the back of the ready queue. This simple mechanism gives the algorithm its defining characteristics: fairness, low response time, and predictable behavior. It is the textbook example of a fair-share scheduler and forms the basis for more complex schedulers used in Linux, Windows, and real-time systems.

Why does round robin cpu scheduling matter so much? In a multiprogramming environment, the CPU is the most valuable resource. Without an effective scheduling discipline, a single CPU-bound process could monopolize the processor, causing interactive processes to freeze and degrading overall system throughput. Round robin solves this by enforcing time multiplexing. Its importance extends far beyond academic operating system courses; the same principle powers load balancers distributing requests across web servers, routers fairly forwarding packets, and container orchestrators allocating CPU shares. Understanding its trade-offs is essential for any systems programmer, backend engineer, or DevOps professional.

Key Terminology

To understand round robin scheduling, you must be familiar with a few core concepts. The time quantum (or time slice) is the maximum uninterrupted time a process can use the CPU, typically ranging from 10 to 100 milliseconds. The ready queue is a FIFO queue holding all processes ready for execution. A context switch is the overhead of saving the state of the preempted process and loading the state of the next process. Finally, key performance metrics include turnaround time (total time from arrival to completion), waiting time (time spent in the ready queue), and response time (time from arrival until first CPU allocation).

The choice of time quantum is the single most critical tuning parameter. If the quantum is too large, round robin degenerates into FCFS and loses its responsiveness advantage. If it is too small, the system spends more time context switching than doing useful work, drastically reducing CPU utilization. An optimal quantum balances responsiveness with efficiency, typically keeping context switch overhead below 1-2% of the quantum.

How It Works

Round robin cpu scheduling operates on a simple circular queue principle. All runnable processes are kept in the ready queue in order of arrival. The CPU scheduler picks the process at the head of the queue, dispatches it, and sets a timer interrupt for the time quantum. Two scenarios can then occur. If the process has a CPU burst less than or equal to the quantum, it will execute to completion, voluntarily release the CPU, and terminate or block for I/O. The scheduler then immediately selects the next process.

If, however, the process still needs CPU time after the quantum expires, the timer interrupt fires. The operating system preempts the running process, saves its program counter and registers into its Process Control Block (PCB), and moves it to the tail of the ready queue. The scheduler then dispatches the new head of the queue. This cycle repeats indefinitely. Newly arriving processes are simply appended to the tail of the queue, ensuring they will get their turn in the next cycle. Because every process cycles through the queue, no process is ever starved indefinitely.

This mechanism relies heavily on hardware support for timer interrupts and the ability to perform fast context switches. The scheduler itself is invoked on every quantum expiration, process completion, and new process arrival. From a theoretical perspective, round robin can be modeled as a cyclic executive where each process receives 1/n of the CPU time over the long run, assuming n processes are always ready. This fairness guarantee makes it ideal for time-sharing but not necessarily optimal for minimizing average waiting time.

The Role of Arrival Times and Bursts

In a realistic system, processes do not all arrive at time zero. The scheduler must handle dynamic arrivals. When the ready queue is empty, the CPU remains idle until the next arrival. When a process arrives while another is running, it is enqueued but does not preempt the current process until the quantum expires — round robin is preemptive only at quantum boundaries, not on arrival. This distinguishes it from preemptive Shortest Job First (SRTF).

The algorithm also interacts with I/O. If a running process issues an I/O request before its quantum expires, it blocks and leaves the ready queue. Once its I/O completes, it re-enters the tail of the ready queue. This behavior naturally prioritizes I/O-bound processes, which tend to have short CPU bursts and thus often finish before their quantum expires, leading to excellent interactive performance.

Illustrative Gantt Chart Logic

Consider a ready queue with processes P1, P2, P3. The execution order with a quantum of 4 would look like: P1 (0-4), P2 (4-8), P3 (8-12), P1 (12-16), P2 (16-18) if P2 finishes early, P3 (18-22), and so on. The Gantt chart is the primary tool for visualizing this interleaved execution and for manually calculating waiting and turnaround times in academic examples.

Implementation

Implementing round robin cpu scheduling in software requires simulating the ready queue, tracking remaining burst times, and advancing a global clock. While an OS kernel implements this in C with hardware interrupts, we can model the core logic cleanly in Python for study and simulation. The key data structures are a queue (using collections.deque) and arrays for arrival times, burst times, and remaining times.

The following implementation provides a complete simulation that handles arbitrary arrival times and calculates completion, turnaround, and waiting times. It faithfully models the preemptive, cyclic nature of the algorithm.

from collections import deque

def round_robin_scheduling(processes, burst_times, arrival_times, quantum):
    """
    Simulate Round Robin CPU Scheduling.
    processes: list of process IDs e.g., ['P1', 'P2', 'P3']
    burst_times: list of CPU burst times
    arrival_times: list of arrival times
    quantum: time slice
    """
    n = len(processes)
    remaining = burst_times[:]  # Remaining burst time for each process
    completion = [0] * n
    waiting = [0] * n
    turnaround = [0] * n
    
    # Queue holds indices of processes in ready queue
    ready_queue = deque()
    time = 0
    completed = 0
    # Track which processes have arrived and been enqueued
    visited = [False] * n
    gantt = []  # For visualization: list of (process_id, start, end)

    # Sort by arrival time to handle out-of-order input
    idx_sorted = sorted(range(n), key=lambda i: arrival_times[i])
    
    # Initialize by adding first arriving process
    # Advance time to first arrival if CPU is idle
    time = arrival_times[idx_sorted[0]]
    for i in idx_sorted:
        if arrival_times[i] <= time and not visited[i]:
            ready_queue.append(i)
            visited[i] = True

    while completed < n:
        if not ready_queue:
            # CPU idle: jump to next arrival
            next_arrival = min(arrival_times[i] for i in range(n) if not visited[i])
            time = next_arrival
            for i in idx_sorted:
                if arrival_times[i] <= time and not visited[i]:
                    ready_queue.append(i)
                    visited[i] = True
            continue

        pid_idx = ready_queue.popleft()
        start_time = time
        
        # Execute for quantum or remaining time, whichever is smaller
        exec_time = min(quantum, remaining[pid_idx])
        time += exec_time
        remaining[pid_idx] -= exec_time
        gantt.append((processes[pid_idx], start_time, time))

        # Enqueue any new arrivals that came during this execution
        for i in idx_sorted:
            if not visited[i] and arrival_times[i] <= time:
                ready_queue.append(i)
                visited[i] = True

        if remaining[pid_idx] == 0:
            # Process completed
            completed += 1
            completion[pid_idx] = time
            turnaround[pid_idx] = completion[pid_idx] - arrival_times[pid_idx]
            waiting[pid_idx] = turnaround[pid_idx] - burst_times[pid_idx]
        else:
            # Not finished, re-queue at tail
            ready_queue.append(pid_idx)
            
    return gantt, completion, turnaround, waiting

This first example captures the essential loop: dequeue, execute for min(quantum, remaining), check for new arrivals, and either mark complete or re-enqueue. Note how we handle CPU idle time by jumping the clock forward — a common edge case beginners miss.

def calculate_metrics_example():
    """Example usage and metric calculation for Round Robin."""
    processes = ['P1', 'P2', 'P3', 'P4']
    burst_times = [8, 4, 9, 5]
    arrival_times = [0, 1, 2, 3]
    quantum = 3

    gantt, completion, turnaround, waiting = round_robin_scheduling(
        processes, burst_times, arrival_times, quantum
    )

    print("Gantt Chart (Process, Start, End):")
    for pid, s, e in gantt:
        print(f"{pid}: {s} -> {e}")

    print("\nPID | Burst | Arrival | Completion | Turnaround | Waiting")
    for i, pid in enumerate(processes):
        print(f"{pid:3} | {burst_times[i]:5} | {arrival_times[i]:7} | {completion[i]:10} | {turnaround[i]:10} | {waiting[i]:7}")

    avg_waiting = sum(waiting) / len(waiting)
    avg_turnaround = sum(turnaround) / len(turnaround)
    print(f"\nAverage Waiting Time: {avg_waiting:.2f}")
    print(f"Average Turnaround Time: {avg_turnaround:.2f}")

# Uncomment to run:
# calculate_metrics_example()

The second block demonstrates how to derive the classic scheduling metrics from the simulation. Average waiting time and average turnaround time are the standard ways to compare scheduling algorithms quantitatively. Notice that waiting time is derived as turnaround minus burst time, which isolates the time spent not executing.

def round_robin_with_io_simulation(processes, bursts, quantum):
    """
    Simplified RR where processes may block for I/O after partial execution.
    bursts: list of lists, e.g., [[4, 2], [3]] means P1 needs 4 CPU, then I/O, then 2 CPU
    This models I/O-bound vs CPU-bound behavior.
    """
    from collections import deque
    n = len(processes)
    # Flatten bursts into remaining CPU chunks
    remaining_chunks = [deque(b) for b in bursts]
    remaining_in_chunk = [chunks.popleft() if chunks else 0 for chunks in remaining_chunks]
    ready_queue = deque(range(n))
    time = 0
    io_queue = []  # (wake_time, pid_idx)

    while ready_queue or io_queue:
        # Wake up I/O completed processes
        io_queue.sort(key=lambda x: x[0])
        while io_queue and io_queue[0][0] <= time:
            _, pid = io_queue.pop(0)
            if remaining_in_chunk[pid] > 0 or remaining_chunks[pid]:
                ready_queue.append(pid)

        if not ready_queue:
            # Jump to next I/O completion
            if io_queue:
                time = io_queue[0][0]
            continue

        pid = ready_queue.popleft()
        exec_time = min(quantum, remaining_in_chunk[pid])
        time += exec_time
        remaining_in_chunk[pid] -= exec_time

        if remaining_in_chunk[pid] == 0:
            if remaining_chunks[pid]:
                # Needs I/O, block for 5 units (simulated)
                io_queue.append((time + 5, pid))
                remaining_in_chunk[pid] = remaining_chunks[pid].popleft()
            else:
                print(f"{processes[pid]} completed at time {time}")
        else:
            ready_queue.append(pid)
        
        if time > 50:  # Safety break for demo
            break

This third example extends the model to handle I/O blocking, which is crucial for understanding why round robin favors interactive processes. A process that blocks early yields the CPU and, upon waking, rejoins the tail of the queue, but its short CPU bursts mean it will cycle quickly.

def generate_gantt_text(gantt):
    """Generate a simple text-based Gantt chart for visualization."""
    # gantt is list of (pid, start, end)
    timeline = ""
    labels = ""
    for pid, start, end in gantt:
        duration = end - start
        # Scale: 1 time unit = 2 chars
        block = f"| {pid} "
        block = block.ljust(duration * 2 + 3, "-") 
        timeline += block
        labels += str(start).ljust(duration * 2 + 3)
    timeline += "|"
    labels += str(gantt[-1][2])
    print(timeline)
    print(labels)

# Example: gantt = [('P1', 0, 3), ('P2', 3, 6), ('P1', 6, 8)]
# generate_gantt_text(gantt)
# Output: | P1 ---| P2 ---| P1 -|
#          0      3      6     8

The final helper shows how to visualize the schedule. In interviews and OS courses, drawing the Gantt chart is often the first step to computing metrics manually. Automating it helps verify your understanding of the execution interleaving.

Step-by-Step Example

Let us walk through a concrete example to solidify the mechanics of round robin cpu scheduling. Consider four processes with the following arrival and burst times, and a time quantum of 3 milliseconds:

P1: Arrival 0, Burst 5; P2: Arrival 1, Burst 3; P3: Arrival 2, Burst 8; P4: Arrival 3, Burst 6. We will trace the ready queue, the running process, and the clock tick by tick.

At time 0, only P1 has arrived. Ready Queue: [P1]. P1 runs from 0 to 3. Its remaining burst becomes 2. During this interval, P2 (at 1), P3 (at 2), and P4 (at 3) all arrive. At time 3, P1 is preempted and moved to the tail. Before the next dispatch, we enqueue the new arrivals in order. Ready Queue becomes [P2, P3, P4, P1].

At time 3, P2 is dispatched. It needs 3 units, exactly one quantum, so it runs 3 to 6 and completes. No new arrivals. Ready Queue is now [P3, P4, P1]. At time 6, P3 runs 6 to 9. Its remaining goes from 8 to 5. It is re-queued. Ready Queue: [P4, P1, P3]. At time 9, P4 runs 9 to 12. Remaining 6 to 3. Re-queued. Ready Queue: [P1, P3, P4].

At time 12, P1 runs 12 to 14. It only needed 2, so it completes at 14. Ready Queue: [P3, P4]. At time 14, P3 runs 14 to 17. Remaining 5 to 2. Re-queued. Ready Queue: [P4, P3]. At time 17, P4 runs 17 to 20. Remaining 3 to 0, completes at 20. Ready Queue: [P3]. At time 20, P3 runs its final 2 units, 20 to 22, and completes.

Calculating Metrics

From this trace, completion times are: P1=14, P2=6, P3=22, P4=20. Turnaround Time = Completion - Arrival: P1=14-0=14, P2=6-1=5, P3=22-2=20, P4=20-3=17. Average Turnaround = (14+5+20+17)/4 = 14. Waiting Time = Turnaround - Burst: P1=14-5=9, P2=5-3=2, P3=20-8=12, P4=17-6=11. Average Waiting = (9+2+12+11)/4 = 8.5.

Notice how P2, with the shortest burst, still had to wait for P1's first quantum, but completed quickly once scheduled. P3, the longest job, was interleaved throughout and finished last, but the system remained responsive — no process waited more than a few quanta before getting CPU again. This is the fairness guarantee in action. If we had used FCFS, P3 would have blocked P4 for 8 full units, increasing average waiting time.

This manual walkthrough is exactly what you would do in a whiteboard interview. The key is to meticulously maintain the ready queue order and to remember that new arrivals are added to the tail before re-queueing the preempted process, or immediately after, depending on the precise definition used — both are acceptable if you state your assumption consistently.

Complexity Analysis

Analyzing round robin cpu scheduling requires distinguishing between the scheduling overhead per decision and the overall simulation complexity. For each scheduling decision — selecting the next process — the operation is O(1) if the ready queue is implemented as a circular queue or deque. Enqueue and dequeue are constant time. However, simulating the entire schedule for n processes with total burst time B and quantum q requires O(B/q + n) context switches and queue operations.

In the worst case, where burst times are large and quantum is small (e.g., quantum = 1), the number of slices is proportional to the total burst time. If we simulate tick-by-tick, complexity becomes O(B). A more efficient event-driven simulation, as shown in our code, jumps from one quantum expiration to the next, giving O(n + number_of_slices). The number_of_slices in the worst case is sum(burst_i / quantum), which can be large if quantum is 1 and bursts are large.

Space complexity is O(n) for storing process control blocks, remaining times, and the ready queue. The Gantt chart itself, if stored, can be O(number_of_slices) in size. For an OS kernel, the per-process overhead is minimal — just a few pointers and counters.

The most important takeaway from the table is that round robin's per-operation cost is excellent — constant time — but its total overhead scales inversely with quantum size. Halving the quantum doubles the number of context switches. Since each context switch has a non-trivial cost (flushing pipelines, TLB, cache pollution), the effective CPU utilization is: Utilization = quantum / (quantum + context_switch_time). With a 10ms quantum and 0.1ms switch time, utilization is ~99%; with a 1ms quantum, it drops to ~91%.

Response time analysis is also critical. In round robin, the worst-case response time for a newly arriving process is (n-1) * quantum, assuming all n-1 processes ahead of it use their full quantum. This predictable bound is why round robin is favored for interactive systems, whereas FCFS can have unbounded response time if a long job is ahead.

Variations and Optimizations

Classic round robin is simple but not always optimal. Several variations have been developed to improve its average waiting time, handle priorities, and adapt to workload characteristics. Understanding these is key to appreciating how modern schedulers are built.

Weighted Round Robin (WRR) assigns a weight to each process or flow, allowing processes with higher weight to receive more quanta per cycle or a larger quantum. This is widely used in network packet scheduling and load balancing where not all clients should be treated equally. For example, a high-priority process might get two consecutive quanta per round while others get one.

Deficit Round Robin (DRR), popularized by Cisco for packet scheduling, addresses variable-sized jobs. Each queue is assigned a quantum and a deficit counter. If a packet (or job) is too large to be sent in one quantum, the deficit is carried over, allowing the queue to send it in the next round. This ensures long-term fairness even with variable burst sizes without needing to know job sizes in advance.

Adaptive / Dynamic Quantum Round Robin adjusts the time slice based on system load or process behavior. Under light load, the quantum can be large to reduce switches; under heavy load, it shrinks to keep response time low. Some systems use a dynamic quantum that is a function of the shortest remaining burst time, blending round robin with Shortest Remaining Time First to reduce average waiting time while preserving fairness. Another common heuristic is to give I/O-bound processes a higher priority or smaller quantum, since they will block quickly anyway.

Multilevel Feedback Queue (MLFQ)

The most important optimization in practice is the Multilevel Feedback Queue, which uses multiple round robin queues with different quanta and priorities. New processes start in the highest-priority queue with a small quantum (e.g., 8ms). If they use their full quantum, they are demoted to the next lower queue with a larger quantum (e.g., 16ms). Processes that block for I/O before exhausting their quantum remain in the same queue or are promoted. This elegantly approximates Shortest Job First without requiring prior knowledge of burst times: short, interactive jobs stay in high-priority queues, while long CPU-bound jobs sink to lower queues and run with larger quanta, reducing context switch overhead.

Linux's Completely Fair Scheduler (CFS) and Windows' scheduler both incorporate MLFQ-like ideas. CFS is not strictly round robin but achieves similar fairness by tracking virtual runtime and always picking the process with the smallest virtual runtime, which results in round-robin-like fairness with variable quanta based on nice values (weights).

Real-World Applications

While round robin cpu scheduling was conceived for operating system process scheduling, its principle of fair cyclic sharing is ubiquitous across computing.

In Operating Systems, round robin is the default time-sharing discipline in many educational and embedded OS kernels. Even when not used alone, it forms the lowest level of MLFQ systems. Real-Time Operating Systems (RTOS) often use round robin among tasks of equal priority to ensure deterministic sharing.

In Web Servers and Load Balancers, round robin is the simplest and most common load distribution algorithm. NGINX, HAProxy, and cloud load balancers (AWS ELB, GCP) offer round robin to distribute incoming HTTP requests across a pool of backend servers in circular order. This ensures no single server is overwhelmed while others sit idle, assuming requests are roughly homogeneous.

In Networking, routers and switches use round robin and its variants (WRR, DRR) to schedule packets from different input queues onto an output link. This prevents a single heavy flow from starving others and provides fairness among users. The same logic is used in wireless base stations to allocate time slots to mobile devices.

In Databases and Microservices, connection pools and request handlers often service client queries in round robin fashion to ensure fair latency. Container orchestrators like Kubernetes use round robin within services (kube-proxy) to distribute traffic among pods.

The table highlights how the abstract concept of a time quantum maps to different granularities — from milliseconds for CPU scheduling to whole requests for load balancing. The unifying theme is cyclic fairness without needing to know job sizes in advance, which is precisely when round robin shines.

Comparison with Alternatives

No scheduling algorithm is universally best. The choice depends on workload characteristics and optimization goals: minimizing average waiting time, maximizing throughput, meeting deadlines, or ensuring fairness. Round robin excels at fairness and response time but often pays a price in average waiting time and throughput compared to algorithms that favor short jobs.

First-Come, First-Served (FCFS) is the simplest non-preemptive algorithm. It has minimal overhead but suffers from the convoy effect, where a long job blocks all short jobs behind it, leading to high average waiting time and poor response time. Shortest Job First (SJF) is optimal for minimizing average waiting time but requires knowing burst times in advance and can starve long jobs. Priority Scheduling generalizes SJF but risks starvation for low-priority processes unless aging is used.

Round robin strikes a middle ground: it does not need burst time knowledge, it is starvation-free, and it provides bounded response time, but its average waiting time is often higher than SJF, and its throughput is lower due to frequent context switches.

As the comparison shows, round robin is rarely used in isolation in modern general-purpose operating systems. Instead, it is a building block. MLFQ, for instance, combines the fairness of round robin with the efficiency of SJF by using multiple round robin queues and feedback. If your goal is pure throughput for a batch workload where all jobs are known upfront, SJF will beat round robin. If your goal is to keep a UI responsive while background compilation runs, round robin or MLFQ is the clear winner.

Common Mistakes and Best Practices

Implementing and tuning round robin cpu scheduling is deceptively simple; subtle mistakes can severely degrade performance or produce incorrect metrics.

Mistake 1: Choosing an inappropriate quantum. A classic error is setting the quantum too small (e.g., 1ms on a system with 0.5ms context switch time) leading to thrashing where more time is spent switching than executing. Conversely, a quantum larger than the longest burst turns the system into FCFS. Best practice: benchmark. A rule of thumb is that the quantum should be large enough that context switch overhead is < 5% of the quantum, but small enough that response time meets your SLA. For interactive systems, 20–50ms is a common sweet spot. Always measure CPU utilization and response time under realistic load.

Mistake 2: Ignoring arrival times and idle CPU. Many textbook implementations assume all processes arrive at time zero. In real simulations and kernels, you must handle the case where the ready queue is empty and the CPU should idle until the next arrival. Forgetting to advance the clock to the next arrival time leads to infinite loops or incorrect waiting time calculations. Always sort by arrival time and implement the idle-jump logic shown in the code above.

Mistake 3: Incorrect waiting time calculation. Beginners often compute waiting time as simply time spent in queue without accounting for the initial arrival offset. The correct formula is Waiting = Turnaround - Burst, where Turnaround = Completion - Arrival. Another pitfall is double-counting the time a process spends running. Ensure you only accumulate waiting while the process is in the ready queue, not while it is executing or blocked for I/O.

Mistake 4: Not handling re-queue order correctly. When a quantum expires and new processes arrive at the same instant, the order in which you enqueue new arrivals versus the preempted process affects fairness and metrics. Most definitions enqueue new arrivals first, then the preempted process at the tail. Whichever you choose, document it and be consistent, especially for interview problems where the expected Gantt chart depends on this tie-breaking rule.

Best Practices: Use a deque or circular linked list for O(1) queue operations. Keep PCB updates atomic. In production kernels, combine round robin with priorities and aging to avoid penalizing I/O-bound jobs. Log context switch rate and average queue length as key health metrics. For load balancers, consider weighted round robin if backend servers have heterogeneous capacity, and use health checks to skip failed nodes rather than blindly cycling.

Interview Questions

Round robin cpu scheduling is a staple of operating system interviews. Expect both conceptual and hands-on simulation questions. Here are common questions with concise, interview-ready answers.

Q1: What is round robin scheduling and why is it considered starvation-free?

Round robin is a preemptive scheduling algorithm where each process is assigned a fixed time quantum and executed in circular order from a FIFO ready queue. If a process does not complete within its quantum, it is preempted and moved to the tail of the queue. It is starvation-free because every process in the ready queue is guaranteed to get CPU time within (n-1) * quantum time units, where n is the number of processes. No process can be indefinitely postponed by others, unlike SJF or priority scheduling without aging.

Q2: How does the choice of time quantum affect performance? What happens if it is too large or too small?

The quantum controls the trade-off between responsiveness and efficiency. If the quantum is too large (greater than most burst times), round robin behaves like FCFS: response time suffers and the convoy effect returns. If it is too small, context switch overhead dominates, CPU utilization drops, and throughput falls, even though response time is excellent. An optimal quantum keeps context switch overhead low (e.g., < 1% of quantum) while keeping response time within acceptable bounds for interactive users, typically 10–100ms.

Q3: Walk through round robin for P1(5), P2(3), P3(8) with quantum 2, all arriving at 0. What is the average waiting time?

Gantt: P1 0-2, P2 2-4, P3 4-6, P1 6-8, P2 8-9 (finishes, needs only 1), P3 9-11, P1 11-12 (finishes), P3 12-16 (finishes). Completion: P1=12, P2=9, P3=16. Turnaround: P1=12, P2=9, P3=16. Waiting = Turnaround - Burst: P1=7, P2=6, P3=8. Average Waiting = (7+6+8)/3 = 7. This demonstrates the interleaving and shows that even though P2 is shortest, it still waits due to cyclic order.

Q4: How does round robin differ from FCFS and SJF in terms of average waiting time and response time?

FCFS has low overhead but high average waiting time due to convoy effect and poor response time. SJF minimizes average waiting time but has poor response time for long jobs and can starve them, and it requires burst time knowledge. Round robin provides the best response time (bounded) and fairness without needing burst estimates, but its average waiting time is typically worse than SJF and it incurs higher context switch overhead. In practice, MLFQ is used to get SJF-like waiting time with round robin-like response time.

Q5: How would you implement round robin to handle processes with different priorities?

Use Weighted Round Robin or Multilevel Feedback Queue. In WRR, assign each process a weight and give it proportional quanta per cycle (e.g., weight 2 gets two slices per round). In MLFQ, maintain multiple queues with different priorities and quanta; high-priority queues get smaller quanta and are served first. A process that uses its full quantum is demoted; one that blocks early stays high. Add aging to promote long-waiting low-priority processes to prevent starvation. This combines priority handling with round robin fairness.

Mastering these questions — and being able to quickly draw a Gantt chart and compute metrics — will demonstrate both theoretical understanding and practical ability to reason about scheduling trade-offs, which is exactly what interviewers look for when evaluating systems knowledge.