Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Concurrency control and locking

Clear, exam-ready notes on concurrency control and locking: definitions (schedule, serializability, locks), two-phase locking and its variants, lock compatibility, deadlocks and detection, with worked examples and exam tips.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Concurrency control and locking are used by engineers to make sure many users (or transactions) can access the same database at once without corrupting data. These techniques can guarantee correctness (serializability) under protocols like two-phase locking (2PL), enable recoverability and avoidance of cascading aborts under strict/rigorous 2PL, and help detect and resolve deadlocks in multi-user OLTP systems.

Key ideas

  • Conflict (conflicting operations): Two operations conflict if (1) they are by different transactions, (2) they access the same data item, and (3) at least one is a write. Typical conflicts: read–write, write–read, write–write on same item.

  • Conflict-equivalence and Conflict-serializability: A schedule S is conflict-equivalent to a serial schedule S' if by swapping non-conflicting adjacent operations in S we can obtain S'. A schedule is conflict-serializable if it is conflict-equivalent to some serial schedule. For completeness: view-serializability is a more general notion based on preserving reads-from and final writes; every conflict-serializable schedule is view-serializable, but not vice versa, and testing view-serializability is NP-complete.

  • Precedence (or conflict) graph: a directed graph with one node per transaction; add an edge Ti -> Tj if an operation of Ti conflicts with a later operation of Tj on the same data item. Key theorem: A schedule is conflict-serializable iff its precedence graph is acyclic. (Assumptions: conflicts defined as above, operations total order in the schedule.)

    To draw this in an exam: draw circles labelled T1, T2,... For each pair of conflicting operations where Ti's operation appears earlier than Tj's, draw a directed arrow from Ti to Tj and label it with the data item (optional). If the graph has any directed cycle, the schedule is not conflict-serializable.

  • Locks and lock modes: A lock is a mechanism to control access to a data item. Two basic modes:

    • Shared lock (S): allows reading; multiple transactions may hold S on the same item concurrently.
    • Exclusive lock (X): allows writing; only one X lock on the item at a time and no other S or X may be held concurrently.

    The lock compatibility matrix (what to draw in an exam) is a 2×2 table with rows = requester mode, columns = existing mode; fill with "compatible" or "incompatible". (S with S = compatible; S with X = incompatible; X with S = incompatible; X with X = incompatible.) Some systems also define an Update (U) lock that is compatible with S but not with U or X to reduce upgrade deadlocks (DBMS-dependent). Note: tuple/page S/X locks do not prevent phantom reads; preventing phantoms requires predicate or index-range locking (e.g., next-key locks) under serializable isolation.

  • Two-Phase Locking (2PL): A transaction follows 2PL if it has two phases: (1) a growing phase where it may acquire locks but not release any, and (2) a shrinking phase where it releases locks but does not acquire new ones. 2PL theorem: Any schedule produced by transactions that follow 2PL is conflict-serializable. Assumptions: locks grant mutual exclusion according to compatibility matrix, and the schedule reflects actual lock acquisition/release order. Proof sketch (exam-style): choose each transaction’s first lock release as its serialization point; by 2PL, any conflicting edge Ti -> Tj implies Ti’s first unlock precedes Tj’s first unlock, yielding an acyclic order; therefore the schedule is conflict-serializable.

  • Strict 2PL: a stronger variant where a transaction holds all its exclusive (X) locks until it commits or aborts. Strict 2PL implies both conflict-serializability and that schedules are recoverable and free of cascading aborts (because no other transaction can read uncommitted writes). Conservative (static) 2PL: a variant where a transaction obtains all the locks it will ever need before it begins; this prevents deadlocks but may reduce concurrency.

  • Recoverable schedule and cascading abort: A schedule is recoverable if whenever Ti reads a value written by Tj, Tj must commit before Ti commits. A cascading abort happens when aborting one transaction forces aborts of others that read its uncommitted changes. Strict 2PL prevents cascades because X locks are held until commit. Schedules that avoid cascading aborts are called cascadeless; strict schedules are both cascadeless and recoverable.

  • Deadlock: occurs when a set of transactions are each waiting for locks held by others in the set. Represent with a wait-for graph: nodes are transactions; add edge Ti -> Tj if Ti is waiting for a lock held by Tj. A cycle in the wait-for graph means deadlock.

    To draw: nodes labelled T1,T2,... and directed edges for waits. Show cycle to indicate deadlock.

  • Deadlock handling: three approaches: (1) prevention (impose a resource or lock-ordering, or use timestamps such as wait-die or wound-wait to avoid cycles), (2) detection and resolution (build wait-for graph periodically; if cycle found, choose a victim to abort), (3) timeout (if a transaction waits too long, abort it). When aborting a victim, typically choose a transaction with lowest cost (fewest updates or latest start time/youngest) or lowest priority.

  • Lock manager: component in DBMS that grants locks; maintains lock table with queue per data item of lock requests; uses compatibility to grant locks immediately or make requests wait.

  • Optimistic / validation-based protocols: allow transactions to run without locks and validate at commit; used when conflicts are rare. (These are covered in the broader track under Validation-based protocols and multiple granularity.)

Formulas

