Saturday, January 24, 2009

To Lock or Not to Lock?

Over the weekend, I was at CUSEC 2009 and an interesting computer science problem occured to me. Let me know what you think.

Consider a multi-threaded application with (at least) two threads: the main thread and a message-based worker thread.

Consider also an indexed ADT and consider a synchronized iteration through the elements of this enumeration (shown for clarity in Java without loss of generalization), running in the main thread:

List list = getList();
synchronized (list) {
    for (int i = 0; i < list.size(); i++) {
        T element = list.get(i);
        process(element);
    }
}

And consider a process(T element) method that sends a message to the worker thread to process this element. This worker thread, in turn, processes the element by accessing the original enumeration in a synchronized fashion. For example:

private void processInWorkerThread(T element) {
    List list = getList();
    sychronize (list) {
        // For example, get the index
        // within the list:
        // int index = list.indexOf(element);
        // setResult(index);
        respondToMainThread();
    }
}

When the enumeration is run, this algorithm will cause a deadlock. The main thread is waiting for the background thread to unblock, which will only happen when the main thread releases its lock on the list, which will never happen. This is deadlock.

Spotting a deadlock is one thing. Fixing a deadlock is another. And fixing a deadlock in a clean, future-proof, backwards-compatible way is practically an extinct species.

Clearly there is something wrong with the above design. Point out the flaws, what the options are, how you would fix them, and why you chose the solution that you chose. I welcome clarifying questions regarding the context or scope of the application.

Let the commenting begin!