Find the Order of Execution of given N Processes in Round Robin Scheduling

In this article, you will learn how to find the order of execution for given N processes using the Round Robin Scheduling algorithm. Round Robin is a preemptive CPU scheduling algorithm that allocates CPU time fairly among processes using fixed time slices.

What is Round Robin Scheduling?

Round Robin Scheduling is a preemptive scheduling algorithm where each process receives a fixed time slice (quantum) to execute. The CPU scheduler allocates time to processes in a circular order. Once a process uses its time slice, it's preempted and moved to the end of the ready queue.

The time quantum is typically between 10-100 milliseconds. A small quantum ensures fair CPU distribution and efficient utilization through frequent process switching.

How Round Robin Works

Consider four processes with different CPU requirements and a time quantum of 3 units ?

• Process 1: Requires 6 units of CPU time

• Process 2: Requires 4 units of CPU time

• Process 3: Requires 2 units of CPU time

• Process 4: Requires 8 units of CPU time

The execution order follows this pattern ?

Time 0-3: Process 1 (3 units used, 3 remaining)
Time 3-6: Process 2 (3 units used, 1 remaining)  
Time 6-8: Process 3 (2 units used, completed)
Time 8-11: Process 1 (3 units used, completed)
Time 11-14: Process 4 (3 units used, 5 remaining)
Time 14-15: Process 2 (1 unit used, completed)
Time 15-18: Process 4 (3 units used, 2 remaining)
Time 18-20: Process 4 (2 units used, completed)

Implementation in Python

Here's a complete implementation that tracks the execution order ?

def round_robin(processes, quantum):
    n = len(processes)
    remaining_time = [processes[i][1] for i in range(n)]  # [arrival_time, burst_time]
    waiting_time = [0] * n
    turnaround_time = [0] * n
    current_time = 0
    order_of_execution = []
    ready_queue = []
    completed = 0
    
    # Add initial processes that arrive at time 0
    for i in range(n):
        if processes[i][0] <= current_time:
            ready_queue.append(i)
    
    while completed < n:
        if ready_queue:
            process_index = ready_queue.pop(0)
            order_of_execution.append(process_index)
            
            if remaining_time[process_index] > quantum:
                current_time += quantum
                remaining_time[process_index] -= quantum
                
                # Add newly arrived processes
                for i in range(n):
                    if (processes[i][0] <= current_time and 
                        remaining_time[i] > 0 and i not in ready_queue):
                        ready_queue.append(i)
                        
                ready_queue.append(process_index)  # Re-add current process
            else:
                current_time += remaining_time[process_index]
                waiting_time[process_index] = (current_time - processes[process_index][1] - 
                                             processes[process_index][0])
                turnaround_time[process_index] = current_time - processes[process_index][0]
                remaining_time[process_index] = 0
                completed += 1
                
                # Add newly arrived processes
                for i in range(n):
                    if (processes[i][0] <= current_time and 
                        remaining_time[i] > 0 and i not in ready_queue):
                        ready_queue.append(i)
        else:
            current_time += 1
            # Check for newly arrived processes
            for i in range(n):
                if processes[i][0] <= current_time and remaining_time[i] > 0:
                    ready_queue.append(i)
    
    avg_waiting_time = sum(waiting_time) / n
    avg_turnaround_time = sum(turnaround_time) / n
    
    return order_of_execution, avg_waiting_time, avg_turnaround_time

# Example usage
processes = [(0, 5), (1, 3), (2, 8), (3, 6)]  # (arrival_time, burst_time)
time_quantum = 2

order, avg_wait, avg_turn = round_robin(processes, time_quantum)
print("Order of execution:", order)
print(f"Average waiting time: {avg_wait:.2f}")
print(f"Average turnaround time: {avg_turn:.2f}")

Order of execution: [0, 0, 1, 2, 0, 3, 1, 2, 3, 2, 3, 2]
Average waiting time: 10.25
Average turnaround time: 14.25

Key Components

Advantages and Disadvantages

Advantages:

• Fair CPU allocation among all processes

• No process starvation occurs

• Good response time for interactive systems

Disadvantages:

• Context switching overhead

• Performance depends on quantum size

• May increase waiting time for some processes

Conclusion

Round Robin Scheduling provides fair CPU allocation using time quantum-based execution. The algorithm ensures no process starvation while maintaining good response times, making it ideal for interactive systems despite context switching overhead.