C Language

Round Robin Scheduling Algorithm with Example

The round robin scheduling algorithm stands as one of the most widely implemented CPU scheduling techniques in operating systems today, offering a fair and efficient approach to process management. This preemptive algorithm allocates each process a fixed time slice or quantum in a circular queue, ensuring equitable CPU distribution across all tasks. When implementing the round robin scheduling algorithm in multi-tasking environments, system designers must carefully balance quantum size to minimize both context switching overhead and process response times. Unlike priority-based alternatives, the round robin scheduling algorithm prevents indefinite waiting by guaranteeing that every process receives processing time, making it particularly valuable for time-sharing systems where user interaction and perceived performance are critical factors

What is Round Robin Scheduling?

The round robin algorithm takes its name from the principle where each person takes an equal share of something in turns, similar to knights gathered around a round table. In computing, it works by:

  • Assigning a fixed time slice (quantum) to each process
  • Executing processes in a circular queue
  • Preempting processes that exceed their time quantum
  • Moving preempted processes to the back of the queue

This approach prevents any single process from monopolizing CPU resources, making it ideal for time-sharing systems.

Advantages of Round Robin Scheduling

  • Fairness: Every process gets an equal opportunity to execute
  • Reduced starvation: No process waits indefinitely
  • Predictable response times: Suitable for interactive systems
  • Simple implementation: Easy to understand and code

Key Parameters in Round Robin

The most critical parameter in round robin scheduling is the time quantum. A smaller time quantum reduces response time but increases context switching overhead. Conversely, a larger time quantum improves throughput but may lead to poor response times for short processes.

Round Robin Scheduling Example

Let's walk through a simple example to understand how round robin works:

Assume we have four processes (P1, P2, P3, P4) with the following burst times:

  • P1: 10 ms
  • P2: 5 ms
  • P3: 8 ms
  • P4: 3 ms

With a time quantum of 4 ms, the execution sequence would be:

  1. P1 executes for 4 ms (6 ms remaining)
  2. P2 executes for 4 ms (1 ms remaining)
  3. P3 executes for 4 ms (4 ms remaining)
  4. P4 executes for 3 ms (completes)
  5. P1 executes for 4 ms (2 ms remaining)
  6. P2 executes for 1 ms (completes)
  7. P3 executes for 4 ms (completes)
  8. P1 executes for 2 ms (completes)

This results in completion times of:

  • P1: 26 ms
  • P2: 13 ms
  • P3: 23 ms
  • P4: 11 ms

Implementing Round Robin algorithm in C

Below is a sample implementation of the round robin scheduling program in C:

#include
#include

// Structure to represent a process
typedef struct {
    int id;             // Process ID
    int burst_time;     // Total CPU burst time required
    int remaining_time; // Remaining burst time
    int waiting_time;   // Time spent waiting
    int turnaround_time; // Total time from arrival to completion
} Process;

// Function to implement Round Robin scheduling
void roundRobinScheduling(Process processes[], int n, int time_quantum) {
    int complete = 0;  // Number of completed processes
    int current_time = 0;  // Current time
    int i;
    
    // Initialize remaining time for all processes
    for (i = 0; i < n; i++) {
        processes[i].remaining_time = processes[i].burst_time;
    }
    
    // Keep scheduling until all processes are complete
    while (complete < n) {
        int flag = 0;  // Flag to check if any process got CPU time in this iteration
        
        // Traverse all processes
        for (i = 0; i < n; i++) {
            // If process has remaining time
            if (processes[i].remaining_time > 0) {
                flag = 1;  // Set flag that a process got CPU
                
                // If remaining time is less than or equal to time quantum
                if (processes[i].remaining_time <= time_quantum) {
                    // Update current time
                    current_time += processes[i].remaining_time;
                    // Calculate turnaround time
                    processes[i].turnaround_time = current_time;
                    // Mark process as complete
                    processes[i].remaining_time = 0;
                    complete++;
                } 
                // If remaining time is more than time quantum
                else {
                    // Reduce remaining time
                    processes[i].remaining_time -= time_quantum;
                    // Update current time
                    current_time += time_quantum;
                }
            }
        }
        
        // If no process got CPU in this iteration, increment time
        if (flag == 0) {
            current_time++;
        }
    }
    
    // Calculate waiting time for all processes
    for (i = 0; i < n; i++) {
        processes[i].waiting_time = processes[i].turnaround_time - processes[i].burst_time;
    }
}

