Round Robin Program in C

Round Robin (RR) scheduling is one of the most widely used CPU scheduling algorithms developed to allocate CPU time to each process in a round-robin way. Round Robin scheduling is cyclic in nature and is also known as Time Slicing Scheduling. Each process is allotted a fixed time slice or quantum. If the process does not finish the execution of its work within the time assigned, it is placed at the end of the ready queue, and the CPU scheduler will pick up the next process. In this way, every process is treated more or less fairly; all processes will be given equal amounts of CPU time in a round-robin manner.

Characteristics of Round Robin Scheduling 

Here are the characteristics of round robin scheduling:

1. Time quantum (time slice)

• Each task is assigned a fixed time quantum to execute. The time quantum decides how long a process executes before being sent to the back of the queue.
• If the time quantum is small, it ensures better responsiveness but increases the overhead (cost, time, or resources) due to constant switching.
• If the time quantum is large, it might decrease responsiveness.

2. Fairness

• Each task gets the same time to execute before being moved to the back of the line.
• It ensures that no task dominates.

3. Preemptive Scheduling

• It interrupts a task after completion of its time quantum even if the task isn’t completed.
• This increases responsiveness, especially in a system with multiple interactive users.

4. Order of Execution

• Processes are managed in a cyclic queue.

5. Efficiency

• It is suitable for time-sharing systems where response time is crucial.

What is FCFS Scheduling Algorithm?

FCFS stands for the First Come First Serve method for CPU scheduling; it runs processes in the order in which they come to the queue. The process that arrives first gets executed first, and the process that arrives next will have to wait, and so on. One of the simplest CPU scheduling algorithms, FCFS scheduling generally consists of a FIFO (First In First Out) queue.

Characteristics of FCFS Scheduling

Here are the characteristics of FCFS scheduling:

• Non-Preemptive: Once its execution starts, a process cannot be preempted by another process. A process can finish only after it has run till completion.
• Arrival Time Based: PCs consider arrival time in the ready queue when selecting processes.
• FIFO Queue: Processes are executed in the order they arrive; the process that comes first will be allocated CPU first.
• Fairness: All processes get a fair chance for execution; however, longer processes may cause waiting time to short ones.
• High Wait Time: The CPU is busy executing longer jobs first; therefore, the shorter processes may have to wait quite a bit.
• Simple and Feasible: Simple work suits a batch processing system.
• Not Preemptive: This algorithm does not preempt a running process for another even if there is one waiting for execution, which makes it appropriate for such environments where no interruption occurs.

The C language is widely recognized as a versatile programming language, offering a host of advantages for various applications. One notable implementation is the Round Robin scheduling algorithm, which is used in operating systems to manage processes efficiently. Here are some key advantages of using Round Robin in C:

• Due to its low-level nature, C makes it possible to interact directly with the computer hardware and system resources. This control ensures better optimization of the scheduling algorithm.
• C is a compiled language, meaning it generates highly efficient machine code. This efficiency makes it easier to run tasks faster without utilizing many resources.
• Linux and Unix are written in C. Since the Round Robin program works closely with the OS, it is easier to implement it in real-world systems.
• Regular context switching happens in Round Robin Scheduling when tasks are not completed. They are sent to the back of the queue while the next task is executed. This is handled very well in C.
• C is one of the first languages students learn; executing the Round Robin program in C gives them a better understanding of how CPU works and how an algorithm is converted to code.
• Debugging becomes relatively easy when executed with C.

Round Robin CPU Scheduling algorithm allocates a fixed amount of processing time to a job before it is forced to wait its turn again. Each process gets a chance to execute for one time unit (as defined here), depending on the time section al-zampa, and upon the expiration of its time quantum, is sent back to the end of the queue. This is repeated until all processes finish executing.

Let’s assume:

• Processes: P1, P2, P3, P4
• CPU Burst Times:
  
  • P1 = 3 units
  • P2 = 5 units
  • P3 = 2 units
  • P4 = 4 units
• Time Quantum = 1 unit

Step 1: Understanding the Gantt Chart

In this step, the Gantt chart illustrates the order in which processes execute.

Step 2: Calculating Waiting Time

To obtain the waiting time for each process, we need to know when it finished firing and how long it waited while other job arrivals were being executed.  Thus waiting time can be calculated as:

Waiting time=Turnaround time−Burst time

Where Turnaround time is the total time spent from arrival to completion.

