.png)
Mobiprep has created last-minute notes for all topics of Deadlock to help you with the revision of concepts for your university examinations. So let’s get started with the lecture notes on Deadlock.
Our team has curated a list of the most important questions asked in universities such as DU, DTU, VIT, SRM, IP, Pune University, Manipal University, and many more. The questions are created from the previous year's question papers of colleges and universities.
Deadlock Lecture Notes
Question 1 - What is Deadlock?
Answer - Deadlock is a condition in which a group of processes are waiting for the resources held by some other process, while holding a resource which is required by the other process. Under such condition, none of the processes can proceed further in execution. Hence, these processes are blocked.
Question 2 - Give a real world scenario of deadlock.
Answer - Consider a bridge which can allow only one vehicle to pass across it at a time (The width of the bridge is narrow). When two vehicles try to cross the bridge from opposite directions, a deadlock occurs. Neither of the two vehicles can move further. Here, we consider the bridge as the resource and the vehicles as processes.
Question 3 - What are the necessary conditions for deadlock to occur?
Answer - For a deadlock to occur in a system when all the following conditions hold:
Mutual exclusion: Mutual exclusion is a condition in which only one process can hold a resource at a time.
Hold and Wait: A process holds a resource until it gets another resource.
No pre-emption: A process does not give-up a resource before it has completed execution.
Circular wait: Circular wait condition occurs when a group of processes are waiting for the resources held by each other in a circular fashion.
Question 4 - How can we prevent deadlock?
Answer - Deadlock can be prevented by making one of the below four conditions False.
Mutual Exclusion
Hold and Wait
No pre-emption
Circular Wait
Mutual Exclusion: The mutual exclusion condition can be violated if a resource is used by more than one process at a time. But, removing the mutual exclusion condition is impossible as it might lead to un-sharable resources.
Hold and Wait: Hold and wait condition can be prevented by preventing a process from holding a resource or by preventing the process from waiting for a resource. Such a condition can be achieved by the allocation of necessary resources before the execution of a process.
No pre-emption: Pre-emption can be achieved by stopping a process while execution and taking away the resource held by that process. But, this is not an advisable approach.
Circular Wait: Circular wait can be avoided by assigning a number to each resource and each process. A process should not be able to request a resource with a number less than itself. This ensures the prevention of the circular wait condition.
Question 5 - What is Deadlock Avoidance?
Answer - Deadlock avoidance is different from deadlock prevention. In deadlock avoidance, our aim is to avoid unsafe states. Deadlock avoidance methods allocate resources to the processes only if the system remains in the safe state. Safe state refers to the condition in which deadlock cannot occur. The most commonly used deadlock avoidance algorithm is the ‘Banker’s Algorithm'.
Question 6 - What is Wait-for-Graph?
Answer - Wait-for-graph method is used for deadlock detection. This method involves the transaction graph. A transaction graph is drawn by considering the transactions and their lock on the resource. If a cycle is detected in the graph, then deadlock is said to exist in the system. Else, there is no deadlock.
Example:
In the above transaction graph, a cycle exists. Hence, the system is in deadlock.
Question 7 - Discuss the drawbacks of Deadlock Avoidance Algorithm.
Answer - The following are the disadvantages of deadlock avoidance algorithm:
The deadlock avoidance algorithms are not efficient because they cause unwanted delays while trying to avoid the unsafe states.
It is applicable to only limited number of resources and processes.
It does not completely prevent deadlock. So, deadlock might occur.
Question 8 - Explain Banker's Algorithm in detail with data structure.
Answer - The Banker’s algorithm is a deadlock avoidance algorithm which checks for safe state. It simulates the resource allocation before actually allocating the resources to the processes. Hence, it detects the possible un-safe states and avoids deadlock.
Need matrix: The need matrix shows the resources which are needed by the processes, but still are not allocated.
Safety Algorithm: The safety algorithm is used to find whether the given system is safe or not.
Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively.
Initialize: Work = Available
Finish[i] = false; for i=1, 2, 3, 4….n
2) Find an i such that both
a) Finish[i] = false
b) Needi <= Work
if no such i exists goto step (4)
3) Work = Work + Allocation[i]
Finish[i] = true
goto step (2)
4) if Finish [i] = true for all i
then the system is in a safe state
Resource Request Algorithm
1) If Requesti <= Needi
Goto step (2) ; otherwise, raise an error
2) If Requesti <= Available
Goto step (3); otherwise, Pi must wait
3) Have the system pretend to have allocated the requested resources to process Pi by modifying the state as follows:
Available = Available – Requesti
Allocationi = Allocationi + Requesti
Needi = Needi– Requesti
Example:
The resources A, B and C have 12, 7 and 8 instances respectively.
Process | Allocation | Max | Available |
P0 | A - 2 B - 0 C - 0 | A - 5 B - 7 C - 2 | A - 4 B - 4 C - 4 |
P1 | A - 0 B - 1 C - 0 | A - 3 B - 2 C - 1 | |
P2 | A - 2 B - 1 C - 1 | A - 2 B - 1 C - 1 | |
P3 | A - 3 B - 0 C - 2 | A - 5 B - 3 C - 3 | |
P4 | A- 1 B - 1 C - 1 | A - 3 B - 3 C - 3 | |
Need Matrix:
Need [i, j] = Max [i, j] – Allocation [i, j]
Process | Need |
P0 | A - 3 B - 7 C - 2 |
P1 | A - 3 B - 0 C - 2 |
P2 | A - 0 B - 0 C - 0 |
P3 | A - 2 B - 3 C - 1 |
P4 | A - 2 B - 2 C - 2 |
By applying the safety algorithm, we find that the system is safe
Question 9 - What are the different methods of recovery from deadlock?
Answer - Once the deadlock is detected, the system must be recovered from deadlock. The following are the three methods of data recovery after deadlock:
Preemption: By preemption, the resources held by a process are taken back to avoid deadlock. The resources taken are given to another process that is waiting for that resource. By doing so, the ‘Hold and Wait’ condition is eliminated and the system can recover from deadlock.
Kill the Process: Another method of removing deadlock is by killing the processes one by one. After killing each process, the existence of deadlock is checked. If the deadlock still exists, this process is continued. The processes are killed until the system is free from deadlock.
Rollback: The different states of the process are recorded by the Operating System. When a deadlock occurs, the processes are rolled back to their previous states. If the system is free from the deadlock in any of the previous states of a process, then, the process is rolled back to that particular state. In this way, the system can be freed from deadlock.