Locking: Shared, Exclusive, and Deadlock

Snapshots let readers avoid waiting for writers, but two transactions that want to write the same thing must take turns, and a database that runs on locks makes everything take turns. A lock manager is the component that decides who may touch a resource now, who must wait, and what to do when the waiting goes in a circle.

Two modes

A lock is held in one of two modes:

• Shared (S): "I am reading this; nobody may change it meanwhile." Any number of transactions can hold S on a resource at once.
• Exclusive (X): "I am changing this; nobody else may read or write it." Only one transaction can hold X, and nobody may hold S alongside it.

Two modes conflict unless both are S. That one rule is the whole compatibility matrix:

A request that cannot be granted does not fail: it waits in a queue for that resource, and the transaction is blocked until the lock manager grants it.

The queue must be fair

Imagine three transactions holding S on a table and a fourth waiting for X. Now a fifth asks for S. It is compatible with the current holders, so it could be granted at once. But if new readers keep slipping in ahead of the writer, the writer waits forever (starvation). The standard fix, and the rule here: a new request is granted immediately only if the queue is empty and its mode is compatible with the holders. Otherwise it joins the back of the queue.

When a lock is released, the manager grants from the front of the queue for as long as the front request is compatible: one X waiter takes the lock alone; a run of S waiters is granted together; and it never skips over a blocked request to reach a later one.

holders: t1(S)        queue: t2:X, t3:S, t4:S
t1 releases   ->  t2 gets X.   t3 and t4 still wait behind it
t2 releases   ->  t3 and t4 both get S at once

Upgrades

A transaction that holds S and now wants X is upgrading. If it is the only holder, it simply becomes X. If others also hold S it must wait for them to leave, and it goes to the front of the queue: it already holds a lock, so it should not queue behind newcomers. Asking again for a mode you already cover (S when you hold S or X, X when you hold X) just keeps what you have.

Deadlock

t1 holds A, wants B (held by t2)  ->  t1 waits for t2
t2 holds B, wants A (held by t1)  ->  t2 waits for t1

Neither can ever proceed. Waiting forever is not an option, so the manager keeps a wait-for graph: an edge from each blocked transaction to every transaction it is waiting for. A transaction is waiting for the holders whose mode conflicts with its request, and also for the conflicting requests queued ahead of it. A cycle in this graph is a deadlock.

A cycle can only form at the moment a request starts to wait, so the manager checks right then: starting from the transaction that just queued, follow edges and see whether the walk returns to it. If it does, someone must be sacrificed. The simplest policy, used here, makes the requester the victim: its queued request is dropped and all its locks are released, which usually lets the others continue. A real system would then abort that transaction and let the application retry it.

Upgrades deadlock too: two transactions both hold S and both ask for X; each waits for the other to let go. Same detection, same cure.

Commands

LOCK <txn> <resource> S|X prints GRANTED ..., WAIT ... blocked-by=<txns> or DEADLOCK <txn> released=<n>. UNLOCK <txn> <resource> releases one lock. RELEASE <txn> drops everything a transaction holds or waits for (what happens at commit or abort). Each release prints UNBLOCKED <txn> <resource> <mode> for every waiter it lets through, resources in sorted name order. STATUS <resource> shows mode, holders and queue.

Common mistakes

• Granting a new reader past a waiting writer. Starvation.
• Letting a blocked upgrade queue at the back. It then deadlocks with newcomers it should have outranked.
• Forgetting the queue in the wait-for graph. A request also waits on conflicting requests ahead of it, not only on holders.
• Skipping the front of the queue when it cannot be granted but a later request could.

Your exercise

The starter parses and prints. You implement request, blocked_by, grant_waiters and deadlocked. The mistake to avoid: checking only the holders and never the queue.