Deadlocks & Classical Problems

1. What is a deadlock?

A deadlock is a state where every process in a set is waiting for an event that only another process in the set can cause. In practice: process A holds resource 1 and waits for resource 2, while process B holds resource 2 and waits for resource 1. Neither can proceed, so the whole set is stuck forever.

The key insight is that each process is blocked, and the blocking forms a cycle. Nothing will change unless the system intervenes, because the only process that could release a needed resource is itself waiting on another.

2. What are the four necessary conditions for deadlock?

All four must hold simultaneously for a deadlock to occur (the Coffman conditions):

• Mutual exclusion — resources are non-sharable; only one process can use a resource at a time.
• Hold and wait — a process holds at least one resource while waiting for additional resources.
• No preemption — resources cannot be forcibly taken from a process; they are released only voluntarily.
• Circular wait — there is a cycle in the resource-allocation graph, where each process waits for a resource held by the next.

If any one of these is absent, deadlock cannot occur. This is exactly what prevention exploits.

3. What is the difference between deadlock prevention and avoidance?

Prevention is static — it ensures, by design, that at least one of the four conditions can never hold. For example, impose a total ordering on resources (request resource 1 before resource 2) to break circular wait, or require processes to request all resources up front to break hold-and-wait. Prevention can cause low resource utilization because processes hold resources longer than needed.

Avoidance is dynamic — it allows requests but checks, before granting, whether the grant could lead to an unsafe state, using the Banker’s Algorithm. Avoidance requires advance knowledge of each process’s maximum resource needs. The trade-off: prevention is simpler but wasteful; avoidance is efficient but needs the maximum-need information that real systems often can’t provide.

4. What is a safe state?

A state is safe if there exists a sequence of process executions that allows all processes to complete without deadlocking. The system checks: can we find a process whose remaining needs are satisfiable with available resources? If so, assume it completes and returns its resources, then repeat. If every process can eventually complete in some order, the state is safe.

An unsafe state may — but doesn’t necessarily — lead to deadlock. Avoidance algorithms refuse to grant a request that would move the system into an unsafe state, because from an unsafe state a bad sequence of future requests could cause deadlock.

5. How does the Banker’s Algorithm work?

The Banker’s Algorithm is a deadlock-avoidance algorithm. For each process, it knows the allocation (resources currently held) and the maximum (resources it may ever request); need = max − allocation. Available tracks what’s free.

When a request comes in, the algorithm simulates granting it, then checks: find a process whose need ≤ available. Assume it finishes — available += its allocation. Repeat. If all processes can finish in some order, the grant is safe and is allowed; otherwise the request is refused and the process must wait. It’s named after a banker who won’t approve a loan that could leave the bank insolvent.

6. What is a resource allocation graph and how do you detect a deadlock with it?

A resource allocation graph is a directed graph: circles are processes, squares are resources (with dots inside representing instances). An edge from a process to a resource is a request; an edge from a resource to a process is an assignment.

If the graph contains a cycle, there is a deadlock — provided each resource type has only one instance. With multiple instances per resource type, a cycle is necessary but not sufficient for deadlock, so detection must use the Banker’s-style algorithm instead.

7. How does an OS detect and recover from a deadlock?

Detection: build a wait-for graph — a variant where edges show which process is waiting for a resource held by another — and check for cycles. If a cycle exists, there’s a deadlock.

Recovery options:

• Kill all deadlocked processes — drastic but simple.
• Kill one process at a time, re-checking until the cycle breaks.
• Preempt resources from a process and give them to others — this may require rolling the process back to a safe checkpoint.

The trade-off is between the cost of the detection algorithm and the cost of the disruption.

8. What is the ostrich algorithm?

The ostrich algorithm is simply to ignore the problem — stick your head in the sand and pretend deadlocks don’t happen. Most desktop operating systems use it.

The reasoning is economic: real deadlocks are rare enough, and the overhead of prevention or avoidance is significant enough, that it’s cheaper to let a rare deadlock occur and reboot than to constantly pay the cost of guaranteeing it can’t happen. The assumption breaks down in safety-critical or high-availability systems, where deadlock prevention is non-negotiable.

9. How do you prevent deadlock by breaking each condition?

• Mutual exclusion — make resources sharable where possible. Hard in general (printers, files, mutexes are inherently exclusive).
• Hold and wait — require processes to request all resources before they begin, or to release everything before requesting more. Guarantees a process never waits while holding, but causes low utilization.
• No preemption — allow resources to be preempted: take a resource from a waiting process and give it to another, then return it later. Works but can be hard for stateful resources.
• Circular wait — impose a total order on resource types and require every process to request resources in that order. If a process holds resource i, it can only request resources with index > i, so no cycle can form.

Prevention breaks one condition at design time, which is why it’s called static.

10. How do semaphores solve the Producer-Consumer problem?

The Producer-Consumer (bounded buffer) problem needs three semaphores: empty (initialized to buffer size N — counts empty slots, the producer waits on it), full (initialized to 0 — counts filled slots, the consumer waits on it), and mutex (binary — protects the buffer from simultaneous modification).

The producer does wait(empty), wait(mutex), adds to the buffer, signal(mutex), signal(full). The consumer does wait(full), wait(mutex), removes from the buffer, signal(mutex), signal(empty). The empty/full pair ensures the producer can’t overflow a full buffer and the consumer can’t underflow an empty one; the mutex ensures they never modify the buffer simultaneously.

