JavaMemoryModel: Prioritizing IE without notifyAll().

From: Sylvia Else (sylviae@optushome.com.au)
Date: Thu Nov 20 2003 - 01:18:55 EST


Hi.

Looking back over the stuff relating to the interrupt/notify race, it seems
to me that the preferred position (though not mine) was:

1) Notify followed by interrupt should cause the interrupted thread to
throw IE.
2) If another thread was waiting at the time of the notify, it must wake up.

This then raised the issue how this can be achieved, because causing the
interrupted thread to issue a notify can result in the sole wake up of a
thread that was not waiting at the time of the original notify. The
solution being for the interrupted thread to invoke notifyAll(). This then
becomes one source of spurious wakeups. It's also potentially rather expensive.

Yet it occurs to me that if the implementation knows at the point where a
thread wakes up, whether or not it was woken by a notify, then there is a
solution that does not require the use of notifyAll, and indeed does not
produce spurious wakeups.

Attach a counter to each object, and a separate counter, tcounter, to each
thread, and modify wait, notify as follows.

long counter = 0;

wait() {
     Thread.currentThread().tcounter = this.counter;
     // release monitor, wait, wakeup, reacquire monitor, keeping track of
why woken.

     if(Thread.interrupted()) {
         if(wokenByNotify) {
              // Wakeup one of the threads that were already waiting when
the notify that
              // caused this thread to wakeup was performed.
              notifySpecial(Thread.currentThread().tcounter);
         }
         throw new InterruptedException();
     }
}

notify() {
     Thread wakeThread = ...remove a thread from the wait set.
     wakeThread.tcounter = this.counter;
     this.counter++;

     // do wakeup stuff to wakeThread.
}

notifySpecial(long c) {
     Thread wakeThread = ...remove a thread from the wait set with tcounter
<= c, such that
                                     there is no other thread in the wait
set with tcounter <= c, but greater
                                     than the tcounter of the removed
thread. This prevents one notifySpecial
                                     from stealing the thread that another
notifySpecial with smaller c needed.
     wakeThread.tcounter = c;

     // do wakeup stuff to wakeThread.
}

Mind you, I'm not quite sure what to do after 2 to the power 63
notifications of an object.

Sylvia.

-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel



This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:54 EDT