Is it a safe assumption when it comes to THREADS?

[Barkat Mardhani]

Hi All gurus,
I am just begining to understand threads. But following is puzzling me.
In most thread codes, the main thread creates a second thread. After start() statement, jvm has two candidate threads to chose from; main or second thread. In many thread questions, I observed, it is automatically assumed that main thread will be executed first. Is that safe assumption? To find how many times jvm chose second thread, I wrote following code. It asserts that about 15-20% of times, second thread will be executed first. I do not think that can be safely ignored.

<font size="2">class Test implements Runnable {
static int counter = 0; 
static boolean b = false;
static int trials = 1000;
public static void main(String[ ] args) {
if (args.length > 0) trials = Integer.parseInt(args[0]) ; 
for (int i = 0 ; i < trials ; i++) { 
b = false ;
Thread t = new Thread(new Test() , "2nd thread" );
t.start();
synchronized (t) { 
if (b) { counter++ ; b = false; } else b = false;
} 
}
System.out.println(counter);
}
synchronized public void run() { b = true ;} // 2nd thread run before main continued.
}
</font>

Here is an example from K & B. If second thread goes first, the main thread is going to wait for ever:

<font size="2"> 1. class ThreadA {
2. public static void main(String [] args) {
3. ThreadB b = new ThreadB();
4. b.start();
5.
6. synchronized(b) {
7. try {
8. System.out.println("Waiting for b to complete...");
9. b.wait();
10. } catch (InterruptedException e) {}
11. }
12. System.out.println("Total is: " + b.total);
13. }
14. }
15.
16. class ThreadB extends Thread {
17. int total;
18.
19. public void run() {
20. synchronized(this) {
21. for(int i=0;i<100;i++) {
22. total += i;
23. }
24. notify();
25. }
26. }
27. } </font>

[ September 25, 2003: Message edited by: Barkat Mardhani ]

[Alton Hernandez]

Originally posted by Barkat Mardhani:
In many thread questions, I observed, it is automatically assumed that main thread will be executed first. Is that safe assumption?

I would not use the words executed first. Instead, I would say that it is wrong to assume that the main thread will not be swapped out.
The fact that it is the main thread that started the 2nd thread means that it is already executing. However, anytime the JVM may decide that the main thread had enough execution time and be swapped out. For a similar reason, ,it would also be wrong to assume that the main thread will reach a synchronized method or synchronized block first(i.e. ahead of the 2nd thread) simply because it is started first.
[ September 24, 2003: Message edited by: Alton Hernandez ]

[Steve Lovelace]

