RE: Thread starvation with mutex

> From: Jamie Lokier [mailto:[email protected]]
> Perez-Gonzalez, Inaky wrote:
> > 1. Thread A calls FUTEX_WAKE
> > 2. Thread A receives 0 from FUTEX_WAKE
> > 3. Thread A atomically unlocks the user space word
> >
> > Now, if some Thread B comes in between 2 and 3 and tries to
> > lock, it will see the user space word locked and go down to
> > wait in the kernel. It will sit there for ever because
> > in (3) the word is locked and nobody knows B is there sleeping.
> 
> After step 2, Thread B sees the user space word is locked and does an
> atomic decrement (or whatever) to indicate that there is a waiter, as
> usual.
> 
> In step 3, Thread A tries to unlock by doing an atomic copmare and
> exchang, and then it sees that the word indicates there is a waiter,
> so loops back to 1.

Ouch, I had forgotten we had the counter, not just a cmp/exchange.
Thanks for the correction.

But I still think the deadlock apples (in slightly more twisted fashion): 
B, in between 2 and 3, has decremented and gone down to the kernel. 
Before it is able to grab the futex spinlock, A is running, sees there is
a waiter according to the userspace word, so goes back to one. FUTEX_WAKE
returns 0 (because B still hasn't had the chance to queue up), so it 
unlocks. Now B reaches the futex and sleeps for ever.

Did I miss anything in this scenario?

Not that I am trying to corner the issue against a wall, but I am trying
to clear up all the cases I have been thinking of when designing fulocks
(top of my head, btw--now I wish I had written them down) to see where,
could I have simplified the whole thing.

> [me confused too] In that text I'm talking about strict ownership
> transferral, but in other emails on this thread, specifically when
> mentioning RT futex, I've been talking about FIFO wakeup order.

ACK

Iñaky Pérez-González -- Not speaking for Intel -- all opinions are my own (and my fault)