The code for w1_ 2 in this example is wrong. We cannot delay getting the l_timestamp1 lock because it might
produce inconsistent results. Even though it might be
slower, we always have to get the lock:
void w1_ 2(long *r, time_t *t) {
lock(l_counter1);
lock(l_timestamp1);
*r = counter1++;
if (*r & 1) {
*t = timestamp2;
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: ( 1) it is easy to get into a
situation where many separate mutex locks are needed to
allow for enough parallelism; and ( 2) 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.
RE WRI T TEN USING TM
The previous example could be rewritten using TM. In the
following 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++;
}
void w1_ 2(long *r, time_t *t) {
tm_atomic {
*r = counter1++;
if (*r & 1)
*t = timestamp2;
}
}
void w2_ 1(long *r, time_t *t) {
tm_atomic {
*r = counter2++;
if (*r & 1)
*t = timestamp1;
}
}
All we have done in this case is enclose the operations
within a block called 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 below. 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 transaction.
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 (a) 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 (b)
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 earlier in this
article).
What is needed now is a definition of the work that is
done when the end of the tm_atomic block is reached
