Timestamp Protocol-Concurrency Control

Views:
 
Category: Entertainment
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

Concurrency Control (Timestamp Protocol):

Concurrency Control (Timestamp Protocol) By: Anshul Choure CS-1 3 rd year

Session Objectives :

Why Timestamp-Based Protocol? Assumptions Role in Serializability How to Apply Timestamp Working Session Objectives

Why……???:

There are Two basic Drawbacks of 2PL Protocol. Deadlock Starvation Why……???

How to…..????:

A number of different ways have been used to generate timestamp Use the value of the system's clock at the start of a transaction as the timestamp. Use a thread-safe shared counter that is incremental at the start of a transaction as the timestamp. A combination of the above two methods. How to…..????

Working :

Each transaction is issued a timestamp when it enters the system. If an old transaction T i has time-stamp TS( T i ), a new transaction T j is assigned time-stamp TS( T j ) such that TS( T i ) <TS( T j ). The protocol manages concurrent execution such that the time-stamps determine the serializability order. In order to assure such behavior, the protocol maintains for each data Q two timestamp values: W-timestamp ( Q ) is the largest time-stamp of any transaction that executed write ( Q ) successfully. R-timestamp ( Q ) is the largest time-stamp of any transaction that executed read ( Q ) successfully. Working

Ordering:

The basic TO algorithm compares the timestamp of T with read_TS(X) and write_TS(X) to ensure that the timestamp order of transaction execution is not violated . If this order is violated, then transaction T is aborted and resubmitted to the system as a new transaction with a new timestamp. If T is aborted and rolled back. Ordering

Ordering (Cont.):

The concurrency control algorithm must check whether conflicting operations violate the timestamp ordering in the following two cases: 1. Transaction T issues a write_item ( X ) operation: a. If read_TS( X ) > TS(T) or if write_TS( X ) > TS(T), then abort and roll back T and reject the operation. This should be done because some younger transaction with a timestamp greater than TS(T)—and hence after T in the timestamp ordering—has already read or written the value of item X before T had a chance to write X , thus violating the timestamp ordering. b. If the condition in part (a) does not occur, then execute the write_item( X ) operation of T and set write_TS( X ) to TS(T). Ordering (Cont.)

Ordering (Cont.):

2. Transaction T issues a read_item ( X ) operation: a. If write_TS( X ) > TS(T), then abort and roll back T and reject the operation. This should be done because some younger transaction with timestamp greater than TS(T)—and hence after T in the timestamp ordering—has already written the value of item_X before T had a chance to read X . b. If write_TS( X ) <= TS(T), then execute the read_item ( X ) operation of T and set read_TS( X ) to the larger of TS(T) and the current read_TS( X ). Ordering (Cont.)

Example Use of the Protocol:

Step 1 Example Use of the Protocol A partial schedule for several data items for transactions T 1 , T 2 , T 3 , T 4 , T 5 with timestamps t1 < t2 < t3 < t4 < t5 T 1 t1 T 2 t2 T 3 t3 T 4 t4 T 5 t5 read 2 ( Y ) read 1 ( X ) read 3 ( Y ) write 4 ( Y ) write 5 ( Z ) read 6 (Z) read 7 ( Y ) abort read 8 ( X ) write 9 ( Z ) abort write( Y ) write( Z ) R W R W R W 1 t5 2 t2 4 t3 6 t5 5 t3 X Y Z Now this needs to be rolled back

Thank you…..:

Thank you…..

authorStream Live Help