--- title: "Lock, deadlock; deadlock avoidance" subject: "Distributed System" chapter: 8 key: "semester_7/distributed_system:lock-deadlock-avoidance" source: https://www.bctengineer.com/q/semester_7/distributed_system/lock-deadlock-avoidance site: BCT Engineering --- # Lock, deadlock; deadlock avoidance Distributed System · Chapter 8: Transaction and Concurrency Control - Asked in: 2073 Shrawan, 4+6 marks - Video: [Distributed Deadlocks | Deadlocks Prevention |](https://www.youtube.com/watch?v=N28knQu44eA) — EG2Study (Adhikari Sir) - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/distributed_system/lock-deadlock-avoidance - Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-8 ## Question What is LOCK and DEADLOCK in DS? Discuss the methods of distributed deadlock avoidance. ## Short answer A lock controls concurrent access; strict 2PL holds write locks until commit. Deadlock is a wait-for cycle; distributed deadlock involves multiple servers. Avoidance: acquire all locks atomically, impose global resource ordering, use lock timeouts, or apply timestamp-based wait-die (abort younger requester) or wound-wait (preempt younger holder) to ensure waits go one direction. Timestamp ordering and optimistic schemes avoid locks entirely. ## Answer #### Lock A **lock** is a variable associated with a data item that controls concurrent access. A transaction must obtain the lock before it reads or writes the item, and releases it when finished. Common modes are **read (shared) lock** and **write (exclusive) lock**; several transactions can hold read locks together, but a write lock excludes all others. In **two-phase locking (2PL)** a transaction has a growing phase (acquires locks) followed by a shrinking phase (releases locks, never acquires again). **Strict 2PL** holds all locks until commit or abort, which prevents dirty reads and cascading aborts. #### Deadlock in a distributed system A **deadlock** is a state in which each transaction in a set is waiting for a lock held by another transaction in the set, so none can proceed. It is shown by a cycle in the **wait-for graph** (nodes are transactions, an edge T → U means T waits for U). A **distributed deadlock** occurs when the wait-for cycle spans several servers. Each server sees only a part of the graph (a local wait-for graph without a local cycle), but the global graph has a cycle. Example: T holds a lock on A at server X, and U holds a lock on B at server Y. T now requests B at Y (so T waits for U), and U requests A at X (so U waits for T). ```text Server X: U -> T (U waits for T on A) Server Y: T -> U (T waits for U on B) Global: T -> U -> T (cycle = deadlock) ``` #### Methods of avoiding distributed deadlock Deadlock can be prevented by breaking one of its necessary conditions (mutual exclusion, hold and wait, no pre-emption, circular wait). 1. **Lock all objects at the start (no hold and wait)**: a transaction acquires all its locks at the start in one atomic step. It is simple but wastes concurrency, and the required objects are often not known in advance. 2. **Ordering of resources (no circular wait)**: lock objects in a fixed global order. A transaction cannot request an earlier object while holding a later one. This is hard to apply across many servers. 3. **Timeouts**: a lock is valid for a limited time. After the time limit, the lock is *vulnerable*; if another transaction wants it, the holder is aborted. Easy, but it aborts transactions that were only slow, and the timeout value is hard to choose. 4. **Timestamp-based prevention** (each transaction has a unique timestamp, older = smaller): - **Wait-die** (non-pre-emptive): if the requester is older than the holder, it waits; if younger, it dies (aborts and restarts with the same timestamp). - **Wound-wait** (pre-emptive): if the requester is older, it wounds (aborts) the holder; if younger, it waits. In both, waiting goes in only one direction (by age), so no cycle can form, and there is no starvation because a restarted transaction keeps its original timestamp. 5. **Optimistic or timestamp ordering concurrency control**: no locks, so no deadlock. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which lock combination is allowed on the same object? A. Two read locks B. A read and a write lock C. Two write locks D. A write lock and another write lock Answer: A. Read (shared) locks are compatible; a write lock excludes all others. (Key point: Lock modes) 2. What does an edge T -> U in the wait-for graph mean? A. T waits for a lock held by U B. U waits for T C. T committed before U D. T is older than U Answer: A. Edges point from the waiting transaction to the holder; a cycle means deadlock. (Key point: Wait-for graph) 3. What condition does locking all objects at the start eliminate, and what is its drawback? A. Hold and wait; it wastes concurrency and needs objects known in advance B. Circular wait; it needs a global clock C. Mutual exclusion; it needs logs D. No pre-emption; it causes phantom deadlocks Answer: A. Acquiring everything atomically means no holding while waiting, but reduces concurrency. (Key point: Lock all at start) 4. What is a drawback of lock timeouts? A. They may abort transactions that were merely slow, and the timeout is hard to choose B. They cause deadlocks C. They require wait-for graphs D. They need timestamps Answer: A. A vulnerable lock can be broken even though no deadlock exists. (Key point: Timeouts) ## Related in Distributed System - [Lock; distributed CC; deadlock situation](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alock-cc-deadlock-situation) — Distributed System, chapter 8 - [Distributed deadlock and recovery](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Adistributed-deadlock-note) — Distributed System, chapter 8, asked 3× - [Distributed deadlock; two-phase commit](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Adistributed-deadlock-2pc) — Distributed System, chapter 8 - [Approaches to avoid distributed deadlock](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Adeadlock-avoidance-approaches) — Distributed System, chapter 8 - [Define DS and its requirements](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Adefine-ds-requirements) — Distributed System, chapter 1, asked 3× ## Related in other subjects - [Deadlock occurrence and avoidance methods](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-avoidance-methods-examples) — Operating System, chapter 7 - [Avoidance, detection, prevention techniques](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-avoidance-detection-prevention) — Operating System, chapter 7