Database Concurrency Protocols

Two way phase locking 2PL

guarantees conflict serializability
may be subjected to deadlocks
doesnot guarantees cascading rollbacks
In expanding phase, number of locks can only increase
In shrinking phase locks only released

2PL is superset of SS2PL(rigourness)

Strict 2PL
For any two transactions T1, T2, if a write operation precedes a conflicting operation of T2 (either read or write), then the commit event of T1 also precedes that conflicting operation of T2.

Any strict schedule is cascadeless, but not the converse. Strictness allows efficient recovery of databases from failure.

//http://en.wikipedia.org/wiki/Schedule_%28computer_science%29#Strict

Release exclusive lock only after end of transaction that is unlock happens only after commit or abort
guarantees serialiability and recoverable schedule too
read locks can be released
S2PL class of schedule is (2PL intersection Strictness)
release its write locks only after it has ended
read locks are released regularly during phase 2
we need to know the phase 1 end seperate from transaction end


Transaction can be in following states

Running its executing
Ready its programs execution has ended and its waiting to be Ended
Ended or completed It is either commited or Aborted de

SS2PL Strong Strict 2PL (Rigorous )
release both locks only after END
has actully one phase only, no phase 2
SS2pL enforce both conflict serializability and strictness


Deadlock in 2PL

Other enforcing mechanism for serializability
Time stamp ordering
Correctness of database transaction is defined by its
serializability or isolation and its recoverability
relaxing the serializability criteria isolation levels
view and conflict serializability



Problem 1

Determine whether
1)schedule is serializable or not
2)schedule can be produced by 2PL
3)schedule can be produced by Strict 2PL

Schedule S1

T1	T2	T3
		r(D)
w(A)
	r(B)
w(B)
	r(D)
		w(D)

Solution

1) To check the serializability we draw the precedence graph of the schedule

http://www-stud.uni-due.de/~selastoe/?mdl=dbms&mode=precedence

T2--------->T1
 |
 |
 v
T3

Since the graph is acyclic, so its serializable

2)
Non-serializable schedules can not be 2PL or strict 2PL.
Subset of serializable schedules can be 2PL or strict 2PL

2PL protocol says for a transaction all locks should be requested before releasing any lock

T1	T2	T3
		Ls(D)
		r(D)
Lx(A)
w(A)
	Ls(B)
	r(B)
	Ls(D) U(B)
Lx(B)
w(B)
U(A) U(B)
	r(D)
	U(D)
		Lx(D)
		w(D)
		U(D)

 Fig. showing how 2 phase locking protocol works for this schedule


Here  transaction requested shared lock for read and exclusive lock for write
Shared locks on data item are compatible like here T2 requested shared lock on data item D which was shared locked by T3.

If we look at only the transaction lock requests we can see that for each transaction we first requested all the
locks before releasing any

T1	T2	T3
		Ls(D)
Lx(A)
	Ls(B)
	Ls(D) U(B)
Lx(B)
U(A) U(B)
	U(D)
		Lx(D)
		U(D)

 Fig showing only the lock request and lock release for all transactions



Ls = shared lock
Lx = Exclusive lock
 U = Unlock



converting shared lock to exclusive lock is part of growing phase while
converting exclusive lock to shared lock is part of shrinking phase

Problem read to write lock and write to read lock conversions
Solution A read lock can be converted to write lock if no other readers, this converion happens by first unlocking the data item and then acquiring the write lock, if the request are already queued by some other processes for write lock might not get lock instantly
write to read is always possible.

If transaction Ti has shared lock and transaction Tj request exclusive lock on same item first transaction Ti has to release the lock and then transaction Tj can acquire the lock

Problem consider schedule  S =T1 R(x), T2:R(Y) ,T1:W(z) , T1:commit, T3:R(y) , T3:r(z) ,T2 w(y), T3: w(x),T2:commit , T:commit

2PL
T1           T2            T3
Ls(x)
r(x)
               Ls(y)
               r(y)
Lx(z)
w(z)
U(x)U(z)
commit;
                                Ls(y)
                                 r(y)
                                Ls(z)
                                 r(z)
                                 Lx(x) U(y)
                 Lx(y)
                 w(y)
                 U(y)
                commit;
                               w(x)
                               U(x)
                              commit;

Strick 2PL would require that T2 gets the Lx(y) while T3 has shared lock on y but T3 commits after T2 request so it cannot get the Lx(y)

In the 2PL we are allowed to read or write even after some unlock only condition is no lock can come after first unlock

In S2pL all exclusive lock unlocks comes at the end after commit or abort

Dealing with Deadlock
Deadlock Prevention
A transaction locks all data item it refers to before execution this prevents deadlocks since transaction never has to wait
Another approach is to impose ordering on all the data items and to require that transactions lock data items only in sequence consistent with ordering  example tree protocol

Conservative 2PL uses this approach

Deadlock detection and resolution
wait for graph,created using lock table, is kept which is used to detect the  cycle  and then one of the transaction is rolled back
transactions are added to wait for graph as they get blocked

Deadlock Avoidance
some avoid deadlock by not letting the cycle to  complete, if discovers that blocking a transaction is likely to create a cycle it rollback the transaction
wound wait and wait die algorithms use timestampt to avoid deadlock by rolling back victim

Starvation
particular transaction never gets a chance to proceed further

 Timestamp Protocol
selects ordering among transaction in advance instead at time of execution

timestamp monotonically increasing
timestamp is assigned by system before transaction starts
timestamp for transaction determines serializability order thus if Ti < Tj then system must ensure that Ti appears before transaction Tj in schedule

we associate with each data item Q two timestamps
W-timestamp(Q) largest timestamp of any transaction that executed write (Q) successully
simliarly R-timestamp(Q) for read

Timestamp ordering Protocol
ensures conflict serializability
ensures freedom  from deadlock since no transaction ever waits , its just killed
possibility of starvation
can generate schedules not recoverable but can be guaranteed in several ways

1) when transaction T issues write(X)  check if
read_TS(X) > TS(T) or write < TS then some younger transaction has already read the data item X so abort
and rollback T
when transaction issues read(X)
if younger  transaction has already written to the data item X abort and rollback T
ensures that any conflicting operations are executed in timestamp order

Strict Timestamp Ordering
ensures strict schedule along with conflict serializable
instead of writing when transaction has higher timestamp then on data item it waits until transaction that wrote value of data item commits or aborts

Thomas write Rule
does not ensures conflict serializability
1)IF read_ts(X) >TS(T) that is some younger transaction read the data item before T
abort and rollback T and reject operation
2)write_ts(x) > ts(T) donot execute the write but continue and will be detected in 1)