Arrange all tasks based on their arrival time in the ready queue. The ready queue operates on a First In, First Out (FIFO) structure to manage the execution sequence of all CPU processes.
Step 2: Next, we move the initial task from the ready queue to begin its execution for a predetermined duration, which is assigned by every process upon entering the queue.
If the task cannot finish within the specified time slot because it is preempted by another process moving from the ready queue to run its task upon reaching its arrival time, the CPU saves the current state of the process. This enables the system to continue the process from where it was paused. If there is still remaining burst time for the process, it is placed at the end of the ready queue.
Step 4: Likewise, the scheduler picks an additional process from the ready queue to perform its operations. Once a process completes its task within the designated time slots, it will not proceed with further execution as its burst time has elapsed.
Similarly, we iterate through each step in the process until the task is completed.
Characteristics of Round Robin
- It is a pre-emptive algorithm.
- It shares an equal time interval between all processes to complete their task.
- It is a starvation free CPU scheduling algorithm. Hence it is known as the fairest and simple algorithm.
- It does not face any starvation issues or convoy effect.
- Each process gets equal priority to the fair allocation of CPU.
- It is easy to implement the CPU Scheduling algorithm.
- Each new process is added to the end of the ready queue as the next process's arrival time is reached.
- Each process is executed in circular order that shares a fixed time slot or quantum.
- Every process gets an opportunity in the round-robin scheduling algorithm to reschedule after a given quantum period.
- If the time quantum is lower, it takes more time on context switching between the processes.
- It does not provide any special priority to execute the most important process.
- The waiting time of a large process is higher due to the short time slot.
- The performance of the algorithm depends on the time quantum.
- The response time of the process is higher due to large slices to time quantum.
- Getting a correct time slot or quantum is quite difficult for all processes in the round-robin algorithm.
Advantages
Disadvantage
Round Robin CPU Scheduling Example:
Let's explore the principles of Round Robin scheduling through an illustration. Consider a scenario with five processes named P1, P2, P3, P4, and P5. The table below presents the arrival and burst times for each process. The time slice, or time quantum, is set at three units.
| Process | Arrival Time (AT) | Burst Time (BT) |
|---|---|---|
P1 |
0 | 8 |
P2 |
5 | 2 |
P3 |
1 | 7 |
P4 |
6 | 3 |
P5 |
8 | 5 |
Now we have to create the ready queue and the Gantt chart for Round Robin CPU Scheduler.
Arrival queue: P1, P3, P1, P2, P4, P3, P5, P1, P3, P5
Here is the Gantt chart:
At time 0, process P1 joins the ready queue and commences its execution for the specified time slot of 3. Within the 3 units of the time slice, a new process, P3, enters the ready queue as its arrival time is 1 unit.
Step 2: Following that, the execution of process P3 commences with a time slot of 3 units, causing process P1 to remain in a waiting state. Once process P3 completes its execution, process P1 then recommences its execution for another 3 unit time slot.
During the execution of process P1, two additional processes, namely P2 and P4, join the ready queue to start their execution. P2, being the first to arrive, will be processed for a time quantum of 2 units before P4 begins its execution.
Step 4: In this scenario, P4 has run for a duration of 3 time units, and as its Burst Time (BT) is 2, the task is considered finished. Consequently, it will not be reentered into the ready queue.
Next, the system proceeds with executing P3 from the ready queue during time slot 3, followed by the arrival of process P5 for the same time slot.
Meanwhile, while process P5 is running, processes P1 and P3 are required to remain in the ready queue.
Step 7: Next, retrieve process P1 from the ready queue and initiate its execution for time slot 2, as it necessitates only 2 BT to complete its operations. Consequently, there is no need for it to return to the ready queue for additional execution.
Step 8: Next, the procedure P3 is carried out during time slot 1, since it demands only 1 block of time to finish its assignments.
Step 9: The ultimate procedure P5 is carried out during time slot 2 as it necessitates solely 2 BT for task fulfillment.
The following are the important terms to find the Completion time, Turn Around Time (TAT) , Response Time (RT) and Waiting Time (WT).
- Completion Time : It defines the time when processes complete their execution.
- Turn Around Time : It defines the time difference between the completion time (CT) and the arrival time (AT). Turn Around Time (TAT) = Completion Time (CT) - Arrival Time (AT)
- Waiting Time : It defines the total time between requesting action and acquiring the resource. Waiting Time (WT) = Turn Around Time (TAT) - Burst Time (BT)
- Response Time : It is the time that defines at which time the system response to a process.
| Process | Arrival Time | Burst Time | Completion Time | Turn Around Time | Waiting Time | Response Time |
|---|---|---|---|---|---|---|
P1 |
0 | 8 | 22 | 22 | 14 | 0 |
P2 |
5 | 2 | 11 | 6 | 4 | 4 |
P3 |
1 | 7 | 23 | 22 | 15 | 2 |
P4 |
6 | 3 | 14 | 8 | 5 | 5 |
P5 |
8 | 5 | 25 | 17 | 12 | 9 |
Completion time for process P1 = 22, P2 = 11, P3 = 23, P4 = 14 and P5 = 25.
The turnaround time for Process 1 is calculated as the Completion Time (CT) minus the Arrival Time (AT) which equals 22. For Process 2, it is 6, for Process 3, it is 22, for Process 4, it is 8, and for Process 5, it is 17.
The waiting time for process P1 is calculated as the Turn Around Time (TAT) minus the Burst Time (BT), resulting in 14. For P2, it is 4, for P3 it is 15, for P4 it is 5, and for P5 it is 12.
The average waiting period is calculated by adding up the individual waiting times (14, 4, 15, 5, 12) and then dividing by the total number of instances, which in this case is 5. This results in an average waiting time of 10.
The average Turn Around Time is calculated as the sum of individual times divided by the total number of times, which in this case is (22 + 6 + 22 + 8 + 17) / 5 = 75 / 5 = 15.
Round Robin CPU Scheduling example with sequential arrival time
Let's explore a different illustration of Round Robin with sequential arrival time. In this scenario, we are dealing with four processes named P1, P2, P3, and P4. Details regarding the arrival and execution time for each process can be found in the table provided below. The time quantum allocated for this example is set at 6 units.
| Process | Arrival Time | Burst Time |
|---|---|---|
P1 |
0 | 8 |
P2 |
1 | 5 |
P3 |
2 | 10 |
P4 |
3 | 11 |
Here is the Gantt chart:
At time 0, task P1 enters the ready queue and performs tasks for a time quantum of 6 units. Within this time frame, processes P2, P3, and P4 join the ready queue. Subsequently, P1 moves back to the end of the queue to await further execution.
Next in line, task P2 initiates its operation lasting for a duration of 5 time units due to a Burst Time (BT) of 5. Subsequently, it remains within its current state without transitioning to the ready queue for additional processing.
Following the completion of the previous step, P3 will initiate its operation with a Burst time of 10, under a time quantum of 6 units. Consequently, it will carry out its activities within a specified time frame before being appended to the tail of the ready queue.
Following that, the procedure P4 commences its operation in Step 4, with a burst time of 11, and a time quantum of 6 units. It carries out its functions for a duration of 6 seconds before joining the tail of the ready queue.
After the completion of P4's execution, P1 will resume for a duration of 2 units or seconds before terminating. Likewise, once P1 finishes its entire execution, P3 will continue with its remaining 4 units of Burst Time before concluding the process.
After the full completion of process P3, the subsequent step involves the execution of process P4 within the remaining time slice of 5 units, ultimately concluding the process.
| Process | Arrival Time | Burst Time | Completion Time | Turn Around Time | Waiting Time |
|---|---|---|---|---|---|
P1 |
0 | 8 | 25 | 25 | 17 |
P2 |
1 | 5 | 11 | 10 | 5 |
P3 |
2 | 10 | 29 | 27 | 17 |
P4 |
3 | 11 | 34 | 31 | 20 |
Now we find the completion, Turn around time, waiting time and the average TAT and waiting time.
The time taken to complete P1 is: 25 P2 takes 11 units to complete. P3 requires 29 units to finish. P4's completion time is 34 units.
The time taken to complete a process, known as Turn Around Time, is calculated by subtracting the Arrival Time from the Completion Time. For process P1, it is 25 (CT) - 0 (AT) = 25. For process P2, it is 11 (CT) - 1 (AT) = 10. For process P3, it is 29 (CT) - 2 (AT) = 27. For process P4, it is 34 (CT) - 3 (AT) = 31. The average Turn Around Time across all processes is calculated as (25 + 10 + 27 + 31) / 4 = 23.25.
Process Waiting Time:
P1 equals 25 minus 8, resulting in 17. P2 is calculated by subtracting 5 from 10, yielding 5. P3 is determined by subtracting 10 from 27, giving 17. Lastly, P4 is found by subtracting 11 from 31, resulting in 20. The average waiting time is calculated by adding the waiting times for P1, P2, P3, and P4, then dividing by 4, resulting in an average waiting time of 14.75.
Write a program of round robin CPU scheduling in C language.
#include<stdio.h>
#include<conio.h>
void main()
{
// initlialize the variable name
int i, NOP, sum=0,count=0, y, quant, wt=0, tat=0, at[10], bt[10], temp[10];
float avg_wt, avg_tat;
printf(" Total number of process in the system: ");
scanf("%d", &NOP);
y = NOP; // Assign the number of process to variable y
// Use for loop to enter the details of the process like Arrival time and the Burst Time
for(i=0; i<NOP; i++)
{
printf("\n Enter the Arrival and Burst time of the Process[%d]\n", i+1);
printf(" Arrival time is: \t"); // Accept arrival time
scanf("%d", &at[i]);
printf(" \nBurst time is: \t"); // Accept the Burst time
scanf("%d", &bt[i]);
temp[i] = bt[i]; // store the burst time in temp array
}
// Accept the Time qunat
printf("Enter the Time Quantum for the process: \t");
scanf("%d", &quant);
// Display the process No, burst time, Turn Around Time and the waiting time
printf("\n Process No \t\t Burst Time \t\t TAT \t\t Waiting Time ");
for(sum=0, i = 0; y!=0; )
{
if(temp[i] <= quant && temp[i] > 0) // define the conditions
{
sum = sum + temp[i];
temp[i] = 0;
count=1;
}
else if(temp[i] > 0)
{
temp[i] = temp[i] - quant;
sum = sum + quant;
}
if(temp[i]==0 && count==1)
{
y--; //decrement the process no.
printf("\nProcess No[%d] \t\t %d\t\t\t\t %d\t\t\t %d", i+1, bt[i], sum-at[i], sum-at[i]-bt[i]);
wt = wt+sum-at[i]-bt[i];
tat = tat+sum-at[i];
count =0;
}
if(i==NOP-1)
{
i=0;
}
else if(at[i+1]<=sum)
{
i++;
}
else
{
i=0;
}
}
// represents the average waiting time and Turn Around time
avg_wt = wt * 1.0/NOP;
avg_tat = tat * 1.0/NOP;
printf("\n Average Turn Around Time: \t%f", avg_wt);
printf("\n Average Waiting Time: \t%f", avg_tat);
getch();
}
Output: