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
    • xli(A) = transaction Ti requests an exclusive lock for A
      • if another txn holds any lock for A, Ti 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
    • sli(A) = transaction Ti requests a shared lock for A
      • if another txn holds an exclusive lock for A, Ti must wait until that lock is released

Recall: Two-phase Locking

  • Can we impose additional locking rules that ensure recoverability and cascadelessness?
  • 2PL guarantees serializability.
  • Recoverable? Cascadeless?
    • 2PL alone does not guarantee either of them.
  • Example:    2PL? yes

not recoverable. why not?

r1(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

  • Under strict locking, a txns must 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

  • Nonetheless, strict locking is not enough to guarantee serializability.

  • Under strict locking, it’s possible to get a schedule that does not correspond to any equivalent serial schedule.

  • Rigorous locking requires txns to hold all locks until commit/abort. (rigorous + 2PL = rigorous 2PL)
  • It guarantees that transactions commit in the same order as they would in the equivalent serial schedule.

Deadlock

  • Consider the following schedule:

element A A element B B T2 exclusive · T2 unlocked T2 acquires an exclusive lock on A T2 exclusive · T2 T1 shared · T1 T1 acquires a shared lock on B T2 exclusive · T2 T1 shared · T1 T2 requests xl(B) T2 exclusive · T2 T1 shared · T1 T2 waits for T1 T1 holds B, so the exclusive request waits T2 exclusive · T2 T1 shared · T1 T2 waits for T1 T1 requests sl(A) T2 exclusive · T2 T1 shared · T1 T1 waits for T2 T2 waits for T1 each holds one lock and waits for the other
  • 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 in a few minutes how to deal with this.

Lock Upgrades

  • It can be problematic to acquire an exclusive lock earlier than necessary.
  • Consider a transaction that first reads an item and then writes to it (very common pattern).
  • The transaction must acquire an exclusive lock to write the item.
  • But it only needs a shared lock to read the item.
  • 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

  • Nonetheless, under any of these locking schemes, we can still get deadlocks.
    • deadlocks can occur involving only exclusive locks
  • 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

Detecting and Handling Deadlocks (cont.)

Here is an example:

  • In this situation, the DBMS must
    • detect the deadlock
    • choose one of the transactions to abort (rollback)