Locking, Two-Phase Locking and Deadlocks

Coordinating access with locks

Lock-based concurrency control makes transactions acquire locks before accessing data. A shared (S) lock allows reading and is compatible with other shared locks; an exclusive (X) lock allows writing and conflicts with all other locks. Two-phase locking (2PL) requires each transaction to have a growing phase (acquiring locks, never releasing) followed by a shrinking phase (releasing, never acquiring); 2PL guarantees conflict serializability. Strict 2PL holds all exclusive locks until commit or abort, preventing cascading aborts; rigorous 2PL holds all locks until the end. Locks can cause deadlocks, where transactions wait for each other in a cycle. Systems handle them by detection (build a wait-for graph, find a cycle and abort a victim), timeouts, or prevention using timestamps: in wait-die, an older transaction may wait for a younger one, but a younger requester is aborted (dies); in wound-wait, an older requester aborts (wounds) the younger holder, while a younger requester waits. Real databases also use lock granularity (row, page, table) and intention locks.

A deadlock cycle

Each transaction holds a lock the other needs, so both wait forever unless one is aborted.

How a deadlock happens

Two transfers lock the same accounts in opposite orders.

time  T1 (transfer A -> B)          T2 (transfer B -> A)
----  ----------------------------  ----------------------------
t1    X-lock(A)  granted
t2                                  X-lock(B)  granted
t3    X-lock(B)  waits for T2
t4                                  X-lock(A)  waits for T1
      wait-for graph: T1 -> T2 -> T1   (cycle = deadlock)
      DBMS aborts one (the victim); the application should retry it

prevention in code: always lock accounts in a fixed order (e.g. by account number)

Lock in a consistent order

Most application deadlocks disappear when every transaction locks rows in the same order, such as ascending primary key. Still, write code that retries transactions aborted as deadlock victims.

Quick check: Which variant of two-phase locking prevents cascading aborts by holding exclusive locks until commit?

• Basic 2PL
• Wait-die
• Strict 2PL
• Optimistic locking