void w1 _ 2(long *r, time _t *t) { lock(l _ counter1); lock(l _ timestamp1);

*r = counter1++; if (*r & 1) {

*t = timestamp2;

void w2_ 1(long *r, time _ t *t) { tm _ atomic {

*r = counter2++; if (*r & 1)

*t = timestamp1; }

}

unlock(l _ timestamp1); unlock(l _ counter1);

}

 

It’s a simple change, but the result is also wrong. Now we try to lock the required locks in w1 _ 2 in a different order from f1 _ 1. This potentially will lead to deadlocks. In this simple example it is easy to see that this is the case, but with just slightly more complicated code it is a very common occurrence.

What this example shows is: it is easy to get into a situation where many separate mutex locks are needed to allow for enough parallelism; and using all the mutex locks correctly is quite complicated by itself.

As can be expected from the theme of this article, TM will be able to help us in this and many other situations.

All we have done in this case is enclose the operations with a block header by tm _ atomic. The tm _ atomic keyword indicates that all the instructions in the following block are part of a transaction. For each of the memory accesses, the compiler could generate code as listed here. Calling functions is a challenge since the called functions also have to be transaction-aware. Therefore, it is potentially necessary to provide two versions of the compiled function: one with and one without support for transactions. In case any of the transitively called functions uses a tm _ atomic block by itself, nesting has to be handled. The following is one way of doing this:

1. Check whether the same memory location is part of another.

2. If yes, abort the current transaction.

3. If no, record that the current transaction referenced the memory location so that step 2 in other transactions can find it.

4. Depending on whether it is a read or write access, either load the value of the memory location if the variable has not yet been modified or load it from the local storage in case it was already modified; or write it into a local storage for the variable.

Step 3 can fall away if the transaction previously accessed the same memory location. For step 2 there are alternatives. Instead of aborting immediately, the transaction can be performed to the end and then the changes undone. This is called the lazy abort/lazy commit method, as opposed to the eager/ eager method found in typical database transactions (described previously).

What is needed now is a definition of the work that is done when the end of the tm _ atomic block is reached (that is, the transaction is committed). This work can be described as follows:

1. If the current transaction has been aborted, reset all internal state, delay for some short period, then retry, executing the whole block.

2. Store all the values of the memory

Rewritten using tm The previous example could be rewritten using TM as follows. In this example we are using nonstandard extensions to C that in one form or another might appear in a TM-enabled compiler. The extensions are easy to explain.

 

void f1_ 1(long *r, time _ t *t) { tm _ atomic {

*t = timestamp1; *r = counter1++;

}

}

 

void f2_ 2(long *r, time_ t *t) { tm _ atomic {

*t = timestamp2; *r = counter2++;

}

}

illUstration by oli larUelle

void w1_ 2(long *r, time_ t *t) { tm _ atomic {

*r = counter1++; if (*r & 1)

*t = timestamp2; }

}

feBRuaRY 2009 | vol. 52 | No. 2 | CommunICatIons of the aCm

41