Concurrency control: locking, deadlocks and timestamps
Goals and assumptions
Use shared/exclusive locks and two-phase locking (2PL), distinguish its variants, diagnose wait-for cycles, and trace basic timestamp ordering. This lesson uses item-level locks with explicit releases and single-version timestamp rules unless stated otherwise. These protocol guarantees apply when all participating transactions follow the protocol. A plain read/write schedule does not reveal which locks were held unless the locking protocol is specified.
1. Shared and exclusive locks
A shared lock S(X) permits reading X. An exclusive lock X(X) permits writing and reading X. Different transactions may hold S locks on the same item together. An X lock conflicts with any S or X held by another transaction. This compatibility rule permits concurrent readers but excludes concurrent writers and readers of a writer-locked item. Do not confuse the symbol X for an item with the X lock mode.
A transaction may request upgrading S to X, but the upgrade waits until other holders release incompatible locks. Downgrading X to S reduces its permissions. Under 2PL, an upgrade is a growing-phase acquisition and a downgrade starts or belongs to the shrinking phase. Lock acquisition is permission to access, not the access itself.
Example: T1 and T2 both obtain S(A). Both can read A. If both request an upgrade to X(A) while retaining their S locks, each waits for the other; lock conversion can deadlock. A correct lock manager never grants both exclusive locks to resolve the wait.
2. Two-phase locking and variants
Basic 2PL has a growing phase during which locks may be acquired but not released, followed by a shrinking phase during which locks may be released but no new lock is acquired. The transaction's lock point is when it acquires its last lock. Ordering transactions by lock points gives a conflict-equivalent serial ordering, so 2PL ensures conflict serializability. It can still deadlock and can allow dirty reads if exclusive locks are released before commit.
Example violation: lock-S(A),read(A),unlock(A),lock-X(B),write(B). A new lock is acquired after a release; this is not 2PL even if these particular operations happen to appear in a serializable schedule. Protocol compliance is sufficient for the guarantee, not a necessary condition for every serializable schedule.
In the convention used here, strict 2PL holds all exclusive locks until commit/abort and follows ordinary 2PL for other locks. It gives conflict serializability and strict schedules. Shared locks may be released earlier only if no later lock acquisition/upgrade occurs. Rigorous 2PL holds both shared and exclusive locks until commit/abort; its serial order can follow commit order. Some materials use “strict 2PL” to mean the rigorous variant, so read the stated definition instead of relying on the label alone.
Conservative/static 2PL obtains all needed locks before it begins the transaction's data operations, atomically or with a wait-without-holding policy. Thus it avoids hold-and-wait deadlocks, at the cost of knowing the lock set in advance and potentially reduced concurrency. Merely requesting locks one by one at the beginning while retaining a partial set is not the deadlock-free conservative protocol.
3. Deadlock detection and prevention
A wait-for graph has Ti→Tj when Ti waits for a lock incompatible with one held by Tj. With the stated ordinary lock-wait model, a directed cycle indicates deadlock. A precedence graph, by contrast, records the order of already executed conflicting operations and tests serializability. Do not use these graphs interchangeably.
Worked deadlock: T1 holds X(A), T2 holds X(B). T1 requests X(B), giving T1→T2. T2 then requests X(A), giving T2→T1. A detector chooses a victim, aborts it, rolls back its effects and releases its locks, letting another transaction proceed. Choosing victims fairly matters: repeatedly aborting the same transaction can cause starvation. A timeout may suspect deadlock but does not prove a cycle.
Global lock ordering prevents circular wait if every transaction acquires item locks in the same total order and handles conversions consistently with the protocol. Timestamp-based prevention offers two classic policies. Let smaller timestamps denote older transactions. In wait-die, an older requester may wait for a younger holder, but a younger requester asking an older holder must abort. In wound-wait, an older requester aborts (“wounds”) a younger holder, while a younger requester waits for an older holder. Restarting with the same timestamp preserves age and helps prevent starvation under usual progress assumptions.
Worked comparison: T_old has timestamp 5 and T_young has 12. If young requests a lock held by old, wait-die aborts young while wound-wait makes young wait. If old requests a lock held by young, wait-die makes old wait while wound-wait aborts young. “Old always waits” and “young always aborts” are not universal across both protocols. These rules prevent deadlock; fairness and eventual resources are still needed for progress guarantees.
4. Basic timestamp ordering
Assign each transaction TS(T). For each item X keep R_TS(X), the largest timestamp of a transaction that successfully read X, and W_TS(X), the largest timestamp of a transaction that successfully wrote X. Initial values can be 0 when all transaction timestamps are positive. The protocol attempts to serialize transactions in timestamp order rather than making them wait for item locks.
Read rule for T reading X: if TS(T)<W_TS(X), abort/restart T because the value was already overwritten by a transaction that should come later. Otherwise allow the read and set R_TS(X)=max(R_TS(X),TS(T)).
Basic write rule for T writing X: if TS(T)<R_TS(X), abort T, because a later transaction already read a value inconsistent with this earlier write. Otherwise, if TS(T)<W_TS(X), abort T because a later write already happened. Otherwise allow the write and set W_TS(X)=TS(T). Equality is not the failing case; a transaction can access its own writes.
Worked trace: R_TS(X)=0,W_TS(X)=0. T20 reads X: allowed, so R_TS(X)=20. T10 then tries writing X: 10<20, so T10 aborts, even though W_TS is still 0. Alternatively, if T20 first writes X, W_TS becomes 20 and a later attempted read by T10 aborts because 10<20. Timestamp order is transaction age, not the wall-clock order in which requests reach the scheduler.
Basic timestamp ordering is conflict serializable in timestamp order and deadlock-free because requests do not wait for locks. Repeated restarts can cause starvation, and the basic rules alone do not guarantee recoverability or cascadelessness: a newer transaction may read an older transaction's uncommitted write. Strict timestamp variants add commit-related waiting; distinguish those variants from the basic no-wait rules.
5. Thomas write rule and scope extensions
Thomas write rule modifies the obsolete-write case: after first checking TS(T)<R_TS(X) and aborting if so, a write with TS(T)<W_TS(X) may be ignored rather than aborting the transaction. That write is obsolete because a later timestamp already supplied the version that should survive. The read-timestamp check remains essential. This extension can accept some view-serializable schedules that are not conflict serializable, so do not transfer the basic protocol's conflict-serializability claim unchanged.
Multiversion concurrency control keeps several versions and chooses a visible version according to its timestamp/snapshot rules. Older readers may then avoid blocking writers or aborting merely because a newer version exists. However, “MVCC” alone does not imply serializability: snapshot isolation can admit write skew. Predicate/range locking or suitable validation is needed when constraints involve sets of rows. If T1 tests that no row satisfies a predicate while T2 inserts such a row, locking only existing matching rows may miss this phantom. These are supporting cautions, not a full treatment of every industrial isolation implementation.
Exam checklist
Write down the exact protocol variant, lock compatibility and release points. For deadlock, draw waits on current holders; for serializability, draw ordered conflicts. For timestamp traces, update R_TS/W_TS only after successful operations and apply checks in the stated order. Do not equate deadlock-free with starvation-free, strict with serializable, or a protocol's sufficient guarantee with necessity for an individual schedule.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. Which lock pair held by different transactions on one item is compatible?
A. S and S B. S and X C. X and S D. X and X
Answer: A
A: Shared readers may coexist.
B: An exclusive lock excludes other shared holders.
C: An exclusive holder excludes another reader.
D: Two exclusive holders are not allowed.
P02. Which sequence violates basic 2PL?
A. Acquire A, acquire B, release A, release B B. Acquire A, release A, acquire B C. Acquire A, acquire B, commit, release both D. Acquire A, release A, commit
Answer: B
A: No acquisition follows a release.
B: A new lock is acquired in the shrinking phase.
C: Holding locks through commit respects 2PL.
D: No new acquisition occurs after release.
P03. Which protocol is deadlock-free by acquiring its whole lock set before data operations without holding a partial set while waiting?
A. Basic 2PL B. Strict 2PL alone C. Conservative 2PL D. Arbitrary lock upgrades
Answer: C
A: Basic 2PL can have circular waits.
B: Strictness does not remove lock deadlocks.
C: It eliminates hold-and-wait under the stated acquisition policy.
D: Competing upgrades can deadlock.
P04. Under wait-die, a younger transaction requests a lock held by an older transaction. What happens?
A. Younger waits B. Younger aborts C. Older aborts D. Both acquire exclusive access
Answer: B
A: That is the younger-requester rule in wound-wait, not wait-die.
B: Younger requesters die when the holder is older.
C: Wait-die does not wound the holder.
D: Incompatible locks cannot both be granted.
P05. Basic timestamp ordering: TS(T)=10, R_TS(X)=20, W_TS(X)=0. T requests write(X). Result?
A. Allow and set W_TS=10 B. Abort because 10<20 C. Wait for an item lock D. Ignore because W_TS is larger
Answer: B
A: The read timestamp check forbids this write.
B: A later transaction has already read X.
C: Basic timestamp ordering uses rejection, not lock waiting.
D: W_TS is 0, and the failed read-timestamp check requires abort even under Thomas rule.
P06. Thomas rule: TS(T)=10, R_TS(X)=5, W_TS(X)=20. A write by T is:
A. Applied, replacing the newer value B. Ignored as obsolete C. Aborted due to R_TS D. Blocked until W_TS decreases
Answer: B
A: It must not replace the later timestamp version.
B: The read check passes, but a newer write makes this write obsolete.
C: 10 is not less than 5.
D: Timestamps do not decrease to make the request valid.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Databases syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in