Optimistic Cocurrency Conrtol - Sacrifice Protocol

Real-time optimistic concurrency control protocols, OCC-Sacrifice, How does OCC-Sacrifice work?

Optimistic Concurrency Control – Sacrifice

This method includes priority mechanism in OCC-BC. This change makes this protocol as one of the real-time optimistic algorithms. OCC-Sacrifice works as follows;

All the transactions can work on any data items freely as in the case of OCC-BC.

• When a transaction reaches its validation stage, it checks for the conflicts in all the ongoing concurrent transactions.

• If there exists any conflicts, then check for the priority of the conflicting transactions.

• If one or more of those transactions’ priorities are higher than the validating transaction, then validating transaction gets restarted, i.e., it sacrificed for the higher priority transactions to meet their deadlines.

Pseudocode for OCC-Sacrifice

If Conflicting Higher Priority transactions in conflict set then

Restart the validating transaction;

Else

Restart transactions in conflict set;

Commit the validating transaction;

Example 1:

Consider three transactions T1, T2, and T3 that are working concurrently on some data items. Assume that the following are the complete information about these transactions;

• T1 and T2 are working on data item X, and T3 is working on data item Y.

• T1 is working with higher priority, T2 with lower priority and T3 with any priority.

• T2 has reached the end of the transaction. That means, T2 is the validating transaction according to the OCC-Sacrifice algorithm.

Now OCC-Sacrifice works as follows;

• T2 checks for a conflict with any other ongoing concurrent transactions for conflicts.

• T3 will not conflict with T2 because T3 is working on different data items. T1 will conflict with T2 as both are working on same data item X.

• The protocol now has to check for the priority of the conflicting transaction (T1). The priority of T1 is higher than that of T2 (Given, P(T1) > P(T2)). Now, according to the protocol, T2 (validating transaction) restarts by sacrificing the work done so far. This will lead T1 to reach its deadline without delay.

Example 2:

Consider three transactions T1, T2, and T3 that are working concurrently on some data items. Assume that the following are the complete information about these transactions;

• T1 and T2 are working on data item X, and T3 is working on data item Y.

• T2 is working with higher priority, T1 with lower priority and T3 with any priority.

• T2 has reached the end of the transaction. That means, T2 is the validating transaction according to the OCC-Sacrifice algorithm.

Now OCC-Sacrifice works as follows;

• T2 checks for a conflict with any other ongoing concurrent transactions for conflicts.

• T3 will not conflict with T2 because T3 is working on different data items. T1 will conflict with T2 as both are working on same data item X.

• The protocol now has to check for the priority of the conflicting transaction (T1). The priority of T2 is higher than that of T1 (Given, P(T2) > P(T1)). Now, according to the protocol, T2 (validating transaction) commits and T1 restarts by sacrificing the work done so far. This will lead T2 to reach its deadline without delay.

Disadvantage:

Wasted sacrifices are possible. That is, a transaction is sacrificed due to lower priority but later the higher priority transaction discarded due to some other reasons. This is similar to that of 2PL-HP protocol.

********

Go back to Optimistic Concurrency Control protocol page

Go to REAL TIME DATABASE Home page