Even Trickier

I’ve just realized there’s a potential problem with this algorithm too: Assume the second to last sync point of the schedule is being processed, and a thread is waiting for it. This thread will be woken up, and the current thread will wait for the last sync point to be hit. However, since it’s the last sync point in the schedule, compactWait will never be entered again. The last thread will never complete!

This isn’t really a problem in this application, though, since the there are these eight sync points produced by “DestroyJavaVM” (thread 9) that don’t show up in the recorded trace. Thread 9 will enter compactWait and wake up the last thread. But now thread 9 will look for its sync point, and it’s not in the schedule. So it will wait for a buffer update… which will never come.

Therefore, when a thread is woken up so it can continue, it needs to check if the next entry in the sync point array marks the end of the schedule (SP_END). If so, replay needs to be disabled and all threads waiting for a buffer update need to be woken up.

Another problem arises, unfortunately: If it’s the end of the buffer, compactWait cannot determine if the end of the schedule has been reached without reloading the buffer. But reloading the buffer needs to happen in a synchronized block.

It’s probably the easiest to have another static flag, LASTBUFFER, that the master VM sets if this is the last block. compactWait will disable scheduled replay if the index is at the end of the buffer and the LASTBUFFER flag is set, or if the next sync point marks the end. Note that this “or” has to short-circuit.

So, without further ado, another sketch of the algorithm:

  1. Repeat this… (“RETRY” loop)
    1. Begin of synchronized block
      1. If the buffer has never been loaded, or if the index is at the end of the buffer…
        1. If the LASTBUFFER flag is set…
          1. Disable scheduled replay.
          2. Wake up all threads waiting for a buffer update.
          3. Break out of the “RETRY” loop.
        2. Otherwise…
          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. 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.
    2. End of synchronized block
    3. If a “wait object” has been set for this method…
      1. Call wait() on that object (make sure to continue waiting if interrupted).
      2. 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. Advance the indices.
        2. If the index is at the end of the buffer and the LASTBUFFER flag is set, or the sync point at the new index marks the end of the schedule (note: this must short-circuit)…
          1. Disable scheduled replay.
          2. Wake up all threads waiting for a buffer update.
          3. Break out of the “RETRY” loop.
  2. …while the thread is not allowed to exit the loop and scheduled replay is enabled (end “RETRY” loop).
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