Two threads, the same static variable, same value, simultaneous access

Question

I was trying to prepare for the SCJP exam, which should take place next week, and I came across 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-} 

• What is true? (Select all that apply.)
• The output may be PQRS
• The output may be PRSQ
• The output may be PRQS
• The output may be PQPQ
• A program can cause a dead end.
• Fail compilation.

The answer says:
A, B and C are correct. Since select () is static and release () is non-stationary, these are two locks. If pick () was non-stationary, only A will be correct.

It also says that PQPQ output is actually not an option, and it is impossible to get such results.

At first, I really did not believe in the answer key, but then I saw that as a result of this application it is impossible to see this result. (After starting the class.)

Now, this part of me is a little confusing, And that's why

I thought a PQPQ or RSRS result should be possible. Because there is always a chance for a situation that makes the variable identifier the same for both threads. In other words, for example, when the first thread just finished executing line 6, it could abandon its queue to another, and after that another could change the value of the id variable, and then voila! They could go the same way if the block was happy .

I tried to see this situation again and again (with Eclipse Juno and Java 7). It just doesn't happen. I am sure that something is wrong with my thinking, and I am interested to know what it is. I need to know what is the rule that prevents these two threads from accessing the variable identifier in the same state.

Answer 1

In fact, there are many opportunities, some of which are highly unlikely, but they are still possible, and after 1 million executions this is what I found.

the 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... [RSPQ , PQRS , PRSQ , RPQS ] 100000... [RSPQ , PQRS , PRSQ , RPQS ] 150000... [RSPQ , PQRS , PRSQ , RPQS ] 200000... [RSPQ , PQRS , PRSQ , RPQS ] 250000... [RSPQ , PQRS , PRSQ , RPQS ] 300000... [RSPQ , PQRS , PRSQ , RPQS ] 350000... [RSPQ , PQRS , PRSQ , PRQS , RPQS ] 400000... [RSPQ , PQRS , PRSQ , PRQS , RPQS ] 450000... [RSPQ , PQRS , PRSQ , PRQS , RPQS ] 500000... [RSPQ , PQRS , PRSQ , PRQS , RPQS ] 550000... [RSPQ , PQRS , PRSQ , PRQS , RPQS ] 600000... [RSPQ , PQRS , PRSQ , PRQS , RPQS ] 650000... [RSPQ , PQRS , PRSQ , PRQS , RPQS ] 700000... [RSPQ , PQRS , PRSQ , PRQS , RPQS ] 750000... [RSPQ , PQRS , PRSQ , PRQS , RPQS ] 800000... [RSPQ , PQRS , PRSQ , PRQS , RPQS ] 850000... [RSPQ , PQRS , PRSQ , PRQS , RPQS ] 900000... [RSPQ , PQRS , PRSQ , PRQS , RPQS ] 950000... [PQPQ , RSPQ , PQRS , PRSQ , PRQS , RPQS ] done, results were: PQPQ : 1 RSPQ : 60499 PQRS : 939460 PRSQ : 23 PRQS : 2 RPQS : 15 

I think we have proven that PQPQ indeed possible, albeit with an extremely low probability of about one million ...

[edit: another run, other results showing RSRS :]

 done, results were: RSRS : 1 RPSQ : 2 PQPQ : 1 RSPQ : 445102 PQRS : 554877 PRSQ : 5 PRQS : 2 RPQS : 10 

Answer 2

Yes, you're right, maybe PQPQ .

You can increase the likelihood of this event with the following modification (this does not affect the 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 changes, I got PQPQ after several dozen runs.

Answer 3

Yes, your suspicion is true. However, the code in the run () method is simple enough to be executed in one CPU package, unless you expect any other means.

Answer 4

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

Among all the actions between the threads performed by each thread t, the program order t is the full order, which reflects the order in which these actions will be performed in accordance with the semantics inside the thread t.

The set of actions is sequentially coordinated if all actions are performed in full order (execution order), which is consistent with the order of the program, and, in addition, each read r of the variable v sees the value written in the record w on v such that:

• w comes to r in execution order, and
• there is no other entry w 'such that w comes before w' and w 'comes up to r in execution order.

Consistent consistency is a very strong guarantee that it will be displayed and streamlined during program execution. As part of a sequential sequential execution, there is a complete order over all individual actions (such as reading and writing) that are consistent with the order of the program, and each individual action is atomic and immediately visible to each stream.

AtomicInteger would be the best candidates to avoid this situation.

Answer 5

when the first thread has just completed execution of line 6, it can refuse its call to another, and after that the other can change the value of the id variable, and then voila! They could have done the same if the block had been happy.

Say thread 1 starts first. It flips the id value to 0. Now thread 1 is paused on line 8.

The 2nd stream will pass. He either sees the id value

• one

  All threads are allowed to cache fields locally if they are not marked as mutable. In stream 2, the id value is cached.

  The 2nd stream will pass. It flips the value to 0. And both of them are included in the first if block. If line 1 were paused in line 7. Results may vary.

  It is possible that the output of PQPQ

• 0

  He sees the inverted value from stream 1

  Changes the value to 1 again. The else block enters.

  Case of options A, B, C

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