In Java Bytecode…

I think I found a way how to fulfill both requirements, but so far only in pure Java bytecode. In bytecode, acquiring and releasing monitors isn’t bound to any scoping and thus doesn’t have to happen in a nested, non-overlapping fashion.

If compactWait is written like this (Java/Java byte code blend):

public static void compactWait(long code, long tid) {
...
// beginning of main synchronized block
monitorenter _waitAlgoObj
...
// beginning of waitObj synchronized block
monitorenter waitObj
// end of main synchronized block
monitorexit _waitAlgoObj

// wait for notification
waitObj.wait()

// end of waitObj synchronized blocm
monitorexit waitObj
...
}

and compactThreadExit in a similar way:

public static void compactThreadExit(long tid) {
...
// beginning of main synchronized block
monitorenter _waitAlgoObj
...
// beginning of _waitArray[index] synchronized block
monitorenter _waitArray[index]
// end of main synchronized block
monitorexit _waitAlgoObj

// notify sleeping thread
_waitArray[index].notify()

// end of _waitArray[index] synchronized block
monitorexit _waitArray[index]
...
}

then the regions in which the two monitors are held overlap, and this prevents compactThreadExit from calling notify() before compactWait had a chance to call wait().

Let’s look at a more detailed trace from the last posting:

1. Thread 1 does monitorenter _waitAlgoObj
2. …
3. Thread 1 wakes thread 2 up.
4. Thread 2 wakes up.
5. Thread 2 wants the _waitAlgoObj monitor…
6. Thread 1 scans for its sync point and inserts a new wait object into _waitArray[index].
7. Thread 1 does monitorenter _waitArray[index]
8. Thread 1 does monitorexit _waitAlgoObj
9. Thread 2 does monitorenter _waitAlgoObj
10. Thread 2 advances the index.
11. Thread 2 does monitorexit _waitAlgoObj
12. Thread 2 exits compactWait and executes its code.
13. Thread 2 enters compactThreadExit.
14. Thread 2 does monitorenter _waitAlgoObj
15. Thread 2 wants the _waitArray[index] monitor…
16. Thread 1 calls wait() on that wait object.
17. Thread 2 does monitorenter _waitArray[index]
18. 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.
19. Thread 1 wakes up.
20. Thread 2 does monitorexit _waitArray[index]
21. Thread 2 exits compactThreadExit.
22. Thread 2 terminates.
23. Thread 1 does monitorexit _waitArray[index]
24. Thread 1 exits compactWait and executes its code.
25. …

Whenever a thread wants to call Object.wait() or Object.notify(), the thread first has to own that object’s monitor. By acquiring that monitor in compactWait before the monitor for the entire algorithm is released, we can guarantee that wait() is called before notify() can be called in compactThreadExit.

I’m just not sure what the easiest way to test this is…