Microschedules & Deadlock

Concept. A microschedule shows how transactions interleave operations and acquire locks. The order it grants locks is the microschedule, the time-ordered record of which operation runs when, and overlapping the idle waits is where the speedup comes from. Locking also creates one new risk: two transactions each waiting on the other, a cycle in the WaitsFor graph, which the manager breaks by aborting a victim.

Intuition. Mickey and Minnie both want to write row A. The lock manager hands A to Mickey, queues Minnie behind him, and writes that order into the schedule. When two transactions each hold a row the other is waiting on, the WaitsFor graph closes into a cycle, and the manager aborts a victim to break it.

The lock manager has three jobs. Locks Stack & the Lock Manager introduced the manager and its first job, granting and queuing one lock. This page is the other two, now that many transactions are in flight: build a fast schedule, and break the deadlocks that locking makes possible.

Three transactions T1, T2, T3 each send a lock request to a central component, the lock manager, which holds the lock table showing row A held by T1 with T2 waiting and row B granted to T3. The lock manager does three jobs: grant or queue each request, build the microschedule as the order it grants locks, and detect deadlock by watching the WaitsFor graph for a cycle.

Figure 1. The lock manager again, all three jobs in one view. Job one, grant or queue, came on the Locks Stack page; this page is jobs two and three: the microschedule it builds as it grants locks, and the WaitsFor cycle it watches for. The rest of the page is those two jobs in motion.

What the Lock Manager Does

Each lock follows the pattern Req → Get → [R/W] → Unl. The rest of this page watches the lock manager grant those across three schedules and one deadlock, building the time-ordered microschedule (the record of which operation runs when) as it goes.

Reading the Timeline: A Read or Write Takes Time

Recall from DB Locks & 2PL that an operation is not instant: a read or write takes real time to reach storage and back, and the transaction sits idle in between. The lock manager turns that idle gap into a speedup: it grants another transaction while one waits. The timelines below put a notation on it: a read runs from Rs (read start) to Re (read end), a write from Ws to We, and the span between is the IO lag.

Figure 2. Every read and write on the lock manager's timelines below is drawn as a start and an end (Rs to Re, or Ws to We) because the data has to travel to storage and back. While T1's read of B is in flight, the CPU is idle, so the lock manager grants T2 in that gap. The whole point of a microschedule is to make those overlaps visible.

Example 1: Serial Schedule (S1)

Serial Schedule with T2 → T1 → T3

The lock manager's simplest schedule grants one transaction at a time. Three transactions share one CPU core, so the serial run never overlaps a wait with work.

Serial lock schedule running T2, then T1, then T3 with no overlap: a timeline of each transaction's lock operations (Req and Get, read/write start and end, Unl) over 49 time units.

T2 runs first: 5 operations in time order, all on row A. Req is a lock request, Get the grant, Rs and Re the start and end of a read, Ws and We the start and end of a write, Unl the unlock. T2 requests A at time 1, gets it at 2, starts reading A at 3, ends the read at 8, and unlocks A at 9. T2 never writes.
T2
Req(A)
Get(A)
Rs(A)
Re(A)
Unl(A)

T1 runs second: 7 operations in time order, all on A. T1 requests A at time 10, gets it at 11, reads A from 12 to 17, writes A from 18 to 23, and unlocks A at 24.
T1
Req(A)
Get(A)
Rs(A)
Re(A)
Ws(A)
We(A)
Unl(A)

T3 runs last: 12 operations in time order, on B and then A. T3 requests B at time 25, gets it at 26, reads B from 27 to 32, writes B from 33 to 38, requests A at 39, gets it at 40, writes A from 41 to 46, then unlocks B at 47 and A at 48. Nothing overlaps: each transaction starts only after the one before it has unlocked, and the schedule completes at 49 time units, the serial baseline.
T3
Req(B)
Get(B)
Rs(B)
Re(B)
Ws(B)
We(B)
Req(A)
Get(A)
Ws(A)
We(A)
Unl(B)
Unl(A)

Figure 3. Serial schedule S1 runs T2, then T1, then T3 with no overlap. It is correct by construction but slow: 49 time units end to end, the baseline the interleaved schedules below have to beat. (The serial order is whichever the lock manager picks; any order is equally correct.)

WaitsFor Graph: Who Waits for Whom

Definitions

The lock manager reads its own grant-and-queue state as a graph. Each node is a transaction, and each directed edge points from a waiter to the holder of the lock it needs. Read straight off the graph who is blocked on whom. Most of the time those edges form a chain: every transaction eventually reaches the front and proceeds. Example 4 shows the one case where the edges instead close into a loop.

Example 2: Interleaved Schedule (S2) - Fast Execution

Interleaved Schedule with Optimized Performance

Interleaved lock schedule, completion 31 units: a timeline of lock operations for T1, T2, T3, the per-transaction locks, and a WaitsFor graph forming the chain T3 to T1 to T2 with no cycle (no deadlock).

T1's lane: 7 operations in time order, all on row A. Req is a lock request, Get the grant, Rs and Re the start and end of a read, Ws and We the start and end of a write, Unl the unlock. T1 requests A at time 1 and waits until it gets A at 10. A is free until T2, which requested it at 2, is granted it first, at 3; T2 then holds A until 10. T1 then reads A from 11 to 16, writes A from 17 to 22, and unlocks A at 23. T1 holds A from 10 to 23.
T1
Req(A)
Get(A)
Rs(A)
Re(A)
Ws(A)
We(A)
Unl(A)

T2's lane: 5 operations in time order, all on A. T2 requests A at time 2, gets it at 3, reads A from 4 to 9, and unlocks A at 10. T2 holds A from 3 to 10 and never writes.
T2
Req(A)
Get(A)
Rs(A)
Re(A)
Unl(A)

T3's lane: 12 operations in time order, on B and then A. T3 requests B at time 5, gets it at 6, reads B from 7 to 12, writes B from 13 to 18, then requests A at 19 and waits until it gets A at 23, because T1 holds A. T3 writes A from 24 to 29, unlocks A at 30 and B at 31. The last operation is at 31: the schedule completes at 31 time units.
T3
Req(B)
Get(B)
Rs(B)
Re(B)
Ws(B)
We(B)
Req(A)
Get(A)
Ws(A)
We(A)
Unl(A)
Unl(B)

Per-Transaction Locks panel, T1: 1 lock. A is requested at 1, granted at 10, and unlocked at 23.
T1
A: {"Req": 1, "Get": 10, "Unl": 23}

Per-Transaction Locks panel, T2: 1 lock. A is requested at 2, granted at 3, and unlocked at 10.
T2
A: {"Req": 2, "Get": 3, "Unl": 10}

Per-Transaction Locks panel, T3: 2 locks. B is requested at 5, granted at 6, and unlocked at 31. A is requested at 19, granted at 23, and unlocked at 30. The WaitsFor graph beside this panel has two edges, each pointing from a waiter to the holder: T3 waits for T1 on A from 19 to 23, and T1 waits for T2 on A from 3 to 10. That is a chain T3 to T1 to T2 with no cycle, so there is no deadlock.
T3
B: {"Req": 5, "Get": 6, "Unl": 31}
A: {"Req": 19, "Get": 23, "Unl": 30}

Figure 4. When the lock manager interleaves the same transactions, S2 finishes in 31 units, well under the serial 49. Overlapping the lock-free stretches produces the speedup.

Lock sequence: the lock manager grants T2 lock A at unit 3, releases at 10; T1 then waits and acquires A at 10. T1 asked first, at unit 1, but this schedule hands A to T2 first, and any grant order is legal. The WaitsFor graph is the chain T3 → T1 → T2 (each waits for the next on A). No cycles, no deadlock.

Example 3: Interleaved Schedule (S3) - Different Microschedule

Different Interleaved Schedule for Same Transactions

A different interleaved lock schedule, completion 45 units: the lock timeline, the per-transaction locks, and a WaitsFor graph T2 to T1 to T3 (T2 also waits on T3) with no cycle.

T1's lane: 7 operations in time order, all on row A. Req is a lock request, Get the grant, Rs and Re the start and end of a read, Ws and We the start and end of a write, Unl the unlock. T1 requests A at time 5 and waits until it gets A at 24. It then reads A from 26 to 31, writes A from 32 to 37, and unlocks A at 38. T1 holds A from 24 to 38.
T1
Req(A)
Get(A)
Rs(A)
Re(A)
Ws(A)
We(A)
Unl(A)

T2's lane: 5 operations in time order, all on A. T2 requests A at time 1 and waits until it gets A at 38. It then reads A from 39 to 44 and unlocks A at 45, the last operation: the schedule completes at 45 time units. T2 never writes.
T2
Req(A)
Get(A)
Rs(A)
Re(A)
Unl(A)

T3's lane: 12 operations in time order, on B and then A. T3 requests B at time 2, gets it at 3, reads B from 4 to 9, writes B from 10 to 15, requests A at 16, gets it at 17, writes A from 18 to 23, then unlocks A at 24 and B at 25. T3 holds A from 17 to 24.
T3
Req(B)
Get(B)
Rs(B)
Re(B)
Ws(B)
We(B)
Req(A)
Get(A)
Ws(A)
We(A)
Unl(A)
Unl(B)

Per-Transaction Locks panel, T1: 1 lock. A is requested at 5, granted at 24, and unlocked at 38.
T1
A: {"Req": 5, "Get": 24, "Unl": 38}