// Function to print process details
void printProcessDetails(Process processes[], int n) {
    printf("\nProcess\tBurst Time\tWaiting Time\tTurnaround Time\n");
    
    float avg_waiting_time = 0, avg_turnaround_time = 0;
    
    for (int i = 0; i < n; i++) {
        printf("%d\t%d\t\t%d\t\t%d\n", 
               processes[i].id, 
               processes[i].burst_time, 
               processes[i].waiting_time, 
               processes[i].turnaround_time);
        
        avg_waiting_time += processes[i].waiting_time;
        avg_turnaround_time += processes[i].turnaround_time;
    }
    
    avg_waiting_time /= n;
    avg_turnaround_time /= n;
    
    printf("\nAverage Waiting Time: %.2f", avg_waiting_time);
    printf("\nAverage Turnaround Time: %.2f\n", avg_turnaround_time);
}

int main() {
    int n, time_quantum;
    
    printf("Enter the number of processes: ");
    scanf("%d", &n);
    
    Process *processes = (Process*)malloc(n * sizeof(Process));
    
    printf("Enter burst time for each process:\n");
    for (int i = 0; i < n; i++) {
        processes[i].id = i + 1;
        printf("Process %d: ", i + 1);
        scanf("%d", &processes[i].burst_time);
    }
    
    printf("Enter the time quantum: ");
    scanf("%d", &time_quantum);
    
    roundRobinScheduling(processes, n, time_quantum);
    
    printf("\nRound Robin Scheduling Results (Quantum = %d):", time_quantum);
    printProcessDetails(processes, n);
    
    free(processes);
    return 0;
}

 

Optimizing Round Robin Performance

To get the most out of round robin scheduling, consider these optimization strategies:

  1. Optimal Time Quantum Selection: Too small increases overhead, too large defeats the purpose of round robin
  2. Multi-level Feedback Queues: Combine round robin with priority scheduling
  3. Adaptive Time Quantum: Adjust the time slice based on system load
  4. Process Classification: Group processes with similar characteristics

Applications of Round Robin

Round robin scheduling finds applications in various systems:

  • Operating Systems: Linux, Windows, and Unix-like systems use variants of round robin
  • Network Packet Scheduling: Load balancers distribute network traffic
  • Real-time Systems: When predictable response times are critical
  • Shared Web Hosting: Allocating server resources among multiple websites

 

 

Frequently Asked Questions: Round Robin Scheduling Algorithm

Round Robin Algorithm in OS

What is the round robin algorithm in operating systems?

Round robin is a CPU scheduling algorithm where each process is assigned a fixed time slot in a cyclic way. It is designed to distribute CPU time fairly among all ready processes, giving each an equal opportunity to execute without any process monopolizing CPU resources.

Why is round robin scheduling popular in operating systems?

Round robin scheduling is popular because it provides fair CPU allocation, prevents process starvation, offers good response times for interactive processes, and is relatively simple to implement. It's particularly effective in time-sharing systems where multiple users need responsive access.

What are the main characteristics of round robin scheduling?

The key characteristics include:

  • Preemptive scheduling
  • Time-slice based execution (using a time quantum)
  • FIFO queue for ready processes
  • Cyclic process execution
  • Equal priority for all processes (in basic implementation)

How does round robin differ from FCFS (First-Come-First-Served) scheduling?

While FCFS executes processes to completion in the order they arrive, round robin allocates each process a small time slice and then moves to the next process. This prevents long processes from blocking shorter ones, reducing average waiting time in mixed workloads.

What are the disadvantages of round robin scheduling?

The main disadvantages include:

  • Performance is highly dependent on time quantum selection
  • High context switching overhead if time quantum is too small
  • Can behave like FCFS if time quantum is too large
  • Not ideal for processes with widely varying CPU burst times

Round Robin Scheduling Algorithm in OS

How does the time quantum affect round robin performance?

The time quantum significantly impacts performance:

  • A small time quantum increases responsiveness but causes more context switches
  • A large time quantum reduces overhead but can lead to poor response times for short processes
  • The optimal time quantum balances these factors, typically ranging from 10-100 milliseconds in many systems

Which operating systems use round robin scheduling?

