How do you think through and predict the output of a threading question like this?

Question

I'm prepping for the SCJP, and multithreading has been my shakiest area, mostly because I don't know how to look at multithreading code and walk through it. So far my approach has been to write down in English what might be happening in each thread and testing a few cases with threads randomly intersecting each other, which is a really hit-and-miss and time-consuming approach. So I'd like to see how a pro would go about it. Would you be willing to read the code below (it's the latest question that's giving me trouble) and write down what goes through your head (code-related stuff only, please :) as you work out the possible outputs? The choices that come with the question are at the end. What I'm looking for isn't the solution, which I have, but how one arrives at the solution efficiently on the exam.

And yeah, I know this question doesn't have a precise answer, etc etc. Accepted vote goes to the answer that's clearest and easiest to emulate, okay :)

Thanks everyone!

Question: Which of these answers are possible outputs?

public class Threads1 {

    int x = 0;

    class Runner implements Runnable {

        public void run() {
            int current = 0;
            for (int i = 0; i < 4; i++) {
                current = x;
                System.out.print(current + ", ");
                x = current + 2;
            }
        }
    }

    public static void main(String[] args) {
        new Threads1().go();
    }

    public void go() {
        Runnable r1 = new Runner();
        new Thread(r1).start();
        new Thread(r1).start();
    }
}

Choices (choose all that apply):

A. 0, 2, 4, 4, 6, 8, 10, 6,

B. 0, 2, 4, 6, 8, 10, 2, 4,

C. 0, 2, 4, 6, 8, 10, 12, 14,

D. 0, 0, 2, 2, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, 14, 14,

E. 0, 2, 4, 6, 8, 10, 12, 14, 0, 2, 4, 6, 8, 10, 12, 14,

Answer 1

My approach to multi-threaded problems is to break up the code that the thread will run and then determine how many threads will run that code and if the access any variables that other threads could potentially use.

In the example, there are 3 threads. The main thread calls new Threads1().go();, creates r1, and starts 2 more threads, new Thread(r1).start(); and new Thread(r1).start();. Now that we know how many threads we can track what they are going to do.

The main thread is going to die after it returns from go().

The other 2 threads are each going to enter the run() method of the Runner object, r1. Now what we also know is that each thread will execute run(). So lets look at what run() does. It has a for loop that prints output each time it executes the loop. Therefore the call to run() will print 4 times. So 2 threads each thread will print 4 times. Therefore the output cannot have any more than 8 numbers.

Regarding what those digits will be is not really going to be possible since the Runner instance will be the same for each thread the x variable can change based on the other thread that is also calling run(). Therefore all you need to determine is, is the sequence of digits possible? The answer to that question is 'yes' for A and C. This is due to the fact that you have no idea when each thread will be preempted by the other and since during the loop there is a local copy being made, you could get some very unique orderings.

As mentioned below by SB the, option B even though it has 8 outputs it is not possible. Try and come up with a thread sequence to create that output.

Answer 2

A and C (assuming the question is Which of these answers are possible outputs?)

The hard part, of course, isn't when you find a possible solution. But rather, its to look hard at the ones that you think are not possible and try to convinced yourself that you've got a solid reason why its not possible and that you've eliminated all the ways to get around your reason.

So far my approach has been to write down in English what might be happening in each thread ...

You need to figure out which thread printed each number. Below is the most efficient, succinctness format I could think of represent that and make it easy to crossout/erase/write-over as you work through possibilities. Realize:

• Once you find an possible answer move on. It doesn't matter if it isn't likely in the real world or that there may be other possible (or impossible) combinations. As long as you found 1 possibility, that's all you need to move on.

• Try the simplest approach first, e.g. assume T1 for each number until you hit a number that couldn't be T1, so you fill in T2, and so on.. Hopefully, you get to the end with no contradiction (or contradictions that are easy to resolve). Once you've found a possible combination, move on.

• Feel free to skip around to eliminate the possible ones quickly so you can focus on the likely impossible ones.

Here is the final edit of my scratch-paper/worksheet (appended with my mental annotations):

A. 0, 2, 4, 4, 6, 8, 10, 6,
   1  1  1  2  2  2   2  1     <- possible threads that produced this output - possible solution

B. 0, 2, 4, 6, 8, 10, 2, 4,
   1  2  2  2  2   ?  1        <- to print second '2', T1 interrupted between L10/L11; 4 passes of T2 used up

C. 0, 2, 4, 6, 8, 10, 12, 14,
   1  1  1  1  2   2   2   2   <- possible solution - simplest solution (T2 waits until T1 is completely done) - doesn't matter that it isn't likely, just that is possible

D. 0, 0, 2, 2, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, 14, 14,
   1  2  1  2  1  2  1  2  1  2   ?    <- threads used up

E. 0, 2, 4, 6, 8, 10, 12, 14, 0, 2, 4, 6, 8, 10, 12, 14,
   1  1  1  1  2   2   2   2  ?   <- threads used up

Note:

http://download.oracle.com/javase/tutorial/essential/concurrency/atomic.html

• Reads and writes are atomic for reference variables and for most primitive variables (all types except long and double).
• ...

Atomic actions cannot be interleaved, so they can be used without fear of thread interference.

Answer 3

This question is a lot more deceptive than it looks -- I'm liking it the more I think about it. I started my answer talking about how I look at thread programs -- I analyze the synchronization points and the I/O calls. But this has none except for the println which has no internal synchronization. So we are left with random timing (see race conditions). This combined with no guaranteed way to synchronize the values of x between the threads means that it will be random.

However, if we look at the answers, we can see that some of the answers cannot occur. For example, as @linuxuser27 pointed out, each thread prints out 4 numbers only which removes answers will more numbers printed. Another example of an improper answer would be if any of the answers had a value larger than 14 since the first thread can go 0,2,4,6 and the 2nd could take it to 8,10,12,14 but no higher.

Since each of the threads must print a number 4 times and numbers printed by each thread must be at least 2+ the previous number the thread printed, some of the patterns cannot be generated. I won't give my answer but is is not 'all of the above' and it is not A, B, and C.