What is a lock?
A mechanism to control concurrent access to a data item.
Exclusive (X) vs shared (S) lock.
X: the data item can be both read and written; requested with lock-X. S: the data item can only be read; requested with lock-S.
To whom are lock requests made, and when can the transaction proceed?
To the concurrency-control manager; the transaction can proceed only after the request is granted.
Which locks are compatible?
Only shared with shared: any number of transactions can hold S-locks on an item; if any transaction holds an X-lock, no other transaction may hold any lock on it.
What happens if a requested lock cannot be granted?
The requesting transaction is made to wait till all incompatible locks held by other transactions have been released; then the lock is granted.
T2: lock-S(A); read(A); unlock(A); lock-S(B); read(B); unlock(B); display(A+B). Why is this locking not sufficient to guarantee serializability?
It unlocks A before locking B; if A and B get updated in between the reads, the displayed sum A + B would be wrong.
What is a locking protocol?
A set of rules followed by all transactions while requesting and releasing locks; locking protocols restrict the set of possible schedules.
What are the two phases of two-phase locking?
Growing phase: may obtain locks, may not release locks. Shrinking phase: may release locks, may not obtain locks.
What does two-phase locking guarantee, and in what order are transactions serialized?
Conflict-serializable schedules; transactions can be serialized in the order of their lock points (where each acquired its final lock).
Lock conversions in 2PL: upgrade vs downgrade.
Upgrade: convert lock-S to lock-X — allowed in the first (growing) phase. Downgrade: convert lock-X to lock-S — allowed in the second (shrinking) phase.
What is a deadlock, and how is it handled?
A situation where neither transaction can make progress because each waits for the other to release a lock. One of them must be rolled back and its locks released.
Does two-phase locking ensure freedom from deadlocks?
No — two-phase locking does not ensure freedom from deadlocks.
Give two examples of starvation.
A transaction waits for an X-lock while a sequence of other transactions are granted S-locks on the same item; the same transaction is repeatedly rolled back due to deadlocks.
List the four reasons for starvation.
Unfair waiting scheme for locked items (priority queue); victim selection (same victim repeatedly); resource leak; denial-of-service attack.
How does the lock manager answer a lock request?
With a lock grant message, or a message asking the transaction to roll back (in case of a deadlock); the requesting transaction waits until it is answered.
What is the lock table, and how is it usually implemented?
A data structure recording granted locks and pending requests; usually an in-memory hash table indexed on the name of the data item being locked.
When is a new lock request granted in the lock table?
It is added to the end of the queue for the data item and granted if it is compatible with all earlier locks.
What does an edge Ti → Tj in a wait-for graph mean?
Ti is waiting for Tj to release a data item. The edge is removed when Tj no longer holds a data item needed by Ti.
When is the system in a deadlock state?
If and only if the wait-for graph has a cycle; a deadlock-detection algorithm must be invoked periodically to look for cycles.
Name two deadlock prevention strategies.
Pre-declaration: each transaction locks all its data items before it begins execution. Partial ordering: a transaction locks data items only in the order of a partial order imposed on all items.
Wait-die: what happens to an older and to a younger requester?
Older requester (smaller timestamp) waits; younger requester dies (rolled back) and is restarted later with the same timestamp. Non-preemptive.
Wound-wait: what happens to an older and to a younger requester?
Older requester wounds the younger holder (the holder is rolled back and restarted with its timestamp); younger requester waits. Preemptive.
Wait-die vs wound-wait: preemption, waiting of older transactions, and number of rollbacks.
Wait-die: non-preemptive; older transactions must wait for younger ones; more aborts and rollbacks. Wound-wait: preemptive; older transactions never wait for younger ones; fewer aborts and rollbacks.
Why do wait-die and wound-wait avoid starvation?
A rolled back transaction is restarted with its original timestamp, so older transactions have precedence over newer ones.
Timeout-based schemes: how they work, pro and cons.
A transaction waits for a lock only for a specified time, then is rolled back and restarted, so deadlocks are not possible. Simple to implement, but starvation is possible and a good timeout value is difficult to determine.
Deadlock recovery: which victim, and how far to roll back?
Choose the victim that will incur minimum cost. Either total rollback (abort and restart) or, more effective, roll back only as far as necessary to break the deadlock.
How is starvation avoided in deadlock recovery?
Include the number of rollbacks in the cost factor, so the same transaction is not always chosen as victim.