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):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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:

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

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…

Share

About Mathias

Software development engineer. Principal developer of DrJava. Recent Ph.D. graduate from the Department of Computer Science at Rice University.
This entry was posted in Concurrent Unit Testing. Bookmark the permalink.

Leave a Reply