For each process, we find the waiting times as follows:

• P1: Waiting time = (4-1) + (8-5) = (3) + (3) = 6 units
• P2: Waiting time = (1-0) + (5-2) + (9-6) + (11-10) + (12-11) + (13-12) = 1 + 3 + 3 + 1 + 1 + 1 = 10 units
• P3: Waiting time = (2-0) + (6-3) = 2 + 3 = 5 units
• P4: Waiting time = (3-0) + (7-4) + (10-8) + (12-11) = 3 + 3 + 2 + 1 = 9 units

Step 3: Calculating Average Waiting Time

Average waiting time is the sum of waiting times divided by the number of processes:

Average waiting time=6+10+5+94=304=7.5 units

Considering the quantum time to be 2ms, each process is executed for a maximum of 2ms. If it is not completed, it is sent to the back of the queue for its next turn.

Initial State:

• At time 0, Process A arrives and starts execution.
• The Ready Queue is initially empty but will start filling as processes arrive.

Explanation

• Cycle 1: Process A executes first, followed by Process B, and then Process C.
• Cycle 2: Process A executes again, followed by Process B, which now finishes. Then Process C continues to run.
• Cycle 3: Process A finishes, and then Process C runs.
• Cycle 4: Process C finishes executing.

Algorithm of Round Robin Scheduling program in C

Let’s look at some terminology before entering the algorithm:

• Burst time: It refers to the time required for a task to complete its execution on the CPU without any interruption

It starts when the task gets CPU access till it finishes execution, ignoring any wait time.

• Arrival time: The specific time when a task enters the ready queue, becoming eligible for CPU scheduling.

• Process ID: A unique identifier assigned to each task for managing and tracking purposes.

• Waiting time: The total time a process spends in the ready queue, waiting for its next CPU time slot.

Step-by-Step Algorithm of Round Robin Scheduling

Step 1: Input processes: Gathering process details, including burst time, arrival time and process ID.

Step 2: Sort processes: Arranging processes based on their arrival time.

Step 3: Allocation of time quantum: Each task is assigned a fixed time quantum for execution.

Step 4: Execute processes: All tasks are executed for a time quantum or until the task is completed and either removed from the queue (if finished) or moved to the back of the queue till its next turn.

Step 5: Repeat steps: Continue the cycle till all tasks are executed.

Example Code with Sequential Arrival Time

In a sequential arrival time, each process comes to the CPU one after the other, increasing the process arrival time within a unit interval(i.e., 1 or any other constant). Hence, in this case, all processes were sequentially arriving at the CPU and are scheduled using the Round Robin algorithm.

Here is the example of sequential arrival time:

C Code

#include <stdio.h>

void main() {
    int i, processes, sum = 0, cnt = 0, y, q, wt = 0, tat = 0, at[10], bt[10], temp[10];
    float avg_waitt, avg_turnat;

    // Input the number of processes
    printf("Total number of processes in the system: ");
    scanf("%d", &processes);

    y = processes;  // Assign number of processes to y

    // Input arrival time and burst time for each process
    for(i = 0; i < processes; i++) {
        printf("\nEnter the Arrival and Burst time of Process[%d]\n", i + 1);
        printf("Arrival time: ");
        scanf("%d", &at[i]);
        printf("Burst time: ");
        scanf("%d", &bt[i]);
        temp[i] = bt[i];  // Initialize remaining burst time
    }

    // Input the time quantum
    printf("Enter the Time Quantum: ");
    scanf("%d", &q);

    // Display header for the process info
    printf("\nProcess No \tBurst Time \tTAT \t\tWaiting Time\n");

    // Scheduling loop
    for(sum = 0, i = 0; y != 0;) {
        if(temp[i] <= q && temp[i] > 0) {
            sum = sum + temp[i];
            temp[i] = 0;
            cnt = 1;
        } else if(temp[i] > 0) {
            temp[i] = temp[i] - q;
            sum = sum + q;
        }

        if(temp[i] == 0 && cnt == 1) {
            y--;  // Decrement remaining processes
            printf("\nProcess No[%d] \t%d \t\t%d \t\t%d", i + 1, bt[i], sum - at[i], sum - at[i] - bt[i]);
            wt = wt + sum - at[i] - bt[i];  // Calculate waiting time
            tat = tat + sum - at[i];  // Calculate turnaround time
            cnt = 0;
        }

        if(i == processes - 1) {
            i = 0;
        } else if(at[i + 1] <= sum) {
            i++;
        } else {
            i = 0;
        }
    }

    // Calculate average waiting time and turnaround time
    avg_waitt = wt * 1.0 / processes;
    avg_turnat = tat * 1.0 / processes;

    printf("\nAverage Turnaround Time: %f", avg_turnat);
    printf("\nAverage Waiting Time: %f", avg_waitt);
}

