Locking: compatibility is only the beginning

A transaction needs rules for:

  • Which concurrent access is compatible.
  • How long it retains locks.
  • Which waiting request goes next.
  • What happens when dependencies form a cycle.

The exercise implements grants and detection, not a full transaction manager.

1 / 9

Use precise phase rules

Protocol Rule beyond requesting appropriate locks
2PL Acquire, then release; never acquire after the first release
Strict 2PL Also hold X locks until commit / completed abort
Rigorous 2PL Hold both S and X until completion

All can block. 2PL does not eliminate deadlocks.

2 / 9

Predict the grants

T1 requests S(A)
T2 requests X(A)
T3 requests S(A)

T3 is compatible with T1. Is that sufficient to grant it?

3 / 9

FIFO protects the waiting writer

Event Holders Queue
Three requests complete T1:S T2:X, T3:S
T1 unlocks T2:X T3:S
T2 unlocks T3:S empty

A new request needs both compatibility and an empty queue. An already-held sufficient lock is not a new acquisition.

4 / 9

Upgrades retain their old lock

T1 and T2 hold S(A).

  • T1 requests X(A): waits on T2.
  • T2 requests X(A): waits on T1.
  • Neither upgrade can proceed.

Never add a self-edge merely because an upgrading transaction holds S.

5 / 9

Holder-only graphs can miss a cycle

T1 holds S(A)
T3 holds X(B)
T2 waits for X(A)          T2 → T1
T3 queues for S(A)        T3 → T2  (FIFO)
T1 waits for X(B)         T1 → T3

Cycle: T1 → T3 → T2 → T1.

The detector must model queue ordering as well as incompatible holders.

6 / 9

Drain the queue one grant at a time

X(A) is released. Queue: [T2:S, T3:S, T4:X].

  1. Grant T2:S; update holders.
  2. Grant T3:S; update holders.
  3. Stop at T4:X, now blocked by both readers.

Granting every request against the initially empty holder set is wrong.

7 / 9

A directed cycle check

DFS colors: white=unseen, gray=current path, black=finished.

  • Edge to gray: cycle.
  • Edge to black: not necessarily a cycle.
  • Rebuild dependencies from current state; avoid stale edges.

O(V+E) for DFS after constructing edges. FIFO edges may be quadratic in queue length.

8 / 9

Explain the boundary before coding

lock A → unlock A → lock B can be simulated but violates 2PL.

The API has no commit/abort state to enforce lock lifetimes. A complete engine adds a transaction manager, rollback, and victim selection.

Implement lock-manager; verify both the FIFO trace and the upgrade cycle.

9 / 9
←/→ or click edges to navigate · ? help · N notes · F fullscreen