RR Algorithm
Round-robin Scheduling
Round-robin scheduling allocates each task an equal share of the CPU time. In its simplest form, tasks are in a circular queue and when a task's allocated CPU time expires, the task is put to the end of the queue and the new task is taken from the front of the queue. Round-robin scheduling is not very satisfactory in many real-time applications where each task can have varying amounts of CPU requirements depending upon the complexity of processing required. One variation of the pure round-robin scheduling is to provide priority-based scheduling, where tasks with the same priority levels receive equal amounts of CPU time. It is also possible to allocate different maximum CPU times to each task.
Characteristics
- Round Robin is the preemptive process scheduling algorithm.
- Each process is provided a fix time to execute, it is called a quantum.
- Once a process is executed for a given time period, it is preempted and other process executes for a given time period.
- Context switching is used to save states of preempted processes.
Advantages
- All the jobs get a fair allocation of CPU.
- It deals with all process without any priority
- This scheduling method does not depend upon burst time. That's why it is easily implementable on the system.
- Once a process is executed for a specific set of the period, the process is preempted, and another process executes for that given time period.
- It gives the best performance in terms of average response time.
Disadvantages
- If slicing time of OS is low, the processor output will be reduced.
- This method spends more time on context switching
- Its performance heavily depends on time quantum.
- Decreases comprehension
- Finding a correct time quantum is a quite difficult task in this system.
Example
Time quantum: 4
| process |
Arrival Time |
Burst Time |
| P1 |
0 |
5 |
| P2 |
1 |
6 |
| P3 |
2 |
3 |
| P4 |
3 |
1 |
| P5 |
4 |
5 |
| P6 |
6 |
4 |
Working
- In round robin scheduling algorithm every process is picked up and is allowed to execute for the period of time quantum.After which the process is preempted and again put back in the ready queue after which another process is picked up and the same scenario is repeated over and over until all the processes are completed.
- Once a process is picked up from the ready queue for its execution a precondition is checked weather the process burst time is greater than the time quantum or not.
- If the process burst time is greater than the time quantum the process is allowed to execute for the period of time quantam. After which it is again puts back into the ready queue. (In such case the burst time is deduce by the given time quantum and the process is again put back into the ready queue for its execution for the remaining period of time.)
- The above scenario is repeated until the process is completed and goes to the termination state.
- If the process burst time is less than the time quantum the process is allowed to execute for its burst time and then the process is terminated.
Gantt Chart
| P1 |
P2 |
P3 |
P4 |
P5 |
P1 |
P6 |
P2 |
P5 |
| 0-4 |
4-8 |
8-11 |
11-12 |
12-16 |
16-17 |
17-21 |
21-23 |
23-24 |
Final Table
| Process |
Arrival Time |
Burst Time |
Complition Time |
Turn Around Time |
Waiting Tme |
Response Time |
| P1 |
0 |
5 |
17 |
17 |
12 |
0 |
| P2 |
1 |
6 |
23 |
22 |
16 |
3 |
| P3 |
2 |
3 |
11 |
9 |
6 |
6 |
| P4 |
3 |
1 |
12 |
9 |
8 |
8 |
| P5 |
4 |
5 |
24 |
20 |
15 |
8 |
| P6 |
6 |
4 |
21 |
15 |
11 |
11 |