Java Memory Model (including volatile happens-before guarantee and synchronized)

Stack (pl: stos) (LIFO = last in, first out), data structure with push and pop

Heap (pl: sterta) is a tree-based data structure with all elements following the same pattern of ordering of values (e.g. max-heep: with parent element having value greater then its nodes).

Each thread has it own stack and threads’ stacks are not shared between threads so all the data on the thread’s stack is thread safe. Each stack contains information what methods were called to reach current execution point (so called method execution “call stack”) and these methods’ local variables (local primitives and local references to objects). Even if threads execute the same method their stack would get its own version of all local variables. One thread can only see its own stack data and cannot see stack data from other threads. One thread calling another thread can only pass a copy of its local primitive variables to another thread but not share it.
Each new method execution adds a stack frame on the top of the stack and such frame is removed after the methods returns. Stack is fast and smaller that heap. That is why local primitives and local reference variables are stored on the stack.

On the other hand object graphs can get very big and so they are stored on the heap. Object versions of primitives such as e.g. Integer as also stored on the heap. All threads have access to the heap objects (provided they have a reference to a particular object). The heap is shared among threads so threads can potentially modify the state of same objects at the same time what can lead to race conditions.

class MyClass {

  MyObject myObject = // myObject reference is an object member variable (field) and is created on heap
                      // object member variables (fields) are created on heap
           new MyObject(); // instance of MyObject is created on heap (as all objects)
  
  long id = 123L; // id is a primitive member variable (field) and is also stored on the heap

  static Integer number = new Integer(1); // static class member variables are stored on the heap 
                                          //with its class definition

  public void run() {
    int counter = 1234567; // counter is a local primitive variable of type int, 
                     // counter is created on stack 
                     // (local primitives are created on stack)

    MyObj2 myObj2 = // myObj2 is a local variable referencing object of type MyObj2, 
                    // myObj2 is created on stack 
                    // (local object references are created on stack)

              new MyObj2(); // instance of MyObj2 is created on heap** 
                    // (objects are created on heap)
                    // NOTE if MyObj2 had local variables they would still be stored on 
                    // the stack even though the object itself is stored on the heap  


   Configuration config =
              Configuration.getInstance(); // returns the same configuration 
                                   // for all threads calling this method***
 
  }
}

** if JVM has explicitly escape analysis flag on and myObj2 would never escape the method (e.g. not returned by the method nor passed to other methods outside) so that others threads could not share it then JVM may decide to create MyObj2 on the stack instead of heap

Assuming escape analysis disabled, then each thread calling run() method will have a new copy of counter primitive local variable and each thread will create a new separate instance of MyObject2 on the heap. Each thread will have a separate local reference (created on the stack) to the corresponding object of type MyObject2 (created on the heap).

***It is also possible for threads to have their own local reference pointing to the same object created on the heap e.g. created by static factory method Configuration.getInstance() returning the same shared instance of Configuration object (singleton/global state). If threads start to modify the configuration then configuration changes may not be visible to other threads or threads can overwrite each other changes which leads to race conditions. Thread safety can be achieved then by applying additional synchronization e.g. synchronized method or block.

Immutability
If objects needs to be passed among threads then the best way is to make them immutable (once created cannot change internal state). They should not have any setters nor public fields. If they expose some internal state (e.g. immutableObj.getNames() returning a list), then it should be unmodifiable (e.g Collections.UnmodifiableList) or return a deep copy (new ArrayList(internalList)). It not recommended but if required that such immutable object needs to expose a method to modify the state then such method should return a completely new instance of such immutable object (e.g. ImmutableObject add(List newNames) return new ImmutableObject(addAll(newNames, this.getNames)) ). If a class internally has a reference to immutable field (member variable) it does not necessary mean that this class is immutable itself as it may expose a setter to reset this reference and so the usage of such class may not be thread safe. Then additional synchronization between threads is needed.

RAM, CPU cache and CPU registers
Modern computers have RAM (main shared memory) and CPUs with per CPU cache memory (a dedicated cache for a CPU) and per CPU registers (each CPU with its own register). The regular update or read operations flow goes from RAM to CPU cache(s) and then to CPU registers and back to main memory.

Volatile
If data flush to the RAM is delayed then one thread may not see the data changed by another thread using the different CPU cache. Java ‘volatile’ keyword makes sure that are directly read from RAM and always written to main memory when updated. Since Java 5 volatile also gives extended visibility guarantee so called happens-before guarantee:

public class VolatileHappensBeforeGuarantee {

    private static final Logger LOGGER = LoggerFactory.getLogger(VolatileHappensBeforeGuarantee.class);

