Topic in Operating Systems
A deadlock is a state in which a set of processes wait forever because each one holds a resource that another process in the set is waiting for. Almost every question builds on the four Coffman conditions: mutual exclusion, hold and wait, no preemption and circular wait. You should be able to read a resource-allocation graph, explain why a cycle guarantees deadlock only when every resource has a single instance, and run the Banker's algorithm to decide whether a state is safe. Other material covers prevention by breaking a condition, such as ordering resource types, the wait-for graph for detection, recovery through process termination or preemption, victim selection, and livelock.
Below are 30 practice questions from a pool of 210 Deadlocks MCQs, one of 12 topics in Operating Systems. Each shows the correct answer with an explanation; when you are ready, take a timed quiz to test recall under exam conditions.
Each question below shows the correct answer with a full explanation. Use these to build conceptual understanding before attempting a timed quiz.
Q1. A deadlock occurs when:
A deadlock is a situation where two or more processes are each waiting for a resource held by another process in the set, creating a circular wait where none can proceed.
Q2. How many necessary conditions must hold simultaneously for a deadlock to occur?
Four conditions must hold simultaneously: mutual exclusion, hold and wait, no preemption, and circular wait. These are known as the Coffman conditions.
Q3. Which of the following is NOT a necessary condition for deadlock?
The four necessary conditions are: mutual exclusion, hold and wait, NO preemption (not preemption), and circular wait. Preemption would actually help prevent deadlock.
Q4. The 'hold and wait' condition means:
Hold and wait means a process is holding at least one resource and is waiting to acquire additional resources that are currently being held by other processes.
Q5. Circular wait means:
Circular wait exists when there is a chain of processes P0, P1, ..., Pn where P0 waits for a resource held by P1, P1 waits for P2, and so on, with Pn waiting for P0.
Q6. Deadlock prevention works by:
Deadlock prevention ensures that at least one of the four necessary conditions (mutual exclusion, hold and wait, no preemption, circular wait) cannot hold, making deadlock structurally impossible.
Q7. A resource allocation graph is used to:
A resource allocation graph uses vertices (processes and resources) and edges (request edges from process to resource, assignment edges from resource to process) to represent the allocation state.
Q8. If a resource allocation graph has no cycle, then:
If the resource allocation graph contains no cycle, then no deadlock exists. A cycle is a necessary condition for deadlock. However, a cycle does not always guarantee deadlock.
Q9. Deadlock avoidance requires:
Deadlock avoidance requires advance information about the maximum resource needs of each process. The system uses this to make decisions that ensure it never enters an unsafe state.
Q10. The Banker's Algorithm is used for:
The Banker's Algorithm is a deadlock avoidance algorithm that checks whether granting a resource request would leave the system in a safe state. If not, the request is denied.
Q11. A safe state is one where:
A state is safe if there exists a sequence of all processes such that each process can be allocated its needed resources (from available + resources held by preceding processes in the sequence) to complete.
Q12. What is the relationship between safe state and deadlock?
A safe state guarantees no deadlock. An unsafe state does not guarantee deadlock but means deadlock is possible. Deadlock avoidance ensures the system never enters an unsafe state.
Q13. To prevent the 'hold and wait' condition, a process must:
To prevent hold and wait: either a process requests all resources before starting (may cause low utilization) or it must release all currently held resources before requesting new ones.
Q14. To prevent circular wait, one approach is:
To prevent circular wait, assign a numerical ordering to all resource types and require that processes request resources in strictly increasing order of their assigned numbers.
Q15. In the Banker's Algorithm, the 'Need' matrix represents:
The Need matrix = Max - Allocation. It represents the remaining resources that each process may still request to complete its task. Need[i][j] = Max[i][j] - Allocation[i][j].
Q16. What is deadlock detection?
Deadlock detection allows deadlocks to occur but uses algorithms to periodically check for deadlocks and then applies recovery techniques (process termination or resource preemption) to resolve them.
Q17. For deadlock detection with single-instance resources, which algorithm is used?
For single-instance resources, a wait-for graph is used. It is a variant of the resource allocation graph where resource nodes are removed. A cycle in the wait-for graph indicates deadlock.
Q18. Which deadlock recovery method terminates processes?
Process termination can abort all deadlocked processes (expensive) or terminate one process at a time until the deadlock is broken (requires re-running detection after each termination).
Q19. When recovering from deadlock by process termination, which factor is NOT typically considered?
When selecting a process to terminate, factors include priority, computation time completed, resources held, resources needed, number of processes to terminate, and whether it is interactive or batch.
Q20. The ostrich algorithm for handling deadlocks refers to:
The ostrich algorithm simply ignores deadlocks ('burying its head in the sand'). It is used when deadlocks are very rare and the cost of prevention, avoidance, or detection is deemed too high. Used by most general-purpose OSes.
Q21. In the Banker's Algorithm safety check, what is the time complexity for n processes and m resource types?
The Banker's Algorithm safety check has time complexity O(n^2 * m) because in the worst case, it needs to scan all n processes n times (each scan finds at least one process that can finish), and each comparison involves m resource types.
Q22. What is the problem with resource preemption as a deadlock recovery method?
Resource preemption challenges include: selecting which process to preempt (cost minimization), rolling back the preempted process to a safe state, and ensuring the same process isn't always selected (starvation).
Q23. In a resource allocation graph with multiple instances per resource type, a cycle:
With multiple instances per resource type, a cycle is necessary but not sufficient for deadlock. A cycle may exist without deadlock if other processes can release resources to break the wait.
Q24. What is a livelock and how does it differ from deadlock?
In a livelock, processes are not blocked but continuously change their states in response to each other without making any real progress. Unlike deadlock, the processes are active but unproductive.
Q25. How does the 'no preemption' condition get addressed in deadlock prevention for resources like CPU registers and memory?
For preemptable resources: if a process requests a resource that is unavailable, its currently held resources are implicitly released (preempted) and added to the list of available resources.
Q26. What is the main limitation of the Banker's Algorithm in practice?
The Banker's Algorithm requires each process to declare maximum resource needs in advance, which is often impractical. Additionally, the number of processes and resources changes dynamically in real systems.
Q27. How frequently should a deadlock detection algorithm be invoked?
Detection frequency is a tradeoff: invoke at every resource request (expensive), at fixed intervals, or when CPU utilization drops below a threshold (suggesting possible deadlock). The choice depends on system characteristics.
Q28. In distributed systems, what additional challenges does deadlock detection face?
In distributed systems, deadlock detection is complicated by communication delays, the absence of a global state, and the possibility of phantom (false) deadlocks detected due to outdated or inconsistent information across nodes.
Q29. What is a two-phase locking protocol and how does it relate to deadlocks?
Two-phase locking has a growing phase (acquiring locks, no releases) and shrinking phase (releasing locks, no acquisitions). It ensures serializability but does not prevent deadlocks - processes can deadlock while in the growing phase.
Q30. What is the wound-wait scheme for deadlock prevention in database systems?
In wound-wait: if an older transaction needs a resource held by a younger one, the younger is 'wounded' (rolled back). If a younger transaction needs a resource held by an older one, it waits. This prevents circular wait.
Take a timed quiz drawn from 210+ questions on this topic. No signup required — your progress saves in your browser.
Start Deadlocks Quiz