Concurrency Problems

An interviewer can quickly learn how well you understand multithreaded programming by asking you to solve one or two classic problems involving multiple threads of execution.

Busy Waiting

Important 

Explain the term “busy waiting” and how it can be avoided.

This is a simple problem, but one with important performance implications for any multithreaded application.

Consider a thread that spawns another thread to complete a task. Assume that the first thread needs to wait for the second thread to finish its work, and that the second thread terminates as soon as its work is done. The simplest approach is to have the first thread wait for the second thread to die:

 Thread task = new TheTask(); task.start(); while( task.isAlive() ){     ; // do nothing }

This is called busy waiting because the waiting thread is still active, but it’s not actually accomplishing anything. It’s “busy” in the sense that the thread is still executed by the processor, even though the thread is doing nothing but waiting for the second thread to finish. This actually “steals” processor cycles away from the second thread (and any other active threads in the system), cycles that could be better spent doing real work.

Busy waiting is avoided using a monitor or a semaphore, depending on what’s available to the programmer. The waiting thread simply sleeps (suspends itself temporarily) until the other thread notifies it that it’s done. In Java, any shared object can be used as a notification mechanism:

 Object theLock = new Object(); synchronized( theLock ){     Thread task = new TheTask( theLock );     task.start();     try {         theLock().wait();     }     catch( InterruptedException e ){         .... // do something if interrupted     } } ..... class TheTask extends Thread {     private Object theLock;     public TheTask( Object theLock ){         this.theLock = theLock;     }     public void run(){         synchronized( theLock ){             .... // do the task             theLock.notify();         }     } }

In fact, the preceding code can be simplified somewhat by using the class instance itself for the signaling:

 Thread task = new TheTask(); synchronized( task ){     task.start();     try {         task.wait();     }     catch( InterruptedException e ){         .... // do something if interrupted     } } ..... class TheTask extends Thread {     public void run(){         synchronized( this ){             .... // do the task             this.notify();         }     } }

For extra bonus points, ask the interviewer if the first thread is an event thread. Blocking an event thread is almost never acceptable, so waiting indefinitely for a lock to be released won’t cut it in a real-world application. That’s why most graphical user interface toolkits provide a way for applications to queue pseudo-events for processing by the event thread, which is what the second thread would do when it finished its task.

Producer/Consumer

Important 

Write a Producer thread and a Consumer thread that share a fixed-size buffer and an index to access the buffer. The Producer should place numbers into the buffer, while the Consumer should remove the numbers. The order in which the numbers are added or removed is not important.

This is one of the canonical concurrency problems. The first step is to answer the problem without using any concurrency control, and then comment on what the problems are. The algorithm isn’t very difficult when concurrency isn’t an issue. The data buffer looks like this:

 public class IntBuffer {     private int   index;     private int[] buffer = new int[8];     public void add( int num ){         while( true ){             if( index < buffer.length ){                 buffer[index++] = num;                 return;             }         }     }     public int remove(){         while( true ){             if( index > 0 ){                 return buffer[--index];             }         }     } }

The producer and consumer are almost trivial:

 public class Producer extends Thread {     private IntBuffer buffer;     public Producer( IntBuffer buffer ){         this.buffer = buffer;     }     public void run(){         Random r = new Random();         while( true ){             int num = r.nextInt();             buffer.add( num );             System.out.println( "Produced " + num );         }     } } public class Consumer extends Thread {     private IntBuffer buffer;     public Consumer( IntBuffer buffer ){         this.buffer = buffer;     }     public void run(){         while( true ){             int num = buffer.remove();             System.out.println( "Consumed " + num );         }     } }

Then, somewhere in the code you start the threads:

 IntBuffer b = new IntBuffer(); Producer p = new Producer( b ); Consumer c = new Consumer( b ); p.start(); c.start();

There are two problems with this approach, however. First, it uses busy waiting, which wastes a lot of CPU time. Second, there is no access control for the shared resource, the buffer: If a context switch occurs as the index is being updated, the next thread may read from or write to the wrong element of the buffer.

You may think at first that making the add and remove methods synchronized will fix the problem:

 public class IntBuffer {     private int   index;     private int[] buffer = new int[8];     public synchronized void add( int num ){         while( true ){             if( index < buffer.length ){                 buffer[index++] = num;                 return;             }         }     }     public synchronized int remove(){         while( true ){             if( index > 0 ){                 return buffer[--index];             }         }     } }

This won’t fix anything, however. Instead, the first thread to call add or remove will prevent the other thread from even entering the other method. Nothing will happen: One of the threads will busy-wait indefinitely and the other will be permanently suspended. The code inside the methods needs to be changed so that the producer suspends itself when the buffer is full and waits for a slot to open up, while the consumer suspends itself if the buffer is empty and waits for a new value to arrive:

 public class IntBuffer {     private int   index;     private int[] buffer = new int[8];     public synchronized void add( int num ){         while( index == buffer.length - 1 ){             try {                 wait();             }             catch( InterruptedException e ){             }         }         buffer[index++] = num;         notifyAll();     }     public synchronized int remove(){         while( index == 0 ){             try {                 wait();             }             catch( InterruptedException e ){             }         }         int ret = buffer[--index];         notifyAll();         return ret;     } }

This code actually allows multiple producers and consumers to use the same buffer simultaneously, so it’s even more general-purpose than the two-thread-only solution you’d be expected to come up with.