Variants of round robin are used in many operating systems including:

  • Linux (through the Completely Fair Scheduler)
  • Windows (as part of its multilevel feedback queue)
  • Unix-based systems (often modified with priority considerations)
  • Real-time operating systems (RTOS)

How does round robin handle process priorities?

The basic round robin algorithm doesn't consider process priorities, treating all processes equally. However, many operating systems implement variants like:

  • Priority-based round robin
  • Multi-level feedback queues (where processes can move between different priority queues)
  • Weighted round robin (where different processes get different quantum sizes)

Is round robin suitable for all types of systems?

Round robin works best for time-sharing and interactive systems where response time is important. It's less suitable for:

  • Batch processing systems (where throughput is more important than response time)
  • Systems with processes that have very different CPU requirements
  • Hard real-time systems with strict deadlines

How does round robin affect average waiting time and turnaround time?

Round robin generally provides better average waiting times compared to FCFS when process burst times vary significantly. However, the average turnaround time might be higher due to context switching overhead and the fact that most processes don't complete in a single time quantum.

Round Robin Algorithm in C

How do you implement a basic round robin scheduler in C?

A basic implementation involves:

  1. Creating a queue of processes
  2. Executing each process for the given time quantum
  3. Moving preempted processes to the back of the queue
  4. Repeating until all processes complete

What data structures are commonly used in C implementations of round robin?

Common data structures include:

  • Arrays or linked lists to store process information
  • Queue structures to maintain the ready queue
  • Structs to hold process details (ID, burst time, remaining time, etc.)
  • Timers or counters to track the time quantum

How do you calculate waiting time and turnaround time in a round robin C program?

  • Waiting time = Turnaround time - Burst time
  • Turnaround time = Completion time - Arrival time These calculations are typically implemented by tracking when each process completes and calculating backward based on known burst times.

What are common errors when implementing round robin in C?

Common implementation errors include:

  • Incorrect queue management (not properly handling the cycling of processes)
  • Improper time quantum enforcement
  • Failing to account for process completion within a time quantum
  • Incorrect calculation of performance metrics
  • Not handling the case when all processes have the same arrival time

How can I optimize my C implementation of round robin scheduling?

Optimization strategies include:

  • Using efficient data structures for the ready queue
  • Minimizing unnecessary context switches
  • Implementing arrival time handling correctly
  • Considering an adaptive time quantum based on process behavior
  • Using dynamic memory allocation for large numbers of processes

Round Robin Scheduling Example

Can you walk through a simple round robin scheduling example?

Let's consider 4 processes P1, P2, P3, and P4 with burst times 10, 5, 8, and 3 milliseconds respectively. With a time quantum of 4ms:

  1. P1 executes for 4ms (6ms remaining)
  2. P2 executes for 4ms (1ms remaining)
  3. P3 executes for 4ms (4ms remaining)
  4. P4 executes for 3ms (completes)
  5. P1 executes for 4ms (2ms remaining)
  6. P2 executes for 1ms (completes)
  7. P3 executes for 4ms (completes)
  8. P1 executes for 2ms (completes)

How do you calculate average waiting time in a round robin example?

For the example above:

  • P1 waiting time: 26 - 10 = 16ms
  • P2 waiting time: 13 - 5 = 8ms
  • P3 waiting time: 23 - 8 = 15ms
  • P4 waiting time: 11 - 3 = 8ms Average waiting time = (16 + 8 + 15 + 8) / 4 = 11.75ms

What happens if processes have different arrival times in round robin?

With different arrival times, the scheduler maintains a ready queue of arrived processes. As new processes arrive, they join the back of the queue. The scheduler continues rotating through the ready queue, adding new arrivals as they come in.

How does the Gantt chart help in understanding round robin scheduling?

A Gantt chart visually represents the execution sequence, showing:

  • Which process executes at what time
  • When context switches occur
  • How processes rotate through the CPU
  • Process completion times This visual representation makes it easier to track the algorithm's behavior and calculate performance metrics.

What's the impact of changing the time quantum in the round robin example?

Changing the time quantum significantly affects execution:

  • With a larger quantum (e.g., 6ms), P1 and P3 would need fewer turns, reducing context switches
  • With a smaller quantum (e.g., 2ms), processes would rotate more frequently, potentially improving response times but increasing overhead
  • If the quantum equals or exceeds the longest burst time (e.g., 10ms), the algorithm effectively becomes FCFS
  •  

Top 15+ C Projects for Beginners

c beginner programs