Practice · Deadlocks: Prevention, Avoidance, Detection and Recovery

Q1

Which of the following is not one of the four necessary conditions for deadlock?

A Hold and wait B Preemption C Mutual exclusion D Circular wait

Q2

A resource-allocation graph contains a cycle, and every resource type has exactly one instance. What can you conclude?

A There may or may not be a deadlock. B The graph is invalid. C There is a deadlock. D There is no deadlock.

Q3

A resource-allocation graph contains a cycle, but one resource type in the cycle has two instances, and the second instance is held by a process outside the cycle that is not waiting for anything. What can you conclude?

A Livelock. B Starvation. C Deadlock, certainly. D No deadlock: the outside process will finish and release its instance, breaking the cycle.

Q4

Requiring every process to request all its resources at once before starting prevents deadlock by breaking which condition?

A No preemption B Hold and wait C Circular wait D Mutual exclusion

Q5

A team decides: "every thread must acquire locks in increasing order of lock ID". Which condition does this break?

A No preemption B Hold and wait C Circular wait D Mutual exclusion

Q6

Why do Linux and Windows mostly ignore deadlocks among user processes (the "ostrich approach")?

A Because they are rare and prevention/avoidance would be costly and restrictive for all programs; applications handle them B Because deadlocks cannot happen in modern OSs C Because deadlocks only occur in databases D Because the Banker's algorithm is patented

Q7

In the Banker's algorithm, how is the Need matrix computed?

A Need = Allocation − Max B Need = Available − Allocation C Need = Max + Allocation D Need = Max − Allocation

Q8

Which statement about safe and unsafe states is correct?

A An unsafe state is always a deadlock. B A safe state may contain a deadlock. C A safe state guarantees that deadlock can be avoided; an unsafe state means deadlock is possible but not certain. D Safety depends only on Available.

Q9

EdgeCampus state (resources GPU, CPU, MEM): Available = (2, 3, 4); Need P0 = (3 3 6), P1 = (1 3 4), P2 = (2 1 6), P3 = (2 3 4); Allocation P0 = (1 1 2), P1 = (1 0 2), P2 = (1 1 2), P3 = (0 2 0). Scanning P0…P3 in passes, what safe sequence do you find?

A The state is unsafe. B P1, P2, P3, P0 C P3, P2, P1, P0 D P0, P1, P2, P3

Q10

Same EdgeCampus state. P0 requests (1 1 2), which is currently available. What does the Banker's algorithm do?

A Makes P0 wait: after the allocation Available would be (1 2 2) and no process's need would fit — unsafe. B Reports an error: P0 exceeds its maximum. C Grants it, because the resources are available. D Aborts P0.

Q11

Process P3 has Max = (2 2 2) and Allocation = (2 1 1). It requests (1 0 0). What happens?

A Deadlock detected B Granted C Error: the request exceeds its declared maximum claim (Need = (0 1 1)) D Wait

Q12

Why is the Banker's algorithm rarely used directly in general-purpose operating systems?

A It causes deadlocks. B It only works with one resource type. C Processes rarely know their maximum demands in advance, the number of processes changes constantly, and it costs O(m·n²) per request. D It is incorrect.

Q13

Three processes share 4 identical GPU slots; each process needs at most 2 slots at a time, and holds slots while waiting for more. Can a deadlock occur?

A Only with preemption B Yes, if all request at once C Yes, always D No: even if each holds 1 slot, one slot is still free, so some process can get its second slot, finish and release

Q14

With the detection algorithm (current Request instead of Need), a process that holds no resources is marked finished at the start. Why?

A Because it has already terminated B Because it is a system process C To make the algorithm faster only D Because a process holding nothing cannot be part of a cycle of waiting (nobody waits for it)

Q15

A database finds a deadlock between transactions T1 (running for 2 s, updated 3 rows) and T2 (running for 40 s, updated 5,000 rows). Which victim is usually chosen?

A T1: rolling it back loses the least work B T2: it is older C Both D Neither; the database waits

Q16

Two threads repeatedly detect a conflict, both release their locks, wait the same fixed time and retry — forever. What is this, and a fix?

A Deadlock; reboot B Starvation; use aging C Priority inversion; use priority inheritance D Livelock; use randomized (and growing) back-off before retrying

