Locking II

Strict/Rigorous Locks, Lock Upgrades, Deadlocks

Data Science 310

Boston University

Recall: Exclusive vs. Shared Locks

• An exclusive lock allows a transaction to write or read an item.
  • gives the txn exclusive access to that item
  • only one txn can hold it at a given time
  • xl_i(A) = transaction T_i requests an exclusive lock for A
    • if another txn holds any lock for A, T_i must wait until that lock is released
• A shared lock only allows a transaction to read an item.
  • multiple txns can hold a shared lock for the same data item at the same time
  • sl_i(A) = transaction T_i requests a shared lock for A
    • if another txn holds an exclusive lock for A, T_i must wait until that lock is released

Recall: Two-phase Locking

• 2PL guarantees serializability.
• Recoverable? Cascadeless?
  • 2PL alone does not guarantee either of them.
• Example:    2PL? yes

not recoverable. why not?

r₁(A) is a dirty read, and reader commits before writer.

not cascadeless. why not?

the dirty read. if T2 is rolled back after that read, T1 must be, too.

Strict Locking

• Strict locking makes txns hold all exclusive locks until they commit or abort.

• doing so prevents dirty reads, which means schedules will be recoverable and cascadeless

• strict + 2PL = strict 2PL

Rigorous Locking

• Under strict locking, it’s possible to get something like this:

• Rigorous locking requires txns to hold all locks until commit/abort.

• It guarantees that transactions commit in the same order as they would in the equivalent serial schedule.

• rigorous + 2PL = rigorous 2PL

Deadlock

• Consider the following schedule:

• This schedule produces deadlock.
  • T1 is waiting for T2 to unlock A
  • T2 is waiting for T1 to unlock B
  • neither can make progress!

• We’ll see later how to deal with this.

Lock Upgrades

• It can be problematic to acquire an exclusive lock earlier than necessary.

• Instead:
  • acquire a shared lock to read the item

• upgrade to an exclusive lock when you need to write

• may need to wait to upgrade if others hold shared locks

• Note: we’re not releasing the shared lock before acquiring the exclusive one. why not?

• doing so would violate 2PL!

A Possible Problem with Lock Upgrades

• Upgrades can lead to deadlock:
  • two txns each hold a shared lock for an item
  • both txns attempt to upgrade their locks
  • each txn waits for the other to release its shared lock
  • deadlock!
• Example:

Update Locks

• To avoid deadlocks from lock upgrades, some systems take the following approach:
  • don’t allow the upgrading of shared locks
  • provide a third lock mode known as an update lock
    • like a shared lock, it allows a txn to read an item
    • it can be upgraded to an exclusive lock

• only one txn can hold an update lock for a given item

• thus, we won’t get deadlocks from upgrades
• see next slide for more details

• if read-only → acquire a shared lock
• if read-modify-write (RMW) → acquire an update lock for the read, and upgrade it to exclusive for the write

Update Locks (cont.)

• To avoid deadlocks from lock upgrades, some systems provide two different lock modes for reading:
  • shared locks – used if you only want to read an item
  • update locks – used if you want to read an item and later update it

Different Locks for Different Purposes

• If you only need to read an item, acquire a shared lock.

• If you only need to write an item, acquire an exclusive lock.

• If you need to read and then write an item:
  • acquire an update lock for the read
  • upgrade it to an exclusive lock for the write

• this sequence of operations is sometimes called read-modify-write (RMW)

Compatibility Matrix with Update Locks

• When there are one or more shared locks on an item, a txn can still acquire an update lock for that item.
  • allows for concurrency on the read portion of RMW txns

• There can’t be more than one update lock on an item.
  • prevents deadlocks when upgrading from update to exclusive

• If a txn holds an update lock on an item, other txns can’t acquire any new locks on that item.
  • prevents the RMW txn from waiting indefinitely to upgrade

Example of Using Update Locks

Detecting and Handling Deadlocks

• When DBMS detects a deadlock, it rolls back one of the deadlocked transactions.

• How does it know when there is a deadlock?

• Can use a waits-for graph to detect the deadlock.

• the vertices are the transactions

• an edge from T1 → T2 means T1 is waiting for T2 to release a lock

• a cycle indicates a deadlock

• Example: