Previous Year Questions: Deadlock | Operating System - Computer Science Engineering (CSE) PDF Download

Q1: Which of the following statements is/are TRUE with respect to deadlocks?  (2022)
MSQ
(a) Circular wait is a necessary condition for the formation of deadlock.
(b) In a system where each resource has more than one instance, a cycle in its wait-for graph indicates the presence of a deadlock.
(c) If the current allocation of resources to processes leads the system to unsafe state, then deadlock will necessarily occur.
(d) In the resource-allocation graph of a system, if every edge is an assignment edge, then the system is not in deadlock state.
Ans: (a, d)
Sol: 
A. Circular Wait is one of the four necessary conditions for deadlock to happen. So, option #A is True.
B. Not necessarily, if every resource had only a single instance then, a cycle would’ve been necessary and sufficient for a deadlock to occur. A Cycle in a multi-instance resource is necessary but isn’t sufficient and in this case, each resource is made up of more than one instance, a simple contradiction. So, option #B is False
C. An Unsafe state is where no method of allocation of resources can prevent deadlock from happening. Whereas in a safe state, there exists a method of allocation in which all processes are complete. Hence, option #C is False.
D. Resource Allocation graph accommodates future resource requirements in the form of request edges. If there are no request edges, then resource requirements for all the processes are satisfied. So, option #D is True.

