Explain briefly Deadlock Avoidance and Detection?

Deadlocks are a serious issue that needs to be avoided since it can cause the whole system to hang or crash.

What is Deadlock Avoidance?

- Avoiding a deadlock is possible only if certain information regarding the processes is available with the operating system.
- This information has to be made available to the OS just before the resources are allocated to the processes.
- These are the processes that are to be consumed by the process in its lifetime.
- For every resource request made by the process, any potential threats are checked by the system i.e., whether granting the request of the process will send it in to an unsafe zone or not.
- If it is so then there are possibilities that the system could enter a deadlock.
- Therefore, only those requests are granted by the process that will ensure a safe state of the process.
- It is important for the system to determine whether the next level of the process will be safe or unsafe.
- There are 3 things that the operating system must know at any before or after the execution of the process:
1. The currently available resources.
2. The resources currently allocated to the processes.
3. Resources to be required and released in the future by these processes.

- It is possible that a process might be in an unsafe state but still may not cause a deadlock.
- By the notion of the safe and unsafe state of the process we refer to the system’s ability of entering in to a deadlock.
An example will make it clearer:
- Consider a resource A requested by a process which would make the process state unsafe.
- At the same time it releases another resource say B preventing the circular wait of the resources.
- In such a situation, the system is said to be in an unsafe state though not necessarily in a deadlock.
- There are various algorithms that have been designed for deadlock avoidance and one such is the banker’s algorithm.
- To use this algorithm knowledge about the resource usage limit is required in advance.
-  It is impossible for most of the systems to know what a process will request for in advance.
- This only implies that the deadlock avoidance is also not possible here.
- There are other two algorithms for achieving this task namely wound/ wait and wait/ die algorithms.
- Each of them makes use of a symmetry breaking technique.

What is Deadlock Detection?

- Deadlocks are free to occur under the implementation of this concept.
- Then through the state of the system, the occurrence of the deadlock is confirmed and subsequently mended.
- Here, the resource allocation activities are tracked along with the process states by certain algorithms.
- After this, the algorithm is used for removing the deadlock.
- Deadlock detection is quite easy since the OS scheduler knows about the resources that have been locked by the processes.
- Model checking is one of the techniques used for deadlock detection.
- In this a finite state model is created up on which a progress analysis of the process is carried out and all the terminal sets of the model are found.
- Each of these stands for a deadlock.
- Correction of the deadlock can be done by any of the below mentioned methods after the deadlock has been detected:
1. Process termination: This is about aborting one or more of the processes that cause the deadlock thus ensuring a certain and speedy removal of the deadlock. But this method might prove to be a little expensive because of the loss of the partial computations.
2. Resource preemption: This is about a successive preemption of the allocated resources until the breakdown of the deadlock.

What is a Safe State and what is its use in deadlock avoidance?

Safe state plays a great role in avoiding the deadlocks. In this article we discuss in detail the concept of this safe state.
When do we call a state safe?
It is when even if the system allocates resources to all the processes and no deadlock occurs. This allocation is to the maximum limits and can be done in any preferred order. To put it down more formally, we can say that a system is considered to be in a safe state only if a safe sequence exists. This would become clearer from the following example:

Consider the following sequence of processes:

- Now this sequence is considered to be a safe one for the current state of the allocation if the resource requests made by each of the processes Pi can be satisfied by resources that are currently available including the resources held by some another process that precedes Pi.
- In this case, if the resources required by the Pi are not presently available, then it can wait till the preceding process completes its executions and releases the resources.
- Once it finishes, the resources it held, now can be utilized by the Pi for completing the task assigned to it and then it also releases back the resources to be used by succeeding processes.
- It then finally terminates.
- If there exists no sequence like this, then the system is said to be in an unsafe state.
- A deadlock cannot occur in a safe state and so this state cannot be called a deadlocked one. 
- But on the other side, a state is unsafe if it has a deadlock.
- However, it is not necessary that the reason for all states being unsafe is the deadlock.
- An unsafe state can however lead to a deadlock. 
- It is in the safe states, that the operating system is capable of avoiding the deadlocks.
- When the operating system falls in an unsafe state, it is no more in a position to prevent the requests of the processes that would cause a deadlock to occur.
- It is the behavior of the processes by which the unsafe states of the system are controlled.
- Another major difference between the safe and the unsafe states is that in a safe state it is guaranteed by the operating system that the execution of the processes will be completed in expected time but in the case of unsafe states it gives no such guarantee.
- If the concept of the safe state is predefined, then algorithms can be designed that would make sure that no deadlocks occur.
- The idea behind these algorithms would be to ensure the following things:
1. The system does not come out of the safe state.
2. The system is kept in a safe state initially.
3. The system must be able to determine if a resource requested by a process can be allocated immediately to it or it requires waiting.
4. The system grants the request of the process if and only if after finishing it, the system would still be in a safe state.

- One disadvantage of such algorithms is low resource utilization. It is because the process would still have to wait for the resource even if it is available.
- A deadlock occurs when two or more processes that are competing with one another to wait for each other to finish and neither of them do so.
- The deadlock which involves only two processes is called a deadly embrace.
- This may also occur if one process is waiting for the other to finish which in turn is waiting for some other process to finish and so on.