Lock Manager (Strict 2PL)

Simulate a lock manager with shared/exclusive locks and deadlock detection.

Types

type LockOp struct {
    Txn  int
    Res  string
    Mode string // "S" or "X"
    Kind string // "lock" or "unlock"
}

type Grant struct {
    Txn  int
    Res  string
    Mode string
}

func SimulateLocks(ops []LockOp) (grants []Grant, deadlock bool)

Rules

• Compatibility:
  • S is compatible with S.
  • X is compatible with nothing else.
• A lock request is granted immediately if compatible with current holders.
• Otherwise it is queued (FIFO) for that resource.
• On unlock, try to grant queued requests in order (FIFO). Keep granting while the head is compatible.
• Lock upgrades: if a txn already holds S and requests X, allow upgrade only if it is the sole holder; otherwise it must wait.

Deadlock detection

• After each queued lock request, build a wait-for graph.
• An edge A -> B exists if txn A is waiting on a resource held by txn B.
• If the graph has a cycle, return deadlock=true immediately.

Output

• grants: lock grants in the order they were granted.