Re: [patch] Real-Time Preemption, plist fixes

[Esben Nielsen <simlo@phys.au.dk>]

On Sun, 5 Jun 2005, Ingo Molnar wrote:

> * Thomas Gleixner <tglx@linutronix.de> wrote:
> 
> > + * (C) 2005 Thomas Gleixner <tglx@linutronix.de>
> > + * Tested and made it functional. I'm still pondering if it is
> > + * worth the trouble.
> 
> you had a long Saturday night debugging session i guess:
> 
> > Date: Sun, 05 Jun 2005 02:17:12 +0200
> 
> but i think the fundamental question remains even on Sunday mornings -
> is the plist overhead worth it? Compared to the simple sorted list we 
> exchange O(nr_RT_tasks_running) for O(nr_RT_levels_used) [which is in 
> the 1-100 range], is that a significant practical improvement? By 
> overhead i dont just mean cycle cost, but also architectural flexibility 
> and maintainability.
>
Sorted lists works deterministicly O(1) on UP if no owner of the lock
blocks while having the lock. On SMP or worse if an owner blocks in the
lock, the wait list can grow very long. Thus insertion of new elements
takes a long time - with preemption disabled :-(

If this is supposed to be used for user-space PI as well I would say it
would have to be completely bounded, i.e. plists are certainly needed.
If it is in the kernel only, you might argue that the code is under
control and thus not make very long wait-lists. Therefore it is
not worth the extra CPU cycles to use them. However, there is no way
to know for sure. In extreme load situations we could end up with a lot of
waiters on mmap_sem forinstance.

Esben