[RFC][PATCH 0/8] Use EDF to throttle RT task groups

From: Fabio Checconi
Date: Mon Jun 15 2009 - 14:54:54 EST


This patchset introduces a group level EDF scheduler to extend the
current throttling mechanism, in order to make it support generic
period assignments. With this patch, the rt_runtime and rt_period
parameters can be used to specify arbitrary CPU reservations for
RT tasks.

The first two patches fix two problems of the current implementation.

This is an early RFC, I'm interested in having an idea of what people
think about this feature, if it's worth working on it, what can be
improved in the design, etc.

The main design issues involved:

- It is no more possible to specify RUNTIME_INF for a task group
when throttling is enabled. Rationale: supporting both throttled
and unthrottled groups would have required too much extra complexity
(I didn't find anything simpler than two parallel runqueues, one for
throttled and one for unthrottled groups).

- Since it is not easy to mix tasks and groups on the same scheduler
queue (tasks have no deadlines), the bandwidth reserved to the tasks
in a group is controlled with two additional cgroup attributes:
rt_task_runtime_us and rt_task_period_us. These attrinutes control,
within a cgroup, how much bandwidth is reserved to the tasks it
contains.

- Shared resources are still handled using boosting. When a group
contains a task inside a critical section it is scheduled according
the highest priority among the ones of the tasks it contains.
In this way, the same group has two modes: when it is not boosted
it is scheduled according to its deadline; when it is boosted, it
is scheduled according its priority. Boosted groups are always
favored over non-boosted ones.

- The old priority array is now gone. To use only a single data
structure for entities using both priorities and deadlines (due
to boosting), the only possible choice was to use an rb-tree;
the function used to order the keys takes into account the
prioritization described above (boosted tasks, ordered by
priority are favored to non-boosted tasks, ordered by increasing
deadline).

- Given that the various rt_rq's belonging to the same task group
are activated independently, there is the need of a timer per
each rt_rq.

The patchset is against sched-devel, and (temporarily) depends on
CONFIG_RT_GROUP_SCHED.

Any kind of feedback is welcome.

Fabio Checconi (8):
Fix rt_rq->pushable_tasks initialization in init_rt_rq()
Fix hrtick handling
Replace struct prio_array with an RB tree
Remove the balancing logic
Use EDF to throttle RT tasks hierarchically
Modify the curr/next priority tracking
Reprogram timers only when necessary
Use hrtick when available

include/linux/init_task.h | 1 -
include/linux/sched.h | 2 +-
kernel/sched.c | 553 +++++++++++++++++++++++++------------
kernel/sched_debug.c | 4 +-
kernel/sched_rt.c | 672 +++++++++++++++++++++++++++------------------
5 files changed, 781 insertions(+), 451 deletions(-)
--
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/