- A Concurrent Affair - https://www.concurrentaffair.org -

Right Direction, Not Right

I’m writing my little unit tests now, and in some cases, the fix with compactThreadExit actually helped. However, now there’s another problem:

Assume we have this schedule:

1 1
1 2
2 1

Let thread 2 go first. It’ll wait to be woken up in the second line. Then thread 1 executes the synchronization point in line 1 right away, then gets to its second synchronization point. Then the following things are supposed to happen:

  1. Thread 1 wakes thread 2 up.
  2. Thread 2 wakes up.
  3. Thread 1 scans for its sync point and inserts a new wait object into the wait array.
  4. Thread 1 calls wait() on that wait object.
  5. Thread 2 advances the index.
  6. Thread 2 exits compactWait and executes its code.
  7. Thread 2 enters compactThreadExit.
  8. Thread 2 checks if there is an object in the wait array and, because there is, calls notify() on the wait object, waking thread 1 up.
  9. Thread 1 wakes up.
  10. Thread 2 terminates.
  11. Thread 1 exits compactWait and executes its code.

Unfortunately, because thread 1 exits the synchronized block that prevents concurrent execution before it waits, thread 2 executes compactThreadExit before thread 1 is actually waiting:

  1. Thread 1 wakes thread 2 up.
  2. Thread 2 wakes up.
  3. Thread 1 scans for its sync point and inserts a new wait object into the wait array.
  4. Thread 2 advances the index.
  5. Thread 2 exits compactWait and executes its code.
  6. Thread 2 enters compactThreadExit.
  7. Thread 2 checks if there is an object in the wait array and, because there is, calls notify() on the wait object, but thread 1 wasn’t waiting yet!
  8. Thread 2 terminates.
  9. Thread 1 calls wait() on that wait object and never gets woken up!

The problem I’m facing now are these two contradictory requirements:

  1. I may not be in the synchronized block when thread 1 calls wait(), because then no other thread can enter the synchronized block (as previously [1] noted).
  2. I may not exit the synchronized block that prevents concurrent execution until thread 1 has begun to wait, i.e. wait() has to be called inside the synchronized block.

It is obvious that a simple synchronized block cannot be used. I think a mutex might work, but I have to play around with the algorithm first. It’s amazing how complicated this is getting…

[2] [3]Share [4]