Definitely Tricky

I just noticed that my algorithm still isn’t correct. Right now, when compactWait finds a thread that is waiting, it wakes it up and continues with the current thread if the next sync point matches. Then we have two threads running concurrently. Instead, when a waiting thread is woken up, the current thread must wait.

It seems like this can be accomplished the easiest by not advancing the indices if a thread was woken up, and then entering the “scan ahead” portion. The indices are advanced only after a thread waiting on a sync point has been woken up again.

This has the effect that when a thread was woken up, the scan for the current thread starts with the next sync point, and the current thread will wait for there. The newly awoken thread then advances the the indices, and the current thread will be woken up the next time a sync point is encountered.

This seems to be the algorithm now:

  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, reload buffer and notify all threads waiting for a buffer update.
      2. 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.
      3. 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”).
      4. 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 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 the thread is allowed to exit the “RETRY” loop (i.e. it was not a “new buffer” wait)…
        1. Advance the indices.
  2. …until the thread is allowed to exit the loop (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