Memory Consistency Errors vs Thread interference

Question

What is the difference between memory consistency errors and thread interference? How does the use of synchronization to avoid them differ or not? Please illustrate with an example. I couldn't get this from the sun Java tutorial. Any recommendation of reading material(s) to understand this purely in context of java would be helpful.

Answer 1

Memory consistency errors can't be understood purely in the context of java--the details of shared memory behavior on multi-cpu systems are highly architecture-specific, and to make it worse, x86 (where most people coding today learned to code) has pretty programmer-friendly semantics compared to architectures that were designed for multi-processor machines from the beginning (like POWER and SPARC), so most people really aren't used to thinking about memory access semantics.

I'll give a common example of where memory consistency errors can get you into trouble. Assume for this example, that the initial value of x is 3. Nearly all architectures guarantee that if one CPU executes the code:

STORE 4 -> x     // x is a memory address
STORE 5 -> x 

and another CPU executes

LOAD x
LOAD x

will either see 3,3, 3,4, 4,4, 4,5, or 5,5 from the perspective its two LOAD instructions. Basically, CPUs guarantee that the order of writes to a single memory location is maintained from the perspective of all CPUs, even if the exact time that each of the writes become known to other CPUs is allowed to vary.

Where CPUs differ from one another tends to be in the guarantees they make about LOAD and STORE operations involving different memory addresses. Assume for this example, that the initial values of both x and y are 4.

STORE 5 -> x   // x is a memory address
STORE 5 -> y // y is a different memory address

then another CPU executes

LOAD x
LOAD y

In this example, on some architectures, the second thread can see 4,4, 5,5, 4,5, OR 5,4. Ouch!

Most architectures deal with memory at the granularity of a 32 or 64 bit word--this means that on a 32 bit POWER/SPARC machine, you can't update a 64-bit integer memory location and safely read it from another thread ever without explicit synchronization. Goofy, huh?

Thread interference is much simpler. The basic idea is that java doesn't guarantee that a single statement of java code executes atomically. For example, incrementing a value requires reading the value, incrementing it, then storing it again. So you can have int x = 1 after two threads execute x++, x can end up as 2 or 3 depending on how the lower-level code interleaved (the lower-level abstract code at work here presumably looks like LOAD x, INCREMENT, STORE x). The basic idea here is that java code is broken down into smaller atomic pieces and you don't get to make assumptions of how they interleave unless you use synchronization primitives explicitly.

For more information, check out this paper. It's long and dry and written by a notorious asshole, but hey, it's pretty good too. Also check out this (or just google for "double checked locking is broken"). These memory reordering issues reared their ugly heads for many C++/java programmers who tried to get a little bit too clever with their singleton initializations a few years ago.

Answer 2

Thread interference is about threads overwriting each other's statements (say, thread A incrementing a counter and thread B decrementing it at the same time), leading to a situation where the actual value of counter is unpredictable. You avoid them by enforcing exclusive access, one thread at a time.

On the other hand, memory inconsistency is about visibility. Thread A may increment counter, but then thread B may not be aware of this change yet so it might read some prior value. You avoid them by establishing a happens-before relationship, which is

is simply a guarantee that memory writes by one specific statement are visible to another specific statement.(per Oracle)

Answer 3

The article to read on this is "Memory Models: A Case for Rethinking Parallel Languages and Hardware" by Adve and Boehm in the August 2010 vol. 53 number 8 issue of Communications of the ACM. This is available online for Association for Computer Machinery members (http://www.acm.org). This deals with the problem in general and also discusses the Java Memory Model.

For more information on the Java Memory Model, see http://www.cs.umd.edu/~pugh/java/memoryModel/