[PATCH] New condvar implementation that provides stronger ordering guarantees.

[Ondřej Bílka]

On Fri, Jul 03, 2015 at 11:03:25AM +0200, Torvald Riegel wrote:
> On Thu, 2015-07-02 at 23:48 +0200, Ondřej Bílka wrote:
> > > > > > PI support is "kind of" included.  There is no internal lock anymore, so
> > > > > > the thing that Darren proposed the fix for is gone.  So far so good;
> > > > > > however, we don't requeue, and Darren's paper states that requeue would
> > > > > > yield better latency in the PI scenario (is this still the case?).
> > > > > >
> > > > You have problem that when kernel keeps FIFO api requeue gives you fairness while
> > > > with waking everything a important thread could be buried by lower
> > > > priority threads that after each broadcast do something small and wait
> > > > for broadcast again. 
> > > 
> > > If you wake several threads, then the those with highest priority will
> > > run.
> > 
> > While they will run that doesn't mean that they will win a race. For
> > example you have 4 core cpu and, 3 low priority threads and one high
> > priority one. Each will check condition. If true then it will consume 
> > data causing condition be false. If condition not met he will wait again. 
> > Then high priority thread has only 1/4 chance to be first to get lock 
> > to consume data. With requeue he could always do it.
> 
> No, if the lock is of a PI kind, the lower prio thread will acquire it,
> put it's TID as lock owner, which then will allow a higher-prio to boost
> the priority of the lower prio thread.  So, the locks itself are fine.
> There is no guarantee that a higher-prio thread will be able to grab a
> signal when a lower-prio thread tries to grab one concurrently.  But
> that's not something that the condvar is required to guarantee.  (But
> note that what the new algorithm fixes is that when a waiter is eligible
> for consuming a signal (and there's no other thread that's eligible too
> and could grab it first), a waiter that starts waiting after the signal
> (ie, isn't eligible) cannot steal the signal anymore). 

While there are still issues I realized that it doesn't matter much as
condvar doesn't handle PI well. While it sort-of handles
signal-broadcast it doesn't handle that condition itself is could be
affected by priority inversion.

I don't know how to fix that without allocating memory for each
convar/thread pair to give thread that grabs mutex to satisfy condition
correct priority.