Is id = 1 - id atomic?

Question

From page 291 of OCP Java SE 6 Programmer Practice Exams, question 25:

public class Stone implements Runnable {
    static int id = 1;

    public void run() {
        id = 1 - id;
        if (id == 0) 
            pick(); 
        else 
            release();
    }

    private static synchronized void pick() {
        System.out.print("P ");
        System.out.print("Q ");
    }

    private synchronized void release() {
        System.out.print("R ");
        System.out.print("S ");
    }

    public static void main(String[] args) {
        Stone st = new Stone();
        new Thread(st).start();
        new Thread(st).start();
    }
}

One of the answers is:

The output could be P Q P Q

I marked this answer as correct. My reasoning:

1. We are starting two threads.
2. First one enters run().
3. According to JLS 15.26.1, it firstly evaluates 1 - id. Result is 0. It is stored on the thread's stack. We are just about to save that 0 to static id, but...
4. Boom, scheduler chooses the second thread to run.
5. So, the second thread enters run(). Static id is still 1, so he executes method pick(). P Q is printed.
6. Scheduler chooses first thread to run. It takes 0 from its stack and saves to static id. So, the first thread also executes pick() and prints P Q.

However, in the book it's written that this answer is incorrect:

It is incorrect because the line id = 1 - id swaps the value of id between 0 and 1. There is no chance for the same method to be executed twice.

I don't agree. I think there is some chance for the scenario I presented above. Such swap is not atomic. Am I wrong?

Answer 1

Am I wrong?

Nope, you're absolutely right - as is your example timeline.

In addition to it not being atomic, it's not guaranteed that the write to id will be picked up by the other thread anyway, given that there's no synchronization and the field isn't volatile.

It's somewhat disconcerting for reference material like this to be incorrect :(

Answer 2

In my opinion, the answer in the Practice Exams is correct. In this code, you are executing two threads which have access to the same static variable id. Static variables are stored on the heap in java, not on the stack. The execution order of runnables is unpredictable.

However, in order to change the value of id each thread :

1. makes local copy of the value stored in id's memory address to the CPU registry;
2. performs the operation 1 - id. Strictly speaking, two operations are performed here (-id and +1);
3. moves the result back to memory space of id on the heap.

This means that although the id value can be changed concurrently by any of the two threads, only the initial and final values are mutable. Intermediate values will not be modified by one another.

Futhermore, analysis of the code can show that at any point in time, id can only be 0 or 1.

Proof:

• Starting value id = 1; One thread will change it to 0 ( id = 1 - id ). And the other thread will bring it back to 1.

• Starting value id = 0; One thread will change it to 1 ( id = 1 - id ). And the other thread will bring it back to 0.

Therefore, the value state of id is discrete either 0 or 1.

End of Proof.

There can be two possibilities for this code:

• Possibility 1. Thread one accesses the variable id first. Then the value of id (id = 1 - id changes to 0. Thereafter, only the method pick () will be executed, printing P Q. Thread two, will evaluate id at that time id = 0; method release() will then be executed printing R S. As a result, P Q R S will be printed.

• Possibility 2. Thread two accesses the variable id first. Then the value of id (id = 1 - id changes to 0. Thereafter, only the method pick () will be executed, printing P Q. Thread one, will evaluate id at that time id = 0; method release() will then be executed printing R S. As a result, P Q R S will be printed.

There are no other possibilities. However, it should be noted that variants of P Q R S such as P R Q S or R P Q S, etc. may be printed due to pick() being a static method and is therefore shared between the two threads. This leads to the simultaneous execution of this method which could result in printing the letters in a different order depending on your platform.

However in any case, never will either the method pick() or release () be executed twice as they are mutually exclusive. Therefore P Q P Q will not be an output.