Tricky Bit of Code

The wait algorithm is turning out to be trickier than expected. I think I have answers for the two questions I posed a few days ago. Let’s go in reverse order, actually:

  1. When one thread has to wait inside compactWait, which is a synchronized method, can other threads even enter it?

I’m almost embarrassed I had to ask this. Of course, other threads cannot enter compactWait at the same time. The current thread relinquishes control of the object it is waiting on (either the one in the wait array or the one for a new buffer), but it doesn’t reliquish control of all monitors it has. This, of course, means that the entire method cannot be synchronized. Certain portions, however, do have to be synchronized, as explained below.

  1. When threads are notified that a new buffer has been loaded, they might all work with the list of sync points simultaneously. This might create race conditions. Are these important?

It’s true that the sync points are unique: There will (or at least should) never be two threads looking for the same sync point. However, all threads are manipulating the indices into the sync point and wait arrays concurrently, so I think this actually is an issue.

When threads resume after waiting for a new buffer, they should not concurrently run through the method; otherwise, they might, for example, dispatch a thread that’s waiting twice, or attempt to do so but cause a NullPointerException because the entry in the wait array was non-null, but another thread made it null before the first thread could call notify(). Another really important thing is that buffer reloads are synchronized; otherwise, two threads could concurrently try to reload the buffer, and nasty things would happen.

This pretty much leads to the follwing structure:

  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, notify it and continue with the next sync point.
      3. If the current sync point in the array is the right one…
        1. Advance indices.
        2. Allow the thread to exit the “RETRY” loop.
      4. Otherwise…
        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, call wait() on that object (make sure to continue waiting if interrupted).
  2. …until the thread is allowed to exit the loop (end “RETRY” loop).

The most important change here is that the entire method is not synchronized anymore, but the entire block that does notification and scanning is. The waiting happens outside the synchronized block. This allows other threads to run through the block when threads are waiting.

I’m writing a piece of code that simulates the behavior outside of the actual program right now. I should probably write unit test, hm?


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