New paradigms for concurrent programming: Transactional Memory

Java and other mainstreams programming languages rely on shared state concurrency for concurrent programming. Race conditions between different threads are prevented using synchronization structures.
Traditionally in Java synchronized blocks along with wait and notify methods are used but Java 5 introduces new easier concepts.

Still it is quite difficult to implement correctly those patterns and there is no way to prove the code is correct.

New paradigms are slowly introduced intending to simplify or replace locking constructions.
This article will focus on Transactional Memory.

Transactional Memory

Transactional memory is an alternative to lock based synchronization relying on shared states.
This is achieved by applying the concept of transaction and ACID properties to your programming structures. Key points here are Atomicity and Isolation. Concurrent executions effects are equivalent to individual serial executions.

The main idea is to wrap a block of code in a transaction which is committed at the end. Read/write memory accesses can be dealt differently (optimistic/pessimistic locking) depending on concurrency control algorithm. If a conflict is detected during the execution of the atomic block by a thread the whole operation is roll-backed and retried. Details on retries strategies are implementation specific.

Biggest advantage of this technology is simplicity. Programmer doesn’t have to care about how to implement safe concurrent access (dealing with locks, wait..) but only identify which block of code should be treated as atomic.
Better performances are not ensured but correctness is.

More detailed explanation on transactional memory can be found here, here, here and here.

Usage

In most of languages/libraries transactional memory support will be little intrusive by relying on special keyword or meta-data. For language without built-in transactional memory support this can be achieved by using bytecode manipulation.

Regular synchronized block


public void test() {
  synchronized(map1) {
    synchronized(map2) {
      value = map1.remove("key");
      map2.put("key", value+1);
    }
  }
}

Here you have to synchronize modification of 2 structures. This can be hard to correctly implement especially if several methods have to synchronize on the same structure. In this particular sample you have to take a particular care about potential deadlock which might be introduce if you don’t acquire/release locks in the same order.

Transactional memory


@Atomic
public void test() {
  value = map1.remove("key"); 
  map2.put("key", value+1);
}

Transactional memory ensures that your atomic block of code will be executed atomically. Still there is no magic and you need to identify atomic blocks of code.
Moreover you don’t have to think about locking optimization, which is hard especially when multiple structure access have to be synchronized from different execution path. Because everything is handled by the language (or library) smart optimization might be applied and you are not responsible for this.

This technique does not solve all concurrency problems but certainly helps for some of them. Still you will have to rely on Semaphore, Barrier and other advanced structures for more complex scenarii.

Language support

Haskell

Haskell was the first language to have builtin support for STM. Details can be found here.

Java

Atomic types, locks (Java 5) and Fork/Join (Java 7) are lock-free structures using compare and swap algorithm. Implementation is similar to transactional memory but for a single element. Details about their implementation choice can be found here and here.

To benefit from atomicity capacity you will have to use a full transactional memory implementation.

A number of Java implementation are available:

Multiverse’s author discusses similarities between TL2 and Multi Version Concurrency Control (MVCC) algorithms .

.Net

Microsoft also provides STM support with STM.NET.

Fortress

Fortress language supports transactional memory as part of its semantic. Current implementation relies on DTSM2 but plan is to switch to Hybrid Transactional Memory (mix of hardware and software implementation) when available.

On top of atomicity, most of fortress syntaxic structures (loop for instance) are executed in parallel by multiple threads. While powerful this introduces complexity as a simple loop adding numbers will have to manipulate atomic structures.

Clojure

Clojure supports STM based on MVCC.

Hardware Transaction Memory

In the near future transactional memory paradigm will be implemented at hardware level providing even better performance. Rock processor from SUN (recently released paper describes HTM features) and Vega 3 from Azul implement it. Other approaches have been documented here and here.

Cons

Transactional memory is not the panacea and some critics (here and here) appeared recently.
Others techniques aiming at facilitating concurrent programming will be discussed later.