Round Robin Scheduling


Round Robin is a preemptive CPU scheduling algorithm used in multitasking operating systems. It ensures that each process gets a fair share of the CPU time by allowing them to run in a cyclic queue for a fixed time slice called the time quantum. 
 
The Round Robin (RR) CPU scheduling algorithm is one of the most common algorithms used in operating systems to manage the execution of processes. It's designed to provide fair allocation of CPU time to all processes in the system. Here's how it works:

  1. Queue: The ready queue contains all the processes that are ready to execute. In Round Robin, this queue is typically implemented as a first-in-first-out (FIFO) queue.

  2. Time Quantum: A fixed time quantum (also known as a time slice or time interval) is defined. This time quantum represents the maximum amount of CPU time that a process can have before it's preempted.

  3. Execution: The CPU scheduler selects the process at the front of the ready queue for execution. The selected process is allowed to run for the duration of one time quantum or until it voluntarily relinquishes the CPU, whichever comes first.

  4. Preemption: At the end of the time quantum, if the process hasn't completed its execution, it's preempted and moved to the back of the ready queue. This allows other processes to get a chance to execute.

  5. Next Process Selection: The CPU scheduler then selects the next process from the ready queue for execution. This process can be the same process that just completed its time quantum (if it's still ready), or it can be the next process in the queue.

  6. Repeat: Steps 3-5 are repeated continuously, with processes being executed in a circular manner until they all complete their execution.

Round Robin scheduling ensures fairness by giving each process an equal share of the CPU time over a period. It's particularly useful in time-sharing systems where multiple users are interacting with the system simultaneously, as it prevents any single process from monopolizing the CPU for an extended period. However, the choice of time quantum is crucial, as a too-short quantum may lead to high overhead due to frequent context switches, while a too-long quantum may result in poor responsiveness.

 
Let’s dive into an example to understand how it works:

Consider the following three processes with their burst times:
Process P1: Burst time = 4
Process P2: Burst time = 3
Process P3: Burst time = 5

Assume a time quantum of 2 seconds.
Step 1: Execution begins with P1 (burst time 4). P2 and P3 are still in the waiting queue.
Step 2: At time = 2, P1 is added to the end of the queue, and P2 starts executing.
Step 3: At time = 4, P2 is preempted and added to the end of the queue. P3 starts executing.
Step 4: At time = 6, P3 is preempted and added to the end of the queue. P1 starts executing.
Step 5: At time = 8, P1 completes its burst time of 4. P2 starts execution.
Step 6: P2 has a burst time of 3. It has already executed for 2 seconds. At time = 9, P2 completes execution. Then, P3 starts execution until it completes.
 
 Average waiting time:
Waiting time for P1: 0 + 4 = 4
Waiting time for P2: 2 + 4 = 6
Waiting time for P3: 4 + 3 = 7
Average WT=5.666667 
Average Turn Around Time
Turn Around Time For P1=8
Turn Around Time For P2=9
Turn Around Time For P3=12
Average TAT=9.666667

In summary, Round Robin ensures fairness by allowing each process to run for a fixed time slice, preventing starvation and providing predictable response times. It’s widely used in traditional operating systems.

//**************************************************
// C Program Implementation Round Robin Scheduling
//**************************************************
#include <stdio.h>

// Structure to represent a process
struct Process {
    int id;
    int burst_time;
};

// Function to simulate Round Robin scheduling
void roundRobin(struct Process processes[], int n, int time_quantum) {
    int remaining_time[n];
    int wt[n],tat[n];
    for (int i = 0; i < n; ++i)
        remaining_time[i] = processes[i].burst_time;

    int current_time = 0;
    int completed = 0;

    while (completed < n) {
        int flag = 0;
        for (int i = 0; i < n; ++i) {
            if (remaining_time[i] > 0) {
                flag = 1;
                if (remaining_time[i] <= time_quantum) {
                    current_time += remaining_time[i];
                    remaining_time[i] = 0;
                    printf("Process P%d completed at time %d\n", processes[i].id, current_time);
                    tat[i]=current_time;
                    wt[i]=tat[i]-processes[i].burst_time;
                    printf("Process P%d WT=%d TAT=%d\n",processes[i].id,wt[i],tat[i]);
                    completed++;
                } else {
                    current_time += time_quantum;
                    remaining_time[i] -= time_quantum;
                }
            }
        }
        if (!flag)
            break;
    }

    float awt=0;
    float atat=0;
    for(int i=0;i<n;i++)
    {
        awt=awt+wt[i];
        atat=atat+tat[i];
    }
    printf("Average WT=%f Average TAT=%f",awt/n,atat/n);
    
}

int main() {
    int n = 3; // Number of processes
    struct Process processes[] = {{1, 4}, {2, 3}, {3, 5}};
    int time_quantum = 2;

    printf("Round Robin Scheduling:\n");
    roundRobin(processes, n, time_quantum);

    return 0;
}

Output:
Round Robin Scheduling:
Process P1 completed at time 8
Process P1 WT=4 TAT=8
Process P2 completed at time 9
Process P2 WT=6 TAT=9
Process P3 completed at time 12
Process P3 WT=7 TAT=12
Average WT=5.666667 Average TAT=9.666667
 

In the previous implementation we assumed that all process arrive at time 0.Lets consider a detailed implementation with linked list.Here the processes arrive in different time.

There are six processes named as P1, P2, P3, P4, P5 and P6. Their arrival time and burst time are given below in the table. The time quantum of the system is 4 units.
Process ID    Arrival Time        Burst Time
1                             0                         5
2                             1                         6
3                             2                         3
4                             3                         1
5                             4                         5
6                             6                         4

GANTT CHART
Note: In the following implementation we will assume that the processes are in the order of arrival time.The print queue function can be used to print the ready queue.

// C Program Implementation 
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>

// Structure to represent a process
typedef struct {
    int name;      // Process name (1,2,3 ...)
    int arrival;    // Arrival time
    int burst;      // Burst time
    int remaining;  // Remaining burst time
    int status;  // in queue or not
    int completion;//completion time
    int waiting; // waiting time
    int turnaround; // turn around time
} Process;

// Structure to represent a node in the waiting queue
typedef struct Node {
    Process process;
    struct Node* next;
} Node;
Node *front=NULL;
Node *rear=NULL;

// Function to enqueue a process into the waiting queue
void enqueue(Process process) {
    Node* newNode = (Node*)malloc(sizeof(Node));
 
    newNode->process = process;
    newNode->next = NULL;

    if (front == NULL) {
        front=rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
}

// Function to dequeue a process from the waiting queue
Process dequeue() {
   
    Node* temp = front;
    Process process = temp->process;
    front = front->next;
    free(temp);
    return process;
}
void printqueue()
{
    Node *temp=front;
    while(temp!=NULL)
    {
        printf("%d-->",temp->process.name);
        temp=temp->next;
        
    }
    printf("NULL\n");
}
int main() {
    // Define the processes
    Process processes[] = {
        {1, 0, 5, 5,0,-1,-1,-1},  
        {2, 1, 6, 6,0,-1,-1,-1},  
        {3, 2, 3, 3,0,-1,-1,-1},
        {4, 3, 1, 1,0,-1,-1,-1},  
        {5, 4, 5, 5,0,-1,-1,-1},  
        {6, 6, 4, 4,0,-1,-1,-1}
        
    };
    int n = sizeof(processes) / sizeof(Process); // Number of processes

    // Time quantum
    int quantum = 4;

    // Initialize variables
    int currenttime = 0;
    int completed = 0;
   
    printf("Time  |  Process\n");
    printf("------+-------------------\n");

    // Loop until all processes are completed
     enqueue(processes[0]);
     processes[0].status=1;
    while (completed < n ) {
        // Enqueue processes that arrive at the current time
        
       //  printqueue();
        // Execute processes in the waiting queue
        if (front != NULL) {
            Process currentProcess = dequeue();
            int execution_time = (currentProcess.remaining < quantum) ? currentProcess.remaining : quantum;
            currentProcess.remaining -= execution_time;
            currenttime += execution_time;
            for (int i = 0; i < n; i++) {
            if (processes[i].arrival <= currenttime && processes[i].status!=1) {
                enqueue(processes[i]);
                processes[i].status=1;
            }
        }
            printf("%-5d |  P%d\n", currenttime, currentProcess.name);
            if (currentProcess.remaining <= 0) {
                completed++;
                for(int i=0;i<n;i++) if (processes[i].name==currentProcess.name)
                           {processes[i].completion=currenttime;break;}
            } else {
                currentProcess.status=1;
                enqueue(currentProcess);
            }
        } else {
            currenttime++; // Move to the next time unit if no process is ready to execute
        }
    }

    float avwt=0.0;
    float avtat=0.0;
    printf("Process ArrivalTime BurstTime  CompletionTime  TurnAroundTime WaitingTime\n");
    for(int i=0;i<n;i++)
    {
    processes[i].turnaround=processes[i].completion-processes[i].arrival;
    processes[i].waiting=processes[i].turnaround-processes[i].burst;
    printf("P%d%10d%10d%20d%10d%20d\n",processes[i].name,processes[i].arrival,processes[i].burst,processes[i].completion,processes[i].turnaround,processes[i].waiting);
    avwt=avwt+processes[i].waiting;
    avtat=avtat+processes[i].turnaround;
    }
    printf("Average Waiting Time=%f\n",avwt/n);
    printf("Average Turn Around Time=%f\n",avtat/n);
      return 0;  
}
Output:
Time  |  Process
------+-------------------
4     |  P1
8     |  P2
11    |  P3
12    |  P4
16    |  P5
17    |  P1
21    |  P6
23    |  P2
24    |  P5
Process ArrivalTime BurstTime  CompletionTime  TurnAroundTime WaitingTime
P1                 0             5                      17                            17                  12
P2                 1             6                      23                            22                  16
P3                 2             3                      11                             9                   6
P4                 3             1                      12                             9                   8
P5                 4             5                      24                            20                  15
P6                 6             4                      21                            15                  11
Average Waiting Time=11.333333
Average Turn Around Time=15.333333

Comments

Post a Comment

Popular posts from this blog

CSL 204 OPERATING SYSTEM LAB KTU IV SEM CSE

About Me Syllabus Scheme Program List Linux Basics 1. Linux History and GNU 2. Linux Basic Features and Architecture 3. How to Install Linux 4. Install Linux Inside Windows using WSL 5. Free software 6. Linux Chronology 7 .Package Management 8 .Compile and install from source 9 .Important Directories 10. File Permissions 11. Special Permissions 12 .Shell 13. Bash shell in windows 10 14 .Basic Linux command for beginners 15. Input Output Redirection  16. Directory Commands 17. File Commands 18 .Communication Commands 19. Information Commands  20 .IO Commands   21 .Process Management Commands 22. Account Administration Commands 23. Pipes and Filters  24. Top 100 commands to learn.         Familiarization of Basic  Linux Commands- ls, mkdir, rmdir , rm, cat, cp, mv , chmod          User and Group management- useradd, userdel,groupadd,groupdel, passwd           Familiarization of basic  ...
Read more

FCFS and SJF

Image
CPU Scheduling in Operating Systems: In the context of operating systems, CPU scheduling involves determining which process (or task) should be executed next by the central processing unit (CPU). The goal is to maximize CPU utilization, minimize waiting time, and ensure fair allocation of resources. Various scheduling algorithms are used to achieve these objectives. First-Come-First-Serve (FCFS) Scheduling: Definition: FCFS is the simplest CPU scheduling algorithm. It is non-preemptive, meaning once a process starts executing, it cannot be interrupted until completion. Processes are placed in a queue based on their arrival time. The process that arrives first gets executed first. Execution Order : Processes are executed in the order they arrive. The process at the front of the queue is selected for execution. Advantages: Easy to implement. Minimal overhead. Disadvantages: Often results in long waiting times. Leads to the convoy effect (where a long process holds up other processes). Sh...
Read more

Banker's Algorithm- Deadlock Detection

The Banker's Algorithm is a deadlock avoidance algorithm used in operating systems to prevent deadlocks in a system with limited resources. It was developed by Edsger Dijkstra in 1965. The algorithm ensures that the system will allocate resources in such a way that it will avoid deadlock, even if resources are requested in an arbitrary order. Let's break down the Banker's Algorithm into steps: 1. System Initialization: At the beginning, the system must know the total number of resources of each type and the maximum demand of each process. It also needs to keep track of the currently available resources of each type. 2. Allocation: When a process requests resources, the system must check if granting those resources would put it in an unsafe state (i.e., could potentially lead to a deadlock). If the request can be granted without causing an unsafe state, the resources are allocated. Otherwise, the process must wait until the requested resources can be safely allocated. Safety...
Read more