Barkat:
Not a guru, sorry, but you got me interested. I ran your code and sure enough, the counter got hit about 18% of the time. So then I wondered if there might be some noise in the count, because the test loop can step on its own tail like this:
1. main creates t1, starts it
2. main locks t1 first, sets b to false
3. main releases t1 lock
4. main creates t2, starts it
5. main locks t2 first
6. t1 locks (on itself) and runs, sets b to true
7. main increments counter
The new thread is the object being used for the lock each time. This means there is no synchronization between main and the previously created thread. I changed one line of your code to force main to wait for the second thread to finish. This way each loop starts clean. (At least, this is what I'm trying to do.)

 class Test implements Runnable {
static int counter = 0;
static boolean b = false;
static int trials = 1000;
public static void main(String[ ] args) {
if (args.length > 0) trials = Integer.parseInt(args[0]) ;
for (int i = 0 ; i < trials ; i++) {
b = false ;
Thread t = new Thread(new Test() , "2nd thread" );
t.start();
synchronized (t) {
if (b) { counter++ ; b = false; }
else try {t.join();} catch (Exception ex) {};
}
}
System.out.println(counter);
}
synchronized public void run() { b = true ;} // 2nd thread run before main continued.
} 

But now I don't understand the results: it says that main wins every time, and your contention that it might not always win seems right to me. So I tried another variation: this is your original code except that all threads are locking on the same object.

 class Test implements Runnable {
static int counter = 0;
static boolean b = false;
static int trials = 1000;
static Object lock = new Object();
public static void main(String[ ] args) {
if (args.length > 0) trials = Integer.parseInt(args[0]) ;
for (int i = 0 ; i < trials ; i++) {
b = false ;
Thread t = new Thread(new Test() , "2nd thread" );
t.start();
synchronized (lock) {
if (b) { counter++ ; b = false; } else b = false;
}
}
System.out.println(counter);
}
public void run() {synchronized (lock) {b = true;}} // 2nd thread run before main continued.
} 

Now we're back to 18% wins for the new thread. Thinking about this, I realized that even with good synchronization, main doesn't know if b has just been set to true by the new thread winning, or by the previous losing thread. So I tried one more. This is the above code except that each thread (via its runnable) remembers which trial it belongs to. It only updates b if it is in the right trial, i.e., really won.

 class Test implements Runnable {
static int counter = 0;
static boolean b = false;
static int trials = 1000;
static Object lock = new Object();
static int currentTrial;
int trial;
public static void main(String[ ] args) {
if (args.length > 0) trials = Integer.parseInt(args[0]) ;
for (int i = 0 ; i < trials ; i++) {
currentTrial = i;
b = false ;
Thread t = new Thread(new Test(i) , "2nd thread" );
t.start();
synchronized (lock) {
if (b) { counter++ ; b = false; } else b = false;
}
}
System.out.println(counter);
}
Test(int i) {trial = i;}
public void run() {
synchronized (lock) {
if (currentTrial == trial) b = true;
}
} // 2nd thread run before main continued.
} 

I was frustrated enough to keep hitting the run button on this one, and lo and behold, about every 5,000 trials the 2nd thread wins. This caused me to go back and give the first variation a large number of chances, but without any successes. I guess that if it's just the GC, main, and one child thread running, main will win just about every time. But I wouldn't stake my life on it.

[Barkat Mardhani]

Hi Steve,
Thanks for your working on my code. I guess you pointed out some potential noise in the count. So I have changed it a bit. How do you find it now? I am getting a count of 0 to 9 for trials = 10,000.

 class Test implements Runnable {
static int counter = 0; 
static boolean b = false;
static int trials = 1000;
public static void main(String[ ] args) {
if (args.length > 0) trials = Integer.parseInt(args[0]) ; 
for (int i = 0 ; i < trials ; i++) { 
b = false ;
Runnable r = new Test();
Thread t = new Thread(r , "2nd thread" );
t.start();
synchronized (r) { 
if (b) { counter++ ; b = false; } else b = false;
}
try {t.join() ;} catch(InterruptedException ie) { } 
}
System.out.println(counter);
}
synchronized public void run() { b = true ;} // 2nd thread run before main continued.
}
 

[Steve Lovelace]

The synchronized sections of code can still be accessed by two threads simultaneously. This could be responsible for the entire count. But I'm not even sure of my last try - could get a race condition between the main thread setting currentThread and the previous thread reading it. This is tricky stuff.

[Barkat Mardhani]

posted by Steve:

The synchronized sections of code can still be accessed by two threads simultaneously. This could be responsible for the entire count. But I'm not even sure of my last try - could get a race condition between the main thread setting currentThread and the previous thread reading it. This is tricky stuff.

I do not think so. Both synchronized codes are locking on same Runnable object r. Also, main thread is waiting for 2nd thread to finish before starting a new iteration of loop. So I think now code is clean. I am finding that upto 9 times out of 10,000 trials, the jvm is deciding to swap to 2nd thread after start statement.
Thanks
Barkat

[Marlene Miller]

In theory, your two threads could be running in two different CPUs. The main thread starts the other thread, then both of them are executing, not concurrently, but simultaneously.
But even if your two threads are running in the same CPU, after the main thread starts the other thread, other events in your operating system could preempt your main thread. When that other thing blocks, either the main thread or the new thread could run.
Your tests might be occurring in a relatively passive environment with no reason for the JVM to preempt the main thread. If you were running on a machine that processes a million transactions per day, there might be more reasons for your main thread to be preempted.
[ September 24, 2003: Message edited by: Marlene Miller ]

[Barkat Mardhani]

Hi Marlene,
Thanks for your comments. I gather from them that you agree that main thread can be preempted by 2nd thread more so in some situation than others. I have not done any thread programming but some of the examples I have seen, assumed that main thread will never be preempted by 2nd thread. Is that assumption safe? For example, review following code from K & B. It is possible that main thread is preempted by thread b. When that happens, the program does not work logically right. It will wait for ever. So if this code happens to be on server where thousands of clients are invoking it, it is possible that upto 9 out 10,000 clients will get hung up.
My point is that with threads it is emphazied very much that there are no guarantees. So design your apps accordingly. Then why this fact is ignored.

<font size="2">
class ThreadA {
 public static void main(String [] args) {
  ThreadB b = new ThreadB();
  b.start();
  synchronized(b) {
   try {
   System.out.println("Waiting for b to complete...");
   b.wait();
   } catch (InterruptedException e) {}
  }
  System.out.println("Total is: " + b.total);
 }
}
class ThreadB extends Thread {
 int total;
 public void run() {
  synchronized(this) {
   for(int i=0;i<100;i++) {
   total += i;
  }
  notify();
 }
}
}
</font>

[ September 25, 2003: Message edited by: Barkat Mardhani ]

[Marlene Miller]

Hi Barkat,

I gather from them that you agree that main thread can be preempted by 2nd thread more so in some situation than others.

There has to be a reason for the scheduler to preempt a running thread. If the scheduler uses time-slicing, the reason might be that the thread has used up its time slice. If the scheduler uses priorities, the reason might be that a higher priority thread has completed I/O or finished waiting or sleeping and is ready to run. The TCP/IP process of the underlying operating system might want to poll the network, so the JVM is swapped out. Timers, priorities, I/O, aging policies, fairness policies.

I have not done any thread programming but some of the examples I have seen, assumed that main thread will never be preempted by 2nd thread. Is that assumption safe?

No, it is not a good assumption. When the main thread invokes t.start() and before start() returns, the Java virtual machine is free to allocate a new thread stack, schedule the new thread to be run, select the new thread, swap out the main thread and execute the run() method of the new thread. All this before start() returns.
On the other hand, some people mistakenly assume invoking start() means the run() method is immediately invoked. Another bad assumption. The Java virtual machine is free to schedule the new thread, and then return from start() and continue executing the main thread.

It is possible that main thread is preempted by thread b. When that happens, the program does not work logically right. It will wait for ever.

Yes, it is possible. Yes, the main thread will wait forever.

Then why this fact is ignored.

It is unfortunate. Here is a very important concept to understand. I will try to be concise. Stay with me.
The wait() method lets one thread wait until some condition occurs, and the notification methods notifyAll() and notify() tell waiting threads that something has occurred that might satisfy that condition.
There is a standard coding idiom that is important to use with wait and notification. The thread waiting for a condition should always do something like this:

synchronized void doWhenCondition() {
    while (! condition)
        wait();
    // Do what must be done when the condition is true
}

Notification code typically looks something like this:

synchronized void changeCondition() {
    // Change some value used in a condition test
    notifyAll(); // or notify()
}

In the Bates-Sierra example, if the two threads used wait and notify with a condition, the effect of notify() executed before a wait() would not be lost.
[ September 25, 2003: Message edited by: Marlene Miller ]

[Barkat Mardhani]

Thanks Marlene for taking time to educate me. In the following piece of code from your post:

synchronized void doWhenCondition() {    
while (! condition)        
wait();    
// Do what must be done when the condition is true} </font></font>

Did we need wait() for certain time? e.g.

synchronized void doWhenCondition() {    
while (! condition)        
wait(1000);    
// Do what must be done when the condition is true}  </font></font>

Otherwise, first time the main thread hits the wait() statement, it will wait for ever. It will not check while condition periodically. This is assuming the worst case situation when notify is issued by second thread before main thread hits wait().
Thanks
Barkat
[ September 25, 2003: Message edited by: Barkat Mardhani ]
[ September 25, 2003: Message edited by: Barkat Mardhani ]

[Steve Lovelace]

Barkat:

The synchronized sections of code can still be accessed by two threads simultaneously.

I should have said: The synchronized sections of code can still be accessed by two threads separately but simultaneously. As I looked at this I realized that only the main thread can access the synchronized block in the main method, and only a child thread can access its synchronized run method, so synchronization is not being used to prevent multiple threads accessing a particular piece of code, but to prevent two pieces of code from being executed simultaneously. This seems interesting and useful - is it a recognized idiom, a pattern even?
Please note though that if the common lock is the new child thread, then the main thread and the previous child thread can be executing their synchronized sections simultaneously, which is what I was trying to say. This is why I changed the code to use a single common lock.

[Marlene Miller]

We do not need to use an expiration time.
Suppose the second thread invokes notify() before the main thread invokes wait(). The second thread also changes the condition. The second thread releases the lock and the main thread acquires the lock. The main thread tests the condition before invoking wait(), finds the condition to be satisfied and therefore, does not wait.
I have added a simple condition to the Bates-Sierra example and �rearranged� the code. (One nice but unrelated change is to use the lock of some object other than a Thread object.)
An important conceptual change is to put wait() and notify() in the same object. This is not required, but it shows how a Java object is a monitor.

class ThreadA {
    public static void main(String[] args) {
        Work w = new Work();
        new ThreadB(w).start();
//        Thread.yield();  // let the other thread go first
        w.m2();
    }
}
//
class ThreadB extends Thread {
    Work w;
    ThreadB(Work w) { this.w = w; }
    public void run() { w.m1(); }
}
//
class Work {
    boolean condition = false;
    int total = 0;
    synchronized void m1() {
        for (int i = 0; i < 100; i++)
            total += i;
        condition = true;
        notifyAll();
        System.out.println("Notify the world");
    }
//
    synchronized void m2() {
        System.out.println("I am waiting");
        try {
            while (!condition)
                wait();
        } catch (InterruptedException e) {
        }
        System.out.println("I am done waiting");
    }
}

When experimenting with threads, I use yield() to influence who goes first.
[ September 25, 2003: Message edited by: Marlene Miller ]

[Barkat Mardhani]

posted by Steve:

I should have said: The synchronized sections of code can still be accessed by two threads separately but simultaneously. As I looked at this I realized that only the main thread can access the synchronized block in the main method, and only a child thread can access its synchronized run method, so synchronization is not being used to prevent multiple threads accessing a particular piece of code, but to prevent two pieces of code from being executed simultaneously. This seems interesting and useful - is it a recognized idiom, a pattern even?
Please note though that if the common lock is the new child thread, then the main thread and the previous child thread can be executing their synchronized sections simultaneously, which is what I was trying to say. This is why I changed the code to use a single common lock.

Response to first bold: As I said I am beginning to program in Java. I have to yet learn what is meant by terms idioms or patterns.
The way I understand it is that:
- there are two threads; main and 2nd thread
- they are both locking on same Runnable object r
- there two pieces of synchronized codes in same class; one is a block in main method and second is run method
- therefore, it is imposible that both thread could be 'executing' any of the synchronized codes at the same time.
- only mitigating factor is that a new r is being created in each iteration of for loop which can result in errors in count. It is resolved by the t.join statement at the end of the loop. So that run method on last r returns before a new r is created.
Response to second bold: Not possible as explained above...
I hope it makes sense.
Thanks
Barkat
[ September 26, 2003: Message edited by: Barkat Mardhani ]

[Barkat Mardhani]

posted by Marlene:

We do not need to use an expiration time.

Got it. Thanks

[Steve Lovelace]

Barkat:
Yes, I believe you are right: with t.join() in the main line there cannot be any simultaneous execution. I was not giving the start() method credit for having seen the thread enter a running or runnable state before returning. I looked around for some assurance on this, something like "the start() method does not return before the thread has left the 'new' state." It gets implied in the places I looked, but not stated explicitly. Nothing else is reasonable though - we could never trust the join() or isAlive() methods if it weren't true.