Methods for Concurrency control
- Locking Methods
- Timestamp methods
- Optimistic methods
“A lock is a variable, associated with the data item, which controls the access of that data item.”
Locking is the most widely used form of the concurrency control.
Locks are further divided into three fields:
- Lock Granularity
- Lock Types
1. Lock Granularity :
Lock granularity indicates the level of lock use.
The size of the data item chosen as the unit of protection by a concurrency control program is
Locking can take place at the following level :
- Database level.
- Table level.
- Page level.
- Row (Tuple) level.
- Attributes (fields) level.
Database level Locking :
- At database level locking, the entire database is locked. Thus, it prevents the use of any tables in the database by transaction T2 while transaction T1 is being executed.
- Database level of locking is suitable for batch processes. Being very slow, it is unsuitable for on-line multi-user DBMSs.
Table level Locking :
- At table level locking, the entire table is locked. Thus, it prevents the access to any row (tuple) by transaction T2 while transaction T1 is using the table.
- Less restrictive than database level lock.
- It can cause traffic jam when many transactions are waiting to access same table. Not suitable for multi-user DBMSs.
Page level Locking :
- At page level locking, the entire disk-page (or disk-block) is locked.
- A table can span several pages, and a page can contain several rows (tuples) of one or more tables.
- Page level of locking is most suitable for multi-user DBMSs.
Row (Tuple) level Locking :
- At row level locking, particular row (or tuple) is locked.
- A lock exists for each row in each table of the database.
- The DBMS allows concurrent transactions to access different rows of the same table, even if the rows are located on the same page.
- The row level lock is much less restrictive than database level, table level, or page level locks.
- The row level locking improves the availability of data. However, the management of row level locking requires high overhead cost.
Attributes (fields) level Locking :
- At attribute level locking, particular attribute (or field) is locked.
- Attribute level locking allows concurrent transactions to access the same row, as long as they require the use of different attributes within the row.
- The attribute level lock yields the most flexible multi-user data access.
- It requires a high level of computer overhead.
2. Lock Types :
The DBMS mailnly uses following types of locking techniques.
- Binary Locking
- Shared / Exclusive Locking
- Two – Phase Locking (2PL)
• Binary Locking:
Binary lock can have two states:
• Locked (or ‘1′)
• Unlocked (or ‘0′)
- If a database object is locked then no other transaction can use that object.
- This technique use two operations as given below:
- Lock (X): To lock the data item X .
- Unlock (X): To unlock(release) the data item X .
- If any transaction need to access data item X then it calls Lock (X) . Means Lock(X) = 1 & another transaction need to access same data item X , it needs to wait.
- When transaction completes its operation in X , it calls Unlock (X) . It sets Lock(X) = 0.
- Advantage: Easy to implement.
- Disadvantage: Two simultaneous Read can be performed on same data but this technique doesn’t allow such type of concurrent access.
• Shared/Exclusive Locking:
- This technique uses two different type of locks:
• Shared Locks
• Exclusive Locks
• Shared Locks:
- These locks are also referred as Read locks and denoted by ‘ S’ .
- If any transaction has obtained shared lock on data item X then it can read X but can’t write X .
- Multiple shared lock can be placed simultaneously on a data item.
• Exclusive Locks:
- These lock are referred as Write locks and denoted by ‘ X ‘.
- If any transaction has obtained exclusive lock on data item X then it can read X as well as write X .
- Only one exclusive lock can be placed on a data item at a time.
- Advantage: Provide optimal concurrency.
- Disadvantage: More complex to implement compared to Binary Locking.
• Two-Phase Locking
- The Two Phase Locking Protocol defines the rules of how to obtain the locks on a data item and how to release the locks.
- Two phase locking (2PL) is a concurrency control method that guarantees serializability .
- The Two Phase Locking Protocol assumes that a transaction can only be in one of two phases.
• Growing Phase
• Shrinking Phase
- In this phase the transaction may obtain locks , but cannot release any lock.
- The transaction enters the growing phase as soon as it acquires the first lock it wants.
- It cannot release any lock at this phase even if it has finished working with a locked data item.
- Ultimately the transaction reaches a point where all the lock it may need has been acquired. This point is called Lock Point .
- In this phase the transaction may release locks, but cannot obtain any new lock .
- After Lock Point has been reached, the transaction enters the shrinking phase.
- The transaction enters the shrinking phase as soon as it releases the first lock after crossing the Lock Point.
- Initially the transaction is in growing phase, that is the transaction acquires locks as needed. Once the transaction releases lock, it enters the shrinking phase and no more lock request may be issued.
- Upgrading of lock is not possible in shrinking phase , but it is possible in growing phase .
- Below given table shows Two Phase Locking Technique:
|t0||Lock – X (A)||acquire Exclusive lock on A.|
|t1||Read A||read original value of A|
|t2||A = A – 100||subtract 100 from A|
|t3||Write A||write new value of A|
|t4||Lock – X (B)||acquire Exclusive lock on B.|
|t5||Read B||read original value of B|
|t6||B = B + 100||add 100 to B|
|t7||Write B||write new value of B|
|t8||Unlock (A)||release lock on A|
|t9||Unock (B)||release lock on B|
- A deadlock is a condition in which two (or more) transactions in a set are waiting simultaneously for locks held by some other transaction in the set.
- Neither transaction can continue because each transaction in the set is on a waiting queue.
Time-stamp Method for Concurrency Control
- A time-stamp is a unique identifier used to identify the relative starting time of a transaction.
- This method uses either system time or logical counter to be used as a time-stamp .
- A time-stamp for transaction T is denoted by TS(T) .
- To implement this time stamping, following two time-stamp values are associated with each data item.
• Write time-stamp of data-item X is denoted by W-timestamp(X) .
• It specifies the largest timestamp of any transaction that execute write (X)
• Read time-stamp of data-item X is denoted by R-timestamp(X) .
• It specifies the largest timestamp of any transaction that execute Read (X) successfully.
The timestamp ordering protocol ensures that any conflicting Read and Write operations are executed in timestamp order . This method operates as follow:
• If a transaction Ti issues Read (X) operation:
(a) If TS(Ti) < W-timestamp (X)
• Then, Ti needs to read a value of X that was already overwritten .
• Hence, the read operation is rejected , and Ti is rolled back.
(b) If TS(Ti) = W-timestamp (X)
• Then, the read operation is executed, and R-timestamp(X) is set to the maximum of R-timestamp(X) and TS(Ti) .
• If a transaction Ti issues Write (X) operation:
(a) If TS(Ti) < R-timestamp(X)
• Then, the value of X that Ti is producing was needed previously, and the system assumed that that value would never be produced.
• Hence, the write operation is rejected , and Ti is rolled back
(b) If TS(Ti) < W-timestamp(X)
• Then, Ti is attempting to write an obsolete (out-dated) value of X.
• Hence, this write operation is rejected , and Ti is rolled back.
(c) Otherwise, the write operation is executed , and W-timestamp(X) is set to TS(Ti) .
- Ensures serializability among multiple transactions running concurrently.
- Provide freedom from deadlock as no any locks are used in this method.
- Starvation for long transaction is possible, if a sequence of conflicting short transactions causes repeated restarting of the long transaction.
- Increase memory requirement and process overhead. Because two additional fields required in database to store R-Timestamp and W-Timestamp .
Optimistic Method for Concurrency Control
- In this method assume that conflicts are very rare . It allows transaction to run completely. And it checks for conflicts before they commit .
- It is also known as validation or certification method.
- Execution of transaction Ti is done in three phases.
- Read Phase
- Validation Phase
- Write Phase
1. Read Phase:
- The transaction reads input values from the database, performs computation and records the updates in
a temporary local variable that is not accessed by other transactions.
2. Validation Phase:
- Transaction Ti performs a
validation test ” to determine if local variables can be written without violating serializability.
- If test is positive , then transaction goes to the write phase otherwise changes are
discarded and transaction Ti is restarted .
3. Write Phase:
- In this phase changes , recorded in local variables are permanently applied to the database .
- It is very efficient when conflicts are rare.
- If rollback is required then database not involved. So, it is less expensive .
- Conflict requires entire transaction to rollback. So, it becomes more expensive .
- They may suffer from starvation.