Update 2021-04-08: Viliam, a reader on my wordpress spotted an error. Thank you again! I called notify() and wait() on the implicit this rather than the lock! This adds to my argument that the best way to wait for something is to use a Future. There are so many ways to get it wrong.

Programming Interviews Exposed asks us to describe busy waiting and how to avoid it. The book provides a decent solution, but not the best solution. I’ll first introduce the problem and then build upon the solution until we have our best solution.

Busy Waiting

You have busy waiting When one thread, waits for a result from another thread and you use and NOOP/empty loop to wait for that result. We will explore waiting for a result from two sub tasks to demonstrate and solve this problem.

    Thread thread1 = new Thread(new Subtask1Runnable());
    Thread thread2 = new Thread(new Subtask2Runnable());
    thread1.start();
    thread2.start();
    while( waitinigForThread1() && waitingForThread2() ) {
        // empty loop
    }
    // do something with result from thread1 and thread2

You want to avoid this pattern because it wastes CPU cycles:

  1. Other threads you have running could of made use of those cycles
  2. Other processes sharing the same machine could have also used those cycles
  3. If the machine only has one CPU, thread2 could have made use of those cycles

 

Poor Solution: Sleep

So the issue is that we’re wasting CPU cycles by repeatedly checking the condition. So what if we made the thread sleep for a bit.

    while( waitinigForThread1() && waitingForThread2() ) {
        Thread.sleep(1000); // Sleep for 1 second
    }

This is an improvement over busy waiting as we’re now wasting less cycles. However there are still some draw backs to this pattern:

  1. You're still wasting cycles. It may seem like you're wasting one cycle every second. However, every time the thread wakes up it has to reload the thread's stack, registers, and it has to recompute if the other thread is done. There's still significant wastage.
  2. How do you set the sleep duration?
    1. Set it too long, and there is a long delay between the threads finishing and the main thread recognizing that it's done
    2. Set it too short, and you increase the amount of wasted cycles

Better But Still Poor Solution: Exponential Backoff

To take away a bit of the tuning, we can add an exponential backoff. To describe the process, imagine that your plane gets delayed for some unknown period of time. What do you do? Well first you might go to the washroom for a few minutes. Then you might get something to eat for half an hour. Then you might play a game on your cellphone for an hour. Finally, you’ll read a book for the next couple of hours. Your waiting tasks become progressively larger as you wait more. That’s the idea behind exponential backoff. You sleep for progressively longer durations as you wait for longer periods of time.

    private static final int MAX_BACKOFF=1000*60*60; // 1 hour
    private static final int INITIAL_BACKOFF=100; // 100ms
    int backOff=INITIAL_BACKOFF;
    while( waitinigForThread1() && waitingForThread2() ) {
        Thread.sleep(backOff); // Sleep for 1 second
        backOff=backOff<<2; //bit shift to the left to multiply by 2
        if(backOff > MAX_BACKOFF) {
            backOff = MAX_BACKOFF;
        }
    }

 

Now this solution isn’t the best possible solution yet for a couple of reasons:

  1. Ideally we want the the main thread to wake up only once or twice
    1. Once when the first sub task completes
    2. A second time when the second sub tasks completes
  2. We still have to play with the starting back off, and max back off parameters to get decent performance

Decent Solution: Locking or Monitors (Based on Programming Interviews Exposed)

As I hinted in the previous section, is there a way you can just wake up the sleeping thread once each task finishes? This is the solution that Programming Interview Exposed proposes. You can setup up some a lock and have the main thread wait on the lock. Then the two threads ‘notify’ when they have finished. Each ‘notify’ wakes the main thread and the main thread check to see if both threads finished.

This method uses the least possible cycles, but it is error prone. If not coded properly, you can end up with race conditions or deadlocks. Consider our two sub task example:

    Object lock = new Object(); // shared object to synchronize on
    int doneCount = 0;
    Thread thread1 = new Thread(new Runnable() {
        public void run() {
            // ...
            // do sub task 1
            // ...
            synchronized(lock) {
                doneCount++;
                lock.notify();
            }
        }
    });
    Thread thread2 = new Thread(new Runnable() {
        public void run() {
            // ...
            // do sub task 2
            // ...
            synchronized(lock) {
                doneCount++;
                lock.notify();
            }
        }
    });

    // this is the main thread again
    synchronized(lock) {
        thread1.start();
        thread2.start();

        while(doneCount < 2) {
            lock.wait();
        }
    }

This solution is great as the main thread only wakes up twice. Once when sub task 1 finishes, and a second time when sub task 2 finishes.

However, in this example we can mess up in many ways:

  1. If I started the threads outside the synchronized block, the two threads could finish before the main thread calls 'wait()'. This would leave the main thread sleeping forever and no future notifies are called.
  2. If I put the count outside of the synchronized block, the two threads might update them at the same time and I'll get doneCount==1 instead of 2!
  3. If I forget to call notify() on one of the threads, then when the main thread might never wake up because it didn't get one of the notifications.
  4. Placing the entire sub task in the synchronized block instead of just the shared data accesses would of only let one sub task run at a time resulting in no parallelism.
  5. In a previous version of the above pseudocode I wrote notify() and wait() instead of lock.notify() and lock.wait()! If you use a shared Object lock monitor, you have to remember to call notify() and wait() on that lock instead of this.

As a result, I do not recommend the solution presented in Programming Interviews Exposed.

Good Solution: Futures and Other Concurrency Libraries

Instead of trying to carefully code this pattern every time, you can use libraries that have already correctly implemented these patterns. In our example where we’re waiting for two results from two threads so we can apply Futures.

    ExecutorService executor = ...
    Future<String> future1 = executor.submit( new Callable<String>() {
        public String call() {
            /* do work for first result here */
        }
    });
    Future<String> future2 = executor.submit( new Callable<String>() {
        public String call() {
            /* do work for second result here */
        }
    } );
    String result1 = future1.get();
    String result2 = future2.get();

From the example we can immediately see that it’s the most elegant solution, and less bug prone. But more importantly, we still use the least possible cycles as execution of the main thread only resumes when each of the futures complete.

Here we were looking at an example waiting on two sub tasks to complete. However, there are many different waiting scenarios and the standard libraries of C# and Java provide many concurrency facilities to make developers’ lives easier. Before trying to code up your own monitor or locking, see if you problem has been solved before.

Summary

If you want to avoid busy waiting you can apply the write concurrent library for your problem. If the library doesn’t exist, you can try using monitors and locks, but be warned that there are many opportunities to mess up. Finally, don’t use busy loops or sleep to wait on tasks.