Re: [PATCH 12/16] rtmutex: turn the plist into an rb-tree.

[Steven Rostedt]

On Fri, 2012-04-06 at 09:14 +0200, Juri Lelli wrote:
> From: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
> 
> 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@xxxxxxxxxxxxx>
> Signed-off-by: Dario Faggioli <raistlin@xxxxxxxx>
> Signed-off-by: Juri Lelli <juri.lelli@xxxxxxxxx>


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