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.
댓글남기기