Summary of 8 April 1997
We covered the following topics on April 8
Problems in 2 Phase Locking
There are chiefly two problems in
2 phase locking:
- deadlocks, where each processor is waiting for a resource held by the
other
- cascaded rollbacks, where if one transaction rolls back, it causes some
other transaction to roll back and so on, thus causing all the transactions
to roll back
The solution is to use
-
TimeStamps, where each transaction is assigned an unique timestamp and
conflicts are resolved by the timestamp ordering of transactions.
-
If the data is organized in a hierarchical structure, then this can be
exploited to allow some locks to be acquired after some other locks have are
released
Conflict resolution rules
- wait wherein the requesting transaction blocks till the other
completes
- restart one of the conflicting transactions is restarted by
- die: abort and restart the transaction
- wound:try to abort the transaction holding the lock, but if this
transaction is fast enough then it is safe and releases the lock anyway
The Wait-die algorithm
if( T1 < T2 ) // T1 older
then T1 waits
else T1 aborts
The Wound-wait algorithm
if( T1 < T2 ) // T1 older
then T1 wounds T2
else T1 waits
The advantage of the above method is that there is no possibility of deadlock,
as time is a linear order and you cannot have cycles in a linear order. The
flip side is that this is a cautious approach, aborting at the slightest
indication of a problem, and one does not try hard enough.
Hierarchical structure of data
There are three rules that are to be followed before locking a resource:
- A transaction can set a lock on R iff it is holding a lock on
R's ancestor
- After unlocking R, the transaction cannot lock R again
- A transaction can only access R iff it holds a lock on R
An example of the locking and unlocking pattern that can follow is:
|
Example operations
|
Figure
|
lock B
lock D
use D
lock I
unlock D
lock G
use G
unlock I
unlock G
unlock B
|
|
Each object has:
- a read timestamp : R-ts (object)
- a write timestamp: W-ts (object)
Each transaction has a TS that it appends to all operations:
read(object, TS)
write(object, TS)
The rules of the algorithm are:
read(object, TS)
if TS < W-ts(object) then abort
else R-ts(object) = max(R-ts(object),TS)
write(object, TS)
if TS < R-ts(object) or TS < W-ts(object)
then abort
else W-ts(object) = TS
Although the basic timestamp ordering algorithm does not use locks, it still
has aborts. The approach used in the multiversion timestamp algorithm is that
it allows operations that did not happen that way but are not inconsistent
with history. So a read operation never has an abort and a write operation can
have an abort only if it tries to overwrite a newer value with an outdated
value and there is a read operation following the write.
Multiversion TimeStamp Ordering
For each data object, maintain versions of:
- a list of R-ts
- a list of <W-ts, value> pairs
The rules of the algorithm are:
- read(object, TS)
read the version of object with the largest timestamp
less than TS and add TS to the object's R-ts list
- write(object, TS)
reject the operation if there exists a R-ts in the interval
from TS to the smallest W-ts that is larger than TS
else accept the operation and add < TS, v > to the version
Roundup
There is a lot of redundancy in maintaining all the lists but Timestamp
algorithms provide another method of solving concurrency problems especially
when we need an optimistic rather than a conservative approach.