11. How does the Readers-Writers problem work?

Multiple readers can read shared data simultaneously, but only one writer may write, and no reader may read while a writer writes. A read_count variable tracks active readers, protected by its own mutex.

In the reader-preference variant, readers can keep entering as long as no writer is active — writer starvation is possible because readers never wait for each other. In the writer-preference variant, once a writer is ready, no new readers can start; existing readers finish, then the writer proceeds. The first reader acquires the shared lock and subsequent readers just increment the counter; the last reader releases the lock.

12. What is the Dining Philosophers problem and how do you avoid deadlock?

Five philosophers sit around a table with a chopstick between each pair — five chopsticks total. Each philosopher needs both the left and right chopstick to eat. If all five pick up their left chopstick at once, all five wait forever for the right one: classic deadlock.

Solutions:

• Allow only four philosophers at the table — this prevents circular wait because there are never five processes each holding one fork.
• Pick up both chopsticks only if both are available (atomic acquisition).
• Asymmetric ordering: odd philosophers pick up the left fork first, even ones pick up the right fork first. The last philosopher can never complete the cycle.

The problem is a direct application of the four conditions: the deadlock scenario is circular wait, and the solutions break that condition.

13. What is a condition variable and why do you need one?

A condition variable lets a thread wait until a specific predicate becomes true — “wait until the queue is non-empty” — rather than polling. A semaphore signals “a resource is available”; a condition variable signals “the state you’re waiting for might have changed — go check.”

The key operations are wait(cv, mutex) which atomically releases the mutex and sleeps, signal(cv) which wakes one waiter, and broadcast(cv) which wakes all. Condition variables exist because semaphores can’t directly express waiting for an arbitrary condition — without one you’d be stuck busy-waiting in a loop.

14. Why must you always use a while loop with a condition variable?

Because of spurious wakeups and lost wakeups. wait() can return without any signal having occurred, and even after a real signal, another thread might have consumed the condition between the signal and this thread’s wakeup.

So the correct pattern is always while (!predicate) cond_wait(cv, mtx); — re-check the predicate after every wakeup — never if. This is the consequence of Mesa semantics: the signaller continues running, so by the time the woken thread runs, the condition may no longer hold.

15. What is the difference between Mesa and Hoare semantics?

In Hoare semantics, when signal() is called the signaller immediately blocks and the woken thread runs right away — so the condition is guaranteed when the woken thread executes, and it doesn’t need to re-check (an if suffices).

In Mesa semantics, the signaller continues running after signaling, and the woken thread is only moved to the ready queue — it may not run until later, by which time another thread may have consumed the condition. Therefore the waiter must re-check the predicate in a while loop. All real systems — pthreads, Java, C++, Windows — use Mesa semantics.

16. What is the difference between thread-safe and reentrant?

A function is thread-safe if it works correctly when called concurrently by multiple threads — usually by using a mutex or atomic operations to protect shared state. A function is reentrant if it can be interrupted (e.g., by a signal handler) and called again before the first invocation finishes — this requires using only local variables, never locks, and never shared state.

A reentrant function is always thread-safe (there’s no shared state to protect), but a thread-safe function is not necessarily reentrant: it might hold a mutex and deadlock if re-entered from a signal handler. The example is strtok() (not thread-safe, uses internal static state) vs strtok_r() (reentrant — the caller passes the state).

17. How does Thread-Local Storage (TLS) help with thread safety?

TLS gives each thread its own copy of a variable — the OS or compiler maps the TLS variable to a different memory address for different threads. Since there’s no shared state at all, no synchronization is needed.

In C/C++ this is the __thread keyword; Java and Go have similar mechanisms. TLS is the cleanest way to make per-thread state safe: instead of guarding a global with a mutex, each thread just gets its own private copy, which also eliminates contention entirely.

18. What happens when a non-reentrant function is called from a signal handler?

Undefined behavior — corruption, crash, or deadlock. If a signal handler interrupts a program while it is executing the same function (for example, malloc or printf), and the handler calls it again, the internal state is clobbered.

This is why signal handlers must only call async-signal-safe functions — a small, documented set that includes write, _exit, and sigaction. The rule flows directly from the definition of reentrancy: a reentrant function can be safely re-entered, so it’s the only kind safe to call from a handler.

19. What is the difference between deadlock, starvation, and livelock?

Three different ways concurrent systems can get stuck:

• Deadlock — processes are permanently blocked, each holding a resource and waiting for a resource another holds (a circular wait). No process can make progress; the set is stuck forever unless the OS intervenes.
• Starvation — a process is not blocked, but it never gets scheduled. It remains ready but is perpetually passed over because higher-priority jobs keep arriving (e.g. a low-priority process under priority scheduling, or the job at the far end of disk in SSTF).
• Livelock — processes are actively running but making no progress. They keep changing state and responding to each other, but the system never advances — like two people who keep stepping aside for each other in a hallway and never get past.

The key distinctions:

	Blocked?	Progress?	Cause
Deadlock	Yes	None, permanently	Circular wait on held resources
Starvation	No (ready)	Never scheduled	Scheduler keeps choosing others
Livelock	No (running)	None	Processes busy-respond to each other

Deadlock is blocked and stuck; starvation is ready but never chosen; livelock is running but accomplishing nothing. Starvation is fixed with aging; deadlock with prevention/avoidance/detection; livelock by adding randomization or changing the retry strategy.