CSE Roadmap

Core tier · about 2 hours · 5 parts

Part 5 of 5 · 4 min read

Exercises

Easy

Easy 1: Distinguish shared from exclusive locks (15 minutes)

State the key difference between a shared lock and an exclusive lock.

Done when: multiple transactions holding a shared lock concurrently, versus only one transaction holding an exclusive lock with no other locks allowed on that item, is correctly described.

Hint

A shared lock can be held by several transactions at once for reading; an exclusive lock can be held by only one transaction, excluding every other lock on that item, for writing.

Easy 2: Name the two phases (15 minutes)

Name the two phases of two-phase locking.

Done when: the growing phase and the shrinking phase are both correctly named.

Hint

The growing phase and the shrinking phase.

Easy 3: State the rule that triggers the shrinking phase (15 minutes)

State what event marks a transaction's transition from the growing phase to the shrinking phase.

Done when: releasing its first lock is correctly named as the triggering event.

Hint

Releasing its first lock.

Medium

Medium 1: Detect a two-phase locking violation (25 minutes)

A transaction acquires locks on rows A and B, releases A, then attempts to acquire a lock on row C. Determine whether this violates two-phase locking, and why.

Done when: yes is correctly concluded, since the transaction entered its shrinking phase upon releasing A, and acquiring a new lock on C afterward violates the rule against acquiring locks during the shrinking phase.

Hint

Yes, since releasing A already moved the transaction into its shrinking phase, and acquiring a lock on C afterward violates the rule against acquiring new locks during that phase.

Medium 2: Explain why shared locks can coexist (25 minutes)

Explain why multiple transactions can hold a shared lock on the same row at the same time, while only one transaction can hold an exclusive lock.

Done when: the explanation correctly notes concurrent reads do not conflict with each other and can safely coexist, while a write needs sole access to avoid conflicting with any other read or write happening at the same time.

Hint

Concurrent reads do not conflict and can safely coexist under shared locks, while a write needs sole, exclusive access to avoid conflicting with any simultaneous read or write.

Medium 3: Trace a simple two-transaction lock sequence (30 minutes)

Transaction A acquires a shared lock on row X, then transaction B requests an exclusive lock on row X. Describe what happens to transaction B's request, and why.

Done when: the description correctly states transaction B must wait, since an exclusive lock cannot be granted while any shared lock is still held on the same item.

Hint

Transaction B must wait, since an exclusive lock requires excluding every other lock, including the shared lock transaction A is still holding.

Hard

Hard 1: Explain why releasing a lock early would risk correctness (30 minutes)

Explain, in terms of the precedence graph from two pages ago, why allowing a transaction to acquire a new lock after it has already started releasing others could break the serializability guarantee.

Done when: the explanation correctly notes that mixing acquiring and releasing could allow the specific interleaved patterns that create a precedence-graph cycle, which the strict growing-then-shrinking separation is specifically designed to rule out.

Hint

Mixing acquiring and releasing could reintroduce the specific interleaved lock patterns that create a precedence-graph cycle, which the growing-then-shrinking separation is specifically designed to prevent from ever forming.

Hard 2: Connect two-phase locking to the strict schedule property (35 minutes)

Explain how holding locks until a transaction's shrinking phase, often delayed until the transaction actually commits or aborts in practice, relates to the strict schedule property covered two pages ago.

Done when: the explanation correctly notes that if locks are held until commit or abort rather than released as soon as the shrinking phase could allow, this directly produces a strict schedule, since no other transaction can read or write a value until the holder has committed or aborted.

Hint

Holding locks until commit or abort, rather than releasing earlier in the shrinking phase, directly produces a strict schedule, since no other transaction can read or write that value until the holder has definitively finished, matching the strict schedule definition exactly.

Hard 3: Reason about concurrency cost under two-phase locking (40 minutes)

A transaction acquires an exclusive lock early in its execution but does not actually finish its work, and therefore does not release that lock, for a long time afterward. Explain the concurrency cost this imposes on other transactions, and connect it to the deadlocks covered on a later page.

Done when: the explanation correctly notes other transactions needing a conflicting lock on that same item must wait the entire time, and that long-held locks combined with multiple transactions waiting on each other's locks is exactly the setup that can lead to a deadlock, covered in depth on a later page in this level.

Hint

Every other transaction needing a conflicting lock on that same item must wait for the entire duration the lock is held, and this exact pattern, multiple transactions each waiting on locks held by others, is the setup that can produce a deadlock, the subject of a later page in this level.