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
