Explain the Round Robin CPU scheduling algorithm

There are number of CPU scheduling algorithms, all having different properties thus making them appropriate for different conditions. 

- Round robin scheduling algorithm or RR is commonly used in the time sharing systems. 

- This is the most appropriate scheduling algorithm for time sharing operating systems. 

- This algorithm shares many similarities with the FCFS scheduling algorithm but there is an additional feature to it. 

- This feature is preemption in the context switch occurring between two processes. 

- In this algorithm a small unit of time is defined and is termed as the time slice or the time quantum. 

- These time slices or quantum range from 10ms to 100 ms.

- The ready queue in round robin scheduling is implemented in a circular fashion. 

How to implement Round Robin CPU scheduling algorithm

Now we shall see about the implementation of the round robin scheduling:

1. The ready queue is maintained as the FIFO (first in first out) queue of the processes.
2. Addition of new processes is made at the rear end of the ready queue and selection of the process for execution by the processor is made at the front end.
3. The process first in the ready queue is thus picked by the CPU scheduler. A timer is set that will interrupt the processor when the time slice elapses. When this happens the process will be dispatched.
4. In some cases the CPU burst of some processes may be less than the size of the time slice. If this is the case, the process will be voluntarily released by the CPU. The scheduler will then jump to the process next in the ready queue and fetch it for execution.
5. While in other cases the CPU burst for some processes might be higher than the size of the time slice. In this case the timer set will send an interrupt to the processor, thus dispatching the process and putting it at the rear end of the ready queue. The scheduler will then jump to the next process in the queue.

- The waiting time in round robin scheduling algorithm has been observed to be quite long at an average rate. 

- In this algorithm, not more than one time slice can be allocated to any process under any conditions in a row. 

- However, there is an exception to this if there is only one process to be executed.

- If the CPU burst is exceeded by the process, the process is put back at the tail of the queue after preemption.

- Thus, we can call this algorithm as a preemptive algorithm also. 

- The size of the time quantum greatly affects the performance of the round robin algorithm.

- If the size of the time quantum is kept too large then it resembles the FCFS algorithm. 

- On the other hand if the quantum is of too small size, then this RR approach is called the processor sharing approach. 

- An illusion is created in which it seems every process has its own processor that runs at the fraction of the speed of the actual processor. 

- Further, the effect of the context switching up on the performance of the RR scheduling algorithm.

- A certain amount of time is utilized in switching from one process to another. 

- In this time the registers and the memory maps are loaded, a number of lists and tables are updated; memory cache is flushed and reloaded etc.

- Lesser the size of the time quantum, context switching will occur more number of times. 

What is meant by Deadlock? List the necessary conditions for arising deadlocks?

Consider two competing processes or actions in a situation where both of them wait for each other to be done and so neither of them ever finish. Such a situation is called a deadlock. 

- When the number of competing processes is exactly two, then it is said to be a ‘deadly embrace’. 

- The two involved competing actions tend to move towards some sort of tragedy which might be mutual extinction or mutual death. 

"In operating systems a situation occurs where two threads or processes enter the waiting state at the same time because of the resource that they both want is being used by some other process that also in waiting state for some resource being held by another process in waiting state and so on". 

- It so happens that the process is then unable to change its state since the resources it requires are being used by the other processes which is then keeping the process in waiting state indefinitely. 

- The system is now in a deadlock. 

- Systems such as the distributed systems, parallel computing systems, multi-processing systems face the problem of being in a deadlock quite often. 

- This is so because here the hardware and software locks are purposed for handling the resources that are shared and implementing the process synchronization. 

- Deadlocks may also occur in telecommunication systems because of the corrupt signals and their loss rather than resource contention. 

- A deadlock situation can be compared to problems such as that of the catch-22 or chicken or egg problem. 

- A deadlock can also occur in a circular chain pattern. 

- For example, consider a computer having 3 processes and corresponding 3 CD drives i.e., one held by each process. 

- Now all the three processes would be in a deadlock if they all request another drive.

Conditions for a Deadlock to arise

There are certain conditions that should be there for a deadlock to arise:

1. Mutual exclusion: There has to be at least one resource that cannot be shared. So that only one process would use at any given time.
2. Resource holding (or hold and wait): There should be at least one resource held by a process that in turn should be request more resources that are being held by other processes.
3. No preemption: Once the resources have been allocated, they should not de-allocated by the operating system. The condition is that the process holding the resource must release it voluntarily.
4. Circular wait: A circular chain of processes must be formed as explained in the earlier example.

"These 4 conditions for deadlock are collectively called the ‘Coffman conditions’. If any of these conditions is not met, a deadlock can’t occur".

- Handling a deadlock is an important capability of the operating systems. 

- However, there are many modern operating systems that still cannot avoid deadlocks. 

- On occurrence of a deadlock many non-standard approaches are followed by different operating systems for handling it. 

- Many of these approaches try to avoid at least one of the Coffman conditions (generally the 4^th one). 

- Below we discuss some of the approaches:

1. Ignoring deadlock
2. Detection
3. Prevention
4. Avoidance

- There is a second kind of deadlocks called the ‘distributed deadlock’ and it is common where concurrency control is used or we can say in the distributed systems.