compactWait and compactThreadExit

Ok, now I have a strategy that inserts calls to edu.rice.cs.cunit.SyncPointBuffer.compactThreadExit(long tid) at the end of java.lang.Thread.exit, and it seems like that’s actually the last thing a thread does. Good. (Note: I’ve just realized the thread ID isn’t actually necessary in compactThreadExit, so maybe I’ll take it out later. Right now, I’ll leave it in as a debugging help.)

Now the algorithm consists of two pieces. Here’s the part in compactWait:

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. 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. Begin of synchronized block…
            1. Advance the indices.
         2. End of synchronized block.
2. …while the thread is not allowed to exit the loop and scheduled replay is enabled (end “RETRY” loop).

This is basically the algorithm I had earlier, without any of the “fixes” to avoid deadlocks. These deadlocks can occur anywhere in the schedule if the order in which the threads reach their next synchronization points is unfortunate, i.e. current thread A is put to sleep in favor of waking up sleeping thread B and thread B then terminates without reaching another synchronization point.

Now here comes the second part of the algorithm, compactThreadExit:

1. Begin of synchronized block…
   1. If there’s a thread waiting for this wait array entry…
      1. Notify it
   2. Otherwise…
      1. Do nothing, because there’s still a thread awake that will reach this sync point.
2. End of synchronized block.

In the situation described above, thread B terminates, but the last thing it does is check if there’s a thread waiting for the next sync point already. If so, it wakes it up before the thread terminates. If not, then there still is a thread awake that is going to reach this sync point, so nothing has to be done (yes, most of the time, there’s only one thread awake at a time, but at the beginning of the program and after a buffer load multiple threads are looking for their sync points concurrently).

Let’s see how this works…