locations modified in the transaction for which the new values are placed in local storage.

3. Reset the information about the memory locations being part of a transaction.

The description is simple enough; the real problem is implementing everything efficiently. Before we discuss this, let’s take a brief look at whether all this is correct and fulfills all the requirements.

Correctness and fidelity

Assuming a correct implementation (of course), we are able to determine whether a memory location is currently used as part of another implementation. It does not matter whether this means read or write access. Therefore, it is easy to see that we are not ever producing inconsistent results. Only if all the memory accesses inside the tm _ atomic block succeed and the transaction is not aborted will the transaction be committed. This means, however, that as far as memory access is concerned, the thread was completely alone. We have reduced the code back to the initial code without locks, which obviously was correct.

The only remaining question about correctness is: will the threads using this TM technology really terminate if they are constantly aborting each other? Showing this is certainly theoretically possible, but in this article it should be sufficient to point at a similar problem. In IP-based networking (unlike token-ring networks) all the connected machines could start sending out data at the same time. If more than one machine sends data, a conflict arises. This conflict is automatically detected and the sending attempt is restarted after a short waiting period. IP defines an exponential backup algorithm that the network stacks have to implement. Given that we live in a world dominated by IP-based networks, this approach must work fine. The results can be directly transferred over to the problem of TM.

One other question remains. Earlier we rejected the solution of using a single lock because it would prevent the concurrent execution of f1 _ 1 and f2 _ 2. How does it look here? As can easily be seen, the set of memory locations used for the two functions is

the problem
of consistency
is nothing new
in the world
of computers.
In fact, it has
been central to
the entire solution
in one particular
area: databases.

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

disjunct. This means that the sets of memory locations in the transactions in f1 _ 1 and f2 _ 2 is disjunct as well, and therefore the checks for concurrent memory uses in f1 _ 1 will never cause an abort because of the execution of f2 _ 2 and vice versa. Thus, it is indeed trivially possible to solve the issue using TM.

Add to this the concise way of describing transactions, and it should be obvious why TM is so attractive.

Where is tm today?

Before everybody gets too excited about the prospects of TM, we should remember that it is still very much a topic of research. First implementations are becoming available, but we still have much to learn. The VELOX project ( http://www.velox-project.eu/), for example, has as its goal a comprehensive analysis of all the places in an operating system where TM technology can be used. This extends from lock-free data structures in the operating system kernel to high-level uses in the application server. The analysis includes TM with and without hardware support.

The project will also research the most useful semantics of the TM primitives that should be added to higher-level programming languages. In the previous example it was a simple tm _ atomic keyword. This does not necessarily have to be the correct form; nor do the semantics described need to be the most optimal.

A number of self-contained S TM implementations are available today. One possible choice for people to get experience with is TinySTM (http://tinystm. org). It provides all the primitives needed for TM while being portable, small, and depending on only a few services, which are available on the host system.

Based on TinySTM and similar implementations, we will soon see language extensions such as tm _ atomic appear in compilers. Several proprietary compilers have support, and the first patches for the GNU compilers are also available (http://www.hipeac. net/node/2419). With these changes it will be possible to collect experience with the use of TM in real-world situations to find solutions to the remaining issues—and there are plenty of issues left. Here are just a few: