Transactions and Locking: Model Who Can Proceed

A correct recovery routine can still lose committed data if transactions are allowed to overwrite one another's unresolved changes. A correct compatibility matrix can still starve a writer if new readers keep passing it. Transaction isolation requires both a protocol for holding locks and a precise request scheduler.

This lesson follows the WAL module. You will distinguish basic, strict, and rigorous two-phase locking, trace FIFO grants and upgrades, and build the exact wait-for graph of the exercise. The lock-manager problem implements the request scheduler. It deliberately has no transaction commit/abort interface.

Begin with a history that should not be allowed

Let account A initially contain 10:

Step	T1	T2
1	Read A=10
2		Read A=10
3	Write A=11
4		Write A=12
5	Commit	Commit

If T1 means “add 1” and T2 means “add 2,” either serial order should produce 13. The actual interleaving produces 12 because both read the old value. The problem is a lost update, not an arithmetic error.

A transaction that will modify A must acquire exclusive access for that work. If T1 holds X(A), T2 cannot read A under S(A) or write it under X(A) until T1 releases. The second transaction then observes the first transaction's result. Choosing lock scope and lifetime is how the history changes.

Compatibility answers only the local question

For different transactions:

Requested mode	Existing S	Existing X
S	compatible	blocked
X	blocked	blocked

Multiple readers can coexist. An exclusive holder excludes every other reader and writer on that resource. A transaction's own lock is not a blocker: the sole S holder can upgrade to X, and an X holder already has sufficient access for a subsequent S request.

Compatibility says whether a grant is safe at this moment. It does not tell you whether a transaction may acquire another lock after releasing one, whether a new request may bypass an older waiter, or how to resolve a cycle. Those are separate rules that must be made explicit.

Two phases describe a transaction's lifetime

Basic 2PL has a growing phase that may acquire or upgrade locks, followed by a shrinking phase that releases locks. After the first release, no new lock may be acquired. Under correctly scoped locks, this enforces conflict serializability. It does not prevent deadlocks or all exposure of uncommitted writes.

Strict 2PL additionally retains exclusive locks until commit or completed abort. Rigorous / strong strict 2PL retains both shared and exclusive locks until transaction completion. Some teaching materials use “strict” for the all-locks variant; this module uses the distinctions in CMU's 2PL lecture, slide 19.

Why hold a write lock through abort cleanup? Suppose T1 writes A=99 over 10, releases X(A), and T2 commits A=30. T1 later aborts and blindly restores 10. T2's committed result disappears. Holding X(A) until T1's rollback finishes prevents T2 from writing that value too early. This is the isolation assumption behind safe physical before-image undo in the previous lesson.

Basic 2PL can be valid without being strict: T1 may acquire X(A), update A, release it, and commit later, as long as it acquires nothing after that release. A second transaction may then read T1's uncommitted result. Serializability of the operation ordering and safe handling of aborts are different requirements.

What this exercise does and does not enforce

SimulateLocks sees lock and unlock operations, not reads, writes, commits, or abort completion. It tracks holders, wait queues, grant events, and deadlock. It cannot know whether an unlock is premature under a transaction protocol. A complete engine would place a transaction manager above this primitive and release locks according to its chosen protocol.

The input models blocking transactions: once a request is queued, that transaction issues no further operation until the grant occurs. Each transaction has at most one outstanding request. If blocked transactions could arbitrarily release locks while still waiting, a graph cycle would no longer describe the same execution model.

Likewise, a resource string represents whatever the caller chose to lock. Row locks alone do not prove isolation for a predicate such as “all balances above 100”: an inserted matching row may need range/predicate protection. This exercise does not model that larger lock hierarchy.

FIFO changes the grant rule

Track holders[resource][txn] = mode and queue[resource] = requests in order. A genuinely new request is immediately granted only when the queue is empty and all other holders are compatible. Otherwise it joins the tail.

An already sufficient lock is an exception because no new access is being acquired: if T1 holds X(A), another S(A) request by T1 succeeds and leaves its held mode as X. Report the requested S grant; do not downgrade X or add a lock reference count. One unlock releases the held lock.

An S→X upgrade does request stronger access. It must respect an existing queue, retaining S while it waits. Treating “sole holder” as unconditional permission to upgrade would bypass an earlier queued writer.

