Deadlock interview questions, with answers

The questions, with answers

1. 1.What is a deadlock in an operating system?

   In short: A set of processes each waiting for a resource held by another process in the set, so none can ever proceed.

   A deadlock is a state in which every process in a set is blocked, waiting for an event, usually the release of a resource, that only another process in the same set can cause. Since all of them are waiting, none ever releases anything, and they stay blocked until something outside intervenes. The simplest example has two processes and two locks: process A holds lock 1 and requests lock 2, while process B holds lock 2 and requests lock 1. Deadlocks involve resources such as locks, devices, memory and database rows.

2. 2.What are the four necessary conditions for a deadlock?

   In short: Mutual exclusion, hold and wait, no preemption and circular wait must all hold at the same time.

   Coffman's four conditions are all required. Mutual exclusion: at least one resource can be held by only one process at a time. Hold and wait: a process holds at least one resource while waiting for others. No preemption: a resource can only be released voluntarily by the process holding it. Circular wait: there is a cycle of processes, each waiting for a resource the next one holds. Because all four are necessary, making any one of them impossible prevents deadlock, which is the basis of every prevention technique.

3. 3.How can deadlocks be prevented?

   In short: By designing the system so one of the four necessary conditions can never hold, most practically circular wait.

   Prevention removes one condition. Mutual exclusion is usually inherent in the resource, so it rarely helps. Hold and wait can be removed by requiring a process to request all its resources at once, or to release everything before requesting more, at the cost of poor utilisation and possible starvation. No preemption can be removed by taking resources back from a waiting process, which only works for resources whose state can be saved, such as CPU registers. Circular wait is removed by ordering all resources and requiring requests in increasing order, the standard technique for locks in real software.

4. 4.What is deadlock avoidance, and how does the banker's algorithm work?

   In short: Avoidance grants a request only if the system stays in a safe state; the banker's algorithm checks this using each process's declared maximum.

   Avoidance requires each process to declare in advance the maximum resources it may need. Before granting a request, the system checks whether the resulting state is safe, meaning there is an order in which every process can obtain its remaining need and finish. The banker's algorithm does the check: it simulates giving the available resources to any process whose remaining need fits, reclaiming that process's allocation when it finishes, and repeats. If every process can finish, the state is safe and the request is granted; otherwise the requester waits. An unsafe state is not yet a deadlock, but it may lead to one.

5. 5.How are deadlocks detected and recovered from?

   In short: Periodically check the allocation and request information for processes that can never finish, then terminate processes or preempt resources.

   Detection lets deadlocks happen and finds them afterwards. The system periodically runs a detection algorithm over what each process holds and requests, looking for processes that can never finish. Recovery then either terminates processes, all of those involved or one at a time until the deadlock breaks, or preempts resources from a victim and rolls it back to a safe point. Choosing the victim considers priority, work done and resources held, and avoiding always choosing the same victim prevents starvation. Databases detect deadlocks this way and abort one transaction.

6. 6.What is the difference between deadlock and starvation?

   In short: Deadlocked processes wait for each other in a cycle and none progresses; a starved process waits indefinitely while others keep progressing.

   In a deadlock, a set of processes is stuck in a circular wait and none of them can ever proceed without outside intervention. Starvation is different: the system as a whole makes progress, but one process is repeatedly passed over, for example a low-priority process under priority scheduling or a writer that never gets a lock because readers keep arriving. Starvation can end on its own if conditions change, and it is fixed with fairness mechanisms such as aging, which raises a waiting process's priority over time. Every deadlocked process is starved, but starvation does not require a deadlock.

7. 7.Why do many operating systems ignore deadlocks?

   In short: Prevention and avoidance are costly and deadlocks are rare, so general-purpose systems leave them to applications: the ostrich approach.

   Prevention restricts how resources can be requested, avoidance needs maximum demands declared in advance and runs checks on every request, and detection adds periodic overhead. For general-purpose systems, where deadlocks among processes are rare and a reboot or a killed process is an acceptable recovery, these costs are not worth paying, so Linux and Windows largely ignore the problem, an approach nicknamed the ostrich algorithm. Deadlock handling moves to where it matters: databases detect and break deadlocks between transactions, and application developers prevent them by ordering their locks.

How the diagnostic asks it

One question from the Operating Systems bank, exactly as a sitting would show it. The bank has 4 on deadlocks and 30 across Operating Systems.