Two threads, same static variable, same value, concurrent access

Question

i've been trying to get ready for the SCJP exam that i have to take next week, and i've encountered this question about Java Threads.

1-public class Stone implements Runnable {
2-  static int id = 1;
3-
4-  public void run() {
5-      try {
6-          id = 1 - id;
7-          if (id == 0) {
8-                      pick();
9-          } else {
10-             release();
11-         }
12-
13-     } catch (Exception e) {
14-     }
15- }
16-
17- private static synchronized void pick() throws Exception {
18-     System.out.print("P ");
19-     System.out.print("Q ");
20- }
21-
22- private synchronized void release() throws Exception {
23-     System.out.print("R ");
24-     System.out.print("S ");
25- }
26-
27- public static void main(String[] args) {
28-     Stone st = new Stone();
29-     new Thread(st).start();
30-     new Thread(st).start();
31- }
32-}

• Which are true? (Choose all that apply.)
• The output could be P Q R S
• The output could be P R S Q
• The output could be P R Q S
• The output could be P Q P Q
• The program could cause a deadlock.
• Compilation fails.

The answer key says:
A, B, and C are correct. Since pick() is static and release() is non-static, there are two locks. If pick() was non-static, only A would be correct.

It also says that the output P Q P Q is not really an option and It's not possible to get such results.

At the beginning, i didn't really believe the answer key, but then i saw that it's really not possible to see this output as a result of this application. (After running the class.)

Now, that's the part that confuses me a little bit, And here is why

I thought a P Q P Q or an R S R S result must have been possible. Because there is always a chance for a situation that makes the variable id exactly same for both threads. In other words, for example, when the first thread just finished executing the line 6 it could give up its turn to the other one, and after that, the other one could change the value of the variable id and then voila! They could go in to same if block happily.

I tried to see this situation over and over again (with Eclipse Juno and Java 7). It just doesn't happen. I'm sure that there something wrong with my way of thinking, and i wonder to know what it is. I need to know what is the rule that hinders these two threads to access the variable id at its same state.

Answer 1

Actually, there are quite a few possibilities, some extremely unlikely, but they are still possible nonetheless and after 1 million executions this is what I found.

Code:

public class Stone implements Runnable {
    static int id = 1;
    static StringBuffer buffer = new StringBuffer();

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

        } catch (Exception e) {
        }
    }

    private static synchronized void pick() throws Exception {
        buffer.append("P ");
        buffer.append("Q ");
    }

    private synchronized void release() throws Exception {
        buffer.append("R ");
        buffer.append("S ");
    }

    public static void main(String[] args) {
        int count = 1000000;
        Map<String, Integer> results = new HashMap<String, Integer>();
        System.out.println("Running " + count + " times...");
        for (int i = 0; i< count; i++) {
            buffer = new StringBuffer();
            Stone stone = new Stone();
            Thread t1 = new Thread(stone);
            Thread t2 = new Thread(stone);
            t1.start();
            t2.start();
            while (t1.isAlive() || t2.isAlive()) {
                // wait
            }
            String result = buffer.toString();
            Integer x = results.get(result);
            if (x == null) x = 0;
            results.put(result, x + 1);
            if (i > 0 && i % 50000 == 0) System.out.println(i + "... " + results.keySet());
        }
        System.out.println("done, results were:");
        for (String key : results.keySet()) {
            System.out.println(" " + key + ": " + results.get(key));
        }
    }
}

Results:

Running 1000000 times...
50000... [R S P Q , P Q R S , P R S Q , R P Q S ]
100000... [R S P Q , P Q R S , P R S Q , R P Q S ]
150000... [R S P Q , P Q R S , P R S Q , R P Q S ]
200000... [R S P Q , P Q R S , P R S Q , R P Q S ]
250000... [R S P Q , P Q R S , P R S Q , R P Q S ]
300000... [R S P Q , P Q R S , P R S Q , R P Q S ]
350000... [R S P Q , P Q R S , P R S Q , P R Q S , R P Q S ]
400000... [R S P Q , P Q R S , P R S Q , P R Q S , R P Q S ]
450000... [R S P Q , P Q R S , P R S Q , P R Q S , R P Q S ]
500000... [R S P Q , P Q R S , P R S Q , P R Q S , R P Q S ]
550000... [R S P Q , P Q R S , P R S Q , P R Q S , R P Q S ]
600000... [R S P Q , P Q R S , P R S Q , P R Q S , R P Q S ]
650000... [R S P Q , P Q R S , P R S Q , P R Q S , R P Q S ]
700000... [R S P Q , P Q R S , P R S Q , P R Q S , R P Q S ]
750000... [R S P Q , P Q R S , P R S Q , P R Q S , R P Q S ]
800000... [R S P Q , P Q R S , P R S Q , P R Q S , R P Q S ]
850000... [R S P Q , P Q R S , P R S Q , P R Q S , R P Q S ]
900000... [R S P Q , P Q R S , P R S Q , P R Q S , R P Q S ]
950000... [P Q P Q , R S P Q , P Q R S , P R S Q , P R Q S , R P Q S ]
done, results were:
P Q P Q : 1
R S P Q : 60499
P Q R S : 939460
P R S Q : 23
P R Q S : 2
R P Q S : 15

I think we have proved that P Q P Q is indeed possible, even though at an extremely low probability of around one in a million...

[edit: another run, different results showing R S R S is also possible:]

done, results were:
 R S R S : 1
 R P S Q : 2
 P Q P Q : 1
 R S P Q : 445102
 P Q R S : 554877
 P R S Q : 5
 P R Q S : 2
 R P Q S : 10

Answer 2

Yes, you are right, P Q P Q is possible.

You can increase probability of this event by the following modification (it doesn't affect semantics of the program):

public class Stone implements Runnable {
    static int id = 1;
    static CyclicBarrier b = new CyclicBarrier(2);

    public void run() {
        try {
            b.await(); // Increase probability of concurrent execution of subsequent actions

            int t = id;

            Thread.yield(); // Increase probability of thread switch at this point

            id = 1 - t;

            Thread.yield(); // Increase probability of thread switch at this point

            if (id == 0) {
                pick();
            } else {
                release();
            }
        } catch (Exception e) {}
    }
    ...
}

After applying these modifications I got P Q P Q after a few dozens of runs.

Answer 3

Yes your suspicion is right. However, the code in the run() method is simple enough to be executed in one CPU burst, unless waited by some other means.

Answer 4

You are correct in your assumption. P Q P Q is indeed possible because JLS Specification 17.4.3 states the following:

Among all the inter-thread actions performed by each thread t, the program order of t is a total order that reflects the order in which these actions would be performed according to the intra-thread semantics of t.

A set of actions is sequentially consistent if all actions occur in a total order (the execution order) that is consistent with program order, and furthermore, each read r of a variable v sees the value written by the write w to v such that:

• w comes before r in the execution order, and
• there is no other write w' such that w comes before w' and w' comes before r in the execution order.

Sequential consistency is a very strong guarantee that is made about visibility and ordering in an execution of a program. Within a sequentially consistent execution, there is a total order over all individual actions (such as reads and writes) which is consistent with the order of the program, and each individual action is atomic and is immediately visible to every thread.

AtomicInteger's would be better candidates to avoid this situation.