Pitfalls of Parallel Programming #1

The ability to write code that works in a multi-threaded environment is an essential skill for any modern software developer, yet how to accomplish this is rarely taught in school.   This is the first in what will be a series of posts outlining common pitfalls of parallel (or concurrent) programming and their solutions.

Pitfall: “Wait without While”

Rule: All calls to wait on a lock must be surrounded by a while loop that tests the condition for deciding whether to wait on the lock.

To understand this rule, we can look at an example of the violation of the rule that I recently encountered in an open source library:

class Semaphore
{
    private int count;
    Semaphore(int count) {
        if (count < 0) {
            count = Integer.MAX_VALUE;
        }
        this.count = count;
    }

    synchronized void enter() {
        if (count == 0) {
            try {
                wait();
            } catch (InterruptedException e) {
                throw Util.newInternal(e, "");
            }
        }
        Util.assertTrue(count > 0);
        count--;
    }

    synchronized void leave() {
        if (count == Integer.MAX_VALUE) {
            return;
        }
        count++;
        notify();
    }
}

At first glance, this class may appear to work properly as a semaphore, but under high load scenarios, it is possible for the assertion in the enter method to be triggered, even though both the enter and leave methods are synchronized.  The problem is that a thread can increment the count, notify one of the threads waiting on the semaphore to wake up, release the semaphore’s monitor, and still have another thread call the enter method to acquire the semaphore before the notified thread has the opportunity to acquire the semaphore’s monitor and wake up.

By replacing line #12 with the line while (count == 0) this race condition would be avoided. By using a while loop, if another thread acquires the semaphore before the notified thread is woken, the notified thread will realize that it still cannot acquire the semaphore and resume waiting for its opportunity.  This behaviour also demonstrates that the above semaphore implementation is unfair.

(Please note that there is no good reason to ever write your own Java semaphore like this any longer as Java has had an excellent java.util.concurrent.Semaphore since Java 1.5)

Tags: , ,

Reply

Your email address will not be published.