Another Mistake?

I haven’t actually verified it, but I have a gut feeling there’s another mistake in my algorithm. Let’s look at the part when a sync point actually matches right away. I’ve excluded all the parts that don’t get executed and shaded the conditionals that don’t get entered gray:

  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…
      2. If the current sync point marks the end of the schedule…
      3. If there’s a thread waiting for this wait array entry…
      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…
      5. If the “SCAN” flag is set (i.e. either a thread was woken up or the current sync point did not match)…
      6. monitorexit _waitAlgoObj (end of main synchronized block)
    2. If a “wait object” has been set for this method…
  2. …while the thread is not allowed to exit the loop and scheduled replay is enabled (end “RETRY” loop).

Right after the match is found, the indices are advanced, the algorithm lock is released, and the method is exited. Right at this point, another thread could come along, find another match, race past the first thread and mess up the schedule.

How do I prevent this? Maybe advance the indices at the next wait point. How exactly? I don’t know yet.

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