- A Concurrent Affair - https://www.concurrentaffair.org -

Another Concurrency Bug I Might Detect

The first problem [1] that execution with random delays can catch is a temporal dependency: Thread 1 expects that thread 2 has finished performing a task, but this is not enforced through synchronization.

My girlfriend asked if I could detect the exact opposite: What if thread 1 expects that thread 2 has not finished performing some task, but it actually has? This is probably another common problem, especially with novices. It gets particularly bad if it involves wait and notify, and one thread is waiting for another thread’s notification, but that notification was done before the first thread was ready for it. Here’s an example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import junit.framework.TestCase;
/**
 * A multithreaded test case exhibiting a problem with synchronization:
 * One thread is waiting for another thread's notify, but that notify
 * has already occurred.
 * @author Mathias Ricken
 */

public class SyncProblem3 extends TestCase {
    public void testNotifyTooEarly() {
        final Character [2] signal = new Character [2]('x');
        Thread [3] worker = new Thread [3](new Runnable [4]() {
            public void run() {
                System [5].out.println("Worker thread running");
                try { Thread [3].sleep(2000); }
                catch(InterruptedException [6] e) { /* ignore */ }

                synchronized(signal) {
                    System [5].out.println("Worker thread calling notify");
                    signal.notify();
                }

                try { Thread [3].sleep(3000); }
                catch(InterruptedException [6] e) { /* ignore */ }
                System [5].out.println("Worker thread done");
            }
        });
        System [5].out.println("Main thread starting worker thread...");
        worker.start();
        System [5].out.println("Main thread started worker thread...");
        try {
            synchronized(signal) {
                System [5].out.println("Main thread waits...");
                signal.wait();
                System [5].out.println("Main thread woken up");
            }
        }
        catch(InterruptedException [6] e) { /* ignore */ }
        System [5].out.println("Main thread done");
    }
}

Here, the calls to Thread.sleep simulate performing some computation, of course. Under normal circumstances, the worker thread will call signal.notify() long after the main thread has reached signal.wait(), so the main thread gets woken up.

If, however, the main thread for some reason takes longer than usual to get to signal.wait(), then the notification may be lost. The correct way of doing this, of course, is to include a flag that’s protected by the lock of the same object that is being used for signaling: The flag is initially false, gets set to true before the call to notify, and wait is only called if the flag is still false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
...
public class SyncProblem3 extends TestCase {
    boolean flag = false;
    public void testNotifyTooEarly() {
        ...
        Thread [3] worker = new Thread [3](new Runnable [4]() {
            public void run() {
                ...
                synchronized(signal) {
                    flag = true;
                    signal.notify();
                }
                ...
            }
        });
        ...
        try {
            synchronized(signal) {
                if (!flag) {
                    signal.wait();
                }
            }
        }
        ...
    }
}

Note that if the notify is reached first and the notification is lost, then this unit test does not fail but hangs. For this reason, any unit test should have a timeout set, and if the test has not finished executing after the specified time has run out, the test should be considered a failure. An examination of the thread stacks would then show that one of the threads had made a call to Object.wait.

There are probably more elegant ways of doing this. Two things come to my mind right now:

I’m confident I can provide a system that’s useful here, too. And I’m glad I have a smart girlfriend.

[8] [9]Share [10]