BEGIN TRANSACTION (or START TRANSACTION in some systems) — start a transaction; used before operations in many SQL dialects.

  • Meaning: begins a transaction context. No SI unit. Applies to SQL transactional systems.

COMMIT — commit the current transaction; makes changes permanent.

ROLLBACK — aborts the transaction and undoes its changes.

LOCK TABLE table_name IN SHARE MODE; — request a shared lock on a table (DBMS-dependent syntax).

LOCK TABLE table_name IN EXCLUSIVE MODE; — request an exclusive lock on a table (DBMS-dependent syntax).

acquire_lock(T, item, mode) — abstract operation: transaction T requests lock on item in mode S or X.

  • Meaning: if compatible with existing locks on item, grant; else T waits.

release_lock(T, item) — abstract operation: T releases a lock on item.

2PL property: ∀T, there exists a point t* in T such that for time < t* T may acquire locks, for time ≥ t* T may release locks only.

  • Meaning: formal definition of two-phase locking (growing then shrinking). Applies when using lock-based concurrency control.

Conflict edge: Ti -> Tj iff ∃ operations oi ∈ Ti and oj ∈ Tj such that oi precedes oj in schedule and oi and oj conflict (same item, at least one write).

Worked examples

Example 1 — Conflict-serializability check (classical) Schedule S: r1(x), r2(x), w1(x), w2(x) Steps:

  1. List operations in order and note conflicts (read/write on same item counts if at least one is write).
    • r1(x) vs r2(x): both reads — no conflict.
    • r1(x) (index 1) vs w2(x) (index 4): read–write conflict; r1(x) before w2(x) gives edge T1 -> T2.
    • r2(x) (index 2) vs w1(x) (index 3): read–write conflict; r2(x) before w1(x) gives edge T2 -> T1.
    • w1(x) vs w2(x): write–write conflict; w1(x) before w2(x) gives edge T1 -> T2 (already present).
  2. Build precedence graph: nodes T1, T2. Edges: T1 -> T2 and T2 -> T1. This is a cycle.
  3. Conclusion: schedule S is NOT conflict-serializable because precedence graph has a directed cycle.

Example 2 — 2PL lock sequence and deadlock detection Transactions: T1: r1(x), w1(x), r1(y), w1(y), commit T2: r2(y), w2(y), r2(x), w2(x), commit Suppose both use 2PL (acquire the needed lock before each access and do not release any lock until they have acquired all locks they will need—i.e., no release during the growing phase):

  1. T1 acquires S(x), then upgrades to X(x) to write; T2 acquires S(y), then upgrades to X(y) to write.
  2. After writing, T1 tries to acquire S(y) or X(y) but y is locked by T2; T2 then tries to acquire S(x)/X(x) but x is locked by T1. Both wait.
  3. Wait-for graph: T1 -> T2 and T2 -> T1: cycle => deadlock.
  4. Detection: lock manager builds wait-for edges; on finding cycle, choose victim (say abort T2). If T2 aborted, it releases locks; T1 proceeds and completes; T2 may restart later.
  5. If strict 2PL is used (X locks held until commit), and T1 had written x and holds X(x) until commit, T2 cannot read/write x; deadlock still possible and handled the same way.

Example 3 — Strict 2PL avoids cascading aborts (model answer) Transactions: T1: w1(x); (commit or abort) T2: r2(x); commit If the system used non-strict locking and T1 wrote x and released X(x) before commit, T2 might read the uncommitted x; if later T1 aborts, T2 must be aborted too — cascading abort. Under strict 2PL, T1 holds X(x) until commit, so T2 cannot read until after T1 commits; therefore recoverable and no cascading abort.

Common mistakes

  • Thinking 2PL prevents deadlocks — it does not; it guarantees serializability but can cause deadlocks.
  • Saying strict 2PL prevents all aborts — it prevents cascading aborts but transactions can still be aborted for other reasons (e.g., user abort, deadlock victim).
  • Ignoring DBMS-specific LOCK syntax; SQL dialects differ (MySQL, PostgreSQL have different commands).

For your exam

Question types you will see: definitions (define schedule, conflict, 2PL), short notes (compare strict 2PL and conservative 2PL), derivations/proofs (prove 2PL implies conflict-serializability), diagrams (draw precedence graph or wait-for graph), and analysis problems (given a schedule, determine serializability; show lock sequence under 2PL; detect deadlock and propose victim).

What a full-marks answer includes:

  • For definitions: concise definition with bold term used once; mention assumptions.
  • For proofs: clear statement of theorem, assumptions, step-by-step logical argument (e.g., contradiction proof for 2PL theorem), and final conclusion.
  • For schedules: list conflicting operation pairs, build and draw precedence graph with nodes and directed edges, check for cycles and conclude.
  • For lock problems: show explicit acquire_lock and release_lock steps with modes, show wait-for edges if waiting, and state deadlock detection/resolution policy.

Quick check

  1. What is a conflict between two operations?
  2. State the 2PL property in one sentence.
  3. How do you detect a deadlock using a wait-for graph?

Answers: 1) Two operations conflict if they are from different transactions, access the same data item, and at least one is a write. 2) 2PL: a transaction first only acquires locks (growing phase) and then only releases locks (shrinking phase). 3) Build directed wait-for graph of transactions; a cycle indicates deadlock.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?