Re: Hurd_condition_wait

[Neal H. Walfield]

> > What about non-Mach backends?  I would feel better about an
> > internal-interface-guarantee argument rather than an implementation
> > argument.
> 
> This requirement is part of the interface; I was using Mach for
> illustration purposes because I assume that Vincente is familiar with
> Mach concepts.  On, for instance, L4, the sender would do a send and
> block until the receiver is ready.

Linux futexes have the exact same problem and they solve it similarly:
a process A does a down on a semaphore and sees that it is
unavailable.  A is preempted and another process, B, is scheduled and
performs an up on the same semaphore.  It sees that someone should be
woken and thus enters the kernel.  The kernel notes that there are no
waiters and does an up on an internal semaphore.  Process A is
eventually scheduled and the pending semaphore wait arrives.  The
kernel sees that the kernel semaphore is positive, does a down and
immediately returns to A.

To summarize, there are two semaphores: S, which is available from
user space and KS, which is the kernel semaphore and is used in
conjunction with the futex wait queues.

S=0
KS=0

        A                  B             Kernel
    ------------------------------------------------
    DOWN(S) = -1
                       UP(S) = 0
                       <= 0 ==>
T                       futex(S, UP)
i                                    Check wait queue
m                                    empty ==> UP(KS)
e   <= 0 ==>
    futex(S, DOWN)
|                                    Check KS
v                                    > 0 ==>
                                     DOWN(KS)
    ...