Unit 7 Self-Check Quiz

Question

Question 1

Define deadlock and distinguish it from starvation and livelock.

Answer 1

Deadlock: two or more processes are each waiting for a resource held by another, and none can proceed — the processes are blocked and no work is done. Starvation: a process is indefinitely prevented from proceeding because others are always favoured, but the process is not blocked by a cyclic dependency; it is a failure of the scheduling or allocation policy. Livelock: processes are not blocked but continually change state in response to each other without making progress — they are active but useless. All three are liveness failures; deadlock is the only one that requires a cycle of waiting.

Answer 2

Mutual exclusion: at least one resource is non-shareable — only one process may hold it at a time. Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes. No preemption: a resource can be released only voluntarily by the process holding it. Circular wait: there is a closed chain of processes, each waiting for a resource held by the next. All four must hold simultaneously for deadlock to occur; removing any one makes deadlock impossible.

Answer 3

The second choice. With single-instance resources, a cycle in the graph is a sufficient condition: the cycle describes an actual chain of waiting, and no process in the chain can proceed. With multiple-instance resources, a cycle is only necessary: the process may be waiting for any instance of a resource type, and an instance held by a process in the cycle may satisfy the request — so deadlock is possible but not certain.

Answer 4

Hold-and-wait is eliminated: no process holds a resource while waiting for another.
No-preemption is eliminated: a resource is effectively taken away from the holder when it cannot proceed.
Circular-wait is eliminated: if every process acquires in increasing order, no cycle can form.
No-preemption is eliminated: resources can be preempted.

Answer 5

It requires the process to know, before execution, exactly which resources it will need — an impossible prediction for general-purpose programs whose needs depend on input and on decisions made at run time. It also causes very poor resource utilisation: a process holds resources it will not need for some time, blocking other processes that could use them in the interim. Finally, a process that has acquired most but not all of its required resources holds them while waiting for the rest, so the wait may be long and the held resources are unavailable to others.

Answer 6

Prevention is a design-time property of the system: the resource-allocation protocol is designed so that at least one of the four necessary conditions can never hold. The system is guaranteed deadlock-free for any workload the protocol admits. Avoidance is a run-time decision: the system permits the four conditions but grants a request only when the resulting state is safe. Avoidance requires advance knowledge of each process's maximum resource needs (declared as the Max matrix in the Banker's algorithm). Prevention constrains the programmer; avoidance constrains the workload.

Answer 7

Available = (10, 5, 7) − (7, 2, 3) = (3, 3, 4). Need: P0 = (7, 4, 3), P1 = (1, 2, 2), P2 = (6, 0, 0), P3 = (0, 1, 1). Safe sequence: P1, P3, P0, P2. P1 (1, 2, 2) ≤ (3, 3, 4) → Work = (3+2, 3+0, 4+0) = (5, 3, 4). P3 (0, 1, 1) ≤ (5, 3, 4) → Work = (5+2, 3+1, 4+1) = (7, 4, 5). P0 (7, 4, 3) ≤ (7, 4, 5) → Work = (7, 5, 5). P2 (6, 0, 0) ≤ (7, 5, 5) → Work = (10, 5, 7). All processes finish; the state is safe. Other sequences are possible but this one suffices to demonstrate safety.

Answer 8

A state is safe if there exists at least one sequence in which every process can be run to completion using the currently available resources plus the resources held by processes that have already finished. The sequence is called a safe sequence. When a request would lead to an unsafe state, the algorithm denies the request: the requesting process is told to wait (or is blocked) and retries later. Denying is not the same as failing — the request may be granted later, when other processes have released resources and the state has become safe again. The safety check therefore acts as a gatekeeper: it is conservative (some safe sequences may be missed if the check uses only the immediate available vector) but it never grants a request that could lead to deadlock.

Answer 9

Three reasons:

It requires each process to declare its maximum resource needs in advance. General-purpose processes cannot make such a declaration; their needs depend on input and on run-time decisions.
The safety check runs on every request and is O(n² m) in the number of processes n and resource types m. For a system with thousands of processes and many resource types, this is too expensive to run on every allocation.
It cannot handle dynamic process arrival or resources that appear and disappear. A process that has not yet started cannot declare its maximum, and a resource type added later invalidates the previously computed state.

