locations modified in the transaction
for which the new values are placed in
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
is nothing new
in the world
In fact, it has
been central to
the entire solution
in one particular
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: