Re: [RFC] locking/mutex: Fix starvation of sleeping waiters

[Jason Low]

On Tue, 2016-07-19 at 19:53 +0300, Imre Deak wrote:
> On ma, 2016-07-18 at 10:47 -0700, Jason Low wrote:
> > On Mon, 2016-07-18 at 19:15 +0200, Peter Zijlstra wrote:

> > > I think we went over this before, that will also completely destroy
> > > performance under a number of workloads.
> > 
> > Yup, once a thread becomes a waiter, all other threads will need to
> > follow suit, so this change would effectively disable optimistic
> > spinning in some workloads.
> > 
> > A few months ago, we worked on patches that allow the waiter to
> > return
> > to optimistic spinning to help reduce starvation. Longman sent out a
> > version 3 patch set, and it sounded like we were fine with the
> > concept.
> 
> Thanks, with v4 he just sent I couldn't trigger the above problem.
> 
> However this only works if mutex spinning is enabled, if it's disabled
> I still hit the problem due to the other forms of lock stealing. So
> could we prevent these if mutex spinning is anyway disabled?

Good point, when optimistic spinning is disabled, waiters could still
get starved because other threads could steal the lock in the fastpath
and the waiter wouldn't be able to spin for the lock.

One option to address this is by enforcing a ceiling on the amount of
"time" a waiter needs to wait on the lock to avoid starvation when
optimistic spinning is disabled. This would be better than just
unconditionally disabling the fastpath whenever there is a waiter,
because that could reduce performance by quite a bit.

Instead, we can still allow threads to acquire the lock in the fastpath
if there are waiters, but yield the lock to a waiter if the waiter loops
too many times waiting for the lock in the slowpath in the
!CONFIG_MUTEX_OPTIMISTIC_SPINNING case.

I can send out an initial patch for this.

Jason