Java Thread Ping Pong example

Question

I'm trying to understand thread basics, and as a first example I create two thread that write a String on the stdout. As I know the scheduler allows to execute the threads using a round robin schedule. Thats why I got:

PING PING pong pong pong PING PING PING pong pong

Now I want to use a shared variable, so every thread will know if its your turn:

public class PingPongThread extends Thread {
private String msg;
private static String turn;

public PingPongThread(String msg){
    this.msg = msg;
}
@Override
public void run() {
    while(true) {
        playTurn();
    }

}
public synchronized void playTurn(){
    if (!msg.equals(turn)){
        turn=msg;
        System.out.println(msg);
    }
}
}

Main class:

public class ThreadTest {
    public static void main(String[] args) {
        PingPongThread thread1 = new PingPongThread("PING");
        PingPongThread thread2 = new PingPongThread("pong");
        thread1.start();
        thread2.start();
    }
}

I synchronized the "turn manager" but I still get something like:

PING PING pong pong pong PING PING PING pong pong

Can someone explains what I am missing, and Why I'm not getting Ping pong... ping pong. Thanks!

Solution 1

This line:

public synchronized void playTurn(){
    //code
}

is equivalent in behavior to

public void playTurn() {
    synchronized(this) {
         //code
    }
}

that's why no synchronization is occuring, because as Brian Agnew pointed out, the threads are synchronizing on two different objects (thread1, thread2), each on it's own instance resulting in no effective synchronization.

If you would use your turn variable for synchronization, e.g.:

private static String turn = ""; // must initialize or you ll get an NPE

public void playTurn() {
    synchronized(turn) {
         //...
         turn = msg; // (1)
         //...
    }
}

then the situation is a lot better (run multiple times to verify), but there is also no 100% synchronization. In the beggining (mostly) you get a double ping and double pong, and afterwards they look synchronized, but you still can get double pings/pongs.

The synchronized block locks upon value (see this great answer) and not the reference to that value. (see EDIT)

So let's take a look at one possible scenario:

thread1 locks on ""
thread2 blocks on ""
thread1 changes the value of turn variable to "PING" - thread2 can continue since "" is no longer locked 

To verify that I tried putting

try {
    Thread.currentThread().sleep(1000); // try with 10, 100 also multiple times
 } 
 catch (InterruptedException ex) {}

before and after

turn = msg;

and it looks synchronized?! But, if you put

 try {
    Thread.yield();
    Thread.currentThread().sleep(1000); //  also  try multiple times
 } 
 catch (InterruptedException ex) {}

after few seconds you'll see double pings/pongs. Thread.yield() essenitally means "I'm done with the processor, put some else thread to work". This is obviously system thread scheduler implementation on my OS.

So, to synchronize correctly we must remove line

    turn = msg;

so that threads could always synchronize on the same value - not really :) As explained in the great answer given above - Strings (immutable objects) are dangerous as locks - because if you create String "A" on 100 places in your program all 100 references(variables) will point to the same "A" in memory - so you could oversynchronize.

So, to answer your original question, modify your code like this:

 public void playTurn() {
    synchronized(PingPongThread.class) {
         //code
    }
}

and the parallel PingPong example will be 100% correctly implemented (see EDIT^2).

The above code is equivalent to:

 public static synchronized void playTurn() {
     //code
 }

The PingPongThread.class is a Class object, e.g. on every instance you can call getClass() which always has only one instance.

Also you could do like this

 public static Object lock = new Object();

 public void playTurn() {
    synchronized(lock) {
         //code
    }
}

Also, read and program examples(running multiple times whenever neccessary) this tutorial.

EDIT:

To be technically correct:

The synchronized method is the same as synchronized statement locking upon this. Let's call the argument of the synchronized statement "lock" - as Marko pointed out, "lock" is a variable storing a reference to an object/instance of a class. To quote the spec:

The synchronized statement computes a reference to an object; it then attempts to perform a lock action on that object's monitor..

So the synchronizaton is not acutally made upon value - the object/class instance, but upon the object monitor associated with that instance/value. Because

Each object in Java is associated with a monitor..

the effect remains the same.

EDIT^2:

Following up on the comments remarks: "and the parallel PingPong example will be 100% correctly implemented" - meaning, the desired behavior is achieved (without error).

IMHO, a solution is correct if the result is correct. There are many ways of solving the problem, so the next criteria would be simplicity/elegance of the solution - the phaser solution is better approach, because as Marko said in other words in some comment there is a lot lesser chance of making error using phaser object than using synchronized mechanism - which can be seen from all the (non)solution variants in this post. Notable to see is also comparison of code size and overall clarity.

To conclude, this sort of constructs should be used whenever they are applicable to the problem in question.

Solution 2

In conclusion to my discussion with Brian Agnew, I submit this code that uses java.util.concurrent.Phaser to coordinate your ping-pong threads:

