Questions: Deadlock Conditions and Resource Graphs

Question 1

Three processes each hold one resource and are each waiting for the resource held by the next process, forming a cycle. Each resource type has exactly one instance. You draw the resource allocation graph and find a cycle. What can you conclude?

• A. Deadlock is possible but not certain — you must run the Banker's Algorithm to confirm
• B. Deadlock is guaranteed — with single-instance resources, a cycle in the resource allocation graph is sufficient for deadlock
• C. No conclusion is possible from the graph alone; you must check all four conditions independently
• D. Deadlock is guaranteed only if the cycle includes all processes in the system

Answer: (B)

With single-instance resources, a cycle in the resource allocation graph is both necessary and sufficient for deadlock. Every process in the cycle holds one resource and waits for one held by the next — no process can proceed, and none can be unblocked. The four conditions are all already encoded in this situation. The Banker's Algorithm is used for avoidance (preventing cycles before they form), not for detection of an already-present cycle.

Question 2

A system designer wants to prevent deadlock by eliminating one of the four necessary conditions. Which condition is MOST practically eliminable through system design?

• A. Mutual exclusion — most resources can be made shareable if the OS is designed cleverly
• B. No preemption — the OS can always safely force a process to release its resources
• C. Hold-and-wait — processes can be required to request all resources at once before starting
• D. Circular wait — it is impossible to impose a global ordering on arbitrary resource types

Answer: (C)

Requiring processes to request all needed resources at once (or to release held resources before requesting new ones) eliminates hold-and-wait — a practical design choice. Mutual exclusion often cannot be broken (shared mutable state genuinely requires exclusive access). No preemption is dangerous for many resource types (e.g., forcibly preempting a file write causes data corruption). Circular wait CAN be broken via global resource ordering, but hold-and-wait is often simpler to enforce at the system design level.

Question 3

In a resource allocation graph, if every resource type has multiple instances, a cycle is necessary but not sufficient for deadlock.

• T. True
• F. False

Answer: True

With multiple instances, a cycle means deadlock is possible: the cycle shows a waiting pattern, but an instance held by a process outside the cycle might become available and break the deadlock. With single-instance resources, a cycle IS sufficient — there are no extra instances to break the chain. The number of instances per resource type is what changes the sufficiency condition.

Question 4

A cycle in a resource allocation graph usually guarantees that deadlock exists, regardless of how many instances each resource type has.

• T. True
• F. False

Answer: False

With multiple instances of a resource type, a cycle is necessary but not sufficient for deadlock. Another instance of a requested resource may become available from a process outside the cycle, allowing one waiting process to proceed and dissolving the deadlock. Only when every resource type involved has exactly one instance does a cycle guarantee deadlock.

Question 5

Why does breaking the circular-wait condition — for example, by imposing a global numeric ordering on resource types — prevent deadlock, even though processes can still hold multiple resources while waiting?

Model answer: If resources must always be requested in ascending numeric order, no cycle can form in the resource allocation graph. A cycle requires that some process holds a higher-numbered resource while waiting for a lower-numbered one — but the ordering rule forbids this. Since circular wait is one of the four necessary conditions for deadlock, eliminating it guarantees deadlock cannot occur even if the other three conditions (mutual exclusion, hold-and-wait, no preemption) are all present.

The key insight is that all four conditions must be simultaneously present for deadlock to occur. Removing any single one is sufficient to prevent deadlock. Global resource ordering is particularly elegant because it's a static policy imposed at design time — processes don't need to change their behavior other than in which order they request resources.