Explanation

This program implements the Round Robin scheduling algorithm. It receives the number of processes, their arrival and burst times as inputs. Then, once the waiting time, turnaround time, and averages for all processes are calculated, the CPU time is allocated to each process in the time slices of the fixed time quantum.

Output

//Input
Total number of processes in the system: 3

Enter the Arrival and Burst time of Process[1]
Arrival time: 0
Burst time: 5

Enter the Arrival and Burst time of Process[2]
Arrival time: 1
Burst time: 3

Enter the Arrival and Burst time of Process[3]
Arrival time: 2
Burst time: 4

Enter the Time Quantum: 3

//output

Process No    Burst Time    TAT         Waiting Time
Process No[1]    5        8           3
Process No[2]    3        6           3
Process No[3]    4        7           3

Average Turnaround Time: 7.000000
Average Waiting Time: 3.000000

• Time Complexity: O(n * m)‍
• Space Complexity: O(n)

CPU scheduling with zero arrival time is a situation in which all the processes arrive at 0. The scheduler does not discriminate between arrival times; all these processes are available to the CPU at the same point in time, thus making it focus only on the burst times (execution times) of the processes.

Algorithm

Step 1: Initialize the processes with the parameters timeQuantum, current_time, waiting_time, turnaround_time, completed_processes.

Step 2: While less than the total number of processes has been completed:

For any process:

If remaining burst > quantum:

    Subtract quantum increment, current_time.

          Else:

     Increment current_time back with remaining burst, update waiting time and turnaround time, completed.

Step 3: Average waiting time and turnaround time calculated and printed.

C Code

#include <stdio.h>

#define MAX 10  // Maximum number of processes

// Structure to hold process details
struct Process {
    int id;         // Process ID
    int burstTime;  // Burst Time
    int remainingTime; // Remaining Time
};

// Function to implement Round Robin scheduling
void roundRobin(struct Process processes[], int n, int timeQuantum) {
    int time = 0;  // Tracks current time
    int completed = 0;
    int waitingTime = 0, turnaroundTime = 0;

    // Array to track the remaining time of each process
    while (completed < n) {
        for (int i = 0; i < n; i++) {
            // If process still has remaining time
            if (processes[i].remainingTime > 0) {
                if (processes[i].remainingTime > timeQuantum) {
                    processes[i].remainingTime -= timeQuantum;
                    time += timeQuantum;
                } else {
                    time += processes[i].remainingTime;
                    waitingTime += time - processes[i].burstTime;
                    turnaroundTime += time;
                    processes[i].remainingTime = 0;
                    completed++;
                }
            }
        }
    }

    printf("\nAverage Waiting Time = %.2f\n", (float)waitingTime / n);
    printf("Average Turnaround Time = %.2f\n", (float)turnaroundTime / n);
}

// Main function
int main() {
    struct Process processes[MAX];
    int n, timeQuantum;

    printf("Enter the number of processes: ");
    scanf("%d", &n);

    // Input processes burst times
    for (int i = 0; i < n; i++) {
        processes[i].id = i + 1;
        printf("Enter burst time for process %d: ", i + 1);
        scanf("%d", &processes[i].burstTime);
        processes[i].remainingTime = processes[i].burstTime;  // Initialize remaining time
    }

    printf("Enter time quantum: ");
    scanf("%d", &timeQuantum);

    // Run Round Robin Scheduling
    roundRobin(processes, n, timeQuantum);
    
    return 0;
}

Explanation

This above code uses a simulation of Round Robin scheduling by assigning a fixed quantum time for every process. It proceeds in cycles along the processes, executing each in cycles, updating burst times, and then calculating waiting and turnaround times for all processes until completion.

Output

Enter the number of processes: 3
Enter burst time for process 1: 10
Enter burst time for process 2: 5
Enter burst time for process 3: 8
Enter time quantum: 4

Average Waiting Time = 6.33
Average Turnaround Time = 13.33

• Time Complexity: O(n * m)
• Space Complexity: O(n)

