|
Chris Pollett >
Old Classes
> |
HW5 Solutions Page
20.21 Modify the data structures for multiple-mode locks and the algorithms
for read_lock(X), write_lock(X), and unlock(X) so that a upgrading and
downgrading of locks is possible.
We need to add to our data structure for X a list of transactions that
have a lock on X. In the below, nil represents the empty list. LOCK_TRANS(X)
is our list of transaction with a lock on X, and DELETE(T, l) is the
function that deletes all occurrences of l from T. Finally, = condititionals
on lists do item-wise comparisons.
read_lock(X):
=========
B: if LOCK(X) = "unlocked"
then begin LOCK(X) <--"read-locked"
LOCK_TRANS(X) <-- append(this, nil)
end
else if LOCK(X) = "write_locked" AND
LOCK_TRANS(X) = append(this, nil)
then begin LOCK(X) <-- "read_locked"
notify any waiting transactions
in case they are waiting for a read
lock.
end
else if LOCK(X) = "read_locked"
then begin LOCK_TRANS(X) <-- append(this, LOCK_TRANS(X))
else begin wait (until LOCK(X) != "write_locked" and the lock manager
wakes up the transaction)
goto B
end
write_lock(X):
==========
B: if LOCK(X)="unlocked"
then begin LOCK(X)<--"write-locked"
LOCK_TRANS(X) <-- append(this, nil)
end
else if LOCK(X)="read-locked" AND LOCK_TRANS(X) = append(this, nil)
then begin LOCK(X)="write-locked"
end
else begin
wait (until (LOCK(X) = "unlocked" OR
(LOCK(X)="read-locked" AND LOCK_TRANS(X) = append(this, nil)))
AND the lock manager wakes up the transaction)
goto B
end
unlock(X):
=======
if LOCK(X)="write-locked"
then begin LOCK(X)<--"unlocked"
LOCK_TRANS(X) = nil
wake one of the waiting transactions if any
end
else if LOCK(X)="read-locked"
then begin
DELETE(this, LOCK_TRANS(X))
if (LOCK_TRANS(X) = nil)
then begin LOCK(X) <-- "unlocked"
wakeup one of the waiting transactions if any
end
end
20.24 Prove that cautious waiting avoids deadlock.
Proof: In cautious waiting, if T_i tries to lock X but T_j already has the
lock, then T_i is allowed to wait only if T_j is not blocked. Let b(T) denote
the time that a transaction becomes blocks. Then if T_i is allowed to wait on
T_j and they are both blocked we know that b(T_i) < b(T_j). Suppose now that
we are in a deadlock situation. This means that for some transactions
T_1,...,T_n we have T_1 is waiting on T_2, T_i is waiting on T_{i+1} and T_n is
waiting on T_1. Based on our earlier observations this means that:
b(T_1)< b(T_2) < ... <b(T_{n-1}) < b(T_n) <b(T_1).
So b(T_1) < b(T_1). But a fixed time can't be less than itself, so this is a
contradiction. Therefore, deadlocks cannot occur if cautious waiting is used.
21.23 Consider:
[start_transaction, T1]
[read_item, T1, A]
[read_item, T1, D]
[write_item, T1, D, 20]
[commit, T1]
[checkpoint]
[start_transaction, T2]
[read_item, T2, B]
[write_item, T2, B, 12]
[start_transaction, T4]
[read_item, T4, D]
[write_iem, T4,D, 15]
[start_transaction, T3]
[write_item, T3, C, 30]
[read_item, T4, A]
[write_item, T4, A, 20]
[commit, T4]
[read_item, T2, D]
[write_item, T2, D, 25] --crash
Suppose that we use the immediate update protocol with checkpointing. Describe
the recovery process from the system crash. Specify which transaction are
rolled back, which operations are redone and which are undone. Indicate if
there any cascading rollbacks.
For this recovery algorithm, the
list of commited transactions since the last checkpoint (LC) would be
{T4}
The list of active transactions (LA) would be
{T2, T3}
We first undo the write_operations of T2 and T3 in reverse order to how
they appear in the log:
[write_item, T2, D, 25] --> D now 15
[write_item, T3, C, 30] --> C now is whatever its initial value was.
[write_item, T2, B, 12] --> B now whatever its initial value was.
We then redo all the write operations of T4 in the order they appear:
[write_item, T4, D, 15]
[write_item, T4, A, 20]
There are no cascading rollbacks.
Here are some sessions I did to experiment with ALTER SESSION:
Neither READ COMMITTED nor SERIALIZIBLE transaction can experience
dirty reads; however, there are some kinds of transactions
that can distinguish these situations:
First, I give an example of a READ COMMITTED and a SERIALIZABLE session where
the READ COMMITTED session experiences a non-repeatable read. Then
we show that if we reverse the roles of the two sessions this does not happen.
Connected to:
Oracle9i Enterprise Edition Release 9.2.0.1.0 - Production
With the Partitioning, OLAP and Oracle Data Mining options
JServer Release 9.2.0.1.0 - Production
SQL> alter session set isolation_level=read committed;
Session altered.
SQL> select * from counter;
FIRSTDIGIT SECONDDIGIT
---------- -----------
1 1
SQL> /* update and commit by other transaction here */
SQL> select * from counter;
FIRSTDIGIT SECONDDIGIT
---------- -----------
2 1
SQL>
This is what the other transaction looked like:
Connected to:
Oracle9i Enterprise Edition Release 9.2.0.1.0 - Production
With the Partitioning, OLAP and Oracle Data Mining options
JServer Release 9.2.0.1.0 - Production
SQL> alter session set isolation_level=serializable;
Session altered.
SQL> select * from counter;
FIRSTDIGIT SECONDDIGIT
---------- -----------
1 1
SQL> update counter set firstdigit=2 where firstdigit=1;
1 row updated.
SQL> commit;
Commit complete.
SQL>
Now I let the READ COMMITTED transaction do the update and SERIALIZABLE one
do the two SELECTs:
Connected to:
Oracle9i Enterprise Edition Release 9.2.0.1.0 - Production
With the Partitioning, OLAP and Oracle Data Mining options
JServer Release 9.2.0.1.0 - Production
SQL> alter session set isolation_level=serializable;
Session altered.
SQL> select * from counter;
FIRSTDIGIT SECONDDIGIT
---------- -----------
2 1
SQL> /* update and commit done here */
SQL> select * from counter;
FIRSTDIGIT SECONDDIGIT
---------- -----------
2 1
SQL>
Here is the READ COMMITTED session:
Connected to:
Oracle9i Enterprise Edition Release 9.2.0.1.0 - Production
With the Partitioning, OLAP and Oracle Data Mining options
JServer Release 9.2.0.1.0 - Production
SQL> alter session set isolation_level=read committed;
Session altered.
SQL> select * from counter;
FIRSTDIGIT SECONDDIGIT
---------- -----------
2 1
SQL> update counter set firstdigit=1 where firstdigit=2;
1 row updated.
SQL> commit;
Commit complete.
SQL>
Next give show an example where a READ COMMITTED transaction experiences
a phantom read but show this does not happen if seesion was SERIALIZABLE.
Connected to:
Oracle9i Enterprise Edition Release 9.2.0.1.0 - Production
With the Partitioning, OLAP and Oracle Data Mining options
JServer Release 9.2.0.1.0 - Production
SQL> alter session set isolation_level=read committed;
Session altered.
SQL> select * from counter;
FIRSTDIGIT SECONDDIGIT
---------- -----------
1 1
SQL> select * from counter;
FIRSTDIGIT SECONDDIGIT
---------- -----------
2 2
1 1
SQL>
Here is the other session:
Connected to:
Oracle9i Enterprise Edition Release 9.2.0.1.0 - Production
With the Partitioning, OLAP and Oracle Data Mining options
JServer Release 9.2.0.1.0 - Production
SQL> alter session set isolation_level=serializable;
Session altered.
SQL> select * from counter;
FIRSTDIGIT SECONDDIGIT
---------- -----------
1 1
SQL> insert into counter values (2,2);
1 row created.
SQL> commit;
Commit complete.
SQL>
This does not happen if we reverse the roles of the two sessions:
Connected to:
Oracle9i Enterprise Edition Release 9.2.0.1.0 - Production
With the Partitioning, OLAP and Oracle Data Mining options
JServer Release 9.2.0.1.0 - Production
SQL> alter session set isolation_level=serializable;
Session altered.
SQL> select * from counter;
FIRSTDIGIT SECONDDIGIT
---------- -----------
1 1
SQL> /* insert commit done here */
SQL> select * from counter;
FIRSTDIGIT SECONDDIGIT
---------- -----------
1 1
SQL>
Here is what the other session looked like:
Connected to:
Oracle9i Enterprise Edition Release 9.2.0.1.0 - Production
With the Partitioning, OLAP and Oracle Data Mining options
JServer Release 9.2.0.1.0 - Production
SQL> alter session set isolation_level=read committed;
Session altered.
SQL> select * from counter;
FIRSTDIGIT SECONDDIGIT
---------- -----------
1 1
SQL> insert into counter values (2,2);
1 row created.
SQL> commit;
Commit complete.
SQL>
Now for the GRANT examples. First the session that did the granting:
C:\Documents and Settings\cpollett>sqlplus cpollett@ep
SQL*Plus: Release 9.0.1.3.0 - Production on Sun Dec 15 00:45:04 2002
(c) Copyright 2001 Oracle Corporation. All rights reserved.
Enter password:
Connected to:
Oracle9i Enterprise Edition Release 9.2.0.1.0 - Production
With the Partitioning, OLAP and Oracle Data Mining options
JServer Release 9.2.0.1.0 - Production
SQL> create table test1 (a int);
Table created.
SQL> insert into test1 values (3);
1 row created.
SQL> grant select on test1 to public;
Grant succeeded.
SQL> revoke select on test1 from public;
Revoke succeeded.
SQL> grant select on test1 to scott;
Grant succeeded.
SQL>
Next the session to who the grants were given:
C:\Documents and Settings\cpollett>sqlplus scott@ep
SQL*Plus: Release 9.0.1.3.0 - Production on Sun Dec 15 00:46:14 2002
(c) Copyright 2001 Oracle Corporation. All rights reserved.
Enter password:
Connected to:
Oracle9i Enterprise Edition Release 9.2.0.1.0 - Production
With the Partitioning, OLAP and Oracle Data Mining options
JServer Release 9.2.0.1.0 - Production
SQL> select * from cpollett.test1;
select * from cpollett.test1
*
ERROR at line 1:
ORA-00942: table or view does not exist
SQL> /*grant done to public. Note I inserted this line later*/
SQL> select * from cpollett.test1;
A
----------
3
SQL> /*revoke done */
SQL> select * from cpollett.test1;
SQL> /*grant done to scott */
SQL> select * from cpollett.test1;
A
----------
3
SQL>
|