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

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

[Perez-Gonzalez, Inaky]

>From: Ingo Molnar [mailto:mingo@elte.hu]
>
>so the question is - can we have an extreme (larger than 140) number of
>RT tasks? If yes, why are they all RT - they can have no expectation of
>good latencies with a possible load factor of 140!

In practice, didn't we want most tasks to behave like RT?
(for interactivity purposes) -- I recall hearing that's basically
what good interactivity meant; short reponse times to events.

So then, taking await batch/bacground data-munching jobs, we fold 
back to needing a good RT-like behaviour. And then we can reach > 140.

-- Inaky

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

[Ingo Molnar]

* Perez-Gonzalez, Inaky <inaky.perez-gonzalez@intel.com> wrote:

> >From: Ingo Molnar [mailto:mingo@elte.hu]
> >
> >so the question is - can we have an extreme (larger than 140) number of
> >RT tasks? If yes, why are they all RT - they can have no expectation of
> >good latencies with a possible load factor of 140!
> 
> In practice, didn't we want most tasks to behave like RT? (for 
> interactivity purposes) -- I recall hearing that's basically what good 
> interactivity meant; short reponse times to events.

that's not what the current code does (and it's not what the non-plist 
code did either). We dont do PI handling for non-RT tasks. They 
basically have no RT expectations at all, and including them in the PI 
mechanism would only slow them down, and would increase the latencies of 
the RT tasks as well.

But indeed it could improve interactivity (but this has not been proven 
yet) - and also for testing purposes it would sure be useful, so we 
should perhaps make ALL_TASKS_PI default-on, as Daniel suggests. If that 
is done then plists are indeed a superior solution. But if in the end we 
decide to only include RT tasks in the PI mechanism (which could easily 
happen) then there seems to be little practical difference between 
sorted lists and plists.

	Ingo

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

[Daniel Walker]

On Mon, 6 Jun 2005, Ingo Molnar wrote:
> But indeed it could improve interactivity (but this has not been proven 
> yet) - and also for testing purposes it would sure be useful, so we 
> should perhaps make ALL_TASKS_PI default-on, as Daniel suggests. If that 
> is done then plists are indeed a superior solution. But if in the end we 
> decide to only include RT tasks in the PI mechanism (which could easily 
> happen) then there seems to be little practical difference between 
> sorted lists and plists.

The biggest reason that I suggest this is because when I wrote the 
abstracted PI I gave the user of the API the choice to do RT tasks only or 
all tasks. In the case of fusyn or futex , they will do all tasks .. Once 
you throw in one structure that does all tasks , they may as well all be 
doing it. Or that's how I feel.

Daniel

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

[Daniel Walker]

On Mon, 6 Jun 2005, Ingo Molnar wrote:
> 
> yes, it's supposed to be used for user-space PI too. What do you mean by 
> 'completely bounded'. Do you consider the current worst-case O(100) 
> property of plists a 'completely bounded' solution?
> 
> i dont think fusyn's should be made available to non-RT tasks. If this 
> restriction is preserved then fusyn's would become O(max_nr_RT_tasks) 
> too.

	I think making fusyn RT tasks only would be asking a lot. Fusyn 
replaces Futex, and they are both used in pthreads. So non-RT tasks 
wouldn't be able to use pthreads in userspace, or a big chunk of pthread 
..

Daniel

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

[Daniel Walker]

On Mon, 6 Jun 2005, Ingo Molnar wrote:

> 
> * Daniel Walker <dwalker@mvista.com> wrote:
> 
> > 	For me it's strictly a speed question. I was reviewing 
> > V0.7.40-04 and it looks like apples and oranges to me. It's more a 
> > question of where do you perfer the latency , in up() or in down() .. 
> > plist is slower for non-RT tasks, but non-RT tasks also get the 
> > benefit of priority ordering.
> 
> what benefit do non-RT tasks get from plists, compared to the ordered 
> list? Non-RT tasks are not PI handled in any way.

