Assigning Locks to Transactions

A transaction updates a set of shared memory locations and is controlled by a lock. In general, you need to be sure that if two transactions both access the same memory location, they will not run simultaneously. What is the best way to associate locks with transactions to accomplish that? Consider:

// transaction 1
if (a > b) { a -= b; b = b / 2; }
...
// transaction 2
if (c > d) { c -= d; d = d / 2; }
...
// transaction 3
if (a > c) { a -= c; c = c / 2; }
...
// transaction 4
temp = x;
x = y;
y = temp;

You must ensure that if two transactions can access the same memory location, they are controlled by the same lock. The simplest way to do this is to assign locks to sets of memory locations, so that if a transaction accesses two or more memory locations, all of the memory locations accessed in the transaction have the same lock. Then a transaction must be controlled by the lock that is assigned to all of the variables it accesses.

In the example above, variables a and b are both accessed in transaction 1, so they must have the same lock. Variables c and d are both accessed in transaction 2, so they must have the same lock. Variables a and c are both accessed in transaction 3, so they must have the same lock, which must be the same as the locks for b and d. Transaction 4 accesses x and y, so they must have the same lock, which is different from the lock for a, b, c, and d:

int abcd_lock;
int xy_lock;
// ...
ANNOTATE_LOCK_ACQUIRE(&abcd_lock);
if (a > b) { a -= b; b = b / 2; }
ANNOTATE_LOCK_RELEASE(&abcd_lock);
ANNOTATE_LOCK_ACQUIRE(&abcd_lock);
if (c > d) { c -= d; d = d / 2; }
ANNOTATE_LOCK_RELEASE(&abcd_lock);
ANNOTATE_LOCK_ACQUIRE(&abcd_lock );
if (a > c) { a -= c; c = c / 2; }
ANNOTATE_LOCK_RELEASE(&abcd_lock);
ANNOTATE_LOCK_ACQUIRE(&xy_lock);
temp = x;
x = y;
y = temp;
ANNOTATE_LOCK_RELEASE(&xy_lock);
For more complete information about compiler optimizations, see our Optimization Notice.