Round robin scheduling





Round Robin Scheduling
The basic purpose of this algorithm is to support time sharing system. This algorithm is similar to the FCFS algorithm but now it is preempted FCFS scheduling. The preempted take place after a fixed interval of time called quantum time of time slice. Its implementation requires timer interrupt based on which the preemption take place.
Consider the set of the processes lined up in the ready queue. The processes are taken out of the ready queue in FCFS order. Let us suppose that a process has been taken up for execution now. The execution cannot go beyond that time slice. This process may either finish up its execution before the time goes off or CPU will be preempted from it after the timer goes off and this cause an interrupt to the operating system. At this time, context switching will take place. The next process will be taken up from the ready queue. The process, which is left by the CPU, will be added to the tail of the ready queue.

robin hood scheduling

robin hood scheduling

process CPU Burst Time
p1 10
p2 5
p3 2

The Gantt chart is shown below:

robin hood scheduling

robin hood scheduling

Waiting time for P1 = 0 + (6-2) + (10-8) + (13-12) = 7 Millisecond
Waiting time for P2 = 2+ (8-4) + (12-10) = 8 millisecond
Waiting time for P3 = 4millisecond
Therefore average waiting time = (7+8+4)/3 = 6.33 Millisecond

As shown in figure: first p1 gets the cpu and get executed for 2 millisecond, then context switching occurs and P2 get cpu for 2 millisecond, then again content switching occur and P3 get cpu for 2 millisecond, since its cpu burst time is 2 millisecond only, therefore it complete its execution and thus do not get the cpu again. P1 and P2 similarly continue to share the CPU in the same fashion till they are done.

Overall performance depends on

  • Size of the time quantum
  1. If time quantum is large than the CPU burst then this algorithm become same as FCFS and thus performance degrade.
  2. If the time quantum size is very small, then the number of content switches increases and the time quantum almost equal the time taken to switch the CPU from one process to another. Therefore 50% of time spent in switching of processes.
  • Number of context switching

The number of context switches should not be too many to slow down the overall execution of all the processes. Time quantum should be large with respect to the context switch time. This is to ensure that a process keeps CPU for a maximum time as compared to the time spent in the context switching.



Related posts:

  1. Scheduling Introduction Scheduling is the process of determining which processes will...
  2. Processes Scheduling queue As processes enter the system they put in job queue....
  3. First Come First Served Algorithm First come first served scheduling algorithm (FCFS) FCFS also termed...
  4. Process States As the program executes, it generally changes state. A state...
  5. processes creation A process can create several new processes. The creating process...