Answer 10

Avoidance is preventive: the system never enters an unsafe state, so deadlock never occurs. It requires advance knowledge of maximum resource needs and imposes a safety check on every request. Detection is reactive: the system permits deadlock to occur, then periodically (or on demand) runs an algorithm that identifies the deadlocked processes. Detection does not require advance knowledge, but it does require a recovery mechanism (process termination or resource preemption) to restore progress. Detection is appropriate when deadlock is rare and the cost of always avoiding it outweighs the cost of occasional recovery; avoidance is appropriate when the maximum needs can be known and the workload is well-behaved.

Answer 11

The algorithm maintains Work (initially equal to Available) and Finish[i] (initially true for processes with Allocation[i] = 0, false otherwise). It repeatedly finds an i with Finish[i] = false and Request[i] ≤ Work, sets Work = Work + Allocation[i], and sets Finish[i] = true. When no such i remains, the algorithm reports the set of processes with Finish[i] = false. If that set is empty, no deadlock exists. If it is non-empty, those processes are deadlocked — there is no sequence in which they can all finish with the currently available resources. The result is a deadlock set, not necessarily a single cycle; the set may contain several independent deadlocks.

Answer 12

Process termination. Advantage: simple and immediate — killing a process breaks the cycle at once, and the process's resources are released automatically. Disadvantage: partially completed work is lost. If the victim had modified shared data before being killed, the system may need to repair that data. Choosing the victim is also hard: killing all deadlocked processes is wasteful, and killing them one at a time requires re-running detection after each kill. Resource preemption. Advantage: less destructive when the preempted process can be rolled back to a checkpoint; the process retains its identity and resumes later. Disadvantage: requires checkpointing and rollback support, which most general-purpose systems do not have. If the preempted process held a resource in an inconsistent state, that state may be corrupted. Repeated preemption of the same process can cause starvation, so a fairness policy (such as bounding the number of preemptions) is required.

Answer 13

A wait-for graph is a simplified graph in which the nodes are processes and a directed edge from P_i to P_j means "P_i is waiting for a resource held by P_j". It is constructed from the resource allocation graph by removing the resource nodes and replacing each chain P_i → R_a → P_j with a single edge P_i → P_j. Deadlock exists if and only if the wait-for graph contains a cycle. The wait-for graph is the standard representation for detection in database systems and in kernels that maintain explicit dependency information.

Answer 14

The second choice. Each process holds one resource and requests the other; the two requests form a cycle P1 → R2 → P2 → R1 → P1. With single-instance resources, a cycle is a sufficient condition for deadlock. Neither process can proceed, and neither releases what it holds (since there is no preemption in the abstract model). The first choice would be correct only if the system had preemption enabled — but the question describes a state, not a policy.

Answer 15

Assign a unique number to each resource type. Require every process to request resources in strictly increasing order of their numbers. Then a cycle in the wait-for graph is impossible: if P_i waits for a resource held by P_j, the resource held by P_j must have a higher number than the last resource P_i acquired, and P_j must be waiting for a resource with an even higher number. Following the cycle, the resource numbers must strictly increase all the way around and then return to the start — a contradiction. The technique is used in practice: for example, the Linux kernel documents a lock ordering for its major locks, and the POSIX file system imposes an ordering on inode locks. The cost is a discipline on programmers; a resource whose number is not known at design time (such as an anonymous lock allocated at run time) cannot participate.

Answer 16

It breaks circular wait. With at most four philosophers seated, at least one fork is free at all times, so at least one philosopher can always pick up both forks and eat. A circular chain in which every philosopher holds one fork and waits for the other requires all five philosophers to be seated and holding a fork, which is impossible when the semaphore permits only four. The condition that the modification does not break is mutual exclusion (forks are still exclusive) or hold-and-wait (philosophers still hold one fork while waiting for the other). It is the cycle that is broken.

Answer 17

