Concurrency is all about doing multiple things at the same time, and it probably matters now more than it ever has before. Consider a CPU running at 3 GHz, or 3x10^9 cycles per second. The speed of light in a vacuum is 3x10^8 meters/second, which matters for us because we cannot move information faster than this. Ah, and your CPU isn’t a vacuum so the speed that information moves around a CPU is slower than that. Even data did move at the speed of light, that still only allows for up to 10cm of data movement around a circuit per cycle.

This is not all that far, and you can see that scaling clock speeds up further and further will not be sustainable. Making the circuits smaller isn’t sustainable either – you must have sufficient space between “wires” in the chip or you get current leakage and capacitance effects (essentially, electrical problems). And let’s not even talk about quantum tunnelling (yes, we really are getting down to the sizes when quantum effects start to become a real issue).

With our physics lesson over, and our grudging acceptance that our CPUs are just going to have to obey the laws of physics, it becomes clear that it isn’t going to be possible to just keep executing instructions faster. The solution is to do more at the same time instead. This happens already inside most modern CPUs. For a number of years, CPUs have been equipped to execute multiple instructions in parallel from the same program provided that they still respect ordering dependencies. More recently hyper-threading extended this idea to executing multiple instructions from different threads. Now CPUs with multiple cores are becoming the common case.

As developers we need to make use of this technology. Unfortunately, splitting the work a program does into units that can be executed in parallel is often non-trivial. There is still a lot of research today into how to do it well.

There are plenty of places where you can go to learn the practicalities of using threads in whatever language or platform you are using. Today I’m going to take a step back from the details, look at the bigger picture of using threads and explore some of the underlying issues that are good to know about.

Sharing Is Bad

You’ve probably been brought up being told that sharing is good. Well, today I’m here to tell you that sharing is bad. Problems in concurrency only really arise when threads share data. That is, if two threads are started and they never share any information with each other in any way then there will be no concurrency issues between them. Access to shared state is the root of most, if not all, problems in concurrent systems.

Unfortunately, shared state is somewhat inevitable; threads will likely be working together on a task. However, there are a few things we can do to try and minimise it. One technique is to keep as much data as possible unshared (thread local), so only one thread ever accesses it. Going further, you can make copies of shared data in thread local storage – essentially, caching it. However, you must be careful that doing this is safe and will not lead to using stale data (or more specifically, stale data that will lead to a wrong outcome).

Understanding The Hardware Architecture

To understand why sharing is bad we need to look at the underlying hardware architecture that our multi-threaded programs are running on. There are essentially two architectures: SMP (Symmetric Multi-Processing) and NUMA (Non-Uniform Memory Access). Of these, SMP is the one that is of concern to most developers now (since it covers the multi-core CPUs that are on the market). For the sake of this discussion, lets consider each core an individual CPU.

A CPU has a cache, which holds copies of data from main memory for faster access. With a single CPU, when a memory read is issued the CPU checks if the address being read from is already in the cache. If it is, then the read goes ahead. If not, the data at that address has to be requested from main memory (and likely some data around it too, up to the size of the cache line in the CPU). When a write takes place, CPUs with modern (write-back) caches write the data back to the cache, and at a later time this is written back to main memory (usually when the cache line is evicted to make way for some other data being read). Essentially, a cache line can be invalid (nothing stored in it), valid (there is data in it) or dirty (the data in it has been written to and needs to be flushed back to main memory).

Things are not quite so simple when there is more than one CPU (or core), each with its own cache. In the SMP case, all CPUs have access to the same (shared) memory and are connected to the same memory bus, meaning they can see each other’s memory requests. We’ll look at MSI, a bus protocol where a cache line can have one of three states, like in the single CPU example. Obviously, a cache line can still be empty and thus we retain the invalid state. Our valid state is replace with a shared state. This means that one or more CPUs have a copy of the line in their cache. Our dirty state becomes the modified state, meaning that only this CPU has a copy of the cache line and it has been modified.

MSI is a protocol for sharing data between multiple CPUs connected to the same bus. The name represents the three states a cache line can be in: Modified, Shared or Invalid.

If a CPU wants to write to a cache line, it must first do an exclusive read on the bus, even if it already has the data in the shared state in its cache. Each of the other CPUs sees this message and, if it has the data in a shared state, invalidates that cache line. The CPU that requested the write can then perform it, since it is now the only CPU that has the cache line and there will be no inconsistent copies of the data.

