Is id = 1 - id atomic?
JavaMultithreadingAtomicSwapScjpJava Problem Overview
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:
- We are starting two threads.
- First one enters
run()
. - According to JLS 15.26.1, it firstly evaluates
1 - id
. Result is0
. It is stored on the thread's stack. We are just about to save that0
to staticid
, but... - Boom, scheduler chooses the second thread to run.
- So, the second thread enters
run()
. Staticid
is still1
, so he executes methodpick()
.P Q
is printed. - Scheduler chooses first thread to run. It takes
0
from its stack and saves to staticid
. So, the first thread also executespick()
and printsP 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?
Java Solutions
Solution 1 - Java
> 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 :(
Solution 2 - Java
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 :
- makes local copy of the value stored in id's memory address to the CPU registry;
- performs the operation
1 - id
. Strictly speaking, two operations are performed here(-id and +1)
; - 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 methodpick ()
will be executed, printingP Q
. Thread two, will evaluate id at that timeid = 0
; methodrelease()
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 methodpick ()
will be executed, printingP Q
. Thread one, will evaluate id at that timeid = 0
; methodrelease()
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.