Q17

A high-priority task waits for a lock held by a low-priority task, which is preempted by a medium-priority task. Is this a deadlock?

A Yes, a circular wait B No, it is priority inversion: the system still makes progress, and the lock will be released once the low-priority task runs C No, it is livelock D Yes, because of mutual exclusion

Q18

Two 6-GPU training jobs are scheduled pod-by-pod on an 8-GPU cluster, alternating pods. What happens, and which technique prevents it?

A Both run on 4 GPUs each; nothing is needed B The cluster adds GPUs C Each gets 4 GPUs and waits forever for 2 more — deadlock; gang (all-or-nothing) scheduling prevents it D The first job preempts the second automatically

Q19

Why do distributed systems often prefer timeouts and leases to exact deadlock detection?

A Timeouts are more accurate. B No node has a consistent global view of the wait-for graph; delayed messages cause phantom deadlocks, while leases bound the waiting simply and also handle crashed nodes. C Deadlocks cannot happen in distributed systems. D Leases are required by law.

Q20

In a wait-for graph, the edge P1 → P2 means:

A P1 waits for a resource currently held by P2 B P1 holds a resource that P2 wants C P1 created P2 D P1 and P2 share memory

Q21

Which Java practice most directly prevents lock-ordering deadlocks between transfer(a, b) and transfer(b, a)?

A Making the method static B Locking the two accounts in a fixed global order (for example by account ID), independent of the transfer direction C Using volatile balances D Calling Thread.yield()

Q22

Backfilling in a gang scheduler means:

A Restarting failed jobs B Filling GPUs with zeros C Letting smaller jobs use GPUs that are idle while a large job waits for enough GPUs, as long as they do not delay it (or finish in time) D Allocating GPUs pod by pod

Q23

Detection algorithm with Available = (0 0 0). Allocation: P0 = (0 1 0), P1 = (2 0 0), P2 = (3 0 3), P3 = (2 1 1), P4 = (0 0 2). Request: P0 = (0 0 0), P1 = (2 0 2), P2 = (0 0 1), P3 = (1 0 0), P4 = (0 0 2). Which processes are deadlocked?

A P1, P2, P3 and P4 B None C Only P2 D All five

Q24

After detecting a deadlock, a system always chooses the same low-priority batch job as the victim. What problem does this create?

A Starvation of that job — it may never complete B A new deadlock C Priority inversion D Livelock

Q25

Five processes share R identical units; each needs at most 3 units at a time. What is the smallest R that guarantees no deadlock?

A 5 B 11 C 15 D 10

Q26

When is running the deadlock detection algorithm after every blocked request a reasonable choice?

A When deadlocks are frequent and must be resolved immediately, and the graph is small enough to check cheaply (e.g., database lock managers) B Only when the CPU is idle C Never D Always; its cost is negligible

Q27

A training job is chosen as a deadlock victim. What makes rollback much cheaper than a full restart?

A Deleting its data B Running it on a faster GPU C Increasing its priority D Periodic checkpoints: the job restarts from its last saved state instead of from the beginning

Q28 Short answer

Apply the Banker's algorithm to the classic state: resources A, B, C; Available = (3 3 2); Max: P0 (7 5 3), P1 (3 2 2), P2 (9 0 2), P3 (2 2 2), P4 (4 3 3); Allocation: P0 (0 1 0), P1 (2 0 0), P2 (3 0 2), P3 (2 1 1), P4 (0 0 2). (a) Compute Need. (b) Find a safe sequence (scan P0…P4 in passes). (c) P1 requests (1 0 2): grant? (d) Then P0 requests (0 2 0): grant?

Q29 Short answer

For each technique, say which deadlock condition it attacks and give one practical drawback: (a) spooling printer jobs; (b) acquiring all locks at the start of a transaction; (c) taking the CPU away from a process; (d) global lock ordering; (e) gang scheduling of GPU jobs.

Q30 Short answer

A Java service hangs. jstack <pid> prints: "Found one Java-level deadlock: Thread-A waiting to lock <0x1> (Order) which is held by Thread-B; Thread-B waiting to lock <0x2> (Inventory) which is held by Thread-A." Draw the wait-for graph, explain how the deadlock arose, and propose two fixes.