    static boolean nonVolatileDone = false;
    //static boolean volatileDone = false;
    static volatile boolean volatileDone = false; // volatile write

    public static void main(String[] args) {
        LOGGER.debug("started");

        new Thread(new Runnable() {
             
            @Override
            public void run() {
                LOGGER.debug("started");
                while (!nonVolatileDone) { // note that synchronization is still made on non-volatile flag but volatile  
                                           // flag makes the non-volatile flag seen eventually as described below

                    boolean done = volatileDone; // volatile read makes also all subsequent non-volatile reads from RAM 
                                                 // so non-volatile read is also from RAM

                }
                LOGGER.debug("stopped");
            }
        }).start();

        sleepMillis(100); // give additional time to make sure thread-0 started already

        nonVolatileDone = true;
        volatileDone = true; // volatile write makes all preceding writes (so nonVolatileDone = true as well) 
                             // also to be written to RAM

        LOGGER.debug("stopped");
    }

    public static void sleepMillis(int millis) {
        try {
            Thread.sleep(millis);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

/*
2015-10-22 14:08:54,401|main    |started
2015-10-22 14:08:54,401|Thread-0|started
2015-10-22 14:08:54,510|main    |stopped
2015-10-22 14:08:54,510|Thread-0|stopped

but if we remove volatile then
2015-10-22 14:09:59,055|main    |started
2015-10-22 14:09:59,055|Thread-0|started
2015-10-22 14:09:59,164|main    |stopped
(with Thread-0 still running)

Explanation:
Volatile happens-before guarantee makes non-volatile variables write before volatile write to be flushed to RAM as well. 
Then as long as another thread read the volatile variable (from RAM) then the thread will also see changes to the non-volatile variables. 
Note: the example above showed synchronization on a non volatile variable to demonstrate extended visibility. However, it is a good practice for simplicity and clarity to make synchronization on the volatile variable.
*/

Thanks to that extended visibility guarantee it is not needed to declare all variables as volatile but only a few.

Synchronized
Another case is when two threads read the same value from the main memory to their own CPU cache and each of the threads run concurrently increasing the value by one. Then one thread could write original value +1 to the main memory and that value could be overwritten by another that also to the same value (original +1) – even if the variables were declared as volatile. Then the result would be original + 1 instead of expected original +2. To make sure that this increase operation (read, update, write) operation is executed sequentially and atomically by both of the threads Java introduced synchronized block. Synchronized allows only one thread to enter and execute the critical section. All variables in that synchronized block are read from the main memory and flushed back to the main memory on exit of the synchronized block, regardless if the variables declared in synchronized block are volatile or not. All the synchronized methods or blocks that are synchronized on the same object can only have one thread executing it at the same time while other threads waiting for that thread to exit that synchronized block. The difference between synchronization on instance (this) vs on class is that when threads have their own instances of a class with instance synchronized methods/block then these methods will not block. In case if global synchronized access to the method/block is needed then synchronization on class is needed. In other words: one thread per object instance (can be one or more) vs one thread per class (which is typically only one in the JVM). Synchronized gives also visibility guarantee for the data in the synchronized method/block for threads reading and writing this data.

Summary:
Stack: all local primitives and local reference variables (each thread is its own copy)

Heap: all objects (including Object versions of primitives e.g. Integer), all object member variables (fields) (including fields of primitive type and object reference), all static class members variables (along with class definition)

volatile variable – makes reads/writes directly from/to RAM so that the value is always visible to all threads. Since Java 5 volatile also gives happens-before guarantee what means that all the non-volatile variables writes happening before volatile variable write will be also flushed to RAM main memory when the volatile variable is written. Then, when another thread reads the volatile variable from RAM it will also see changes to non-volatile variables that were written along with the volatile write. Moreover, volatile write and reads vs non-volatile writes and reads cannot be reordered (as that would affect which non-volatile variables will be flushed to RAM along with the volatile write and which non-volatile variable changes would be visible to another thread that reads volatile variables). The use case for volatile is when threads modify the volatile variable with that value that does not depend on it previous value (no re-reading), e.g. volatileIsFinished = true. There is no guarantee that making e.g. long primitive increment by two or more threads will be atomic (thread could read the same value from RAM, update it in their own CPU registers and flush the same result to RAM overwriting each other change). To solve that problem use synchronized or even better Atomic classes e.g. AtomicLong.

synchronized method/block – allows only one thread at the time (sequentially) to execute the critical section code with read/writes directly from/to RAM visible to all the threads (visibility guarantee between threads).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s