Key Differences from the Previous Code

1. Arrival Times:

• Previous Code: Considers specific arrival times. It needs to be checked whether a process has arrived or not before its execution
• Current Code: Assumes all processes arrive simultaneously (arrival time = 0), simplifying the logic.

2. Idle CPU Handling:

• Previous Code: Increments currentTime when no processes are ready to execute. As the CPU is idle.
• Current Code: No idle handling is needed since the CPU is always busy.

3. Turnaround Time Calculation:

• Previous Code: Turnaround time = Completion time - Arrival time.
• Current Code: Turnaround time = Completion time, as the arrival time for all processes is 0.

4. Code Complexity:

• Previous Code: More complex due to dynamic arrival times and idle handling.
• Current Code: Simpler due to the assumption of simultaneous arrival.

In Round Robin (RR) scheduling, each process is cyclically assigned a fixed time quantum (or time slice). When there are different arrival times for the processes, the scheduler must consider the arrival time of each process before scheduling it. Round Robin with different arrival times works as follows:

Algorithm

Step 1: Initialize processes with timeQuantum, current_time, waiting_time, turnaround_time, completed_processes.

Step 2: While not all processes are completed:

Step 3: For each process:

• If remaining_burst > quantum, subtract quantum and increment current_time.
• Else, increment current_time by remaining burst, update waiting_time and turnaround_time, mark as completed.

Step 4: Calculate and print average waiting_time and turnaround_time.

Code

#include <stdio.h>

#define MAX 10  // Maximum number of processes

// Structure to hold process details
struct Process {
    int id;             // Process ID
    int arrivalTime;    // Arrival Time
    int burstTime;      // Burst Time
    int remainingTime;  // Remaining Time
    int waitingTime;    // Waiting Time
    int turnaroundTime; // Turnaround Time
};

// Function to implement Round Robin scheduling
void roundRobin(struct Process processes[], int n, int timeQuantum) {
    int currentTime = 0;  // Tracks current time
    int completed = 0;
    float totalWaitingTime = 0, totalTurnaroundTime = 0;

    while (completed < n) {
        for (int i = 0; i < n; i++) {
            if (processes[i].arrivalTime <= currentTime && processes[i].remainingTime > 0) {
                if (processes[i].remainingTime > timeQuantum) {
                    processes[i].remainingTime -= timeQuantum;
                    currentTime += timeQuantum;
                } else {
                    currentTime += processes[i].remainingTime;
                    processes[i].waitingTime = currentTime - processes[i].arrivalTime - processes[i].burstTime;
                    processes[i].turnaroundTime = currentTime - processes[i].arrivalTime;
                    totalWaitingTime += processes[i].waitingTime;
                    totalTurnaroundTime += processes[i].turnaroundTime;
                    processes[i].remainingTime = 0;
                    completed++;
                }
            }
        }
    }

    // Display results
    printf("\nProcess ID | Arrival Time | Burst Time | Waiting Time | Turnaround Time\n");
    for (int i = 0; i < n; i++) {
        printf("%9d | %12d | %10d | %12d | %15d\n", processes[i].id, processes[i].arrivalTime,
               processes[i].burstTime, processes[i].waitingTime, processes[i].turnaroundTime);
    }

    // Calculate averages
    printf("\nAverage Waiting Time = %.2f\n", totalWaitingTime / n);
    printf("Average Turnaround Time = %.2f\n", totalTurnaroundTime / n);
}

// Main function
int main() {
    struct Process processes[MAX];
    int n, timeQuantum;

    // Input number of processes
    printf("Enter the number of processes: ");
    scanf("%d", &n);

    // Input processes' arrival times and burst times
    for (int i = 0; i < n; i++) {
        processes[i].id = i + 1;
        printf("Enter arrival time and burst time for process %d: ", i + 1);
        scanf("%d %d", &processes[i].arrivalTime, &processes[i].burstTime);
        processes[i].remainingTime = processes[i].burstTime;  // Initialize remaining time
    }

    // Input time quantum
    printf("Enter time quantum: ");
    scanf("%d", &timeQuantum);

    // Run Round Robin Scheduling
    roundRobin(processes, n, timeQuantum);

    return 0;
}

Explanation

In the above example, the round robin scheduling with varying arrival times allocates CPU time in fixed time slices that cycle through the set of processes. Processes can start as per their arrival time, and if they don't complete in the quantum time frame, then they are suspended or preempted and get placed back in the queue. The process of CPU execution continues until all processes are executed.

