Right Direction, Not Right

I’m writing my little unit tests now, and in some cases, the fix with compactThreadExit actually helped. However, now there’s another problem:

Assume we have this schedule:

1 1
1 2
2 1

Let thread 2 go first. It’ll wait to be woken up in the second line. Then thread 1 executes the synchronization point in line 1 right away, then gets to its second synchronization point. Then the following things are supposed to happen:

1. Thread 1 wakes thread 2 up.
2. Thread 2 wakes up.
3. Thread 1 scans for its sync point and inserts a new wait object into the wait array.
4. Thread 1 calls wait() on that wait object.
5. Thread 2 advances the index.
6. Thread 2 exits compactWait and executes its code.
7. Thread 2 enters compactThreadExit.
8. Thread 2 checks if there is an object in the wait array and, because there is, calls notify() on the wait object, waking thread 1 up.
9. Thread 1 wakes up.
10. Thread 2 terminates.
11. Thread 1 exits compactWait and executes its code.
12. …

Unfortunately, because thread 1 exits the synchronized block that prevents concurrent execution before it waits, thread 2 executes compactThreadExit before thread 1 is actually waiting:

1. Thread 1 wakes thread 2 up.
2. Thread 2 wakes up.
3. Thread 1 scans for its sync point and inserts a new wait object into the wait array.
4. Thread 2 advances the index.
5. Thread 2 exits compactWait and executes its code.
6. Thread 2 enters compactThreadExit.
7. Thread 2 checks if there is an object in the wait array and, because there is, calls notify() on the wait object, but thread 1 wasn’t waiting yet!
8. Thread 2 terminates.
9. Thread 1 calls wait() on that wait object and never gets woken up!

The problem I’m facing now are these two contradictory requirements:

1. I may not be in the synchronized block when thread 1 calls wait(), because then no other thread can enter the synchronized block (as previously noted).
2. I may not exit the synchronized block that prevents concurrent execution until thread 1 has begun to wait, i.e. wait() has to be called inside the synchronized block.

It is obvious that a simple synchronized block cannot be used. I think a mutex might work, but I have to play around with the algorithm first. It’s amazing how complicated this is getting…