Two-phase locking (2PL) is how a database guarantees concurrent transactions don't corrupt each other's data: shared (S) locks allow concurrent readers, exclusive (X) locks are required to write and conflict with everything else. When a transaction can't get a lock immediately, it has to wait -- and if transactions end up waiting on each other in a cycle, none of them can ever proceed. That's a deadlock, and it's detected by building a "wait-for" graph and checking for cycles.

Implement:

• request_lock(txn_id, resource, mode) -- mode is "S" or "X".
  • If resource is currently unlocked: grant it immediately (record txn_id as the sole holder, in that mode), return True.
  • If txn_id already holds a lock on resource in the SAME mode: return True (no-op, already compatible).
  • If mode is "S" and the resource's current mode is also "S": add txn_id as another holder (shared locks from different transactions are always compatible), return True.
  • Otherwise, it's a conflict: record a wait-for edge from txn_id to every OTHER current holder of resource, and return False.
• has_deadlock(txn_id) -- is there a cycle in the wait-for graph reachable by following edges starting from txn_id?
• release_lock(txn_id, resource) -- a lock manager that can never give a lock back isn't complete: a real transaction eventually commits or aborts and releases everything it held. Remove txn_id from resource's holders. If that empties the holder set, the resource is fully unlocked (reset its mode) so a future request of ANY mode can be granted outright. Releasing one of several shared holders must NOT unlock the resource for the remaining holder(s).

Example

lm = LockManager()
lm.request_lock("t1", "row1", "X")   # granted
lm.request_lock("t2", "row2", "X")   # granted
lm.request_lock("t2", "row1", "X")   # conflicts -- t2 waits on t1
lm.has_deadlock("t1")                # -> False (no cycle yet)
lm.request_lock("t1", "row2", "X")   # conflicts -- t1 waits on t2 -- CYCLE
lm.has_deadlock("t1")                # -> True
lm.release_lock("t1", "row1")        # t1 gives up row1 (e.g. aborted as the victim)

Constraints

• A deadlock check must follow the wait-for graph transitively (through however many transactions), not just check direct neighbors -- see the 3-transaction cycle test.
• Guard against infinite looping on a cycle during the deadlock check itself (track visited nodes).
• release_lock on a resource that was never locked (or that txn_id never held) must be a no-op, not an error.
• release_lock does not need to retroactively clean up wait_for edges that referenced the releasing transaction -- a real deadlock detector periodically rebuilds its wait-for graph from current lock state rather than patching it incrementally, and this exercise's has_deadlock models that same simplification.

Real-world grounding

• Postgres's deadlock detector (wait-for graph cycle detection, exactly this technique): src/backend/storage/lmgr/deadlock.c

Real lock managers additionally choose a "victim" transaction to abort once a deadlock is detected (usually the one that's done the least work, to minimize wasted effort) and support lock upgrades (a transaction holding S requesting X on the same resource) -- this exercise focuses on the detection mechanism itself, which is the same either way.