thread priority

[Chris T.]

Running this code has two threads competing at same priority (5).
<pre>
public class ThreadTest extends Thread {
static boolean ok= true;
public static void main(String[] args) {
new ThreadTest().start();
for (int i= 0; i < 10; i++) {
System.out.println("waiting...");
yield();
}
ok= false;
}
public void run() {
while (ok) {
System.out.println("running...");
yield();
}
System.out.println("done");
}
}
</pre>
-----------------

All the textbooks and online sources say that the choice of which
thread "wins" is determined by Round-Robin arbitration if there is a
tie. So the outputs should be like:

waiting..
running..
waiting..
running..
waiting..
[...]
done..

But instead when I run it, sometimes it looks like

waiting...
waiting...
waiting...
waiting...
waiting...
waiting...
waiting...
waiting...
waiting...
waiting...
done

Does it not use round robin?

[Nikos Karampatziakis]

The problem is that there is no guarantee that when t.start() has
returned thread t is ready to run. So yield() may be doing nothing
because at that point there are no other threads ready to run.

-Nikos

[Robert Escriva]

This is a race condition. Yielding does *not* guarantee anything about
thread execution order.

Disclaimer: I do not deal with JVM internals. What follows is a
discussion of threads on a standard *NIX system. A sane implementation
of the JVM would simply reuse thread primitives provided by the
operating system, and so the following should apply equally well to
Java.

When a thread yields, it is voluntarily saying, "I have nothing more to
do, but can do more if you don't want to let someone else do something."
The end result is that you are seeing your execution run like:

Main: print("waiting...");
Main: yield
Main: print("waiting...");
Main: yield
Main: print("waiting...");
Main: yield
Main: print("waiting...");
Main: yield
Main: print("waiting...");
Main: yield
Main: print("waiting...");
Main: yield
Main: print("waiting...");
Main: yield
Main: print("waiting...");
Main: yield
Main: print("waiting...");
Main: yield
Main: print("waiting...");
Main: yield
Main: ok = false
ThreadTest: check the value of ok. It's false.
ThreadTest: print("done");

You've created ThreadTest, but it may not be ready to run when the main
thread calls "yield". Thus, the main thread keeps running.

If you need to control the order in which threads interleave (in your
case you want a ping-pong behavior), you need to explicitly enforce this
behavior[1][2][3][4]. Code which does not is broken.

I'd like to see which textbooks/online sources you are using as
statements about thread execution order are generally not specified
without discussion of the sources I cite.

-Robert

1. http://download.oracle.com/javase/6/docs/api/java/util/concurrent/package-summary.html
2. http://download.oracle.com/javase/6/docs/api/java/util/concurrent/atomic/package-summary.html
3. http://download.oracle.com/javase/6/docs/api/java/util/concurrent/locks/package-summary.html
4. http://en.wikipedia.org/wiki/List_of_Java_keywords

[Todd Warszawski]

I increased the number of loops in the for loop until the second thread started printing out running.  Even afterward, the print statements do not alternate, instead having long blocks of "waiting..." or "running...".  This example is in our online lecture material.  Could the thread still be not ready to run even after it has started running once?

[Robert Escriva]

Yielding frequently is inefficient. I pulled apart my JVM implementation and it
sometimes turns a "yield" into a NOP[1]. I didn't dig into it too far to find
out under exactly what conditions it does this conversion, but I bet that is the
cause of your trouble. On Solaris, this limit is roughly 100 yields per second.

I'd be willing to bet that if you do a test of the number of System.out.println
calls you can do per second, and then divide it by the number of items in each
block, you'll see how many times per second your Java implementation actually
does a yield. I bet it will be right around 100 (even though you likely don't
run Solaris).

This is above and beyond the goals of this course. Do not feel you are under
any pressure to actually do the above experiment. If you wish to do it, please
do it AFTER your final for this course.

Happy Hacking,
Robert

1. OpenJDK 6.0 hotspot/src/os/windows/vm/os_windows.cpp:3840
2. OpenJDK 6.0 hotspot/src/cpu/sparc/vm/globals_sparc.hpp:39

[Robert Escriva]

I want to add that figuring out the frequency of the yield=>NOP
conversion will not solve anything. The real problem with this code is
that it has a race condition which stems from relying upon the timing of
the yield operations to produce the proper behavior. What if the new
JVM changes to allow 101 yield operations per minute? What if your
power-saving kicks in? What if you run on a machine which can run two
threads in parallel?

You need to add some form of synchronization to make the program
correct.

-Robert