Java Multi-threading : Unexpected result

Question

I am working on a Enterprise application. I am facing some issues while running application in multithreaded environment. I am writing a program in which there is a variable whose value is getting updated(incremented) at very fast rate (for example 10000 updates/persecond). A loop runs for certain iterations and the value of the variable is incremented and stored in HashMap. Once the loop terminates and value the variable in HashMap is printed. I am getting unexpected value of the variable.

Here is demo program (Please read comments for better understanding) :

class test implements Runnable {

    static ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
    static AtomicInteger value_to_be_incremented_stored = new AtomicInteger(0); // variable whose value to be updated
    static AtomicInteger i = new AtomicInteger(0);  // this runs the loop

    @Override
    public void run() {

        for (i.set(0); i.get() < 100000; i.incrementAndGet()) {
            /*
                This loop should run 100000 times and when loop terminates according to me value of variable 
                "value_to_be_incremented_stored" should be 100000 as its value is incremented 
                100000 times the loop also runs 100000 times. 
            */
            System.out.println("Thread > " + Thread.currentThread() + "  " + value_to_be_incremented_stored.incrementAndGet());
            map.put("TC", value_to_be_incremented_stored.intValue());
        }

        System.out.println("Output by Thread  " + Thread.currentThread() + "     " + map.toString());
    }

    public static void main(String[] args) {

        test t1 = new test();
        Thread thread1 = new Thread(t1);
        thread1.setName("Thread 1");

        Thread thread2 = new Thread(t1);
        thread2.setName("Thread 2");

        Thread thread3 = new Thread(t1);
        thread3.setName("Thread 3");

        Thread thread4 = new Thread(t1);
        thread4.setName("Thread 4");

        thread1.start();
        thread2.start();
        thread3.start();
        thread4.start();

    }
}

Output (it varies) :

Issue : I am running loop for 100000 times (i.get() < 100000) then how come value of variable value_to_be_incremented_stored becomes more than 100000.

Answer 1

I found three defects. One there is a race condition in the for loop between the point where you compare the loop counter, and where you increment it. You should do this in one step to get an atomic operation:

for ( ; i.incrementAndGet() < 100000;  ) {

The other is there is also a race condition between the increment of your counter, and placing it in the map. Even though you increment these in series, any thread could be have a different value internally (it's at a different point in the loop) and it could put a previous value in the global map. You need atomicity here to to make sure the value you increment is the value you place in the loop.

synchronized( lock ) { 
    value_to_be_incremented_stored.incrementAndGet();
    map.put("TC", value_to_be_incremented_stored.intValue());
}

Finally for some reason the < comparison produces a value of 99999 for me. I had to use <= to fix it.

(And as we discussed in the comments, setting i.set(0) at the start of each for loop doesn't work for fairly obvious reasons. Four defects, I guess.)

class ThreadTestX implements Runnable {

    static ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
    static AtomicInteger value_to_be_incremented_stored = new AtomicInteger(0); // variable whose value to be updated
    static AtomicInteger i = new AtomicInteger(0);  // this runs the loop
    static final Object lock = new Object();

    @Override
    public void run() {

        for ( ; i.incrementAndGet() <= 100000;  ) {
            /*
                This loop should run 100000 times and when loop terminates according to me value of variable 
                "value_to_be_incremented_stored" should be 100000 as its value is incremented 
                100000 times the loop also runs 100000 times. 
            */
            synchronized( lock ) {
                value_to_be_incremented_stored.incrementAndGet();
    //            System.out.println("Thread > " + Thread.currentThread() + 
    //                 "  " + value_to_be_incremented_stored.get());
                map.put("TC", value_to_be_incremented_stored.intValue());
            }
        }

        System.out.println("Output by Thread  " + Thread.currentThread() 
                + "     " + map.toString());
    }

    public static void main(String[] args) {

        ThreadTestX t1 = new ThreadTestX();
        Thread thread1 = new Thread(t1);
        thread1.setName("Thread 1");

        Thread thread2 = new Thread(t1);
        thread2.setName("Thread 2");

        Thread thread3 = new Thread(t1);
        thread3.setName("Thread 3");

        Thread thread4 = new Thread(t1);
        thread4.setName("Thread 4");

        thread1.start();
        thread2.start();
        thread3.start();
        thread4.start();

    }
}

Output:

run:
Output by Thread  Thread[Thread 4,5,main]     {TC=100000}
Output by Thread  Thread[Thread 3,5,main]     {TC=100000}
Output by Thread  Thread[Thread 1,5,main]     {TC=100000}
Output by Thread  Thread[Thread 2,5,main]     {TC=100000}
BUILD SUCCESSFUL (total time: 0 seconds)

---

Afterthoughts: And in spite of getting marked correct, I'm not sure I was correct. The problem here is that you are trying to keep three things in sync: the loop counter i, the value to be incremented, and the map. Allowing any of these to be executed outside of a synchronized block may invite them to be in an unexpected state. I think the following may be safer:

@Override
public void run() {

    for ( ;;  ) {
        synchronized( lock ) {
            if( i.incrementAndGet() <= 100000 ) {
                value_to_be_incremented_stored.incrementAndGet();
                map.put("TC", value_to_be_incremented_stored.intValue());
            }
            else
                break;
        }
    }
    System.out.println("Output by Thread  " + Thread.currentThread() 
            + "     " + map.toString());
}

This removes the need for declaring the variables as AtomicInteger, but I don't see how else you ensure that their values don't change (due to some other thread) as that loop executes.

Answer 2

Your "demo program" suffers from two simultaneous defects.

Defect #1 is the i.set( 0 ) pointed out by tsolakp. You say you fixed that but you are still getting a value of more than 100000. I also tried it and indeed, the final value is still larger than 100000.

I modified the program to be able to create an arbitrary number of threads, and I tried with 3, 10, and 20 threads. I got a final number of 100003, 100009, and 100019 respectively. See a pattern?

What happens is that on the last iteration, when the value of i is 99999, the expression i.get() < 100000 is true for all threads, so all threads proceed to execute once more. The i.incrementAndGet() clause is visually sitting right next to i.get() < 1000000; but it does not get executed until the end of the loop.

So, all threads get a chance to increment i once more after the last iteration.