CONCURRENCY CONTROL
When multiple transactions are trying to access the same sharable resource, there could arise many
problems if the access control is not done properly. There are some important mechanisms to which
access control can be maintained. Earlier we talked about theoretical concepts like serializability, but
the practical concept of this can be implemented by using Locks and Timestamps. Here we shall
discuss some protocols where Locks and Timestamps can be used to provide an environment in
which concurrent transactions can preserve their Consistency and Isolation properties.
Lock Based Protocol
A lock is nothing but a mechanism that tells the DBMS whether a particular data item is being used
by any transaction for read/write purpose. Since there are two types of operations, i.e. read and write,
whose basic nature are different, the locks for read and write operation may behave differently.
Read operation performed by different transactions on the same data item poses less of a challenge.
The value of the data item, if constant, can be read by any number of transactions at any given time.
Write operation is something different. When a transaction writes some value into a data item, the
content of that data item remains in an inconsistent state, starting from the moment when the writing
operation begins up to the moment the writing operation is over. If we allow any other transaction to
read/write the value of the data item during the write operation, those transaction will read an
inconsistent value or overwrite the value being written by the first transaction. In both the cases
anomalies will creep into the database.
The simple rule for locking can be derived from here. If a transaction is reading the content of a
sharable data item, then any number of other processes can be allowed to read the content of the
same data item. But if any transaction is writing into a sharable data item, then no other transaction
will be allowed to read or write that same data item.
Depending upon the rules we have found, we can classify the locks into two types.
Shared Lock: A transaction may acquire shared lock on a data item in order to read its
content. The lock is shared in the sense that any other transaction can acquire the shared lock
on that same data item for reading purpose.
Exclusive Lock: A transaction may acquire exclusive lock on a data item in order to both
read/write into it. The lock is excusive in the sense that no other transaction can acquire any
kind of lock (either shared or exclusive) on that same data item.
The relationship between Shared and Exclusive Lock can be represented by the following table
which is known as Lock Matrix.
Locks already existing
Locks to
Be granted
How Should Lock be Used?
In a transaction, a data item which we want to read/write should first be locked before the read/write
is done. After the operation is over, the transaction should then unlock the data item so that other
transaction can lock that same data item for their respective usage. In the earlier chapter we had seen
a transaction to deposit Rs 100/- from account A to account B. The transaction should now be written
as the following:
Lock-X (A); (Exclusive Lock, we want to both read A’s value and modify it)
Read A;
A = A – 100;
Write A;
Unlock (A); (Unlocking A after the modification is done)
Lock-X (B); (Exclusive Lock, we want to both read B’s value and modify it)
Read B;
B = B + 100;
Write B;
Unlock (B); (Unlocking B after the modification is done)
Shared Exclusive
Shared TRUE FALSE
Exclusive FALSE FALSE
And the transaction that deposits 10% amount of account A to account C should now be written as:
Lock-S (A); (Shared Lock, we only want to read A’s value)
Read A;
Temp = A * 0.1;
Unlock (A); (Unlocking A)
Lock-X (C); (Exclusive Lock, we want to both read C’s value and modify it)
Read C;
C = C + Temp;
Write C;
Unlock (C); (Unlocking C after the modification is done)
Let us see how these locking mechanisms help us to create error free schedules. You should
remember that in the previous chapter we discussed an example of an erroneous schedule:
T1 T2
Read A;
A = A – 100;
Read A;
Temp = A * 0.1;
Read C;
C = C + Temp;
Write C;
Write A;
Read B;
B = B + 100;
Write B;
We detected the error based on common sense only, that the Context Switching is being performed
before the new value has been updated in A. T2 reads the old value of A, and thus deposits a wrong
amount in C. Had we used the locking mechanism, this error could never have occurred. Let us
rewrite the schedule using the locks.
T1 T2
Lock-X (A)
Read A;
A = A – 100;
Lock-S (A)
Read A;
Temp = A * 0.1;
Unlock (A)
Lock-X (C)
Read C;
C = C + Temp;
Write C;
Unlock (C)
Write A;
Unlock (A)
Lock-X (B)
Read B;
B = B + 100;
Write B;
Unlock (B)
We cannot prepare a schedule like the above even if we like, provided that we use the locks in the
transactions. See the first statement in T2 that attempts to acquire a lock on A. This would be
impossible because T1 has not released the excusive lock on A, and T2 just cannot get the shared
lock it wants on A. It must wait until the exclusive lock on A is released by T1, and can begin its
execution only after that. So the proper schedule would look like the following:
T1 T2
Lock-X (A)
Read A;
A = A – 100;
Write A;
Unlock (A)
Lock-S (A)
Read A;
Temp = A * 0.1;
Unlock (A)
Lock-X (C)
Read C;
C = C + Temp;
Write C;
Unlock (C)
Lock-X (B)
Read B;
B = B + 100;
Write B;
Unlock (B)
And this automatically becomes a very correct schedule. We need not apply any manual effort to
detect or correct the errors that may creep into the schedule if locks are not used in them.
Two Phase Locking Protocol
The use of locks has helped us to create neat and clean concurrent schedule. The Two Phase Locking
Protocol defines the rules of how to acquire the locks on a data item and how to release the locks.
The Two Phase Locking Protocol assumes that a transaction can only be in one of two phases.
Growing Phase: In this phase the transaction can only acquire locks, but cannot release any
lock. The transaction enters the growing phase as soon as it acquires the first lock it wants.
From now on it has no option but to keep acquiring all the locks it would need. 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.
Shrinking Phase: After Lock Point has been reached, the transaction enters the shrinking
phase. In this phase the transaction can only release locks, but cannot acquire any new lock.
The transaction enters the shrinking phase as soon as it releases the first lock after crossing
the Lock Point. From now on it has no option but to keep releasing all the acquired locks.
When multiple transactions are trying to access the same sharable resource, there could arise many
problems if the access control is not done properly. There are some important mechanisms to which
access control can be maintained. Earlier we talked about theoretical concepts like serializability, but
the practical concept of this can be implemented by using Locks and Timestamps. Here we shall
discuss some protocols where Locks and Timestamps can be used to provide an environment in
which concurrent transactions can preserve their Consistency and Isolation properties.
Lock Based Protocol
A lock is nothing but a mechanism that tells the DBMS whether a particular data item is being used
by any transaction for read/write purpose. Since there are two types of operations, i.e. read and write,
whose basic nature are different, the locks for read and write operation may behave differently.
Read operation performed by different transactions on the same data item poses less of a challenge.
The value of the data item, if constant, can be read by any number of transactions at any given time.
Write operation is something different. When a transaction writes some value into a data item, the
content of that data item remains in an inconsistent state, starting from the moment when the writing
operation begins up to the moment the writing operation is over. If we allow any other transaction to
read/write the value of the data item during the write operation, those transaction will read an
inconsistent value or overwrite the value being written by the first transaction. In both the cases
anomalies will creep into the database.
The simple rule for locking can be derived from here. If a transaction is reading the content of a
sharable data item, then any number of other processes can be allowed to read the content of the
same data item. But if any transaction is writing into a sharable data item, then no other transaction
will be allowed to read or write that same data item.
Depending upon the rules we have found, we can classify the locks into two types.
Shared Lock: A transaction may acquire shared lock on a data item in order to read its
content. The lock is shared in the sense that any other transaction can acquire the shared lock
on that same data item for reading purpose.
Exclusive Lock: A transaction may acquire exclusive lock on a data item in order to both
read/write into it. The lock is excusive in the sense that no other transaction can acquire any
kind of lock (either shared or exclusive) on that same data item.
The relationship between Shared and Exclusive Lock can be represented by the following table
which is known as Lock Matrix.
Locks already existing
Locks to
Be granted
How Should Lock be Used?
In a transaction, a data item which we want to read/write should first be locked before the read/write
is done. After the operation is over, the transaction should then unlock the data item so that other
transaction can lock that same data item for their respective usage. In the earlier chapter we had seen
a transaction to deposit Rs 100/- from account A to account B. The transaction should now be written
as the following:
Lock-X (A); (Exclusive Lock, we want to both read A’s value and modify it)
Read A;
A = A – 100;
Write A;
Unlock (A); (Unlocking A after the modification is done)
Lock-X (B); (Exclusive Lock, we want to both read B’s value and modify it)
Read B;
B = B + 100;
Write B;
Unlock (B); (Unlocking B after the modification is done)
Shared Exclusive
Shared TRUE FALSE
Exclusive FALSE FALSE
And the transaction that deposits 10% amount of account A to account C should now be written as:
Lock-S (A); (Shared Lock, we only want to read A’s value)
Read A;
Temp = A * 0.1;
Unlock (A); (Unlocking A)
Lock-X (C); (Exclusive Lock, we want to both read C’s value and modify it)
Read C;
C = C + Temp;
Write C;
Unlock (C); (Unlocking C after the modification is done)
Let us see how these locking mechanisms help us to create error free schedules. You should
remember that in the previous chapter we discussed an example of an erroneous schedule:
T1 T2
Read A;
A = A – 100;
Read A;
Temp = A * 0.1;
Read C;
C = C + Temp;
Write C;
Write A;
Read B;
B = B + 100;
Write B;
We detected the error based on common sense only, that the Context Switching is being performed
before the new value has been updated in A. T2 reads the old value of A, and thus deposits a wrong
amount in C. Had we used the locking mechanism, this error could never have occurred. Let us
rewrite the schedule using the locks.
T1 T2
Lock-X (A)
Read A;
A = A – 100;
Lock-S (A)
Read A;
Temp = A * 0.1;
Unlock (A)
Lock-X (C)
Read C;
C = C + Temp;
Write C;
Unlock (C)
Write A;
Unlock (A)
Lock-X (B)
Read B;
B = B + 100;
Write B;
Unlock (B)
We cannot prepare a schedule like the above even if we like, provided that we use the locks in the
transactions. See the first statement in T2 that attempts to acquire a lock on A. This would be
impossible because T1 has not released the excusive lock on A, and T2 just cannot get the shared
lock it wants on A. It must wait until the exclusive lock on A is released by T1, and can begin its
execution only after that. So the proper schedule would look like the following:
T1 T2
Lock-X (A)
Read A;
A = A – 100;
Write A;
Unlock (A)
Lock-S (A)
Read A;
Temp = A * 0.1;
Unlock (A)
Lock-X (C)
Read C;
C = C + Temp;
Write C;
Unlock (C)
Lock-X (B)
Read B;
B = B + 100;
Write B;
Unlock (B)
And this automatically becomes a very correct schedule. We need not apply any manual effort to
detect or correct the errors that may creep into the schedule if locks are not used in them.
Two Phase Locking Protocol
The use of locks has helped us to create neat and clean concurrent schedule. The Two Phase Locking
Protocol defines the rules of how to acquire the locks on a data item and how to release the locks.
The Two Phase Locking Protocol assumes that a transaction can only be in one of two phases.
Growing Phase: In this phase the transaction can only acquire locks, but cannot release any
lock. The transaction enters the growing phase as soon as it acquires the first lock it wants.
From now on it has no option but to keep acquiring all the locks it would need. 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.
Shrinking Phase: After Lock Point has been reached, the transaction enters the shrinking
phase. In this phase the transaction can only release locks, but cannot acquire any new lock.
The transaction enters the shrinking phase as soon as it releases the first lock after crossing
the Lock Point. From now on it has no option but to keep releasing all the acquired locks.
0 comments:
Post a Comment