Concurrency vs. Multi-Threading

A lot of people tend to treat concurrency and multi-threading as the same thing. In many ways, they are correct given the similarities between the two. But when trying to reason program behaviour, teasing out the distinction is somewhat important. Concurrency, , is by definition multi-threading; but multi-threading, , is not necessarily concurrent.

To make it clear why concurrency is not strictly multi-threading, we start off by defining what concurrency is. Let be the set of all program actions and that and . Also, denotes that the action precedes action .

The explanation is actually straightforward when expressed in plain English.

The set of rules says (1) if all the actions in set precedes all the actions in set , and all the actions in set precedes all the actions in set , then the set of actions are equivalent; (2) for any action that precedes action , and any action that precedes action , then action precedes action . This is known as a transitive relation, but note that while this transitive relation describes an action, broadly this relationship holds within a set of actions as well. (3) All the set of actions in precedes all the set of actions in , i.e. this loosely means that if an action has happened before, then it cannot happen again, which is used to describe how program flows.

To put it simply, concurrency means that for a given quantum of time, there can be one or more program actions happening simultaneously. A set of actions on a given thread T1 will be causally ordered by only on the thread itself, however this set of actions may or may not have an ordering relationship with the set of actions on another thread T2.

Understanding what concurrency is, how is multi-threading different?

Consider multi-threading on a single CPU machine. In a uni-core CPU, all actions are totally ordered, ie no two actions can happen at a single quantum of time, but this is not the case for a multi-core (concurrent) CPU. Obviously, we can easily make a multi-core CPU function like a single core CPU, but certainly not the other way around, which is why .

Even though most times type programs are what we are interested in, we do usually assign an arbitary program order to these programs to make it functionally behave like a single-core program, which is much easier to reason with. You see these to totally ordered conversions from time to time, such as in my discussion of the Implementation of Volatile in the JVM.

To put it simply, threading is a way of describing program actions for concurrent programs, and sequential programs can also be reasoned in the context of threads, but not the other way round. For a simple illustration, consider the following program:

public class MyLock {
  private volatile int thread_id;
  public void lock ( )
  {
     int my_id = Thread.getID ( );
     thread_id = my_id;
     while ( thread_id == my_id ) { } // wait loop
  }
}

The code is multi-threaded; assume that there are 2 threads executing at the moment, and with thread T1, T2 returning IDs of 1, 2 correspondingly.

There is an interesting property with this piece of code - if the threads are concurrent, then eventually the thread_id value will change, and the code can never halt (and the threads will be fairly-scheduled as an interesting side effect). But if the threads are sequential, then one thread will enter the lock ( ) code, and halts the processor in a wait loop.

For those who may be interested, the code in this example is a part of an implementation of Peterson's algorithm, and a simple and poignant example to show how concurrent programs can be different from multi-threading ones.