[Database] Concurrency Control

Concurrency Control : Locking Approach

Lock-Based Protocols

• A locking is a mechanism to control concurrent access to a data item; It obtains permission to read or write a data item for a transaction; Data items can be locked in two modes;
  • (1) S-Lock(A) : Shared
    • : If a transaction T obtains S-Lock on data item A, T can read A.
  • (2) X-Lock(A) : Exclusive
    • : If a transaction T obtains X-Lock on data item A, T can write A.
  • (3) Unlock(A);
    • : If a transaction T has finished read/write on data item A, T releases all locks on A

Compatible Locking Table

• More than one transaction applies S-lock on data item for reading its value; Only one transaction apply X-lock on data item for writing.
• For example, suppose that Ti holds a X-LOCK for data item A; If Tj requests S-LOCK for the A, then this request is denied; Tj must wait until Ti releases its X-LOCK.
• Thus, each transaction is
  • (1) allowed to read/write, or
  • (2) delayed until it is safe to execute read/write.

Basic Locking Protocol

• For any data item A, every transaction T must obey the following rules;
  • (1) T must request S-LOCK(A) (or X-LOCK(A)) before any READ(A) is performed in T.
  • (2) T must request X-LOCK(A) before any WRITE(A) (or READ(A)) is performed in T.
  • (3) T must wait if the request lock (for A) is not compatible with other lock held by another transaction.
  • (4) T must request UNLOCK(A) after all READ(A) and WRITE(A) are completed in T.

Example

Two-Phase Locking (2PL) Protocol

• Every transaction must obey basic locking protocol; In addition, in every transaction, all locks precede all unlock requests; It consists of two phases;
  • Phase 1 : Locking (= Growing) phase
    • : New locks are acquired, but none can be released.
  • Phase 2 : Unlocking (= Shrinking) phase
    • : Existing locks can be released, but no new locks can be acquired.
• A transaction can not release any locks until it once acquires locks on all items it needs.
• A transaction can not request additional locks once it releases any locks.

• 2PL Schedule is conflict equivalent to serial order of transactions according to their first unlocks; That means the order in which transactions enter their shrinking phase.
• If every transaction in a schedule obeys 2PL, it is conflict serializable; 2PL is a concurrency control used in most database systems today.

Example

• 2 PL Protocol : Schedule A

• 2 PL Protocol : Schedule B

Performance Degraded

• 2PL can limit the amount of concurrency.
• 2PL is selfish: may favor for long-term transactions.
• Suppose T1 accesses A, B, C, D, E, . . , sequentially, and T2 accesses B

Deadlocks

• T1 is waiting for T2 to release lock on A, and T2 is waiting for T1 to release lock on B;
• T1 can not release a lock on B; T2 also can not release a lock on A
• Other transactions can not also access either A or B.
• Deadlock: Cycle of transactions waiting for locks to be released by each other. Neither transaction can proceed and they wait forever.
• Two ways of dealing with deadlocks:
  • Deadlock prevention
  • Deadlock detection