UoL CS Notes
Menu

More Flexible Locks, Deadlock & Granularity

COMP207 Lectures

Basic locks are very simple, but not very precise:

  • If we just want to read we need a full lock, even though conflicts don’t happen on a read-read.

2PL Issues

2PL ensure conflict-serialisability, by might lead to:

  • Deadlocks - Where transactions are forced to wait forever.
  • Other issues to be shown later.

Deadlocks in 2PL

If an object is already locked by one transaction and then another transaction also want a lock on the same object then there is a risk of deadlock.

This is as all the lock occur in the first phase so there is no chance that the object can be unlocked in order for the second transaction to use it.

Different Lock Modes

To fix the deadlock issue we can implement different lock modes that can allow read only access.

Shared & Exclusive Locks

Shared Locks (Read Lock):

  • Requested by transactions to read an item $X$.
  • Granted to several transactions at the same time.

The operation can be represented as s-lock(X).

Exclusive Locks (Write Lock):

  • Requested be transactions to write an item $X$.
  • Granted to at most one transaction at a time.

The operation can be represented at x-lock(X).

Additional Rules:

  • Shared lock on $X$ is only granted if no other transaction hold an exclusive lock on $X$.
  • Exclusive lock on $X$ is granted only if no other transaction holds a lock of any kind on $X$.

Schedules with Shared & Exclusive Locks

We can use the following shorthand notation to write schedules:

  • $sl_i(X)$ - Transaction $i$ requests a shared lock for item $X$.
  • $xl_i(X)$ - Transaction $i$ requests an exclusive lock for item $X$.
  • $u_i(X)$ - Transaction $i$ releases all locks on item $X$.

For the following transactions:

$T_1$ $T_2$
s-lock(X) s-lock(X)
read(X) read(X)
unlock(X) x-lock(X)
  write(X)
  unlock(X)

We could write the following schedule:

\[S: \mathbf{sl_1(X)};r_1(X);\mathbf{sl_2(X)};r_2(X);\mathbf{u_1(X);xl_2(X)};w_2(X);\mathbf{u_2(X)};\]

An individual transaction may hold both a shared lock and an exclusive lock for the same item $X$.

Upgrading Locks Issues

A shared lock on $X$ can be upgraded later to an exclusive lock on $X$. You can use this to be friendly to other transactions.

There is still a risk of deadlocks using this method.

Update Locks

These avoid deadlock by giving an indication that you want to write later but not right now.

Update Lock:

  • Requested by a transaction to read an item.
  • May be upgraded to an exclusive lock later (shared locks can no longer be upgraded).
  • Granted to at most one transaction at a time.

The operation can be represented as u-lock(X) or $ul_i(X)$.

Inter-Transaction Lock Policy

You can check if you can use a particular type of lock using the following table:

  Shared Update Exclusive
Shared Yes Yes No
Update No No No
Exclusive No No No

The lock you request is on the top and the locks other transactions hold for the same object are on the side.

2PL with Different Lock Modes

To incorporate shared, upgrade and exclusive locks with 2PL then we just use the same rules as before but for all locks:

  • All lock operations (shared, upgrade and exclusive) precede all unlocks.

This still guarantees conflict-serialisability.

Locks with Multiple Granularity

DBMS may use locks at different levels of granularity (from course to fine):

  • Locking relations.
    • Locking disk blocks.
      • Locking tuples.

Here are some examples on how granular locks might be used:

SELECT name FROM Student WHERE studentID = 123456;

A shared lock on the tuple would suffice.

SELECT avg(salary) FROM Employee;

A shared lock on the relation might be necessary.

Trade-Offs

Lock at too coarse of granularity:

  • Low Overhead
    • Dont need to store as much information.
  • Less Degree of Concurrency
    • May cause unnecessary delays.

Lock at too fine granularity:

  • High Overhead
    • Need to keep track of all locked items.
  • High Degree of Concurrency
    • No unnecessary delays.

You should pay attention to the hierarchy to guarantee conflict-serialisability. The following should not happen:

  • A transaction holds a shared lock for a tuple, while another transaction holds an exclusive lock for the relation.

Intention Locks (Warning Locks)

With this method we use only shared and exclusive locks. These are made for locking with multiple granularity.

We gain the following intention locks:

  • IS - Intention to request a shared lock on a sub-item.
  • IX - Intention to requrest an exlclusive lock on a sub-item.

We have the following rules:

  • If a transaction want to lock an item $X$, it must first put an intention lock on the super-items of $X$.

    This is according to the granularity hierarchy above.

  • Shared locks are IS.
  • Exclusive locks are IX.

For example if I want to request a shared lock on a tuple I must then:

  • Request IS on the parent block.
  • Request IS on the block’s parent relation.

Policy For Granting Locks (Including Intention Locks)

You can check if you can use a particular type of lock using the following table:

  Shared (S) Exclusive (X) IS IX
Shared (S) Yes No Yes No
Exclusive (X) No No No No
IS Yes No Yes Yes
IX No No Yes Yes

The lock you request is on the top. You can grant the lock only if the types of locks held by other transactions are “yes” from the left.