Re: [9fans] sleep/wakeup bug?

[Bakul Shah <bakul+plan9@bitblocks.com>]

On Fri, 25 Feb 2011 09:37:39 +0100 Sape Mullender <sape@plan9.bell-labs.com>  wrote:
> I suppose the use of counting semaphores in sleep/wakeup could
> help in cases like this (but I'm sure there are still plenty of
> other scenarios where they might not help).  The value of the
> semaphore would represent something like "number of things to
> do", so acquire(sema) would (atomically) wait until the value
> of sema is greater than zero, then (using compare&swap, or
> doing the whole thing inside an ilock) decrement the semaphore
> and continue.
> Release(sema) will (atomically) increment the semaphore and, if the
> old value was zero, wake up any waiters.
>
> Now, at first glance that looks like a vast improvement over sleep/
> wakeup, but *inside* acquire and release, you'd still have sleep/wakeup
> and you'd still run the risk of waking up just when something else
> managed to grab the semaphore, or waking up something that hasn't
> actually gone to sleep yet.
>
> So, I think you can think of semaphores as a wrapper for sleep/wakeup
> that can be used in some case to make sure that you can indeed safely
> do a free() of some memory (this was, I think what started the whole
> discussion).

wait(sema) & signal(sema) in either order would do proper
synchronization. Not the case with sleep/wakeup -- they are cheaper
though.

> It's taken a long time to get sleep/wakeup bugfree in Plan 9 and
> some of the greatest minds in code verification (formerly at Bell Labs)
> have been called upon to help get it right.
>
> Russ is perfectly correct in the explanations below and it's a good
> exercise to read through it.  This stuff is really tricky.  Many
> optimization, all of them seemingly correct, failed because of subtle
> race conditions, some of them involving three or more processes.

Is it inherently tricky? Aren't semaphores easier to reason about
and get right?