Warning! Threading in a multiprocessor world

Find out why many tricks to avoid synchronization overhead just don't work

By Allen Holub, JavaWorld.com, 02/09/01

This article discusses why a whole category of techniques that programmers misguidedly use to avoid synchronization overhead simply don't work. Probably the most common of those is double-checked locking, which I'll discuss in a moment. In a recent posting to a Java Memory Model mailing list, Bill Pugh at the University of Maryland (one of the folks who's spearheading the rewriting of the JLS (Java Language Specification) to compensate for some of the problems discussed this month) said, "...this double-check idiom is like a roach infestation. It doesn't matter how many of them you crush under your shoe, more of them crawl out from under the refrigerator." Well, I hope this article will help stamp out the swarm.

So what's the problem?

In the beginning, a CPU could write directly to memory simply by wiggling the voltages on a few wires that connected the CPU chip to the memory chip. All was well with the world. Even with multithreaded systems, only one path to memory existed, and reads and writes to memory always occurred whenever the CPU executed the associated machine instruction. The introduction of memory caches didn't fundamentally change that model (once they got the cache-coherency bugs worked out). Indeed, the cache is transparent to the program if it's implemented correctly. That simple memory model -- the CPU issues an instruction that modifies memory with an immediate effect -- remains in most programmers' minds.

Then somebody had the bright idea that two processors could run in the same box at the same time, sharing a common memory store (Suddenly, the world became much more complicated). In that situation, a given CPU can no longer access memory directly because another CPU might be using the memory at the same time. To solve the problem, along came a traffic-cop chip, called a memory unit. Each CPU was paired with its own memory unit, and the various memory units coordinated with each other to safely access the shared memory. Under that model, a CPU doesn't write directly to memory but requests a read or write operation from its paired memory unit, which updates the main memory store when it can get access, as seen in Figure 1. Those early memory units effectively managed simple read or write request queues.

Figure 1. The memory unit

Relaxed memory

All was well with the world until some bright engineer (I believe at DEC -- at least the Alpha, to my knowledge, was the earliest machine that worked like that) noticed a way to optimize memory operations with the hardware. Consider this code:

int a[] = new int[n];
int b[] = new int[n];
for( int i = 0; i < a.length; ++i )
    b[i] = a[i];

The resulting read/write-request queue is shown in Figure 2. Our intrepid engineer said, "Ah ha! If I allow the memory units to shuffle around the order of pending read/write requests while they're waiting to get access to the main memory store (giving us Figure 3), then I can turn all these atomic moves into one big block move." That is, the memory unit can transform the requests in Figure 2 into the situation shown in Figure 4. That reordering strategy became known as a relaxed memory model.