static final Phaser p = new Phaser(1);
public static void main(String[] args) {
  t("ping");
  t("pong");
}
private static void t(final String msg) {
  new Thread() { public void run() {
    while (true) {
      System.out.println(msg);
      p.awaitAdvance(p.arrive()+1);
    }
  }}.start();
}

The key difference between this solution and the one you attempted to code is that your solution busy-checks a flag, thereby wasting CPU time (and energy!). The correct approach is to use blocking methods that put a thread to sleep until it is notified of the relevant event.

Solution 3

Each instance of the PingPongThread is synchronising on itself and not on a shared resource. In order to control the message passing you'll need to synchronise on a shared resource (e.g. your turn variable ?)

However I don't think this is really going to work. I think you should check out wait() and notify() to do this (if you want to understand the threading primitives). See this for an example.

Comments

[Marko Topolnik]

Better suggest a java.util.concurrent synchronizer, such as Phaser or CountDownLatch.

[Brian Agnew]

@Marko - I was wondering about that. If the aim is to understand the threading primitives, then I stand by the above. However I would certainly advocate your approach for 'production' type code!

[Marko Topolnik]

New Java users simply shouldn't be exposed to wait and notify, except under the category "advanced programming". This a very raw mechanism resulting in either wrong usage or much boilerplate to implement it right. That just sidetracks learners.

[Brian Agnew]

Note the OP's comment about trying to understand thread basics. However, my other thought was to go in completely the opposite direction and suggest an Actor framework (e.g. Akka). After all, that's the perfect abstraction here

[Marko Topolnik]

I just feel that the basics don't always mean "how it's implemented down below", otherwise everyone should start learning Java by first learning CPU architecture, assembler, and C. I agree with your point with Akka (my example in that direction would be the Executor Framework). These tools abstract away the whole concept of threads, but they get the job done the proper way. Synchronizers are the "middle ground" here, basically they just encapsulate the correct wait-notify idioms in a foolproof package.

[Marko Topolnik]

It really is questionable whether the user, as a first lesson, should learn about spurious wakeups and wait sets. In fact, it would be best for most Java users if they never needed to get to the bottom of these low-level artifacts. They are in almost the same category as JNI, for example, or the Unsafe class.

[linski]

It makes me real angry and sad that gentlemen with such great knowledge (and skyrocket rep), first, don't actually answer the question to someone who wants to learn and understand, and secondly, the only advice to his original question is actually wrong and then continue with (very interesting and valuable) discussion which cant help him much (at this point). As to the discussion - if we were talking about learnign programming (paradigms) I would 100% agree. But threading is actually about assembler(where C,Java primitives are just a more readable form) and must be understood at...

[linski]

the level they exist - which is the primitive level. Upon understanding that I would agree to move on the concepts you described. It would be like learning to integrate before you know how to add.

[Marko Topolnik]

@linski Do you also propose that everyone must understand the notions of the p-n barrier, Fermi distribution, conduction bands, CMOS transistors, etc, before daring to code in assembler?

[linski]

LoL, of course not. But if you want to make your own homemade remote control, then you should know something about that, no? I suppose that we agree that you must understand the problem before you can succesfully program it. And in this example also, you must contemplate the execution of the code line by line which is what happens at machine code level - and no I don't think you should program in binary code nor asm, but at first more readable interpretation which is close enough. To correct myself I'would agree that it need not be the very first..

[linski]

but I think it must be amongst the beggining examples. Actually I thought that in the first comment but expressed myself wrongly, sorry about that.

[Marko Topolnik]

@linski It should be more than enough to understand your code at the level of the contract of the APIs/language features you use. So if you use Phaser, as I propose, there will be no need to get involved with wait/notify. Understanding Phaser is quite a bit simpler -- and more empowering -- than wasting time on understanding and debugging wait/notify.

[linski]

let us continue this discussion in chat

[linski]

Kummo I strongly suggest to study the Phaser example - it is very elegant solution. API doc here

[Marko Topolnik]

This statement confuses me: "The synchronized block locks upon value of the variable and not the reference to that value." But the value of a variable is a reference and, indeed, each distinct reference value is associated with a unique monitor (of the unique object that particular value refers to).

[Marko Topolnik]

Also, I would really hesitate to call a busy-waiting solution "correct". Even though it is correct in the narrow technical sense, calling it that without qualification is not exactly educational.

[linski]

The Java terminology (e.g. pointer/reference saga) is confusing :) I updated as suggested, pls verify. I don't understand what do you mean by "without qualification" - please explain and Ill gladly update the post accordingly

[linski]

I think I understood what you ment by "...without qualification is not exactly educational". Thanks for the input :)

[kirhgoff]

Just wonder, how could you be sure both a and b wont do several loops before b.wait() is called?

[Kitten]

Don't lock on String constants since the string gets interned and two threads that should be using different monitors might actually be using the same one.