The original wait list was partial ordered, wasn't it? RT tasks on the 
front, non-RT at the back. Now the whole list is sorted (including non RT 
tasks) . So non-RT task will get the lock in priority sorted order, as 
opposed to just random. Like you said, there is no PI done.


Daniel

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

[Ingo Molnar]

* Esben Nielsen <simlo@phys.au.dk> wrote:

> > i dont think fusyn's should be made available to non-RT tasks. If this 
> > restriction is preserved then fusyn's would become O(max_nr_RT_tasks) 
> > too.
> 
> My pragmatic side agrees with you. My sense of beauty does not. I think
> you make 2 small hacks here:
>
> 1) Adding a limit like above smells wrong.
> 2) Making PI only apply to RT tasks isn't beautifull either.

Enabling PI for all tasks would certainly make plists the only viable 
choice. To achieve that we'd have to do quite careful coding, as the 
priorities of SCHED_OTHER tasks can change quite frequently, and the PI 
code doesnt follow priority changes that well currently.

	Ingo

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

[Esben Nielsen]

On Mon, 6 Jun 2005, Ingo Molnar wrote:

> 
> * Esben Nielsen <simlo@phys.au.dk> wrote:
> 
> > 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 :-(
> 
> the wait list can grow only as long as the max # of RT tasks is. Sorted 
> lists become 'O(1)' if we added some code that globally limits the 
> number of RT tasks to say 50. E.g. /proc/sys/kernel/max_nr_RT_tasks. A 
> user can override it if he needs more RT tasks. There can be an 
> arbitrary number of SCHED_OTHER tasks.
> 
> (note that on Linux there is a RAM-dependent 'max # of tasks' ulimit 
> which is never 'infinity', so theoretically the sorted lists are "O(1)" 
> too. But this is nitpicking.)
> 
> > 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. [...]
> 
> yes, it's supposed to be used for user-space PI too. What do you mean by 
> 'completely bounded'. Do you consider the current worst-case O(100) 
> property of plists a 'completely bounded' solution?
> 
> i dont think fusyn's should be made available to non-RT tasks. If this 
> restriction is preserved then fusyn's would become O(max_nr_RT_tasks) 
> too.
> 

My pragmatic side agrees with you. My sense of beauty does not. I think
you make 2 small hacks here:
1) Adding a limit like above smells wrong.
2) Making PI only apply to RT tasks isn't beautifull either.

On the other hand the plists are "beautifull". It would sadden me if they
are thrown away.

As I said in an earlier mail, I think you should agree on an interface
between the rt_mutex code and list structure. Then Daniel can implement
and test his plist in user space, somebody else can implement and test
the sorted list in userspace and the transition can happen with a switch
of a macro and a recompilation.

I hope I will get some time to help out from next weekend. I am taking
exams right now.

> 	Ingo
> 

Esben

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

[Ingo Molnar]

* Daniel Walker <dwalker@mvista.com> wrote:

> 	For me it's strictly a speed question. I was reviewing 
> V0.7.40-04 and it looks like apples and oranges to me. It's more a 
> question of where do you perfer the latency , in up() or in down() .. 
> plist is slower for non-RT tasks, but non-RT tasks also get the 
> benefit of priority ordering.

what benefit do non-RT tasks get from plists, compared to the ordered 
list? Non-RT tasks are not PI handled in any way.

	Ingo

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

[Ingo Molnar]

* Esben Nielsen <simlo@phys.au.dk> wrote:

> 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 :-(

the wait list can grow only as long as the max # of RT tasks is. Sorted 
lists become 'O(1)' if we added some code that globally limits the 
number of RT tasks to say 50. E.g. /proc/sys/kernel/max_nr_RT_tasks. A 
user can override it if he needs more RT tasks. There can be an 
arbitrary number of SCHED_OTHER tasks.

(note that on Linux there is a RAM-dependent 'max # of tasks' ulimit 
which is never 'infinity', so theoretically the sorted lists are "O(1)" 
too. But this is nitpicking.)

> 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. [...]

yes, it's supposed to be used for user-space PI too. What do you mean by 
'completely bounded'. Do you consider the current worst-case O(100) 
property of plists a 'completely bounded' solution?

i dont think fusyn's should be made available to non-RT tasks. If this 
restriction is preserved then fusyn's would become O(max_nr_RT_tasks) 
too.

	Ingo

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

[Daniel Walker]

On Sun, 5 Jun 2005, Ingo Molnar wrote:
> 
> 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.


	You'll have to explain the "architectural flexibility and 
maintainability" costs . Questioning if plist works correctly isn't 
a long term maintainability problem, in my mind. I don't see any 
architectural costs considering the plist API, which is why I saw a clear 
path to integrate plist in the first place. 

	For me it's strictly a speed question. I was reviewing V0.7.40-04 
and it looks like apples and oranges to me. It's more a question of where 
do you perfer the latency , in up() or in down() .. plist is slower for 
non-RT tasks, but non-RT tasks also get the benefit of priority ordering.

Daniel

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

[Daniel Walker]

On Sun, 5 Jun 2005, Thomas Gleixner wrote:

> On Sun, 2005-06-05 at 07:51 -0700, Daniel Walker wrote:
> 
> > __plist_del was a good fix. I attached a patch on "Plist cleanup on RT" to
> > lkml with what was acceptable to me. A good 60% of Thomas's changes are
> > unacceptable to me.
> 
> Would you be so kind to explain that a bit ? Your patch contains _all_
> my proposed changes except the additional plist_first_entry macro and
> the comment cleanup.
> 
> So what are the 60% which are unacceptable. Comments ? I'm amused.

Whatever was missing was unacceptable. 

Daniel

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

[Thomas Gleixner]

On Sun, 2005-06-05 at 07:51 -0700, Daniel Walker wrote:

> __plist_del was a good fix. I attached a patch on "Plist cleanup on RT" to
> lkml with what was acceptable to me. A good 60% of Thomas's changes are
> unacceptable to me.

Would you be so kind to explain that a bit ? Your patch contains _all_
my proposed changes except the additional plist_first_entry macro and
the comment cleanup.

So what are the 60% which are unacceptable. Comments ? I'm amused.

tglx

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

[Daniel Walker]

On Sun, 5 Jun 2005, Ingo Molnar wrote:

> i think it would be handy to resurrect ALL_TASKS_PI. It was one of the 
> things that stabilized the sorted list approach so quickly. Nothing 
> beats the coverage of running a full graphical desktop with all the PI 
> code active :-)


I keep wondering why I'm dragging ALL_TASKS_PI around in all my patches,
since it doesn't work. Why not have it on all the time?

Daniel 

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

[Daniel Walker]

On Sun, 5 Jun 2005, Ingo Molnar wrote:

> 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.

We use it for all tasks . So for instance all priority levels get sorted ,
not just RT tasks. Most systems aren't going to have many RT tasks, just
interrupts and they don't share many locks. However, there are tons of
userspace tasks that do get sorted.

I think using plist on the wait_list is worth it. Since there aren't
many RT tasks usually . It may be a waste to use it on the pi_waiters.

Daniel

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

[Daniel Walker]

On Sun, 5 Jun 2005, Ingo Molnar wrote:
> 
> in any case, i've added most of your fixes and cleanups (changed the
> O(N) to O(K) and explained K) and have released the -47-17 patch.
> Daniel, do agree with these changes (in particular the __plist_del()
> changes?) and is there anything else missing? It looks like we might be
> near the end of the tunnel and plists are really stabilizing.


__plist_del was a good fix. I attached a patch on "Plist cleanup on RT" to
lkml with what was acceptable to me. A good 60% of Thomas's changes are
unacceptable to me.

