Simulate Transaction Lock Scheduling

Problem Statement

In database management systems, a lock manager controls concurrent access to shared resources. You need to implement an in-memory LockManager supporting Shared ('S') and Exclusive ('X') locks with FIFO wait queues.

Lock compatibility rules:

• Multiple transactions can hold a Shared ('S') lock on the same resource simultaneously.
• An Exclusive ('X') lock requires that no other transaction holds any lock ('S' or 'X') on that resource.

To prevent write starvation, the lock manager must adhere to strict FIFO queuing per resource:

• If a resource currently has an active wait queue, any new lock request for that resource must wait, even if it is an 'S' lock request and the resource is currently held in 'S' mode.
• When a transaction releases its locks, the wait queue for each affected resource must be processed from the front:
  • If the transaction at the front of the queue requested an 'X' lock, it is granted if and only if there are currently zero active lock holders on that resource. Once an 'X' lock is granted, no other waiting transactions for that resource can be granted at this time.
  • If the transaction at the front requested an 'S' lock, it is granted if there are no active 'X' lock holders. The scheduler then continues granting locks to consecutive waiting 'S' requests immediately following it until either an 'X' request is reached or the queue is empty.

Implement the LockManager class with the following methods:

class LockManager:
    def __init__(self):
        pass

    def request_lock(self, tx_id: str, resource_id: str, lock_type: str) -> str:
        """
        Requests a lock ('S' or 'X') on resource_id for transaction tx_id.
        Returns "GRANTED" if the lock was acquired immediately, or "WAITING" if enqueued.
        """
        pass

    def release_all(self, tx_id: str) -> list[str]:
        """
        Releases all locks held by tx_id and removes tx_id from any wait queues.
        Evaluates affected resource wait queues and grants locks according to the rules.
        Returns a list of tx_ids that were unblocked and granted their requested lock,
        ordered by the order they were granted.
        """
        pass

Assumptions & Constraints

• A transaction will never request a lock on a resource it already holds or is already waiting on.
• A blocked transaction (WAITING) will not make further request_lock calls until it is granted.
• tx_id and resource_id are non-empty strings of alphanumeric characters (length <= 32).
• lock_type is either 'S' or 'X'.
• Total operations (calls to request_lock and release_all) <= 2 * 10^4.

Examples

Example 1

lm = LockManager()
lm.request_lock("T1", "R1", "S")  # returns "GRANTED"
lm.request_lock("T2", "R1", "S")  # returns "GRANTED"
lm.request_lock("T3", "R1", "X")  # returns "WAITING" (T1, T2 hold R1)
lm.request_lock("T4", "R1", "S")  # returns "WAITING" (FIFO: queued behind T3)

lm.release_all("T1")
# returns [] (T2 still holds 'S', so T3 cannot be granted)

lm.release_all("T2")
# returns ["T3"] (T3 acquires 'X'; T4 remains waiting behind T3)

lm.release_all("T3")
# returns ["T4"] (T4 acquires 'S')

Example 2

lm = LockManager()
lm.request_lock("T1", "R1", "X")  # returns "GRANTED"
lm.request_lock("T2", "R1", "S")  # returns "WAITING"
lm.request_lock("T3", "R1", "S")  # returns "WAITING"
lm.request_lock("T4", "R1", "X")  # returns "WAITING"

lm.release_all("T1")
# returns ["T2", "T3"]
# Explanation: T2 is granted 'S'. The next request is also 'S' (T3), so it is
# also granted. The queue scan stops at T4 ('X').