Microschedules & Deadlock
Concept. You met the lock manager and one lock's cycle; now it runs many transactions at once. 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.
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.
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
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. 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
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
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.