Concurrency Problems

Issues that you encounter with threads in professional development can be Byzantine in their complexity, but concise thread problems appropriate for an interview are difficult to compose. Therefore the questions you get are likely to come from a fairly small set of classic thread problems, several of which are presented here.

Busy Waiting

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 keep checking whether the second thread is alive and proceed as soon as it is dead:

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. Typically there are more active threads than cores, so 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 by 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 this case, because TheTask terminates after it completes its task, the first thread could also sleep until it completes using join(), but wait() and notify() provide a more general approach that isn’t dependent on thread termination. The preceding code can be simplified somewhat by using the thread object 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();
        }
    }
}

There are a very few circumstances where spinlocks, a form of busy waiting, are actually desirable. If you can guarantee that the lock you’re waiting for will be released in less time than it would take to acquire a conventional lock (a situation often encountered in kernel programming), it may be more efficient to use a spinlock that busy waits for this short period of time.

Another case where spinlocks are useful is high-performance computing (HPC) where the entire system is dedicated to a single application and exactly one compute thread is created per core. In this scenario, if one thread is waiting on data from a second thread running on a different core, there’s no useful work that can be performed on the first thread’s core until the data arrives, so there’s no downside to wasting compute cycles by busy waiting. The time between data arrival and the process proceeding past the lock is often less for a spinlock than a semaphore, so under these specific circumstances an application using spinlocks may have better performance than one using semaphores. In any case, appropriate use of spinlocks requires careful assembly coding (to ensure that the attempts at lock acquisition are atomic); busy waiting should always be avoided in high-level languages.

Producer/Consumer

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 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 fixes 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 actually creates an even worse problem. add and remove still busy wait when the buffer is full or empty (respectively). When a thread is busy waiting in add, no thread can enter remove (because the methods are now synchronized), so the buffer remains full forever. A similar problem is encountered if remove is called when the buffer is empty; the first time either of these situations is encountered, the application locks up in an infinite busy wait loop. 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, and 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.