Two-Phase Locking and Deadlock

Running transactions one at a time is obviously correct and unusably slow. Running them concurrently is fast and, without care, wrong. The standard of correctness is conflict serialisability: the interleaved schedule must produce the same result as *some* serial order of the same transactions.

Two operations conflict when they touch the same item and at least one is a write. 2PL is the classic protocol for guaranteeing serialisability without knowing anything in advance about what the transactions will do.

Growing phase

The transaction may acquire locks. It may not release any.

Shrinking phase

Begins at the first release. From then on the transaction may release locks but may never acquire another.

Lock point

The instant the last lock is acquired — the boundary between the phases. Ordering transactions by lock point gives the serial order the schedule is equivalent to, which is the proof that 2PL works.

Strict 2PL

What real databases run: hold every exclusive lock until commit or abort. This additionally prevents cascading rollback, because nobody can read a value that later gets undone.

The rule that causes deadlock is the same rule that makes 2PL correct. A blocked transaction cannot politely release what it holds, because releasing would end its growing phase and it still needs more locks.

Nothing here breaks the protocol. Both transactions are in their growing phase, both took locks they were entitled to, and the result is that neither can proceed. 2PL guarantees serialisability and says nothing at all about deadlock — the two are separate problems with separate solutions.

• Detection. Maintain a wait-for graph and look for a cycle. On finding one, abort a victim — usually whichever has done least work — and restart it. This is what most databases do.
• Timeout. Assume anything waiting too long is deadlocked. Cheap, and wrong often enough to be annoying.
• Prevention by ordering. Require every transaction to lock items in a fixed global order. No cycle can form, but it demands knowing the whole access set up front.
• Prevention by timestamps. Wait-die and wound-wait use transaction age to decide who waits and who dies, guaranteeing no cycle without any graph search.