Q2: Consider the following snapshot of a system running n concurrent processes. Process i  is holding X _i  instances of a resource R, 1 ≤ i ≤ n . Assume that all instances of R are currently in use. Further, for all i , process i  can place a request for at most Y_i additional  instances of R  while holding the X _i  instances it already has. Of the n processes, there are exactly two processes p and q such that Y _p = Y _q = 0 . Which one of the following conditions guarantees that no other process apart from p and q can complete execution?  (2019)
(a) X _p + X _q < Min {Y_k∣1 ≤ k ≤ n, k ≠ = p, k ≠ = q}
(b) X _p + X _q < Min {Y_k∣1 ≤ k ≤ n, k ≠ = p, k ≠ = q}
(c) Min (X _p , X _q ≤ Min {Y_k∣1 ≤ k ≤ n, k ≠ = p, k ≠ = q}
(d) Min (X _p , X _q  ≤ Max {Y_k∣1 ≤ k ≤ n, k ≠ = p, k ≠ = q}
Ans: (a)
Sol: The process P, holds X _p resources currently and it doesn't request any new resources. Therefore after some time, it will completes it's execution and release the resources which it holds.
The process Q, holds X_q resources currently and it doesn't request any new resources. Therefore after some time, it will completes it's execution and release the resources which it holds.
Total available resources after completion of P and Q = X _p + X _q .
If these resources can not satisfy any process new requests, then no process will be able to completes it's execution.
X _p + X _q < Min {Y_k∣1 ≤ k ≤ n, k ≠ = p, k ≠ = q} ⟹ delivers that no process going to completes except P and Q.  Answer is (A)

Q3: In a system, there are three types of resources: E, F and G. Four processes P₀ , P₁ , P₂  and  ₃  execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Max as given below. For example, Max[ P₂   ,F] is the maximum number of instances of F that P₂ would require. The number of instances of the resources allocated to the various processes at any given state is given by a matrix named Allocation. Consider a state of the system with the Allocation matrix as shown below, and in which 3 instances of E and 3 instances of F are the only resources available.  (2018) 

From the perspective of deadlock avoidance, which one of the following is true?
(a) The system is in safe state.
(b) The system is not in safe state, but would be safe if one more instance of E were available
(c) The system is not in safe state, but would be safe if one more instance of F were available
(d) The system is not in safe state, but would be safe if one more instance of G were available
Ans: (a)
Sol:  Available Resource [ E , F , G ] = ( 3 , 3 , 0 )
With ( 3 , 3 , 0 ) we can satisfy the request of either P ₀ or P ₂
Let's assume request of P₀ satisfied.
After execution, it will release resources.
Available Resource = (3, 3, 0) + (1, 0, 1) = (4, 3, 1 )
Give ( 0 , 3 , 0 ) out of ( 4 , 3 , 1 ) unit of resources to P₂ and P₂ will completes its execution.
After execution, it will release resources.
Available Resource = (4, 3, 1) + (1, 0, 3) = (5, 3, 4 )
Allocate ( 1 , 0 , 2 ) out of ( 5 , 3 , 4 ) unit of resources to P 1 and P 1 will completes its execution.
After execution, it will release resources.
Available Resource = ( 5 , 3 , 4 ) + ( 1 , 1 , 2 ) = ( 6 , 4 , 6 )
And finally, allocate resources to P ₃ .
So, we have one of the possible safe sequence:  P₀ → P₂  → P₁  → P₃ 
Correct Answer: A

Q4: Consider a system with 3 processes that share 4 instances of the same resource type. Each process can request a maximum of K instances. Resource instances can be requested and released only one at a time. The largest value of K that will always avoid deadlock is ____.  (2018)
(a) 2
(b) 3
(c) 4
(d) 5
Ans: (a)
Sol: Number of processes = 3
Number of Resources = 4
Let's distribute each process one less than maximum demand (K−1) resources. i.e. K (K−1)
Provide an additional resource to any of three processes for deadlock avoidance.
So, we have one of the possible safe sequence: Total resources = 3 ( K − 1 ) + 1 = 3 K − 2
Now, this 3K−2 should be less than or equal to the number of resources we have right now.
3K−2  ≤ 4
⟹ ⟹ 3k  ≤ 6
⟹⟹ k  ≤ 2
So, largest value of k = 2

Q5: A system shares 9 tape drives. The current allocation and maximum requirement of tape drives for three processes are shown below:  (2017 SET 2)

Which of the following best describes current state of the system ?
(a) Safe, Deadlocked
(b) Safe, Not Deadlocked
(c) Not Safe, Deadlocked
(d) Not Safe, Not deadlocked
Ans: (b)
Sol: 
Given there are total 9 tape drives,
 So, according to the above table we can see we have currently allocated ( 7 tape drive), so currently Available tape drives = 2
So, P3 can use it and after using it will release it 3 resources New Available = 5
then P1 can use it and will release it 3 resources so New Available = 8
and lastly P2 so, all the process are in SAFE STATE and there will be NO DEADLOCK
Safe Sequence will be P 3 → P 2 → P 1 or P 3 → P 1 → P 2.
Answer will be (B) only.

Q6: A multithreaded program P executes with x number of threads and uses y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentrant, i.e., if a thread holds a lock l, then it cannot re-acquire lock l without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes available. The minimum value of x and the minimum value of y together for which execution of P can result in a deadlock are:  (2017 SET 1)
(a) x = 1, y = 2
(b) x = 2, y =1
(c) x = 2, y =2
(d) x = 1, y = 1
Ans: (d)
Sol: If we see definition of reentrant Lock :
In computer science, the reentrant mutex (recursive mutex, recursive lock) is particular type of mutual exclusion (mutex) device that may be locked multiple times by the same process/thread, without causing a deadlock.
A Re-entrant Lock is owned by the thread last successfully locking, but not yet unlocking it. A thread invoking lock will return, successfully acquiring the lock, when the lock is not owned by another thread. The method will return immediately if the current thread already owns the lock
Reentrant property is provided, so that a process who owns a lock, can acquire same lock multiple times. Here it is non-reentrant as given, process cant own same lock multiple times. So if a thread tries to acquire already owned lock, will get blocked, and this is a deadlock.
Here, the answer is (D).

Q7: Consider the following policies for preventing deadlock in a system with mutually exclusive resources.  (2015 SET 3) 
I. Processes should acquire all their resources at the beginning of execution. If any resource is not available, all resources acquired so far are released
II. The resources are numbered uniquely, and processes are allowed to request for resources only in increasing resource numbers
III. The resources are numbered uniquely, and processes are allowed to request for resources only in decreasing resource numbers
IV. The resources are numbered uniquely. A process is allowed to request only for a resource with resource number larger than its currently held resources
Which of the above policies can be used for preventing deadlock?
(a) Any one of I and III but not II or IV
(b) Any one of I, III, and IV but not II
(c) Any one of II and III but not I or IV
(d) Any one of I, II, III, and IV
Ans: (d)
Sol: A deadlock will not occur if one of the following four conditions doesn’t occur :

• Mutual exclusion: it prevents simultaneous access to a shared resource.
• Hold and wait: Process is holding a resource that may be required by other processes.
• Circular wait: It means there are processes which are waiting for other processes to finish.
• No pre-emption: If a process that is holding some resources requests another resource and that  resource cannot be allocated to it, then it must release all resources that are currently allocated to it.

Option 1:
Processes should acquire all their resources at the beginning of execution. If any resource is not available, all resources acquired so far are released. If this is allowed , then hold and wait will never occur. So, deadlock will not occur.
Option 2:
The resources are numbered uniquely, and processes are allowed to request for resources only in increasing resource numbers. It violates circular wait .
Option 3:
The resources are numbered uniquely, and processes are allowed to request for resources only in decreasing resource numbers. It also violates circular wait.
Option 4:
The resources are numbered uniquely. A process is allowed to request only for a resource with resource number larger than its currently held resources. It also violates circular wait.
So, all options are needed to prevent deadlock.

Q8: A system has 6 identical resources and N processes competing for them. Each process can request at most 2 resources. Which one of the following values of N could lead to a deadlock?  (2015 SET 2)
(a) 1
(b) 2
(c) 3
(d) 4
Ans: (d)
Sol:  3 × 2 = 6
4 x 2 = 8
I guess a question can't get easier than this- (D) choice. (Also, we can simply take the greatest value among choice for this question)
[There are 6 resources and all of them must be in use for deadlock. If the system has no other resource dependence, N= 4 cannot lead to a deadlock. But if N = 4, the system can be in deadlock in presence of other dependencies.
Why N = 3cannot cause deadlock? It can cause deadlock, only if the system is already in deadlock and so the deadlock is independent of the considered resource. Till N = 3, all requests for considered resource will always be satisfied and hence there won't be a waiting and hence no deadlock with respect to the considered resource. ]

Q9: A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks never arise is _________.  (2014 SET 3)
(a) 4
(b) 7
(c) 8
(d) 6
Ans: (b)
Sol: Up to, 6 resources, there can be a case that all process have 2 each and dead lock can occur. With 7 resources, at least one process's need is satisfied and hence it must go ahead and finish and release all 3 resources it held. So, no dead lock is possible.

Q10: An operating system uses the Banker's algorithm for deadlock avoidance when managing the allocation of three resource types X, Y, and Z to three processes P0, P1, and P2. The table given below presents the current system state. Here, the Allocation matrix shows the current number of resources of each type allocated to each process and the Max matrix shows the maximum number of resources of each type required by each process during its execution.  (2014 SET 1)

There are 3 units of type X, 2 units of type Y and 2 units of type Z still available. The system is currently in a safe state. Consider the following independent requests for additional resources in the current state:
REQ1: P0 requests 0 units of X, 0 units of Y and 2 units of Z
REQ2: P1 requests 2 units of x, 0 units of Y and 0 units of Z
Which one of the following is TRUE?
(a) Only REQ1 can be permitted.
(b) Only REQ2 can be permitted
(c) Both REQ1 and REQ2 can be permitted
(d) Neither REQ1 nor REQ2 can be permitted
Ans: (b)
Sol:  Request 1 if permitted does not lead to a safe state.
After allowing Req 1,
Available: X = 3, Y = 2, Z = 0
Now we can satisfy P1′s requirement completely. So Available becomes : X = 6, Y = 4,  Z = 0.
Since, Z is not available now, neither P0′s nor P2′s  requirement can be satisfied. So. it is an unsafe state.
Option (B)

Q11: A system has n resources R ₀ , . . . R _{n − 1}   , and k processes P ₀ , . . . P _{k − 1}  . The implementation of the resource request logic of each process P _i  is as follows:  (2010) 

In which one of the following situations is a deadlock possible?
(a) n = 40,k = 26
(b) n = 21,k = 12
(c) n = 20,k = 10
(d) n = 41,k = 19
Ans: (b)
Sol: From the resource allocation logic, it's clear that even numbered processes are taking even numbered resources and all even numbered processes share no more than 1 resource. Now, if we make sure that all odd numbered processes take odd numbered resources without a cycle, then deadlock cannot occur. The "else" case of the resource allocation logic, is trying to do that. But, if n is odd, R _{n − i} and R _{n − i − 2} will be even and there is possibility of deadlock, when two processes requests the same R _i and R _j . So, only B and D are the possible answers.
Now, in D , we can see that P₀ requests R₀ and R₂ , P₂ requests R₂ and R₄ , so on until, P₁₈ requests R₁₈ and R₂₀ . At the same time P₁ requests R₄₀ and R₃₈ , P₃ requests R₃₈ and R₃₆ , so on until, P₁₇ requests R₂₄ and R₂₂ . i.e.; there are no two processes requesting the same two resources and hence there can't be a cycle of dependencies which means, no deadlock is possible.
But for B , P₈ requests R ₈ and R₁₀ and P₁₁ also requests R₁₀ and R₈ . Hence, a deadlock is possible. (Suppose P₈ comes first and occupies R ₈ . Then P₁₁ comes and occupies R₁₀ . Now, if P ₈ requests R₁₀ and P₁₁ requests R₈ , there will be deadlock)
Correct Answer: B