CSE Roadmap

Specialist tier · about 2 hours · 5 parts

Part 5 of 5 · 4 min read

Exercises

Easy

Easy 1: Describe how a deadlock forms (15 minutes)

State, in one sentence, the condition under which a deadlock forms between two transactions.

Done when: each transaction holding a lock the other is waiting for is correctly described.

Hint

Each transaction holds a lock the other is waiting for, so neither can proceed.

Easy 2: Name what a wait-for graph cycle proves (15 minutes)

State what a cycle in a wait-for graph proves.

Done when: a deadlock existing among the transactions on that cycle is correctly named.

Hint

A deadlock exists among the transactions that form that cycle.

Easy 3: Name what the database does to a deadlock victim (15 minutes)

State what happens to the transaction chosen as the deadlock victim.

Done when: it being aborted, releasing its locks, is correctly described.

Hint

It is aborted, and its locks are released so other transactions can proceed.

Medium

Medium 1: Build a wait-for graph from a scenario (25 minutes)

Transaction A holds a lock on row X and is waiting for a lock on row Y, held by transaction B; transaction B is waiting for a lock on row X, held by transaction A. Draw the resulting wait-for graph, and determine whether a deadlock exists.

Done when: an edge from A to B and an edge from B to A, forming a two-node cycle, is correctly identified, with a deadlock correctly concluded to exist.

Hint

An edge from A to B and an edge from B to A form a cycle, so yes, a deadlock exists.

Medium 2: Explain why prevention sacrifices flexibility (25 minutes)

Explain why requiring every transaction to acquire locks in a fixed order, as deadlock prevention does, imposes a real constraint on how transactions are written.

Done when: the explanation correctly notes that transactions must now be written, or their lock requests reordered, to always request locks in the agreed order, rather than in whatever order the transaction's own logic would naturally produce.

Hint

Lock requests must always follow the agreed fixed order, even if the transaction's own natural logic would have requested locks in a different order, constraining how transactions must be structured.

Medium 3: Decide between detection and prevention for a scenario (30 minutes)

A system has transactions that rarely need more than one lock at a time, making deadlocks extremely rare in practice. Decide whether deadlock detection or deadlock prevention is more appropriate, and explain why.

Done when: detection is reasonably chosen, with the explanation correctly noting that prevention's upfront constraint on lock ordering is not worth imposing when deadlocks are already rare, making occasional detection and victim selection a lower-cost approach overall.

Hint

Detection is more appropriate here, since deadlocks are already rare, making prevention's constant upfront lock-ordering constraint not worth its cost compared to occasionally detecting and resolving a rare deadlock.

Hard

Hard 1: Explain why a cycle is necessary, not just sufficient, for a deadlock (30 minutes)

Explain why the absence of a cycle in the wait-for graph guarantees no deadlock exists, not just that a cycle's presence guarantees one does.

Done when: the explanation correctly notes that if no cycle exists, every transaction's wait-for chain must eventually reach a transaction that is not waiting on anything, meaning that transaction can proceed, release its locks, and the chain behind it can then proceed in turn, ruling out an unresolvable circular wait entirely.

Hint

With no cycle, every wait-for chain must eventually reach a transaction not waiting on anything, which can then proceed and release its locks, allowing the rest of the chain to proceed in turn, so an unresolvable circular wait cannot exist.

Hard 2: Explain the cost trade-off of victim selection (35 minutes)

A database must choose which of several deadlocked transactions to abort as the victim. Explain what a poor victim-selection policy, such as always aborting the transaction that has done the most work so far, would cost compared to a better one.

Done when: the explanation correctly notes that aborting a transaction that has already done significant work wastes that work entirely, requiring it to be redone on restart, so a better policy would generally prefer aborting whichever deadlocked transaction has done the least work so far, minimizing wasted effort.

Hint

Aborting a transaction that already did significant work wastes all of that work, which must be redone on restart; a better policy minimizes wasted effort by preferring to abort whichever deadlocked transaction has done the least work so far.

Hard 3: Connect deadlock prevention to two-phase locking's growing phase (40 minutes)

Explain how a fixed lock-acquisition order, used for deadlock prevention, interacts with two-phase locking's growing phase, covered two pages ago, to make a circular wait structurally impossible.

Done when: the explanation correctly notes that if every transaction must acquire locks in the same fixed order during its growing phase, no transaction can ever be waiting for a lock earlier in that order while holding a lock later in it, which is exactly the pattern a circular wait would require, ruling it out entirely.

Hint

If every transaction acquires locks in the same fixed order during its growing phase, no transaction can ever hold a lock later in that order while waiting for one earlier in it, which is exactly the configuration a circular wait requires, so that configuration simply cannot arise.