Parallel
Programming
with
Transactional Memory

(software TM) is what most research projects are using today. With STM-based solutions it is possible to provide interfaces to TM functionality, which later could be implemented in hybrid TM implementations, using hardware if possible. This allows programmers to write programs using the simplifications TM provides even without HTM support in the hardware.

SHOW ME THE PROBLEM

To convince the reader that TM is worth all the trouble, let’s look at a little example. This is not meant to reflect realistic code but instead illustrates problems that can happen in real code:

long counter1; long counter2; time_t timestamp1; time_t timestamp2;

void f1_ 1(long *r, time_t *t) {

*t = timestamp1;

*r = counter1++;

}

void f2_ 2(long *r, time_t *t) {

*t = timestamp2;

*r = counter2++;

}

void w1_ 2(long *r, time_t *t) {

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

*t = timestamp2;

}

 

void w2_ 1(long *r, time_t *t) { *r = counter2++; if (*r & 1)

*t = timestamp1;

Assume this code has to be made thread-safe. This means that multiple threads can concurrently execute any of the functions and that doing so must not produce any invalid result. The latter is defined here as return counter and timestamp values that don’t belong together.

It is certainly possible to define one single mutex lock and require that this mutex be taken in each of the four functions. Verifying that this would generate the expected results is easy, but the performance is potentially far from optimal.

Assume that most of the time only the functions f1_ 1 and f2_ 2 are used. In this case there would never be any conflict between callers of these functions: callers of f1_ 1 and f2_ 2 could peacefully coexist. This means that using one single lock slows down the code unnecessarily.

So, then, use two locks. But how to define them? The semantics would have to be in the one case “when counter1 and timestamp1 are used” and “when coun- ter2 and timestamp2 are used,” respectively. This might work for f1_ 1 and f2_ 2, but it won’t work for the other two functions. Here the pairs counter1/timestamp2 and counter2/timestamp1 are used together. So we have to go yet another level down and assign a separate lock to each of the variables.

Assuming we would do this, we could easily be tempted to write something like this (only two functions are mentioned here; the other two are mirror images):

 

void f1_ 1(long *r, time_t *t) { lock(l_timestamp1); lock(l_counter1);

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

}

 

void w1_ 2(long *r, time_t *t) { lock(l_counter1);

*r = counter1++;

if (*r & 1) { lock(l_timestamp1); *t = timestamp2; unlock(l_timestamp1);

}

 

unlock(l_counter1);