9


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.

7
  • 2
    R S R S is definitely not possible since "R S" is triggered if id==0, and it definitely wont get there by itself. "P Q P Q" seems possible to me though - both threads see id==1 (run() isnt synchronized), both call pick() ....
    – radai
    Jul 11, 2013 at 7:06
  • R S R S is possible when they both run, decrement id so that's -1 and then enter the conditional. Highly unlikely though as the first thread would have to be interrupted after the decrement.
    – selig
    Jul 11, 2013 at 7:13
  • PQPQ is not possible because the there can be only one thread to arrive the if statement at line 7 with id value 0. The reason for that is that the two threads must go through line 6 and therefore, in case one thread is left behind, it will have the value -1 when reaching line 7. If the two threads travel together, then both of them will have id value -1 when reaching line 7.
    – Tsikon
    Jul 11, 2013 at 7:13
  • @Tsikon - nope. dont think just because you see it as one line of java its atomic. you can think of "id = 1 - id" as "int temp = id-1; id=temp;".
    – radai
    Jul 11, 2013 at 7:24
  • @Tsikon how did you really find the -1 value by 1-id!? and how are you really sure about only just one thread at time would be line 7?
    – user2511414
    Jul 11, 2013 at 7:25

5 Answers 5

7

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
5
  • +1 for good work. 1 in million is a coincidence (not statistically meaningful) and you can't determine PQPQ probability based on it. Though it does prove that such combination is possible.
    – Dariusz
    Jul 11, 2013 at 7:33
  • 1
    That's one fine answer sir, i appreciate it. That proves OCP Java SE 6 Programmer Practice Exams book had a flaw. Thanks to Bates and Sierra anyway. (: Jul 11, 2013 at 7:34
  • I think there is a problem with test! in original code two method can work together because first method hold the class lock and second holds object lock but in you test they both need a lock for stringbuffer so this is not a fair test :) Jul 11, 2013 at 7:35
  • @3yanlis1bos And it wouldn't be the first time either :) Good luck with your exam, in any case (it's actually easier than the books...) Jul 11, 2013 at 7:37
  • @vikingsteve Oh, it's nice to hear that. There questions were giving me a hard time, but i surely can say that i learned a lot. Thanks for good wishes. :) Jul 11, 2013 at 7:40
1

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.

1

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.

1

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.

0

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.

Let's say thread 1 starts first. It flips the value of id to 0. Thread 1 is now suspended at line 8.

Thread 2 starts. It either sees the value of id

  • 1

    All threads are allowed to cache fields locally unless they are marked as volatile. Thread 2 caches the value of id.

    Thread 2 starts. It flips the value to 0. And they both enter the first if block. Had Thread 1 been suspended on line 7. The results might have different.

    It is possible that the output is P Q P Q

  • 0

    It sees the flipped value from thread 1

    Changes the value to 1 again. Enters the else block.

    The case of options A, B, C

It is not even guaranteed that thread 1 starts before thread 2.

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.