| Subject | Re: [PATCH 12/16] rtmutex: turn the plist into an rb-tree. | From | Steven Rostedt <> | Date | Wed, 11 Apr 2012 17:11:55 -0400 |
| |
On Fri, 2012-04-06 at 09:14 +0200, Juri Lelli wrote: > From: Peter Zijlstra <peterz@infradead.org> > > Turn the pi-chains from plist to rb-tree, in the rt_mutex code, > and provide a proper comparison function for -deadline and > -priority tasks.
I have to ask. Why not just add a rbtree with a plist? That is, add all deadline tasks to the rbtree and all others to the plist. As plist has a O(1) operation, and rbtree does not. We are making all RT tasks suffer the overhead of the rbtree.
As deadline tasks always win, the two may stay agnostic from each other. Check first the rbtree, if it is empty, then check the plist.
This will become more predominant with the -rt tree as it converts most the locks in the kernel to pi mutexes.
-- Steve
> > This is done mainly because: > - classical prio field of the plist is just an int, which might > not be enough for representing a deadline; > - manipulating such a list would become O(nr_deadline_tasks), > which might be to much, as the number of -deadline task increases. > > Therefore, an rb-tree is used, and tasks are queued in it according > to the following logic: > - among two -priority (i.e., SCHED_BATCH/OTHER/RR/FIFO) tasks, the > one with the higher (lower, actually!) prio wins; > - among a -priority and a -deadline task, the latter always wins; > - among two -deadline tasks, the one with the earliest deadline > wins. > > Queueing and dequeueing functions are changed accordingly, for both > the list of a task's pi-waiters and the list of tasks blocked on > a pi-lock. > > Signed-off-by: Peter Zijlstra <peterz@infradead.org> > Signed-off-by: Dario Faggioli <raistlin@linux.it> > Signed-off-by: Juri Lelli <juri.lelli@gmail.com>
|