Round Robin Scheduler

Round Robin is a CPU scheduling algorithm where each process is assigned a fixed time slot in a cyclic way.

• It is simple, easy to implement, and starvation-free as all processes get fair share of CPU.
• One of the most commonly used technique in CPU scheduling as a core.
• It is preemptive as processes are assigned CPU only for a fixed slice of time at most.
• The disadvantage of it is more overhead of context switching.

Round Robin(RR) scheduling algorithm is mainly designed for time-sharing systems. This algorithm is similar to FCFS scheduling, but in Round Robin(RR) scheduling, preemption is added which enables the system to switch between processes.

• A fixed time is allotted to each process, called a quantum, for execution.
• Once a process is executed for the given time period that process is preempted and another process executes for the given time period.
• Context switching is used to save states of preempted processes.
• This algorithm is simple and easy to implement and the most important is thing is this algorithm is starvation-free as all processes get a fair share of CPU.
• It is important to note here that the length of time quantum is generally from 10 to 100 milliseconds in length.

Some important characteristics of the Round Robin(RR) Algorithm are as follows:

1. Round Robin Scheduling algorithm resides under the category of Preemptive Algorithms.
2. This algorithm is one of the oldest, easiest, and fairest algorithm.
3. This Algorithm is a real-time algorithm because it responds to the event within a specific time limit.
4. In this algorithm, the time slice should be the minimum that is assigned to a specific task that needs to be processed. Though it may vary for different operating systems.
5. This is a hybrid model and is clock-driven in nature.
6. This is a widely used scheduling method in the traditional operating system.

Important terms

1. Completion Time It is the time at which any process completes its execution.
2. Turn Around Time This mainly indicates the time Difference between completion time and arrival time. The Formula to calculate the same is: Turn Around Time = Completion Time – Arrival Time
3. Waiting Time(W.T): It Indicates the time Difference between turn around time and burst time. And is calculated as Waiting Time = Turn Around Time – Burst Time

Let us now cover an example for the same:

A Process Scheduler schedules different processes to be assigned to the CPU based on particular scheduling algorithms. There are six popular process scheduling algorithms which we are going to discuss in this chapter −

• First-Come, First-Served (FCFS) Scheduling
• Shortest-Job-Next (SJN) Scheduling
• Priority Scheduling
• Shortest Remaining Time
• Round Robin(RR) Scheduling
• Multiple-Level Queues Scheduling

These algorithms are either non-preemptive or preemptive. Non-preemptive algorithms are designed so that once a process enters the running state, it cannot be preempted until it completes its allotted time, whereas the preemptive scheduling is based on priority where a scheduler may preempt a low priority running process anytime when a high priority process enters into a ready state.

First Come First Serve (FCFS)

• Jobs are executed on first come, first serve basis.
• It is a non-preemptive, pre-emptive scheduling algorithm.
• Easy to understand and implement.
• Its implementation is based on FIFO queue.
• Poor in performance as average wait time is high.
  

  Round-robin scheduling (Figure 7.151) 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. An example project is given later on the use of round-robin scheduling.

  18.4.2 Round-robin scheduling and context switching

  In round-robin scheduling the operating system is driven by a regular interrupt (the ‘clock tick’). Tasks are selected in a fixed sequence for execution. On each clock tick, the current task is discontinued and the next is allowed to start execution. All tasks are treated as being of equal importance and wait in turn for their slot of CPU time. Tasks are not allowed to run to completion, but are ‘pre-empted’, i.e. their execution is discontinued mid-flight. This is an example of a ‘pre-emptive’ scheduler.

  The implications of this pre-emptive task switching, and its overheads, are not insignificant and must be taken into account. When the task is allowed to run again, it must be able to pick up operation seamlessly, with no side-effect from the pre-emption. Therefore, complete context saving (all flags, registers and other memory locations) must be undertaken as the task switches. Time-critical program elements should not be interrupted, however, and this requirement will need to be written into the program.

  A diagrammatic example of round-robin scheduling is shown in Figure 18.6. The numbered blocks once more represent the tasks as they execute, but there is a major difference from Figure 18.5. Now each task gets a slot of CPU time, which has a fixed length. The clock tick, which causes this task switch, is represented in the diagram by an arrow. When that time is up, the next task takes over, whether the current one has completed or not. At one stage Task 2 completes and does not need CPU time for several time slices. It then becomes ready for action again and takes its turn in the cycle.

In the above diagram, arrival time is not mentioned so it is taken as 0 for all processes.

Note: If arrival time is not given for any problem statement then it is taken as 0 for all processes; if it is given then the problem can be solved accordingly.