Output

//Input
Enter the number of processes: 3
Enter arrival time and burst time for process 1: 0 10
Enter arrival time and burst time for process 2: 1 5
Enter arrival time and burst time for process 3: 2 8
Enter time quantum: 4

//Output
Process ID | Arrival Time | Burst Time | Waiting Time | Turnaround Time
         1 |           0 |         10 |           6 |              16
         2 |           1 |          5 |           4 |              9
         3 |           2 |          8 |           4 |              12

Average Waiting Time = 4.67
Average Turnaround Time = 12.33

• Time Complexity: O(n * m)
• Space Complexity: O(n)

Key Features

1. Handles Different Arrival Times:

Dynamically checks which processes have arrived at each time step.

2. Idle CPU Handling:

Increments currentTime if no process is ready to simulate the CPU waiting for a new process.

3. Fair Scheduling:

Allocates CPU time evenly to all processes using the round-robin method.

4. Process Preemption:

Processes are preempted after their time quantum expires and placed at the end of the queue.

5. Cyclic Execution:

Processes are cycled through the queue, ensuring continuous execution until completion.

6. Starvation-Free:

Ensures all processes get CPU time, preventing starvation.

7. Efficiency Considerations:

Context switching overhead can increase with small time quanta, so a balance is needed.

1. Used in time-sharing systems, where multiple users have access

• Imagine an institute where numerous students are running programs on a single server. The round robin algorithm ensures that no single program takes up the CPU time entirely.

2. Handling multiple client requests on web servers

• Netflix handles searches and video plays from multiple clients, ensuring a smooth experience.

3. In network scheduling, managing data packets in routers

• In the wi-fi network at home, the round-robin program ensures no single device hogs the bandwidth.

4. In interactive systems, a responsive user interface is very ensured by round robin.

• In word processing applications, multiple processes like typing, spell-check, and auto-saving co-occur, preventing the application from freezing.

Here are the advantages and disadvantages of round robin scheduling in C:

Advantages

• Every process gets an equal share of CPU time, ensuring fairness.
• Enables time-sharing with constant time slices.
• Avoid starvation by permitting all processes to re-schedule after their quantum time.
• Allows no process to wait indefinitely through cyclic scheduling.

Disadvantages 

• Smaller time slices give rise to greater context switching overhead, making them less efficient.
• Longer processes make short ones wait longer.
• Frequent switching incurs overhead and increases even more with smaller time slices.
• It could delay processes which are priority.

Round-robin scheduling ensures fairness and simplicity. Its cyclic ensures that all programs get fair CPU time. It is ideal for time-sharing and real-time systems. It sheds light on process scheduling and the OS's efficiency in managing its resources.

1. What is Round Robin scheduling in operating systems?

Round Robin(RR) is a preemptive CPU scheduling algorithm that assigns a fixed time quantum to each process. After the quantum expires, the process is preempted and placed at the back of the queue, allowing other methods to work on a particular CPU cycle.

2. How does Round Robin scheduling work?

Round Robin scheduling works by maintaining a circular queue of processes. Each process is allocated a time quantum, and when its time quantum expires, the process is moved to the earliest not-yet-finished process in the same queue, ensuring fair CPU time distribution across all processes.

3. What are the advantages of Round Robin scheduling?

Round Robin is a scheduling algorithm emphasising fairness by making every process wait an equal time quantum. Starvation of processes is avoided, as the algorithm is also fair. Round Robin is also a widely accepted way of sharing time, in which all processes are treated equally.

4. What are the limitations of Round Robin scheduling?

The inefficiency of Round Robin scheduling occurs in those processes characterised by high-caliber limits. When a long-running process is transacted with other running processes, an inordinate number of context switches are made that incur overhead. With a small time quantum, there would be excessive switching, causing performance to plummet.

5. Is Round Robin scheduling suitable for real-time systems?

Round Robin cannot be given the right credit to offer a service to real-time systems, since it does not treat the procedures according to their deadline. Real-time systems use scheduling wherein RMS can be treated with great robustness, as this scheduling relates to timing constraints and urgency of the tasks.

6. What is the Round Robin process scheduling in C?

Round Robin process scheduling in C is the algorithm implementation required to manage the process in a queue and assign a fixed time slice to each. Once a process's time slice runs out, it is placed at the end of the queue.