Re: Thread starvation with mutex

Ulrich Drepper wrote:
> Jamie Lokier wrote:
> 
> > No, the problem is _starvation_.  It would be good for the second
> > thread to run _eventually_,
> 
> Why?  This means sacrifizing the superior position the long running
> thread is in.
> 
> Fairness in the presence of a single mutex/semaphore is detrimenal to
> performance.

Fairness isn't the same thing as avoiding starvation (although some
literature may confuse the two :)

Inside the Linux kernel, there is see code which logically requires
all tasks to progress.  This allows everything to ignore priority
inversion - that can't happen if all tasks will make progress
eventually.

Linux doesn't have fancy logic to prevent starvation: it simply
assumes the scheduler won't do that.  It's a very useful assumption to
be able to make.

> This is not what the implementation is supposed to do.  If
> fairness is _needed_ the programmer must take this into account and
> design the program to not have this one big lock.

Instead of us arguing, how about a solution to the genuine problem:

What should the programmer do to prevent starvation without the
considerable performance penalty and complicated logic that handover
scheduling, application-level token passing etc would imply?

It's natural for programmers to simply use a mutex to protect atomic
transactions to data structures, and quite odd when that doesn't
behave the same as using other method to protect atomic transactions.

As a quality of implementation thing, I'd expect these to be roughly
equivalent:

     1. pthread_mutex_lock (&lock);
        x++;
        pthread_mutex_unlock (&lock);

     2. atomic_inc(&x);

Yet, that does not seem to be the case because 1 can starve while 2
cannot.

I don't see how a programmer can realistically use the pthread
primitives in the way you describe to get a non-starving version of 1,
without getting very silly in the application.

> If the kernel gets a scheduler policy where, if a kernel process waits
> for a very long time it'll acrue tons of karma so that it immediately
> displaces all running threads, then this is fine.  I sincerely hope this
> will never be default scheduling policy but, hey, if it makes you feel
> better implement it.

The kernel _already_ implements a scheduling policy like that.
You don't read much linux-kernel do you? :)

When a task sleeps for a long time, or a lot of the time, it
accumulates dynamic priority, also known as negative "prio" in the
scheduler.  When a task with high "prio" (i.e. one that's always
running) wakes a task with low "prio", the latter task is scheduled
immediately.

The decision to do this is in linux/kernel/sched.c:try_to_wake_up, if
you care to look.  It is reached from futex_wake(), so...

> This all has nothing to do with the userlevel code since it was a
> design decision to let the kernel handle all scheduling decisions.

I agree with that design.  I'm surprised the kernel is not scheduling
the second thread in the example.

As I said at the start of the thread, I'd expect thread 2 to be
starved on an SMP box, but the test box is UP.  I've just read
kernel/sched.c where it seems clear that a thread that's been sleeping
for a long time and then woken will immediately preempt its waker.
(Unless it's a synchronous wakeup, but futex wakeups are not).

In this case, thread 2 is starved but it must be periodically waking
and then immediately sleeping as it fails to acquire the mutex.  If
the kernel's dynamic priority calculation isn't giving priority to
thread 2 so that it runs as soon as thread 1 calls futex_wake, there
is a problem with that calculation.

-- Jamie