Threads - How to approach such a question?

[Vyas Sanzgiri]

This question is from Sun practice exams. I need to understand how to approach such a question:

  
Given:


 5. class NoGo implements Runnable {
 6.   private int i;
 7.   public void run() { 
 8.     if (i%10 != 0) { i++; }
 9.     for(int x=0; x<10; x++, i++) 
10.       { if (x == 4) Thread.yield(); }
11.     System.out.print(i + " ");
12.   }
13.   public static void main(String [] args) {
14.     NoGo n = new NoGo();
15.     for(int x=0; x<100; x++) { new Thread(n).start(); }
16.   }
17. }


 

Which is true?


A The output can never contain the value 10.
B The output can never contain the value 30.
C The output can never contain the value 297.
D The output can never contain the value 1020.
E The output can never contain the value 1130.

[Ruben Soto]

You have 100 threads with the same target, and each thread can increment i at most 11 times. Then, 1130 seems impossible. The rest of the items I think are plausible, as there is very little guaranteed.

The way I approach this: Look at what each thread does. Is the method that changes state synchronized, or not? Cross out the statement with the yield() invocation (as that is not guaranteed to do anything.) And remember that very little is guaranteed when multiple threads access the same object without synchronization.

[John Kimball]

Unless I'm missing something, ask yourself this: What is i's initial value?

[Vyas Sanzgiri]

doesn't i go from 0 to 9 which is 10 values?

[John Kimball]

Sorry, I crossed wires. I was thinking of i as a local variable

[mansi gupte]

Ruben Soto wrote:You have 100 threads with the same target, and each thread can increment i at most 11 times. Then, 1130 seems impossible. The rest of the items I think are plausible, as there is very little guaranteed.

The way I approach this: Look at what each thread does. Is the method that changes state synchronized, or not? Cross out the statement with the yield() invocation (as that is not guaranteed to do anything.) And remember that very little is guaranteed when multiple threads access the same object without synchronization.

can you explain how did you come to this conclusion [ marked in bold] ??

[Vyas Sanzgiri]

I am not able to still understand how to solve such weird questions. Looks more like a mathematical question with no programming concepts!

[Ruben Soto]

piya rai wrote:

Ruben Soto wrote:You have 100 threads with the same target, and each thread can increment i at most 11 times. Then, 1130 seems impossible. The rest of the items I think are plausible, as there is very little guaranteed.

The way I approach this: Look at what each thread does. Is the method that changes state synchronized, or not? Cross out the statement with the yield() invocation (as that is not guaranteed to do anything.) And remember that very little is guaranteed when multiple threads access the same object without synchronization.

can you explain how did you come to this conclusion [ marked in bold] ??

Piya,

Look at the code:

 5. class NoGo implements Runnable {
 6.   private int i;
 7.   public void run() { 
 8.     if (i%10 != 0) { i++; }
 9.     for(int x=0; x<10; x++, i++) 
10.       { if (x == 4) Thread.yield(); }
11.     System.out.print(i + " ");
12.   }
13.   public static void main(String [] args) {
14.     NoGo n = new NoGo();
15.     for(int x=0; x<100; x++) { new Thread(n).start(); }
16.   }
17. }

Each thread can increment i once at line 8, and 10 times in the for loop. Total is 11 times per thread. Since we have 100 threads, that makes a total number of possible increments of 1100.

[Vyas Sanzgiri]

I see how you get to the answer and I know that answer is correct.

But line 8 will not execute every time.

[Ruben Soto]

Vyas Sanzgiri wrote:I see how you get to the answer and I know that answer is correct.

But line 8 will not execute every time.

Vyas,

I know it won't execute everytime. But that will only make the total number less than 1100, and we are just wanting to prove that 1130 is impossible. You have to know when you can simply approximate a number and bound it. What I did is provide an upper bound for the number of increments (although that upper bound can't be practically attained.) As long as the upper bound is less than 1130, you can be sure that the actual value of i will always be less than 1130.

[Vyas Sanzgiri]

point noted. Thanks!