Mock-Up

Posted on January 9, 2006 by Mathias

I’ve written a mock-up test of the algorithm with the interleaved synchronized blocks, using a short, inefficient Monitor class that immitates the behavior of Java monitors:

class Monitor {
private AtomicBoolean _b = new AtomicBoolean(false);
private Queue _w = new LinkedList();
public void enter() {
while(!_b.compareAndSet(false,true)) sleep(1);
}
public void exit() {
_b.set(false);
}
public void myWait() throws InterruptedException {
Object o = new Object();
_w.add(o);
exit();
boolean waiting = true;
do {
try {
synchronized(o) {
o.wait();
}
waiting = false;
}
catch(InterruptedException e) {
e.printStackTrace();
}
} while(waiting);
enter();
}
public void myNotify() {
Object o = _w.poll();
if (o!=null) {
synchronized(o) {
o.notify();
}
}
}
public void myNotifyAll() {
Object o;
while((o = _w.poll()) != null) {
synchronized(o) {
o.notify();
}
}
}
}

Using this class, I’ve tried to test the implementation, and it seems to work. Now I just have to find a way to easily write this with Java’s regular monitors and the monitorenter and monitorexit instructions. I don’t feel like writing the two methods entirely in Java bytecode, so I’ll probably write two empty methods, public static void monitorEnter(final Object o) and public static void monitorExit(final Object o), and then write an instrumentation strategy that inserts the bytecode aload\_0; monitorenter; return and aload\_0; monitorexit; return, respectively, as bodies.

When interleaving synchronized blocks this way, there is a greater risk of forgetting to release ownership of a monitor somewhere, producing a deadlock. I think it might be a good idea to also implement this algorithm in Promela and use SPIN to verify it.

I’ve found another mistake in the algorithm, by the way: In compactThreadExit, I also have to check if I’ve reached the end of the schedule, and if that is the case, turn off scheduled replay and notify all threads waiting for a new buffer. Here’s the new, corrected algorithm:

compactWait:

  1. Repeat this… (“RETRY” loop)
    1. monitorenter _waitAlgoObj (beginning of main synchronized block)
      1. If the buffer has never been loaded, or if the index is at the end of the buffer…
        1. Load the buffer and reset the indices.
        2. Wake up all threads waiting for a buffer update.
      2. If the current sync point marks the end of the schedule…
        1. Disable scheduled replay.
        2. Wake up all threads waiting for a buffer update.
        3. monitorexit _waitAlgoObj
        4. Break out of the “RETRY” loop.
      3. If there’s a thread waiting for this wait array entry…
        1. Notify it
        2. Set a flag to scan ahead for the current sync point (“SCAN”).
        3. Do not advance indices.
      4. Otherwise…
        1. If the current sync point in the array is the right one…
          1. Advance indices.
          2. Allow the thread to exit the “RETRY” loop.
        2. Otherwise…
          1. Set a flag to scan ahead (“SCAN”).
      5. If the “SCAN” flag is set (i.e. either a thread was woken up or the current sync point did not match)…
        1. Look for the sync points in the remaining part of the array.
        2. If it could be found…
          1. Insert a new Object() into corresponding slot of the wait array.
          2. Set that Object() as “wait object” for this method.
          3. Allow the thread to exit the “RETRY” loop.
        3. Otherwise…
          1. Set the new buffer wait object as “wait object” for this method.
          2. Do not allow the thread to exit the “RETRY” loop.
        4. monitorenter waitObj (beginning of wait object synchronized block)
      6. monitorexit _waitAlgoObj (end of main synchronized block)
    2. If a “wait object” has been set for this method…
      1. Call wait() on that object (make sure to continue waiting if interrupted).
      2. monitorexit waitObj (end of wait object synchronized block)
      3. If scheduled replay is still enabled and the thread is allowed to exit the “RETRY” loop (i.e. it was not a “new buffer” wait)…
        1. monitorenter _waitAlgoObj (beginning of main synchronized block)
          1. Advance the indices.
        2. monitorexit _waitAlgoObj (end of main synchronized block)
  2. …while the thread is not allowed to exit the loop and scheduled replay is enabled (end “RETRY” loop).

compactThreadExit:

  1. monitorenter _waitAlgoObj (beginning of main synchronized block)
    1. If the index is at the end of the buffer…
      1. Load the buffer and reset the indices.
      2. Wake up all threads waiting for a buffer update.
    2. Otherwise…
      1. monitorenter _waitArray[index] (beginning of wait object synchronized block)
      2. If there’s a thread waiting for this wait array entry…
        1. Notify it.
      3. Otherwise, if the current sync point marks the end of the schedule…
        1. Disable scheduled replay.
        2. Wake up all threads waiting for a buffer update.
      4. Otherwise…
        1. Do nothing, because there’s still a thread awake that will reach this sync point.
      5. monitorexit _waitArray[index] (end of wait object synchronized block)
  2. monitorexit _waitAlgoObj (end of main synchronized block)
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