Implementation of ROUNd Robin SchedULing.
Round-robin is a CPU scheduling algorithm that shares equal portions of resources in circular orders to each process and handles all processes without prioritization. In the round-robin, each process gets a fixed time interval of the slice to utilize the resources or execute its task called time quantum or time slice. Some of the round-robin processes are preempted if it is executed in a given time slot, while the rest of the processes go back to the ready queue and wait to run in a circular order with the scheduled time slot until they complete their task. It removes the starvation for each process to achieve CPU scheduling by proper partitioning of the CPU.
Round Robin CPU Scheduling Algorithm
Step 1: Organize all processes according to their arrival time in the ready queue. The queue structure of the ready queue is based on the FIFO structure to execute all CPU processes.
Step 2: Now, we push the first process from the ready queue to execute its task for a fixed time, allocated by each process that arrives in the queue.
Step 3: If the process cannot complete their task within a defined time interval or slots because it is stopped by another process that pushes from the ready queue to execute their task due to arrival time of the next process is reached. Therefore, the CPU saved the previous state of the process, which helps to resume from the point where it is interrupted. (If the burst time of the process is left, push the process end of the ready queue).
Step 4: Similarly, the scheduler selects another process from the ready queue to execute its tasks. When a process finishes its task within time slots, the process will not go for further execution because the process’s burst time is finished.
Step 5: Similarly, we repeat all the steps to execute the process until the work has finished.
|Process||Arrival Time (AT)||Burst Time (BT)|
Now we have to create the ready queue and the Gantt chart for Round Robin CPU Scheduler.
Ready queue: P1, P3, P1, P2, P4, P3, P5, P1, P3, P5
Here is the Gantt chart:-
Step 1: At time 0, process P1 enters the ready queue and starts its execution for the defined time slot 3. During 3 units of the time slice, another process, P3, arrives in the ready queue because its arrival time is 1.
Step 2: Now, process P3 starts its execution with a time slot of 3 units while process P1 has to wait. After execution of process P3, process P1 again resumes its execution for time slot 3.
Step 3: During the execution of process P1, two more processes P2 and P4, arrive in the ready queue to begin their execution. Since process P2 has come first, it will be executed for time quantum 2 units after that P4 is executed.
Step 4: Here, P4 has executed for time slot 3 units, and its task is completed because BT (Burst Time) is 2. Hence it will not go to the ready queue.
Step 5: After that, process P3 is executed from the ready queue for time slot 3, and then process P5 arrives for time slot 3.
Step 6: Meanwhile, process P5 is executed, process P1 and P3 have to wait in the ready queue.
Step 7: Now process P1 is fetched from the ready queue and starts their execution for time slot 2 as it requires only 2 BT to finish its tasks. Hence it will not go to the ready queue for further execution.
Step 8: Now, the process P3 is executed for time slot 1 as it requires only 1 BT to complete its tasks.
Step 9: The final process P5 is executed for time slot 2 because it requires only 2 BT to complete its tasks.
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 execu.
- 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 resou 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|
Completion time for process P1 = 22, P2 = 11, P3 = 23, P4 = 14 and P5 = 25.
Turn Around Time for P1 = Completion Time (CT) – Arrival Time (AT) 22 – 0 = 22
Turn Around Time for P2 = 11 – 5 = 6
Turn Around Time for P3 = 23 – 1 = 22
Turn Around Time for P4 = 14 – 6 = 8
Turn Around Time for P5 = 25 – 8 = 17
Waiting Time for P1 = Turn Around Time (TAT) – Burst Time (BT) 22 – 8 = 14
Waiting Time for P2 = 6 – 2 = 4
Waiting Time for P3 = 22 – 7 = 15
Waiting Time for P4 = 8 – 3 = 5
Waiting Time for P5 = 17 – 5 = 12
Average Waiting Time = (14 + 4 + 15 + 5 + 12)/5 = 50/5 = 10 Average Turn Around Time = (22+6+22+8+17)/5= 75/5 = 15
Round Robin CPU Scheduling example with sequential arrival time
Let’s understand another example of Round Robin with sequential arrival time. Here we have four processes P1, P2, P3, and P4. The arrival and burst times of each process are mentioned in the following table, as shown below. The time quantum is 6 units.
|Process||Arrival Time||Burst Time|
Here is the Gantt chart:-
Step 1: At time 0, process P1 arrives in the ready queue and executes its tasks for time quantum 6 units. During 6 units of the time slice, another process P2, P3 and P4 arrive in the ready queue. After that, process P1 will return to the end of the ready queue and await their execution.
Step 2: Now, process P2 starts their execution for time slot 5 units because the Burst Time (BT) is 5, and it does not go to the ready queue for further execution.
Step 3: After that process, P3 will start its execution, which has 10 Burst times, but the time quantum is 6 units. Therefore, it executes its tasks for a defined time limit and is added to the ready queue’s end.
Step 4: After that, the process P4 starts its execution, which has burst time 11, but the time quantum is 6 units. It executes its tasks for only 6 seconds and then adds to the end of the ready queue.
Step 5: After the execution of P4, now P1 will start its execution again for 2 units or a second, and the process P1 terminates or end. Similarly, the complete execution of process P1, then P3, starts its remaining execution for Burst Time 4, and the process is completed.
Step 6: After the complete execution of process P3, now process P4 executes for the remaining time slot, which is 5, and the process is finished.
|Process||Arrival Time||Burst Time||Completion Time||Turn Around Time||W|
Now we find the completion, Turn around time, waiting time, and the average TAT and waiting time.
The completion time of P1 is: 25 The completion time of P2 is 11 The completion time of P3 is 29 The completion time of P4 is: 34
Turn Around Time: Completion Time (CT) – Arrival Time (AT)
For process P1: 25 – 0 = 25
For process P2: 11 -1 = 10
For process P3: 29 – 2 = 27
For process P4: 34 – 3 = 31
Average Turn Around Time is: (25+10+27+31)/4 = 23.25
Process Waiting Time:-
P1 = 25-8 =17
P2 = 10-5 =5
P3 = 27-10= 17
P4 = 31-11=20
Average Waiting Time is: (17+5+17+20)/4 = 59/4 = 14.75
Implementation OF SJF ScheDULing Algorithm ->>>click here