The system should choose the victim whose abort is cheapest and whose rollback is least disruptive. Standard heuristics:

Least work done. Abort the transaction that has performed the fewest operations (or written the fewest rows), so the least work is lost.
Fewest locks held. Abort the transaction holding the fewest resources, so the resources are released quickly.
Least critical. Abort the transaction with the lowest priority or the one whose failure is least harmful to the application.
Avoid starvation. A transaction should not be aborted repeatedly; the system should record how many times each transaction has been aborted and favour those that have been aborted often, to guarantee eventual completion.

In practice, most database systems abort the youngest transaction or the one with the fewest modifications. The choice matters both for throughput and for fairness.

Answer 18

A safe sequence is an ordering of the processes such that, for each process in the sequence, its remaining need can be satisfied by the currently available resources plus the resources held by all processes earlier in the sequence. To construct it: start with Work = Available. Repeatedly find a process whose Need vector is ≤ Work, mark it as finished, and add its Allocation to Work. Continue until either all processes are finished (the state is safe, and the sequence in which they were finished is a safe sequence) or no process can be found (the state is unsafe). The order of selection among eligible processes does not matter for the existence test, but different choices produce different safe sequences; any one is sufficient to demonstrate safety.

Answer 19

With multiple instances of a resource type, a request edge from a process to a resource type indicates that the process is waiting for any instance of that type, not for a specific instance. If another process in the cycle holds an instance that matches the request, the request can be satisfied and the cycle is broken.

Answer 20

Not necessarily. If P2 is waiting for the instance R1a, and P1 holds R1a, the request cannot be satisfied (P1 will not release it while waiting for R2), so P2 is blocked. But P1 is waiting for R2, which is held by P2. Both are blocked — this particular assignment is deadlocked. However, if P1 held R1a and the other instance R1b were free, P2's request for R1 could be satisfied by R1b; the cycle in the graph would exist but there would be no deadlock. The cycle is necessary but not sufficient. This is why detection for multiple instances requires the Banker's-style reduction rather than simple cycle detection.

Answer 21

n is the number of processes and m is the number of resource types. The safety check makes at most n passes over the process set, and each pass compares an m-element Need vector to the Work vector. The number of passes is bounded by n, so the total work is O(n² m). For a system with 1,000 processes and 100 resource types, this is 10⁸ comparisons per safety check — far too expensive to run on every resource request. This is one of the reasons general-purpose systems do not use Banker's algorithm.

Answer 22

Because avoidance requires advance knowledge of each process's maximum resource needs, which such a system cannot provide, and because the safety check is expensive to run on every request. Detection does not require advance knowledge: the system runs its detection algorithm periodically (or when it observes a long idle period), finds any deadlocks that have actually occurred, and recovers from them. The cost is paid only when deadlock is suspected, and the algorithm is O(n²) but only runs occasionally. The trade-off is that some work is lost during recovery, but for systems where deadlock is rare and the workload is unpredictable, this is cheaper overall than avoidance.

Answer 23

lockdep is a runtime lock validator built into the Linux kernel. It records the order in which locks are acquired and released, and it maintains a graph of lock dependencies. If it observes that two locks have been acquired in opposite orders by different code paths (a cycle in the dependency graph), it reports a lock-order inversion — the classic precondition for deadlock. It also detects other lock-related bugs: releasing a lock not held, sleeping while holding a spinlock, and acquiring the same lock twice. lockdep is a dynamic analyser: it catches what actually happens during the kernel's execution, including rare code paths that static analysis might miss. It is enabled only in debug kernels because its bookkeeping is expensive.

Answer 24

Each strategy attacks the problem at a different point in the timeline: prevention removes one of the four necessary conditions at design time, avoidance refuses to grant requests that would lead to an unsafe state, detection permits deadlock and identifies it after the fact, and recovery restores progress by terminating or preempting a victim. The choice among them is a trade-off between the cost imposed on every request and the cost of recovery when a deadlock actually occurs, and it depends on whether the workload's resource needs can be known in advance.

Unit 7 Self-Check Quiz

Multiple choice and short answer

Ready for the graded quiz?