Daniel

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

[Esben Nielsen]

On Sun, 5 Jun 2005, Ingo Molnar wrote:

> 
> * Esben Nielsen <simlo@phys.au.dk> wrote:
> 
> > [...] In extreme load situations we could end up with a lot of waiters 
> > on mmap_sem forinstance.
> 
> what do you mean by extreme load. Extreme number of RT tasks, or extreme 
> number of tasks altogether? The sorted-list implementation i had in -RT 
> had all non-RT tasks handled in an O(1) way - the O(N) component was for 
> adding RT tasks (removal was O(1)).
> 
> so the question is - can we have an extreme (larger than 140) number of 
> RT tasks? If yes, why are they all RT - they can have no expectation of 
> good latencies with a possible load factor of 140!

I can't really imagine a properly working application having more than 140
RT tasks pounding on the same lock - except maybe if someone tries to run
an RT application on one of those Altrix thingies (#CPUS>140 :-).

But as I said I could imagine a situation where you have some really
important RT tasks you would like to survive even if your low priority RT
tasks does something bad - like keep spawning RT tasks which all waits on
the same lock. 

Actually this test would make the difference:

thread1:
 lock(&badlock);
 block_on_some_event_which_might_never_arrive();
 unlock(&badlock);

func:
 lock(&badlock);
 unlock(&badlock);
 done=1;

thread2:
 while(!done) {
   create_thread(func,RTprio=50);
   create_thread(func,RTprio=51);
   if(done) break;
   sleep(1);
 }   

If you have enough memory for all the tasks, this kind of code would not
be a problem with plists - it will only take a lot of memory. On the other
hand with sorted lists each thread will take longer time inside raw
spinlocks. At some point it will take the whole 1 sec and basicly nothing
else can run.

Ofcourse you can prevent this with ulimits...

What I would do in this discussion is to abstract the interface:
The rt_mutex code should not care if plists, sorted lists or what ever are
used. It should just have a prio_queue structure and prio_queue_add(),
prio_queue_first(), a prio_queue_for_each macro etc. Then Daniel can play
along with his plists and have it as a config-option for now. Someone who
doesn't care about the memory consumption, could even choose to use the
prio_array from the scheduler!
 
> 
> 	Ingo

Esben

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

[Ingo Molnar]

* Esben Nielsen <simlo@phys.au.dk> wrote:

> [...] In extreme load situations we could end up with a lot of waiters 
> on mmap_sem forinstance.

what do you mean by extreme load. Extreme number of RT tasks, or extreme 
number of tasks altogether? The sorted-list implementation i had in -RT 
had all non-RT tasks handled in an O(1) way - the O(N) component was for 
adding RT tasks (removal was O(1)).

so the question is - can we have an extreme (larger than 140) number of 
RT tasks? If yes, why are they all RT - they can have no expectation of 
good latencies with a possible load factor of 140!

	Ingo

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

[Ingo Molnar]

* Thomas Gleixner <tglx@linutronix.de> wrote:

> > 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.
> 
> That was my question too.

i think it would be handy to resurrect ALL_TASKS_PI. It was one of the 
things that stabilized the sorted list approach so quickly. Nothing 
beats the coverage of running a full graphical desktop with all the PI 
code active :-)

	Ingo

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

[Esben Nielsen]

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

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

[Thomas Gleixner]

On Sun, 2005-06-05 at 10:26 +0200, Ingo Molnar wrote:

> > 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.

That was my question too. 

tglx

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

[Ingo Molnar]

* 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.

in any case, i've added most of your fixes and cleanups (changed the
O(N) to O(K) and explained K) and have released the -47-17 patch.
Daniel, do agree with these changes (in particular the __plist_del()
changes?) and is there anything else missing? It looks like we might be
near the end of the tunnel and plists are really stabilizing.

	Ingo