CSC/ECE 506 Spring 2011/ch10a dc

Chapter 10a Supplement - Java Memory Model

Introduction

This chapter supplement discusses the Java Memory Model (JMM). First of all, we will cover the motivation for a memory model for Java. Secondly, the main aspects of JMM including happens-before relationships and final and volatile variables. And lastly, we'll mention double-checking.

Motivation

With parallel computing becoming more popular, programming languages face many challenges including:

• multiple layers of cache across different processors (this introduces problems with cache consistancy)

• data races (that is, when two threads try to access the data at the same time when it is being altered by another thread)

• synchronization directives. Note: these may be different depending on whether you have a "strong" or "weak" memory model (see pages 290-313 in chapter 10 of Solihin's textbook, "Fundamentals of Parallel Computer Architecture)"

• compiler reordering of instructions (part of compiler optimization)

Programmers need to know how these issues effect program execution so that they can write good software for parallel systems. For example, C/C++ has the pthreads add-on to handle parallel programing. However, Java supports parallel programing by default. The JMM describes what is legal behavior for variables and memory accesses in programs with multiple threads.

Main Aspects

One of the most important parts of the Java Memory Model is the concept of "happens-before." Two statements have a happens-before relationship if one must come before the other.

Happens-before Illustration

For example:

// Thread 1
int xIsWritten = 0;
x = 1;
xIsWritten = 1;

// Thread 2
while(xIsWritten) {
};

In this example it is important that the statement x = 1 is completed before xIsWritten = 1, and that this order is seen by both threads. In other words, x = 1 and xIsWritten need to have a happens-before relationship.

Happens-before Rules

Brian Goetz in Java Concurrency in Practice explains that happens-before relationships require the following rules:

• Program order rule - the order that statements are written in should be the order that every processor sees them executed in.

• Monitor lock rule - only one thread at a time is allowed to work on a synchronized method or block of code (synchronized means that it is protected by a monitor). Whenever a thread wants to enter a synchronized block of code it must acquire a lock (the monitor). The monitor lock rule insures that ever lock and unlock on the monitor is done in order. A monitor is like a key that a thread must get before it can access a synchronized method or block of code, and only one thread can have the key at any one time. Example code:

// synchronized method
public synchronized insertLinkedList(int * element)  
{ // each thread must acquire the monitor associated with the method
  // here before executing the rest of the code
    
  // ... code to insert element into linked list
}

// synchronized block
String myObj;
synchronized(myObj) 
{ // each thread must acquire the monitor associated with the object
  // before executing the rest of the code.

  // ... critical code here
}

Note: any java object regardless of type has a monitor associated with it which can be used to synchronize a block of code via synchronized(myObj).

• Volatile variable rule - volatile variable rule says that a volatile variable is synchronized like a synchronized block of code or method is. In other words, only one thread at a time can write or read a volatile variable.

• Thread start rule - this ensures that insures that a thread can't start executing code before it has been properly set up (i.e. the call to Thread.start() has finished).

• Thread termination rule - this ensures that before a thread is terminated every other thread sees the result of the terminating thread's instructions.

• Interruption rule - one thread must complete the process of calling an interrupt on the other thread before the other thread starts servicing the interrupt.

• Finalizer rule - this ensures that the constructor finishes constructing the thread before the finalizer starts.

• Transitivity - ensures that transitive relationships are kept. For example, if A follows B and C follows B then C *must* follow A.

These rules are the main framework for the Java programming model.

Volatile and Final Variables

Volatile and final variables are also important to the JMM. As mentioned above in the happens-before rules, volatile variables may only be written or read by one thread at a time. Reads and writes to them have a global order. This is critical for global variables that may be written by more than one thread. On the other hand, a final variable can only be written once. This means that they are written once in the constructor of a object. Note that this does not imply that the variables are immutable (see reference for more information).

Secondary Aspects

Beyond the main principles of the Java Memory Model there are many details.

Double-checked Locking

One of the controversial issues that came up with parallel computing and the JMM was double-checked locking. People wanted to avoid time consuming synchronization so they implemented double-checked locking. Here is an example of double-checked locking from Jeremy Manson and Brien Goetz (2004)

// From Manson and Goetz (2004) JSR 133 (Java Memory Model) FAQ
// double-checked-locking - don't do this!

private static Something instance = null;

public Something getInstance() {
  if (instance == null) {
    synchronized (this) {
      if (instance == null)
        instance = new Something();
    }
  }
  return instance;
}

The problem with this code is that the reads may be reordered by the compiler (they are not happens-after statements). This means the code produces indeterminate results which could lead you to attempt to read from a null pointer while thinking that it had been initialized to new Something(). This can be avoided in the new version of the JMM by declaring the instance volatile due to the volatile rule.

A better alternative to this code is the Initialization on Demand Holder Idiom:

// From Manson and Goetz (2004) JSR 133 (Java Memory Model) FAQ
private static class LazySomethingHolder {
  public static Something something = new Something();
}

public static Something getInstance() {
  return LazySomethingHolder.something;
}

Summary

In summary the JMM is a useful and necessary tool. It's useful for programmers trying to deal with multiple threads; because, it lets them know what (and what not) to expect. The happens-after relationship allows the programmers to restrict certain instructions that must be done in order. And, the JMM is necessary because without the tools it provides for synchronization programs may have indeterminate results.

References

1. Barney, Blaise POSIX Threads Programming
2. Goetz, Brian, Java Concurrency in Practice
3. Manson and Goetz, JSR 133 (Java Memory Model) FAQ
4. Manson, Pugh and Adve, The Java Memory Model
5. Solihin, Yan, Fundamentals of Parallel Computer Architencture
6. Wikipedia, Cache Consistancy
7. Wikipedia, Compiler Optimization
8. Wikipedia, Data Race
9. Wikipedia, "Happened-before."
10. Wikipeida, Initialization on Demand Holder Idiom
11. Wikipedia, Parallel Computing
12. Wikipedia, Synchronization (computer science)
13. Wikipedia, Transitive Relation
14. Wikipedia, Volatile Volatile Variables
15. Wikipedia, Final (Java)