Concurrency in Java using synchronized blocks not giving expected results

Question

Below is a trivial java program. It has a counter called "cnt" that is incremented and then added to a List called "monitor". "cnt" is incremented by multiple threads, and values are added to "monitor" by multiple threads.

At the end of the method "go()", cnt and monitor.size() should have the same value, but they don't. monitor.size() does have the correct value.

If you change the code by uncommenting one of the commented synchronized blocks, and commenting out the currently uncommented one, the code produces the expected results. Also, if you set the thread count (THREAD_COUNT) to 1, the code produces the expected results.

This can only be reproduced on a machine with multiple real cores.

public class ThreadTester {

    private List<Integer> monitor = new ArrayList<Integer>();
    private Integer cnt = 0;
    private static final int NUM_EVENTS = 2313;
    private final int THREAD_COUNT = 13;

    public ThreadTester() {
    }

    public void go() {
        Runnable r = new Runnable() {

            @Override
            public void run() {
                for (int ii=0; ii<NUM_EVENTS; ++ii) {
                    synchronized( monitor) {
                        synchronized(cnt) {        // <-- is this synchronized necessary?
                            monitor.add(cnt);
                        }
//                        synchronized(cnt) {
//                            cnt++;        // <-- why does moving the synchronized block to here result in the correct value for cnt?
//                        }
                    }
                    synchronized(cnt) {
                        cnt++;              // <-- why does moving the synchronized block here result in cnt being wrong?
                    }
                }
//                synchronized(cnt) {
//                    cnt += NUM_EVENTS;    // <-- moving the synchronized block here results in the correct value for cnt, no surprise
//                }
            }

        };
        Thread[] threads = new Thread[THREAD_COUNT];

        for (int ii=0; ii<THREAD_COUNT; ++ii) {
            threads[ii] = new Thread(r);
        }
        for (int ii=0; ii<THREAD_COUNT; ++ii) {
            threads[ii].start();
        }
        for (int ii=0; ii<THREAD_COUNT; ++ii) {
            try { threads[ii].join(); } catch (InterruptedException e) { }
        }

        System.out.println("Both values should be: " + NUM_EVENTS*THREAD_COUNT);
        synchronized (monitor) {
            System.out.println("monitor.size() " + monitor.size());
        }
        synchronized (cnt) {
            System.out.println("cnt " + cnt);
        }
    }

    public static void main(String[] args) {
        ThreadTester t = new ThreadTester();
        t.go();

        System.out.println("DONE");
    }    
}

Answer 1

Ok let's have a look at the different possibilities you mention:

1.

for (int ii=0; ii<NUM_EVENTS; ++ii) {
  synchronized( monitor) {
    synchronized(cnt) {        // <-- is this synchronized necessary?
      monitor.add(cnt);
    }
    synchronized(cnt) {
      cnt++;        // <-- why does moving the synchronized block to here result in the correct value for cnt?
    }
}

First the monitor object is shared between the threads, therefore getting a lock on it (that is what synchronized does) will make sure that the code inside of the block will only be executed by one thread at a time. So the 2 synchronized inside of the outer one are not necessary, the code is protected anyway.

2.

for (int ii=0; ii<NUM_EVENTS; ++ii) {
  synchronized( monitor) {
    monitor.add(cnt);
  }
  synchronized(cnt) {
    cnt++;              // <-- why does moving the synchronized block here result in cnt being wrong?
  }
}

Ok this one is a little bit tricky. cnt is an Integer object and Java does not allow modifying an Integer object (Integers are immutable) even though the code suggests that this is what is happening here. But what acutally will happen is that cnt++ will create a new Integer with the value cnt + 1 and override cnt. This is what the code actually does:

synchronized(cnt) {
  Integer tmp = new Integer(cnt + 1);
  cnt = tmp;
}

The problem is that while one thread will create a new cnt object while all other threads are waiting to get a lock on the old one. The thread now releases the old cnt and will then try to get a lock on the new cnt object and get it while another thread gets a lock on the old cnt object. Suddenly 2 threads are in the critical section, executing the same code and causing a race condition. This is where the wrong results come from.

If you remove the first synchronized block (the one with monitor), then your result gets even more wrong because the chances of a race increase.

In general you should try to use synchronized only on final variables to prevent this from happening.