Multithreading: Why this output? Is it deterministic?

Question

I'm learning to write better multi-threaded programs, thread-safe and deterministic. I came across this piece of code

// File Name : Callme.java
// This program uses a synchronized block.
  class Callme {
     void call(String msg) {
        System.out.print("[" + msg);
        try {
           Thread.sleep(1000);
        } catch (InterruptedException e) {
           System.out.println("Interrupted");
        }
        System.out.println("]");
     }
  }

  // File Name : Caller.java
  class Caller implements Runnable {
     String msg;
     Callme target;
     Thread t;
     public Caller(Callme targ, String s) {
        target = targ;
        msg = s;
        t = new Thread(this);
        t.start();
     }

     // synchronize calls to call()
     public void run() {
        synchronized(target) { // synchronized block
           target.call(msg);
        }
     }
  }
  // File Name : Synch.java
  public class Synch {
     public static void main(String args[]) {
        Callme target = new Callme();
        Caller ob1 = new Caller(target, "Hello");
        Caller ob2 = new Caller(target, "Synchronized");
        Caller ob3 = new Caller(target, "World");

        // wait for threads to end
        try {
           ob1.t.join();
           ob2.t.join();
           ob3.t.join();
        } catch(InterruptedException e) {
           System.out.println("Interrupted");
        }
     }
  }

which produces the following output(tried it ~100 times)

[Hello]
[World]
[Synchronized]

So my first question is, is this output guaranteed? I also observed that if I change sleep to 100 it still produces the same output, but if I change sleep to 10 the output changes to

[Hello]
[Synchronized]
[World]

Second question is, If it's guaranteed, why? Last but not the least, Why this output? I expected it to be

[Hello]
[Synchronized]
[World]

are you synching all threads, example: when first thread finishes it signals the second to write. Second finishes and singals the third to write. — huseyin tugrul buyukisik, Jun 19 '13 at 19:35
Starting a thread from the constructor of its `Runnable` target is wrong. The new thread can start executing the `run()` method before the constructor has finished initializing the object. The more general expression of this rule is never make an object visible to another thread before its constructor has returned. — erickson, Jun 19 '13 at 19:52

score 3 · Accepted Answer · edited May 23 '17 at 11:56

3

I think there are two pretty interesting things going on here.

The code tries to rely on a synchronization block to keep the order of the calls consistent. There are two problems with this:

1) The synchronization block isn't fair (see Synchronization vs Lock), so which ever thread gets to the locked synchronized block first may not be the first to be granted access to the object. According to that post, however, synchronization at the method level public synchronized void run() would be a fair lock (in Java 1.5, not Java 1.6), so the first one waiting on the lock would be the first granted access to the object.

2) Even if the synchronization block was fair, the first thread may not, in theory, (the [synchronized]) may not be the first to call some of the code in run(). The [world] could actually call it first.

edited May 23 '17 at 11:56

Community

1
1

answered Jun 19 '13 at 19:46

jmpyle771

635
5
15

1) is wrong, there is no fairness in synchronized methods, and making the run method synchronized would change nothing _even if it was fair_. – jtahlborn Jun 20 '13 at 00:19
See Brian Goetz's "Java Concurrency In Practice" book, section 13.3 for a full discussion of this topic. That was the claim made in the post I was referencing, that synchronized methods are fair (when specified at the method level). AND I didn't say that it would change the fact that its not deterministic. The fact that this block isn't fair just adds another layer of unpredictability to another layer of uncertain behavior. – jmpyle771 Jun 20 '13 at 02:56
So, even if the synchronized block was fair, the original layer of uncertainty would still exist. – jmpyle771 Jun 20 '13 at 03:03
Actually, http://sourceforge.net/apps/trac/lilith/wiki/SynchronizedVsFairLock says that it was fair on java 1.5, but changed with java 1.6. The book being referenced was written in the time of Java 1.5. Thanks for pointing this out. – jmpyle771 Jun 20 '13 at 03:16
1

Fairness isn't prescribed by the JLS but some JVMs have a 'fair' implementation i.e. in HotSpot the wait set on a monitor is implemented as a queue. – selig Jun 21 '13 at 14:32

score 2 · Answer 2 · answered Jun 19 '13 at 19:15

2

No, the output is not guaranteed.

answered Jun 19 '13 at 19:15

jtahlborn

52,909
5
76
118

Is there any reason why I'm getting that output all the times? – vidit Jun 19 '13 at 19:21
3

Race conditions tend to be "deterministic" in testing scenarios and only break when loads spike (i.e. in production). that's what make them so "fun" to track down. – jtahlborn Jun 19 '13 at 19:23

score 1 · Answer 3 · answered Jun 19 '13 at 19:42

There is no output order guaranteed; the output is totally random as it is decided by the OS to which thread should allocate the CPU at a certain amount of time. The algorithms that allocate thread time to CPU are non-deterministic.

To make the code print Hello, Synchronized, World in this order you should change Synch to:

Caller ob1 = new Caller(target, "Hello");
ob1.t.join();
Caller ob2 = new Caller(target, "Synchronized");
ob2.t.join();
Caller ob3 = new Caller(target, "World");
ob3.t.join();

Also there is no need for the synchronized block (in the way it's written) since only one thread will call the run method; also msg is only read, not written to cause any problems and call method on target does not change the state of target in any way.

score 1 · Answer 4 · answered Jun 19 '13 at 20:05

1

The order of the outputs is not guaranteed. The synchronized block prevents the different threads from interleaving while they print their outputs, but it does nothing to ensure any order of the three different outputs. The "deterministic-looking" behavior that you're seeing is unfortunately just chance.

answered Jun 19 '13 at 20:05

Henry Keiter

16,863
7
51
80

But highly likely chance due to the amount of time threads are given on the cpu and the amount of code being run :) ... but yes, still chance. – selig Jun 21 '13 at 14:34

Multithreading: Why this output? Is it deterministic?

4 Answers4