Assignment 7: Java memory model

Java, released in 1995, was one of the earlier mainstream languages to emphasize shared-memory multithreading at the language's core. (But Ada, from 1980, predated it by a long shot.) At the same time, Java also emphasizes cross-platform compatibility, leading to a language definition defining more precisely how programs should work than is customary. This led to the “Java Memory Model,” the first major attempt at defining how variables should work in a shared-memory system.

Though Java's designers were very sharp, multithreading is tricky enough that they they got it wrong. This led to a lot of thought about exactly what a language's memory model ought to be. “Fixing the Java Memory Model,” a 1999 paper by William Pugh, identifies some problems and proposes a new model. (In fact, this paper merely introduces the issue. Java's definition was not repaired to address the issue until Java 5 in 2004. The adopted solution (which doesn't match Pugh's 1999 proposal) is reported in the more technical 2005 paper “The Java Memory Model by Manson, Pugh, and Adve.)

Your assignment is to read “Fixing the Java Memory Model” and to answer the following questions. [Link (or external link)]

1. Pugh goes through quite a bit of effort to set up Figure 5 and then explain it. What is the point of this counterexample? Summarize the structure of his argument (without going into the details of the graphs he draws).

2. Figure 15 gives a trace that Pugh says could lead to a final result where j turns out to be 2. Explain carefully how this could happen. And explain why Pugh contends that this isn't something that should be repaired in a revised memory model.

3. In Pugh's proposed alternative, he suggests that there should not be a dependence between two actions A and B if A is a read and B is a unlock. Explain why we should be comfortable with A and B being reordered in such a situation.

4. In a multicore processor having write-back caches with no attempt toward consistency, implementing Pugh's proposed Java Memory Model does not appear to be straightforward. As a basic example, consider the following two threads.

   Thread A		Thread B
   synchronized (k) {     x = 1;     y = 1; }		synchronized (k) {     x = 2;     y = 2; }

   After executing these two threads, of course it shouldn't happen that x is 1 while y is 2. However, for cache coherency, the actions related to k are irrelevant to when the caches' values for x and y are written back. Thus, A's cache could “write-back” x after B (and so x ends up at 1) while B's cache “writes-back” y after A (so y ends at 2).

   Given that our computer should support at least Java's relaxed form of consistency, how could the computer support this? Your answer could take one of three forms.

   • A basic cache coherency protocol (such as write-invalidate) would ensure that Java's relaxed form of consistency is followed. In this case, you should explain how the coherence protocol forbids the above scenario from occurring.
   • The best way to support this is to modify the cache protocol to support the consistency required. In this case, explain how the cache protocol should work while maintaining enough flexibility to allow parallelism where possible.
   • The best way to address this is to add new instructions that the compiler could produce (or the JVM could execute) to ensure the consistency that Java requires. In this case, explain what instructions you would add while maintaining enough flexibility to allow parallelism where possible.