Re: [patch 00/15] Generic Mutex Subsystem

[Steven Rostedt]

On Sun, 18 Dec 2005, Linus Torvalds wrote:

>
>
> On Mon, 19 Dec 2005, Andi Kleen wrote:
> >
> > Do you have an idea where this big difference comes from? It doesn't look
> > it's from the fast path which is essentially the same.  Do the mutexes have
> > that much better scheduling behaviour than semaphores? It is a bit hard to
> > believe.
>
> Are ingo's mutex'es perhaps not trying to be fair?
>
> The normal mutexes try to make sure that if a process comes in and gets
> stuck on a mutex, and then another CPU releases the mutex and immediately
> tries to grab it again, the other CPU will _not_ get it.
>
> That's a huge performance disadvantage, but it's done on purpose, because
> otherwise you end up in a situation where the semaphore release code did
> wake up the waiter, but before the waiter actually had time to grab it (it
> has to go through the IPI and scheduling logic), the same CPU just grabbed
> it again.
>
> The original semaphores were unfair, and it works really well most of the
> time. But then it really sucks in some nasty cases.
>
> The numbers make me suspect that Ingo's mutexes are unfair too, but I've
> not looked at the code yet.

Yes, Ingo's code does act like this unfairness.  Interesting also is that
Ingo's original code for his rt_mutexes was fair, and it killed
performance for high priority processes.  I introduced a "lock stealing"
algorithm that would check if the process trying to grab the lock again
was a higher priority then the one about to get it, and if it was, it
would "steal" the lock from it unfairly as you said.

Now, you are forgetting about PREEMPT.  Yes, on multiple CPUs, and that is
what Ingo is testing, to wait for the other CPU to schedule in and run is
probably not as bad as with PREEMPTION. (Ingo, did you have preemption on
in these tests?).  The reason is that if you have a high priority process
release a lock (giving it to a lower priority process that hasn't woken up
yet), then try to grab it again, but a lower priority process was waiting
on it,  the high priorty process would need to schedule out and wait on
the lower priority process. Here's a case of priority inversion that can
be solved without priority inheritance.

The way this situation happens is if you have three processes, A B and C
where A is the highest and C is the lowest.  C grabs the lock and is
preempted by A, A tries to grab the lock and goes to sleep, then B
runs and preempts C (remember, we don't have PI here), and then tries to
grab the lock.  C releases the lock and gives it to A, then A releases the
lock (gives it to B) and then tries to grab it again.

Now you must wait for two schedules and B to release the lock, before high
priority process A gets to run again.

So when we have PREEMPT, your fairness is not being very fair.

-- Steve
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/