Microschedules: Deconstructing Concurrent Transactions

What is a Microschedule? 🔬

Key Concept: A microschedule is a specific execution sequence of atomic Read/Write (R/W) and Lock (Req/Get/Unlock) actions from concurrent transactions.

How to Build a Microschedule

1️⃣ Decompose Into Actions

Break each transaction into atomic operations with lock protocol

Lock Pattern: Req→Get→[R/W]Unl
T1: Req(A)→Get(A)→R(A)→W(A)→Unl(A)
T2: Req(B)→Get(B)→R(B)→W(B)→Unl(B)

2️⃣ Interleave for Speed

Mix actions from different transactions to maximize CPU usage

Smart: While T1 waits for IO, run T2
Result: 31 units (interleaved) vs 48 units (serial)
35% speedup from overlapping operations!

3️⃣ Track Dependencies

Build WaitsFor graph to ensure correctness

Graph: T1→T2 = T1 waits for T2's lock
Safety: No cycles = No deadlock ✓
Action: Detect & resolve if cycles appear

Example 1: Serial Schedule (S1) ⚙️

Serial Schedule with T3 → T2 → T1

Serial schedule S1: T3 then T2 then T1, completion = 48 units

Here's an example micro schedule for S1, our serial schedule with T3 → T2 → T1, with completion = 48 units.

📖 How to Read This Timeline

📊 The Setup: 3 Transactions (T1, T2, T3) on 1 CPU Core

Time flows left → right, each transaction gets its own horizontal lane

🔄 The Lock Pattern: Req → Get → [IO] → Unl
  • Req = Request lock
  • Get = Lock granted
  • IO = Rs/Re or Ws/We
  • Unl = Unlock (or Release)
💡 Why This Matters: With 1 core for 3 transactions, the CPU constantly switches - when T1 waits for IO, T2 runs; when T2 waits for a lock, T3 runs. This interleaving maximizes CPU usage!

WaitsFor Graph: Detecting Deadlocks 🔍

Definitions

🔗 WaitsFor Graph

WaitsFor graph is a directed graph that represents the lock dependencies between transactions in a concurrent execution schedule.

Components:
• Each node corresponds to a transaction
• Directed edges indicate waiting relationships
• Labels show the variable and time span of waiting

⚠️ Deadlock Detection

Cycles within the WaitsFor graph signify deadlock.

Example: T1 waits for T2, T2 waits for T1 → Cycle = Deadlock

💥 Impact of Deadlocks

Deadlocks can cause system stalls, leading to inefficiencies in resource utilization and transaction delays.

Consequences:
• System becomes unresponsive
• Transactions cannot proceed
• Manual intervention required

Example 2: Interleaved Schedule (S2) - Fast Execution 🚀

Interleaved Schedule with Optimized Performance

Interleaved schedule S2 with completion = 31 units

Here's an example micro schedule for S2, our interleaved schedule, with completion = 31 units.

📖 How to Read S2: Timeline, Locks & Dependencies

⏱️ Timeline View: Microschedule Execution
  • Time flows left → right (0 to 31 units)
  • Each row = one transaction (T1, T2, T3)
🔒 Per-Transaction Locks: Lock Sequences
  • T2: T2.Req(A) at 2, T2.Get(A) at 3, T2.Unl(A) at 10
  • Note: T1.Get(A) waits for T2.Unl(A)
  • Lock pattern determines execution order
🔗 WaitsFor Graph: No Deadlock
  • Nodes: T1, T2, T3 (transactions)
  • Edge: T1→T2, T1 waits for T2 on variable A (time units 3-10)
  • No cycles detected = No deadlock ✓

Example 3: Interleaved Schedule (S3) - Different Microschedule ⏱️

Different Interleaved Schedule for Same Transactions

Interleaved schedule S3 with completion = 45 units

Here's an example micro schedule for S3, a different interleaved schedule for the same set of transactions, with completion = 45 units.

🔄 S3 vs S2: Different Microschedule, Same Transactions

⏱️ Different Timing:

S3 takes 45 units vs S2's 31 units due to different lock acquisition order and contention patterns

🔒 Different Lock Pattern:

More contention leads to longer waits and slower completion - same transactions, different execution strategy

💡 Key Insight:

Same transactions can have vastly different performance based on microschedule scheduling decisions!

Example 4: Deadlock Detection ⚠️

When Cycles Create System Deadlock

Deadlock scenario with 2 transactions showing circular dependencies

Here's an example where the same transaction pattern could lead to deadlock under different timing.

💥 Understanding Deadlock Scenarios

🔄 Circular Dependencies:
  • T1 waits for T2 to release resource B
  • T2 waits for T1 to release resource A
  • Result: Circular wait = Deadlock!
🔗 WaitsFor Graph Cycles:
  • T1 → T2 → T1 (cycle detected)
  • Each arrow represents a "waits for" relationship
  • Cycle means no transaction can proceed
  • System requires deadlock detection & resolution
📈 Deadlock Complexity:
  • Can occur with 2+ transactions
  • More likely with ≥3 transactions due to dependencies
  • Probability increases with more concurrent transactions
  • Prevention: careful resource ordering

Performance: Why Interleaved Schedules Win 🚀

The Power of Overlapping CPU and IO

Performance comparison showing speedup benefits of interleaved schedules

Interleaved schedules provide significant advantages over serial schedules through smart resource utilization.

⚡ Speedup Analysis: CPU + IO Optimization

🎯 Core Idea: Overlap Operations
  • CPU operations run while waiting for IO completion
  • No idle CPU time during disk/network waits
  • Multiple transactions progress simultaneously
  • Maximum resource utilization achieved
📊 Performance Impact:
  • Serial: T1 complete → T2 complete → T3 complete
  • Interleaved: T1, T2, T3 run concurrently
  • Higher IO lag = bigger speedup opportunity
  • More concurrent transactions = greater parallelism
🚀 Real-World Example:
  • 100 concurrent transactions
  • IO lag: 100 time units
  • Result: 24x speedup!
  • Serial: 10,000 units vs Interleaved: 417 units