CSc 417/517 Assignment # 8
Transaction Processing
Due: By the time of the final exam, if done by Wednesday, feedback
will be prompt.
The following 2 transactions execute the following steps in the order
indicated, unless something has to be delayed, or a transaction
aborted, in order to preserver serializability. The question is,
what will actually happen under these two alternative sets of rules.
Will a deadlock develop? If so, you may choose to abort either
transaction, and proceed with the other.
1. Two-phase locking rules
- A lock must be acquired on a data element prior to any access of
it.
- Once all locks have been acquired, locks may be released as soon
as the transaction has completed all operations on an element.
- "Dirty reads" are allowed. A transaction may read any element
once it acquires the lock. However, if it reads a value written by a
transaction which later aborts, the reading transaction must also abort.
- Because of 3, a transaction may not commit until the dirty read
is resolved, by the other transaction aborting or being likewise ready
to commit. Should two (or more) transactions get into this state
waiting for each other, all may commit.
- [If you don't like rules 3 & 4, revise rule 2 to prohibit
dirty reads]
- If there is a cyle in the graph of transactions waiting for locks
held by another, abort any one of them.
2. Timstamp serialization
- Transactions will be given a timestamp when they perform their
first database accesses, and serialized in that order. In this case T1
comes first, before T2.
- Multiple recent values of an element will be retained.
- Each data element's value also has write and read timestamps: wt: the transaction writing the
value; rt: the latest
transaction reading that value.
- A reading transaction will obtain the most recent value whose wt is less than (or equal) to its
timestamp. It will increase the rt
of this value to its timestamp if necessary.
- Late write aborts: A writing transaction will check that no value
of the element has a rt
greater than its timestamp, or else it aborts. (This is necessary
because the "younger" transaction should have read the value about to
be written.)
- [If you don't like "dirty reads" add a commit bit at rule 3, and
modify rule 4 appropriately]
1. Locking
Put in the lock and unlock statements required, and reorder the
statements as the locks require.
T1
|
T2
|
For your remarks:
|
read A
|
|
|
|
read C
|
|
write A
|
|
|
|
write C
|
|
read B
|
|
|
write B
|
|
|
|
read B
|
|
|
read A
|
|
read C
|
|
|
|
write A
|
|
commit
|
|
|
|
commit
|
|
2. Timstamping:
Write down the values (make up some) and their wt & rt, and
reorder the statements if necessary.