Concurrent Programming, Transactions and Weak Memory

This is the first in a two-part post from Arm Principal Researcher Dr Nathan Chong on his joint research with Tyler Sorensen (Imperial College London) and Dr John Wickerson (Research Fellow, Imperial College London). This research was published as a PLDI 2018 Distinguished Paper: 'The Semantics of Transactions and Weak Memory in x86, Power, Arm, and C++'. In this post, we introduce the ideas of transactions and weak memory in the context of concurrent programs.

"Concurrency is about dealing with lots of things at once." (Pike, Concurrency is not Parallelism)

Karlheinz Stockhausen’s "Gruppen" is a piece of music involving three orchestras and over one hundred musicians, at the same time! Simon Rattle, one of the conductors interviewed in a June 29, 2018 New York Times article about performing this piece, remarks: "Each orchestra is very complicated on its own, but when you put the three together, it’s like this dizzying tessellation of rhythms and sounds." The challenge is in "coordinating all these desperately complicated rhythms and cues, and not losing your head." What a great description of the challenges of concurrent programming too!

Concurrent Programming

Concurrent programming is about the useful interaction of multiple processes over shared resources. Here is a simple example. Imagine you have a bank account with £100 inside. Today, (1) you'll be paid £100 but (2) you also need to withdraw £100. In other words, your bank account should finish the day even at £100.

But what if each account update is split into two actions: (a) reading the balance and (b) writing the balance; and furthermore, the bank interleaves the actions like so:

(1a) Reads current balance of £100
(2a) Reads current balance of £100
(1b) Adds £100 and writes a balance of £200
(2b) Subtracts £100 and writes a balance of £0!

Something has gone terribly wrong! The problem is the interleaving of the actions of the account updates. We need the updates to be atomic so that all the actions of one account update are indivisible with respect to other account updates. In this case, we are concerned with the useful interaction (ensuring atomicity) of multiple processes (account updates) over shared resources (our bank account).

It turns out that ensuring atomicity is just one of the challenges that we face when programming concurrently. The fundamental difficulty is that concurrent programs can have many behaviors due to subtle interactions between multiple components; and the programmer must reason about all of these possible behaviors. Lu et al. (ASPLOS 2008) give a detailed discussion of concurrency problems that occur in real-world codebases.

Transactions and Weak Memory

"A transaction is a sequence of actions that appears indivisible and instantaneous to an outside observer." (Harris et al., Transactional Memory)

"Although the question of how consistent memory must be seems simple, it is remarkably complicated." (Hennessy and Patterson, Computer Architecture: A Quantitative Approach)

The architecture of a computer is the foundational contract between hardware and software: the envelope of behavior that all hardware must conform to, and hence, all software can rely on. So, the concurrency model of an architecture defines the concurrent behavior that software can rely on. Transactions and weak memory are two potential features of this concurrency model.

• Transactions are a sequence of machine instructions that guarantee atomicity and other properties, such as isolation, in order to give the programmer an easier interface, similar to that of a database, for concurrent programming. The idea is to avoid the complexities of fine-grain locking and rely on the optimistic concurrency of transactions for correctness and performance.
• Weak memory (also known as memory consistency) is the specification that governs the ordering requirements of load and store instructions, which may differ from the order specified by the programmer. This is the case for several architectures, including x86, Power, and Armv8.

What makes these two characters interesting to study together is that their aims are at odds with one another. Transactions want to make your life as a programmer simpler whereas weak memory demands that you understand how the machine may reorder your code. We can characterise this tension by saying that transactions reduce the behaviours of a concurrent program (and therefore make reasoning about the program easier); whereas weak memory increase the behaviors (and therefore make reasoning about the program harder).

Each of these features, individually, is complex. How can we deal with the complexity when they are combined? Read my next post where we tackle this problem.