Per-Transaction Locks panel, T2: 1 lock. A is requested at 1, granted at 38, and unlocked at 45.
T2
A: {"Req": 1, "Get": 38, "Unl": 45}

Per-Transaction Locks panel, T3: 2 locks. B is requested at 2, granted at 3, and unlocked at 25. A is requested at 16, granted at 17, and unlocked at 24. The WaitsFor graph beside this panel has three edges, each pointing from a waiter to the holder, all on A: T2 waits for T3 from 17 to 24, T1 waits for T3 from 17 to 24, and T2 waits for T1 from 24 to 38. The edges run T2 to T1 to T3, with T2 also waiting on T3. No cycle, so there is no deadlock.
T3
B: {"Req": 2, "Get": 3, "Unl": 25}
A: {"Req": 16, "Get": 17, "Unl": 24}

Figure 5. S3 is a different valid interleaving of the same transactions, yet it finishes in 45 units, barely better than serial. Interleaving helps only when it overlaps the right operations; the order the lock manager grants in matters, not just the decision to interleave.

S3 vs S2: same three transactions, a different lock-acquisition order produces more contention and longer waits. 45 units vs S2's 31. The lock manager's grant order matters as much as the transactions themselves.

Example 4: Deadlock Detection

This is the deadlock Two-Phase Locking flagged as locking's one new risk, now drawn as a WaitsFor cycle.

When Cycles Create System Deadlock

Deadlock with 2 transactions: a lock-schedule timeline (T1 and T2 acquiring and requesting locks on A and B over time), the per-transaction locks, and a WaitsFor graph whose red cycle T1 to T2 to T1 (T1 waits for B held by T2, T2 waits for A held by T1) is the deadlock.

T1's lane, 7 operations in time order. Req is a lock request, Get the grant, Rs and Re the start and end of a read, Ws and We the start and end of a write. T1 requests A at time 1, gets it at 2, reads A from 3 to 8, writes A from 9 to 14, then requests B at 15 and waits, because T2 holds B. T1 keeps holding A while it waits. No unlock is drawn.
T1
Req(A)
Get(A)
Rs(A)
Re(A)
Ws(A)
We(A)
Req(B)

T2's lane, 7 operations in time order. T2 requests B at time 4, gets it at 5, reads B from 6 to 11, writes B from 12 to 17, then requests A at 18 and waits, because T1 holds A. T2 keeps holding B while it waits. No unlock is drawn.
T2
Req(B)
Get(B)
Rs(B)
Re(B)
Ws(B)
We(B)
Req(A)

Per-Transaction Locks panel, T1: 2 locks. A is requested at 1 and granted at 2. B is requested at 15 and has no grant.
T1
A: {"Req": 1, "Get": 2}
B: {"Req": 15}

Per-Transaction Locks panel, T2: 2 locks. A is requested at 18 and has no grant. B is requested at 4 and granted at 5. The WaitsFor graph beside this panel has two edges, each pointing from a waiter to the holder: T1 waits for T2 on B from time 15, and T2 waits for T1 on A from time 18, with no end time on either. The two edges close into a cycle between T1 and T2, drawn in red: a deadlock, and neither transaction can proceed.
T2
A: {"Req": 18}
B: {"Req": 4, "Get": 5}

Figure 6. The same transaction pattern under different timing deadlocks: each transaction holds a ticket the other needs, so the lock manager's WaitsFor graph forms a cycle and neither can proceed. Interleaving buys performance only until a cycle stops everything.

Circular wait: T1 waits for T2 to release B; T2 waits for T1 to release A. The lock manager's WaitsFor graph has the cycle T1 → T2 → T1. Neither can proceed. Probability rises with more concurrent transactions; the lock manager needs an explicit deadlock-detection-and-resolution mechanism, so it aborts a victim to break the cycle.

Performance: Why Interleaved Schedules Win

The Power of Overlapping CPU and IO

# of Transactions	IOlag	Serial Time	Interleaved Time	Speedup
10	5	135	68	1.99×
10	10	225	76	2.96×
10	100	1,845	229	8.06×
100	5	1,485	698	2.13×
100	10	2,475	704	3.52×
100	100	20,295	825	24.6×

The bottom row is one specific run: 100 transactions at an IO lag of 100, where interleaving wins 24.6×. That exact number depends on the IO numbers you plug in. The trend matters more than the exact number: as the IO lag and the number of concurrent transactions grow, the speedup grows with them, reaching roughly 10× to 100× in IO-bound workloads.

The lock manager earns that speedup by making readers and writers wait for each other on shared rows. The next page, MVCC, removes even that wait: readers never block on writers, because each one reads its own version.