If a CPU, X, holds a cache line in a modified state and another CPU, Y, issues a read for an address in that cache line, then CPU X must jam the bus to prevent CPU Y reading out of date data from memory, and then do a memory write of that address, at the same time dropping the cache line from modified to shared state.

It’s evident from this that having a cache line moving around between the caches of different CPUS is going to be expensive, and that non-shared data that saves us from doing this is a good thing. The bad news is that if you think the SMP case is bad, ccNUMA (Cache Coherent NUMA) can have even worse penalties, including a possible 3-hop miss (where the request for a cache line must make 3 hops across the CPU interconnect before you get access to the data). It scales far better than SMP generally though - beyond 4 CPUs on a shared bus is difficult, and beyond 8 its the contention makes it infeasible.

The False Sharing Problem

A cache line holds a number of contiguous memory locations. The idea behind this is that if you access an area of memory then you are likely to also access other areas of memory nearby. If two pieces of data on a single cache line are being accessed by different CPUs, it will be indistinguishable at a cache level from the multiple CPUs accessing the same item of data. This is called false sharing; despite the two threads not really sharing any data, they are sharing a cache line, since the two pieces of data are on the same cache line.

The most obvious place for this ugly problem to come up is when multiple threads are accessing an array. Even if an application is designed carefully so that multiple threads do not access the same array elements, there may still be poor performance if multiple threads access array elements that are adjacent or near to each other, as shown in the diagram below.



Unfortunately, this is just one of those issues that you must be aware of and consider when designing a shared data structure. This applies equally to members of a structure or object instance data. Don’t underestimate the influence that cache issues can have on the performance of multi-threaded applications.

How Many Threads?

There are a number of reasons for starting threads. One is to work around blocking input and output; for example, a web server may spawn a thread per connection. Another is to attempt to increase performance on a CPU-intensive task by starting a number of threads and having each thread do a part of the task.

Whatever the reason for using threads, it is important to remember that threads have overhead. There is a cost to start a thread and an increased scheduling overhead on the part of the operating system while the thread is running.

For a CPU-bound task (one that is mostly dependent on the CPU to perform computation and does comparatively little I/O), the amount of thread-level parallelism that can be achieved is limited by the number of threads that the hardware can execute concurrently. Spawning 10 threads when only four can be executed concurrently will very likely harm performance, due to increased scheduling overhead and greater lock contention (see below).

Locking Strategy

When threads interact with each other, they usually do so by reading and modifying data structures that they both have access too. We would like these accesses to be safe – that is, we do not want another thread to see the data when it is in an inconsistent “half way” state. For example, say that some money is being moved between two accounts. There are two operations performed: subtracting the money from the first account, and then adding it to the second. If another thread looks at the total amount of money between the two accounts in-between these two steps, it will get an incorrect answer.

For this reason, locks are often used to ensure that only one thread can do modifications to the data at a time, or that no other thread can modify data while it is being read. Locking can be expensive, however; if multiple threads are seeking to obtain the same lock then lock contention will occur. This not only means that the cache lines holding the data will be pinging between the CPUs, but also the cache lines holding the lock may also be doing so as each thread attempts to obtain the lock.

Careful design of the lock taking mechanism is clearly of great importance, but generally a threading library provides this or it may be provided at a language level. For interest, I’ll mention three possible approaches: continually trying to obtain the lock (bad cache performance all the time), trying to obtain it only when it is seen to be released (bad cache performance every so often as many CPUs stampede to get the lock) and placing waiting processes in a queue (fair and possible good cache behaviour, but more complex to implement of the queue and requires memory to store such a queue in).

It would be nice to avoid having to take so many locks, and equally it would be nice to avoid so much contention on a single lock. At the same time we want to enable as much concurrent access as possible.

Imagine we have a shared hash table (dictionary). We could choose to have one lock for the whole table. That means to do any operation on the table only one lock needs be taken. However, this means that only one thread can ever access the table at a time, limiting how much concurrency is possible and possibly causing a lot of contention on the lock. Instead we may have on lock per entry in the table. There is still only one lock to obtain for a read/write on a particular entry, much more concurrency is now possible and contention on any individual lock will likely be far lower. However, for compound operations that affect multiple entries, or even operations that affect the whole table (for example, the hash table may need to be resized), many or all locks would have to be obtained, which would be expensive. The choice of one big lock (coarse-grained) or many smaller locks (fine-grained) is non-trivial and highly situation dependent.

