lkml.org 
[lkml]   [2005]   [Jun]   [6]   [last100]   RSS Feed
Views: [more markup]  [less markup]  [headers]  [forward] 
 
Messages in this thread
/
DateMon, 6 Jun 2005 09:32:29 +0200
FromIngo Molnar <>
SubjectRe: [patch] Real-Time Preemption, plist fixes
* 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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-06-06 07:36    [from the cache]
©2003-2008