Lock, deadlock; deadlock avoidance

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).

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.