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

Advance Only During First Iteration

After I had got up, I had realized that the problem involving advancing the index was caused by a really stupid mistake. The counter should only ever advanced when the compactWait algorithm is entered, i.e. during the first but not during subsequent iterations of the loop. This fixed the problem. The algorithm now looks like this:

compactWait:

  1. If scheduled replay is enabled…
    1. monitorenter _waitAlgoObj (beginning of main synchronized block)
    2. If this is NOT the first sync point for this thread…
      1. Advance the indices.
    3. Repeat this… (“RETRY” loop)
      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. monitorexit _waitAlgoObj
        4. 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. Do not 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.
        4. monitorenter waitObj (beginning of wait object synchronized block)
      6. monitorexit _waitAlgoObj (end of main synchronized block)
      7. If a “wait object” has been set for this method…
        1. Call wait() on that object (make sure to continue waiting if interrupted).
        2. monitorexit waitObj (end of wait object synchronized block)
        3. Do not advance indices.
        4. If the thread is NOT allowed to exit the loop (i.e. it was waiting for a new buffer) AND scheduled replay is enabled…
          1. monitorenter _waitAlgoObj (beginning of main synchronized block for next iteration)
    4. …while the thread is not allowed to exit the loop and scheduled replay is enabled (end “RETRY” loop).

compactThreadExit:

  1. If scheduled replay is enabled…
    1. monitorenter _waitAlgoObj (beginning of main synchronized block)
      1. Advance the indices.
      2. 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.
      3. Otherwise…
        1. monitorenter _waitArray[index] (beginning of wait object synchronized block)
        2. If there’s a thread waiting for this wait array entry…
          1. Notify it.
        3. Otherwise, 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.
        4. Otherwise…
          1. Do nothing, because there’s still a thread awake that will reach this sync point.
        5. monitorexit _waitArray[index] (end of wait object synchronized block)
    2. monitorexit _waitAlgoObj (end of main synchronized block)

This let three of the four simple tests I’ve written pass, but a more complicated one failed. I tracked the error down and realized that I currently don’t guarantee that all threads are actually woken up when a new buffer is loaded. Thread A and B were waiting for a new buffer, thread C loads it and notifies A and B. Threads A wakes up, but thread B doesn’t. Threads A and C run, and one of them requests another new buffer. Thread B hasn’t woken up yet, so it waits for the next buffer as well. If there happens to be a sync point for B in the current buffer, then the program has deadlocked.

I’ve tried several attempts so somehow make sure that all of them are woken up, like using a signal bit that is enabled and that wakes the threads up, which then decrement the number of threads waiting one by one, and all threads involved in this operation wait until that number has reached zero. However, I couldn’t get this to work.

I can probably use arrays and one entry per thread or some kind of ring buffer, but that would complicate the code a lot and obscure the important details of the algorithm. There has to be an easier solution in Promela that allows me to ascertain this. This problem is really annoying, because I have the feeling that it’s not actually a problem with my algorithm, but just a lack of skill in mapping the algorithm from Java to Promela.

I’m tabling this for the day, though, to eat pizza and bum around. It’s MLK day, after all. Wait… that’s not politically correct!

[1] [2]Share [3]