Another option is to consider a more complex locking mechanism. For example, your shared hash table may be used most of the time for reads and only occasional write operations. If this is the case, you could use a MRSW (Multiple Reader, Single Writer) lock. This enables many threads to hold read locks for the hash table, but only one thread at a time to ever hold a write lock. Furthermore, when a thread has the write lock, no read locks can be held. This means that a write can take some time to do, since every reader has to give up their read lock first. This in turn usually means that threads that want to read once the write has been requested have to wait until it is done. This is why writes are expensive, and why you should only use this design in read-heavy situations. However, in such situations, it can allow a great deal more parallelism even if we only have one single lock for the whole hash table.

Lock Free Designs

Recent research has considered how to build lock free data structures – that is, data structures that can be accessed and modified concurrently, but without using locks. Designed these well is difficult, but it is easy to see that you can in theory make any data structure lock free using atomic compare and swap.

Atomic compare and swap, or CAS for short, is an operation often implemented at a CPU level to provide concurrency. It takes three parameters: a memory location, a value that you expect to be at that location and a new value to store. In a single atomic operation (that is, no other CPU can interfere in the middle of it), CAS checks if the value at the location supplied is what you expected it to be, and if it is it stores the new value at the location. It returns the value that it saw, meaning you can then compare that yourself to see if it was what you expected.

We can build a very simple and inefficient lock taking mechanism in a single line of code using this:

while (CAS(address, 0, 1) != 0) { }

Here, address is the location that holds our lock. A value of 0 means that nobody has the lock, a value of 1 means that somebody has it. We expect to see a 0 there (the second parameter) and if we see it want to replace it with 1 (the third parameter). If we tried this but there was not a zero at address, then somebody else must have the lock, so we stay in the loop and try again until we eventually get it.

CAS is the basis for more than this, though. Now imagine that we have a pointer to a data structure stored at “address” (that is, “address” is a pointer to a pointer). If we want to modify the data structure, we store the current pointer to it in a variable, then make a copy of the data structure and do our changes to the copy.

make_change:
original_ptr = *location;
copy = copy_data_structure(original_ptr);
/* Do changes on copy */

Since the copy is thread local and nobody else knows about it, this is safe. We then want to make our modified copy the “official” version. We use CAS to attempt to set the value at “address” to the location of our copy, but only if it contains a pointer to the data structure we originally copied. If it does not, then we know somebody else got in and made a change, so now we have to start over again.

result = CAS(location, original_ptr, copy);
if (result != original_ptr) {
    /* Have to try again; in reality we’d write this as a loop… */
    goto make_change;
}

This works pretty universally, but for many data structures we can do much better. For example, lock free linked lists have been developed that support a range of operations. However, designing and implementing these requires a great deal of care, and the only way to be sure you’ve got it right is to do a proof. Thankfully, we’re used to using data structures that others have implemented for us, and can leave people who know what they’re doing to do the hard parts.

Other Schemes – Present and Future

Livelock is like deadlock in that the system or program as a whole makes no progress, but unlike deadlock the threads are still able to execute. It can happen as a result of bad deadlock detection and resolution algorithms.

Locking has a number of issues (including deadlock, livelock and just plain forgetting to take them). Lock free data structures are attractive because they start to deal with some of these problems, especially that of deadlock and livelock since if your update fails, you know that somebody else’s update was successful and the system has made progress overall (if you want per-thread fairness that may not be good enough for you, though).

Research into other approaches continues. Software Transactional Memory is one example; in fact, it is being used in real world programming languages today: Haskell has it and Perl 6 plans to use it. It works somewhat like transactions in a database; it allows you to mark a sequence of instructions as something that should appear as an atomic operation. For example, the syntax could look like this:

atomic {
    payer.balance -= amount;
    payee.balance += amount;
}

This is a much more declarative approach to concurrency – you do not have to worry about where to take locks or remember to take them.

Another approach that I have yet to see in a real world language, but was described to me by researchers at a recent conference, is annotating variables with how they may be accessed by different threads. For example, when declaring object instance data you might require that some of it is only accessed by one thread at a time, or perhaps have MRSW semantics:

private nocucurrent List<Transaction> BankAccount;
private mrsw HashTable EmployeeInfo;

Maybe in five years we will be using things like this when writing concurrent applications. Maybe we’ll be using something completely different. Maybe we’ll be doing pretty much what we are now, but I like to hope that the mainstream languages will have better concurrency features as developing concurrent applications becomes more and more important.