After an unlock, inspect the queue head. Grant it if compatible, update the holder set, then inspect the new head. Continue until the head cannot be granted. This permits a batch of adjacent S requests, but never skips a blocked X request to reach a later reader.

Trace a reader, a waiting writer, and a new reader

Step	Event	Holders of A	Queue for A	New grant
1	T1 requests S	T1:S	empty	T1:S
2	T2 requests X	T1:S	T2:X	none
3	T3 requests S	T1:S	T2:X, T3:S	none
4	T1 unlocks	T2:X	T3:S	T2:X
5	T2 unlocks	T3:S	empty	T3:S

At step 3, T3's S request is compatible with the holder but blocked by policy. Granting it immediately would permit an unbounded stream of readers to delay the writer. FIFO constrains admission; progress still depends on current holders eventually releasing and on deadlocks being resolved.

If T2 and T3 had both requested S behind an X holder, that holder's unlock could grant both. FIFO means preserving the order of grants, not forcing one reader to finish before the next compatible reader starts.

Build the graph of actual dependencies

A wait-for edge A→B means A cannot proceed until B makes progress. For each queued request add edges to other incompatible holders. Never add an edge to itself for a lock upgrade. Also add edges to earlier queued transactions, because the stated FIFO policy prevents passing them.

The graph must represent the scheduler you implemented. A textbook graph that includes only holder conflicts will miss a cycle created by queue ordering. Consider this history:

1. T1 holds S(A).
2. T3 holds X(B).
3. T2 requests X(A): edge T2→T1.
4. T3 requests S(A): it waits behind T2, so edge T3→T2.
5. T1 requests X(B): edge T1→T3.

The cycle is T1 → T3 → T2 → T1. T3 does not conflict with T1's S(A), yet T3 cannot pass T2. Reporting that both readers are compatible does not resolve the cycle. This is why fairness policy belongs in the deadlock model.

Rebuild the graph from current holders and queues after each newly queued request. Stale edges from previous ownership can manufacture a cycle that no longer exists. A color DFS uses white for unseen, gray for the current recursion path, and black for finished. An edge to gray proves a directed cycle; an edge to black may simply converge on an already explored dependency.

A cycle check is O(V+E) after graph construction. Adding an edge from every queued request to every earlier request can produce O(Q²) edges on one resource; this simple simulator accepts that cost. Do not describe the whole operation as O(number of transactions) while ignoring the edges.

Upgrades reveal the difference between waiting and deadlock

If T1 and T2 both hold S(A), T1's X request waits for T2. There is no cycle yet: T2 can finish and release S. If T2 also requests X(A) while retaining S, both transactions now wait on each other. Detect a deadlock and stop before granting either upgrade.

There is a subtler one-holder case: T1 holds S(A), T2 waits for X(A), then T1 requests X(A). The upgrade must queue behind T2. T2 waits on T1's held S; T1 waits behind T2. The exercise reports deadlock. Real lock managers can choose other upgrade policies, but they must specify them and update detection logic to match.

Detection alone does not recover progress. An engine normally chooses a victim, rolls it back, removes its queued requests, releases locks, and retries surviving waiters. SimulateLocks returns deadlock=true at the first cycle and leaves victim selection outside its scope.

Reconstruct and check

1. Protocol classification. T1 acquires S(A), releases S(A), then acquires X(B). All grants are compatible. Is it 2PL?

Answer: No. Acquiring X(B) after the first release violates the phase rule. The lock primitive can simulate it, which demonstrates why compatibility alone is not a serializability protocol.

2. Upgrade blocker. T1 and T2 hold S(A). T1 requests X(A). Which holder edge is required, and which edge is wrong?

Answer: Add T1→T2. Do not add T1→T1. A self-edge would falsely report deadlock before T2 has even requested anything.

3. Queue drainage. X(A) is released with queue [T2:S, T3:S, T4:X]. Which grants occur immediately?

Answer: T2:S then T3:S. T4 remains queued until both readers release. Updating holders after each grant is essential; looking only at the initially empty holder set would incorrectly grant X too.

4. Safety versus progress. Does the absence of a graph cycle mean every transaction will eventually finish?

Answer: No. A holder may never release, or scheduling may be unfair outside this model. Cycle detection identifies this form of deadlock, not every cause of stalled work.

Implement the simulator only after you can draw both the grant trace and the queue-dependent cycle. Then explain how a transaction manager would use this primitive to retain write locks until commit or completed rollback.