[concurrency-interest] spurious wakeups semantics

David Holmes dholmes at dltech.com.au
Sun Nov 6 19:08:00 EST 2005

Alexander Terekhov wrote:
> David Holmes wrote:
> > No one is really sure where they came from.
> http://citeseer.ist.psu.edu/birrell87synchronization.html

Thanks for the reference Alex - that is a paper that would be of general
reading interest to everyone on the list. They were aware of so many issues
that Java was later to stumble over (eg. interrupt/alert and signal
interaction). And they also (because they followed mesa) diverged from the
semantics of Hoare monitors. (People mistakenly think Java broke new ground
here when in fact it pretty much borrowed everything from elsewhere.)

Is this the source of spurious wakeups? I have no idea and in previous
discussions on comp.programming.threads I don't recall this paper being
discussed - but at least Firefly is mentioned :) The paper obviously allows
"spurious wakeups" by allowing a signal to release more than one thread -
which they seemed to allow for efficiency/performance reasons that aren't
elaborated on in that paper. But see also the referenced paper by Pike et


"Process Sleep and Wakeup on a Shared-memory Multiprocessor  "

which shows how hard SMP programming can be if all you have is a
test-and-set instruction.

Jeremy Manson <jmanson at cs.purdue.edu> wrote:
> Alexander Terekhov wrote:
> > Jeremy Manson <jmanson at cs.purdue.edu> wrote:
> >>This paper gives the same implementation that David describes as broken
> >>in the POSIX rationale, no?
> >
> > I have no idea what piece of broken code in the POSIX rationale David
> > was talking about.
> Okay.  I was specifically thinking of the one on this page:
> http://www.opengroup.org/onlinepubs/009695399/functions/pthread_co

The code Jeremy links to is the "broken" code I was referring to. The key
requirement for the condition wait is that it atomically releases the lock
and suspends the thread (as per the Birrell formal specs) but this code
fails to do that as the two actions are not atomic - hence I claim it is
broken. Whether this relates to the system described in the Birrell paper I
can't say - the paper contains no code listing - maybe the POSIX folk
figured if Birrell had to do that way then it should be allowed to happen by
the spec. I wasn't around then so I don't know the timeline.

Anyway time to put this debate to bed again - till next time of course. :)

David Holmes

More information about the Concurrency-interest mailing list