Skip to contentSkip to conversation

sched: SCHED_DEADLINE v2

RFC PATCH In review Raistlin 4 participants 25 messages Feb 28, 2010 – Apr 15, 2010

Subsystems (11)
lore
Share & tools
lore

Raistlin

author
#0 lore raw

cover sched: SCHED_DEADLINE v2

Hi everybody,

Here it is the new version of the SCHED_DEADLINE patchset.

For the ones that missed the first posting[*], it is basically a new scheduling policy (implemented inside its own scheduling class) aiming at introducing deadline scheduling for Linux tasks, and it is being developed by Evidence S.r.l. (http://www.evidence.eu.com) in the context of the EU-Funded project ACTORS (http://www.actors-project.eu/).

From the previous version, mainly:
- I followed all the suggestions --about bug-fixing and code restyling-- that Peter kindly gave us in his review;
- in particular, I rewrote from scratch the group part, i.e., bandwidth is now accounted for in a per-CPU fashion, such that the interface is the same we already have for RT-throttling;
- I added a first drafted implementation of deadline inheritance, even though it surely needs thorough testing and refinements.

The official page of the project is:
http://www.evidence.eu.com/sched_deadline.html

while the development is taking place at[**]:
http://gitorious.org/sched_deadline/pages/Home
http://gitorious.org/sched_deadline

Still Missing parts:
- bandwidth reclaiming mechanisms, i.e., methods that avoid stopping the tasks until their next deadline when overrunning. There are at least three of them that are very simple, and patches are on their way;
- porting to PREEMPT-RT is almost done --thanks to Nicola and Luca-- and separate patches will be available on the project website soon;
- migration of tasks throughout push and pull (as in -rt), to make it possible to deploy global-EDF scheduling. Patches are ready, they're just being tested and adapted to this last version;
- refinements in deadline inheritance, especially regarding the possibility of retaining bandwidth isolation among non-interacting tasks. This is being studied from both theoretical and practical points of view, and hopefully we can have some demonstrative code soon.

As Fabio said recently, I also would like to remark that we are addressing different problems and providing the kernel with different new features, but we can share some code and we'll definitely do that if it is the case.

Patchset against Linus' master (at the time of this writing) follows, comments and any kind of feedback is, as usual, more than welcome.

Many thanks and Regards,
Dario Faggioli
Claudio Scordino
Michael Trimarchi

[*] http://lwn.net/Articles/353797/
[**] the repositories are outdated right now, I'll post the last changes
and the last version of utilities and testing programs in the very next days.

Dario Faggioli, SCHED_DEADLINE (11)
sched: add sched_class->task_dead.
sched: SCHED_DEADLINE policy implementation.
sched: add extended scheduling interface.
sched: add resource limits for -deadline tasks.
sched: add a syscall to wait for the next instance.
sched: add the sched-debug bits for sched_dl.
sched: add latency tracing for -deadline tasks.
sched: send SIGXCPU at -deadline task overruns.
sched: first draft of deadline inheritance.
sched: add bandwidth management for sched_dl.
sched: add sched_dl documentation.

 Documentation/scheduler/sched-deadline.txt |  188 ++++
 arch/arm/include/asm/unistd.h              |    4 +
 arch/arm/kernel/calls.S                    |    4 +
 arch/x86/ia32/ia32entry.S                  |    4 +
 arch/x86/include/asm/unistd_32.h           |    6 +-
 arch/x86/include/asm/unistd_64.h           |    8 +
 arch/x86/kernel/syscall_table_32.S         |    4 +
 include/asm-generic/resource.h             |    7 +-
 include/linux/sched.h                      |  173 ++++
 include/linux/syscalls.h                   |    9 +
 init/Kconfig                               |   15 +
 kernel/fork.c                              |   12 +
 kernel/hrtimer.c                           |    2 +-
 kernel/sched.c                             | 1329 +++++++++++++++++++++++++++-
 kernel/sched_debug.c                       |   36 +-
 kernel/sched_dl.c                          |  787 ++++++++++++++++
 kernel/sched_fair.c                        |    2 +-
 kernel/sched_rt.c                          |    2 +-
 kernel/sysctl.c                            |   21 +
 kernel/trace/trace_sched_wakeup.c          |   44 +-
 kernel/trace/trace_selftest.c              |   30 +-
 21 files changed, 2630 insertions(+), 57 deletions(-)
Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
author
#1 lore raw

RFC PATCH 1/11 sched: add sched_class->task_dead.

Add a new function to the scheduling class interface. It is called at the end of a cointext switch, if the going out task is in TASK_DEAD state.

It might be of help in case the scheduling class wants to be notified when one of its task dies, e.g. to perform some cleanup actions.

---
 include/linux/sched.h |    1 +
 kernel/sched.c        |    2 ++
 2 files changed, 3 insertions(+), 0 deletions(-)
include/linux/sched.h +1 -0
index 78efe7c..d1de995 100644
@@ -1119,6 +1119,7 @@ struct sched_class {
 	void (*set_curr_task) (struct rq *rq);
 	void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
 	void (*task_fork) (struct task_struct *p);
+	void (*task_dead) (struct task_struct *p);
 
 	void (*switched_from) (struct rq *this_rq, struct task_struct *task,
 			       int running);
kernel/sched.c +2 -0
index 3a8fb30..532dcf1 100644
@@ -2801,6 +2801,8 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev)
 	if (mm)
 		mmdrop(mm);
 	if (unlikely(prev_state == TASK_DEAD)) {
+		if (prev->sched_class->task_dead)
+			prev->sched_class->task_dead(prev);
 		/*
 		 * Remove function-return probe instances associated with this
 		 * task and put them back on the free list.
Signature · 9 lines
1.7.0

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
author
#2 lore raw

RFC PATCH 2/11 sched: SCHED_DEADLINE policy implementation.

In reply to Raistlin

Add a scheduling class, in sched_dl.c and a new policy called SCHED_DEADLINE. It basically is an implementation of the Earliest Deadline First (EDF) scheduling algorithm, augmented with a mechanism (called Constant Bandwidth Server, CBS) that make it possible to isolate the behaviour of tasks between each other.

The typical -deadline task will be made up of a computation phase (instance) which is activated on a periodic or sporadic fashion. The expected (maximum) duration of such computation is called the task's runtime; the time interval by which each instance need to be completed is called the task's relative deadline. The task's absolute deadline is dynamically calculated as the time instant a task (better, an instance) activates plus the relative deadline.

The EDF algorithms selects the task with the smallest absolute deadline as the one to be executed first, while the CBS ensures each task to run for at most the its runtime every (relative) deadline length time interval, avoiding any interference between different tasks (bandwidth isolation).
Thanks to this feature, also tasks that do not strictly comply with the computational model sketched above can effectively use the new policy.

This patch:
- defines the new scheduling policy and all the new data structures needed for its core implementation (e.g., task parameters storage, runqueues, etc.), and takes care of their initialization;
- implements the core logic of the scheduling algorithm in the new scheduling class file;
- provides all the glue code between the new scheduling class and the core scheduler and narrows the interactions between sched_dl and the other existing scheduling classes.

---
 include/linux/sched.h |   61 +++++
 kernel/fork.c         |   12 +
 kernel/hrtimer.c      |    2 +-
 kernel/sched.c        |   58 ++++-
 kernel/sched_dl.c     |  606 +++++++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched_fair.c   |    2 +-
 kernel/sched_rt.c     |    2 +-
 7 files changed, 731 insertions(+), 12 deletions(-)
include/linux/sched.h +61 -0
index d1de995..cd24a7a 100644
@@ -38,6 +38,7 @@
 #define SCHED_BATCH		3
 /* SCHED_ISO: reserved but not implemented yet */
 #define SCHED_IDLE		5
+#define SCHED_DEADLINE		6
 /* Can be ORed in to make sure the process is reverted back to SCHED_NORMAL on fork */
 #define SCHED_RESET_ON_FORK     0x40000000
 
@@ -1228,6 +1229,53 @@ struct sched_rt_entity {
 #endif
 };
 
+/*
+ * Scheduler internal flags.
+ *
+ * These values are only known by the scheduler and are intended to not
+ * be exported to userspace. On the other hand, bits lower than the 16th
+ * are reserved for the userspace to use them to (try to) affect the
+ * scheduler behaviour, and that's why we start from 0x10000.
+ *
+ *  @DL_NEW        tells us that a new instance arrived and that we must
+ *                 start executing it with full runtime and with absolute
+ *                 deadline just dl_deadline away from that time;
+ *  @DL_THROTTLED  tells us that the last instance exhausted the runtime
+ *                 and that the task is waiting for a replenishment to
+ *                 be performed at the next firing of dl_timer.
+ */
+#define DL_NEW			0x00010000
+#define DL_THROTTLED		0x00020000
+
+struct sched_dl_entity {
+	struct rb_node	rb_node;
+	int nr_cpus_allowed;
+
+	/*
+	 * Original parameters. They are copied here  from sched_param_ex
+	 * during sched_setscheduler_ex(), and will remain the same until the
+	 * next sched_setscheduler_ex().
+	 */
+	u64 dl_runtime;		/* maximum runtime for each instance 	*/
+	u64 dl_deadline;	/* relative deadline of each instance	*/
+
+	/*
+	 * Actual scheduling parameters. They are initialized with the
+	 * values above, but they are updated by the scheduler accordingly
+	 * to the task behaviour. Note that the remaining runtime could
+	 * be < 0 in case we are in overrun.
+	 */
+	s64 runtime;		/* remaining runtime for this instance	*/
+	u64 deadline;		/* absolute deadline for this instance	*/
+	unsigned int flags;
+
+	/*
+	 * Bandwidth enforcement timer. In fact, since each task has its
+	 * own bandwidth to be enforced, we need one timer per task.
+	 */
+	struct hrtimer dl_timer;
+};
+
 struct rcu_node;
 
 struct task_struct {
@@ -1250,6 +1298,7 @@ struct task_struct {
 	const struct sched_class *sched_class;
 	struct sched_entity se;
 	struct sched_rt_entity rt;
+	struct sched_dl_entity dl;
 
 #ifdef CONFIG_PREEMPT_NOTIFIERS
 	/* list of struct preempt_notifier: */
@@ -1603,6 +1652,18 @@ static inline int rt_task(struct task_struct *p)
 	return rt_prio(p->prio);
 }
 
+static inline int dl_policy(int policy)
+{
+	if (unlikely(policy == SCHED_DEADLINE))
+		return 1;
+	return 0;
+}
+
+static inline int dl_task(struct task_struct *p)
+{
+	return dl_policy(p->policy);
+}
+
 static inline struct pid *task_pid(struct task_struct *task)
 {
 	return task->pids[PIDTYPE_PID].pid;
kernel/fork.c +12 -0
index f88bd98..10d3753 100644
@@ -937,6 +937,16 @@ SYSCALL_DEFINE1(set_tid_address, int __user *, tidptr)
 	return task_pid_vnr(current);
 }
 
+static void init_task_dl_entity(struct task_struct *p)
+{
+	RB_CLEAR_NODE(&p->dl.rb_node);
+	hrtimer_init(&p->dl.dl_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
+
+	p->dl.dl_runtime = p->dl.runtime = 0;
+	p->dl.dl_deadline = p->dl.deadline = 0;
+	p->dl.flags = 0;
+}
+
 static void rt_mutex_init_task(struct task_struct *p)
 {
 	raw_spin_lock_init(&p->pi_lock);
@@ -1025,6 +1035,8 @@ static struct task_struct *copy_process(unsigned long clone_flags,
 
 	ftrace_graph_init_task(p);
 
+	init_task_dl_entity(p);
+
 	rt_mutex_init_task(p);
 
 #ifdef CONFIG_PROVE_LOCKING
kernel/hrtimer.c +1 -1
index 0086628..e59c2de 100644
@@ -1571,7 +1571,7 @@ long hrtimer_nanosleep(struct timespec *rqtp, struct timespec __user *rmtp,
 	unsigned long slack;
 
 	slack = current->timer_slack_ns;
-	if (rt_task(current))
+	if (dl_task(current) || rt_task(current))
 		slack = 0;
 
 	hrtimer_init_on_stack(&t.timer, clockid, mode);
kernel/sched.c +49 -9

141 lines not on this page · raw message

kernel/sched_dl.c new file +606 -0

606 lines not on this page · raw message

kernel/sched_fair.c +1 -1
index 8fe7ee8..7c31185 100644
@@ -1707,7 +1707,7 @@ static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_
 	int sync = wake_flags & WF_SYNC;
 	int scale = cfs_rq->nr_running >= sched_nr_latency;
 
-	if (unlikely(rt_prio(p->prio)))
+	if (unlikely(dl_task(p) || rt_prio(p->prio)))
 		goto preempt;
 
 	if (unlikely(p->sched_class != &fair_sched_class))
kernel/sched_rt.c +1 -1
index f48328a..84eee27 100644
@@ -1004,7 +1004,7 @@ static void check_preempt_equal_prio(struct rq *rq, struct task_struct *p)
  */
 static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p, int flags)
 {
-	if (p->prio < rq->curr->prio) {
+	if (dl_task(p) || p->prio < rq->curr->prio) {
 		resched_task(rq->curr);
 		return;
 	}
Signature · 9 lines
1.7.0

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
maintainer
#3 lore raw

Re: [RFC][PATCH 02/11] sched: SCHED_DEADLINE policy implementation.

kernel/sched_dl.c line 197

Quoted 9 lines · Raistlin
kernel/sched_dl.c new file +9 -0
+       /*
+        * Arm the timer to fire at wakeup, tying to compensate for
+        * the fact that wakeup is actually coming from rq->clock and
+        * not from hrtimer's time base reading.
+        */
+       act = ns_to_ktime(wakeup);
+       now = hrtimer_cb_get_time(&dl_se->dl_timer);
+       delta = ktime_to_ns(now) - rq->clock;
+       act = ktime_add_ns(act, delta); 

This is sad, but I'm afraid a reality we have to live with..

maintainer
#4 lore raw

Re: [RFC][PATCH 02/11] sched: SCHED_DEADLINE policy implementation.

In reply to Raistlin
Quoted 8 lines · Raistlin

+/*
+ * Pure Earliest Deadline First (EDF) scheduling does not deal with the
+ * possibility of a task lasting more than what it declared, and thus
+ * exhausting its runtime.
+ *
+ * Here we are interested in making runtime overrun possible, but we do
+ * not want a task which is misbehaving to affect the scheduling of all
+ * other tasks.

Quoted 8 lines

+ * Therefore, a budgeting strategy called Constant Bandwidth Server (CBS)
+ * is used, in order to confine each task within its own bandwidth.
+ *
+ * This function deals exactly with that, and ensures that when the runtime
+ * of a task is replenished, its deadline is also postponed. That results
+ * in "priority unboosting" for the overrunning task, and makes it impossible
+ * for it to cause unexpected interfere to other tasks in the system.
+ */

This is not about lock/inheritance related overrun, right? But simply a task that got its WCET wrong.

maintainer
#5 lore raw

Re: [RFC][PATCH 02/11] sched: SCHED_DEADLINE policy implementation.

In reply to Raistlin
Quoted 7 lines · Raistlin

+/*
+ * When a -deadline task is queued back on the runqueue, its runtime and
+ * deadline might need updating.
+ *
+ * The policy here is that we update the deadline of the task only if:
+ * - the current deadline is in the past,
+ * - using the remaining remaining with the current deadline would make

"remaining runtime", I presume?

Quoted 17 lines

+ * the task exceed its bandwidth.
+ */

kernel/sched_dl.c new file +15 -0
+static void update_dl_entity(struct sched_dl_entity *dl_se)
+{
+       struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
+       struct rq *rq = rq_of_dl_rq(dl_rq);
+
+       /*
+        * The arrival of a new task (or of a new task instance) needs
+        * special treatment. The actual scheduling parameters have to be
+        * "renewed" instead of recalculatetd accordingly to the bandwidth
+        * enforcement rule.
+        */
+       if (dl_se->flags & DL_NEW) {
+               setup_new_dl_entity(dl_se);
+               return;
+       }

kernel/sched_dl.c line 168

Quoted 10 lines
kernel/sched_dl.c new file +10 -0
+
+       if (dl_time_before(dl_se->deadline, rq->clock))
+               goto update;
+
+       if (!dl_check_bandwidth(dl_se, rq->clock)) {
+update:
+               dl_se->deadline = rq->clock + dl_se->dl_deadline;
+               dl_se->runtime = dl_se->dl_runtime;
+       }
+} 

We could write that as:

if (dl_time_before(dl_se, rq->clock) ||

      !dl_check_bandwidth(dl_se, rq->clock)) {
	/* reset parameters */

}

Also, I was wondering about a more descriptive name for dl_check_bandwidth(), check _what_ about the bandwidth!?

dl_bandwidth_overflow() perhaps, that would also remove that negation.

maintainer
#6 lore raw

Re: [RFC][PATCH 02/11] sched: SCHED_DEADLINE policy implementation.

In reply to Raistlin
Quoted 13 lines · Raistlin
kernel/sched_dl.c new file +13 -0
+/*
+ * Here we check if --at time t-- a task (which is probably being
+ * [re]activated or, in general, enqueued) can use its remaining runtime
+ * and its current deadline _without_ exceeding the bandwidth it is
+ * assigned (function returns true if it can).
+ *
+ * For this to hold, we must check if:
+ *   runtime / (deadline - t) < dl_runtime / dl_deadline .
+ */
+static bool dl_check_bandwidth(struct sched_dl_entity *dl_se, u64 t)
+{
+       u64 left, right;
+

kernel/sched_dl.c line 133

Quoted 10 lines
kernel/sched_dl.c new file +10 -0
+       /*
+        * left and right are the two sides of the equation above,
+        * after a bit of shuffling to use multiplications instead
+        * of divisions.
+        */
+       left = dl_se->dl_deadline * dl_se->runtime;
+       right = (dl_se->deadline - t) * dl_se->dl_runtime;
+
+       return dl_time_before(left, right);
+} 

So what happens when we overflow u64?

maintainer
#7 lore raw

Re: [RFC][PATCH 02/11] sched: SCHED_DEADLINE policy implementation.

Quoted 18 lines · Peter Zijlstra
Quoted 17 lines · Raistlin
kernel/sched_dl.c new file +17 -0
+/*
+ * Here we check if --at time t-- a task (which is probably being
+ * [re]activated or, in general, enqueued) can use its remaining runtime
+ * and its current deadline _without_ exceeding the bandwidth it is
+ * assigned (function returns true if it can).
+ *
+ * For this to hold, we must check if:
+ *   runtime / (deadline - t) < dl_runtime / dl_deadline .
+ */
+static bool dl_check_bandwidth(struct sched_dl_entity *dl_se, u64 t)
+{
+       u64 left, right;
+
+       /*
+        * left and right are the two sides of the equation above,
+        * after a bit of shuffling to use multiplications instead
+        * of divisions.
Quoted 8 lines

kernel/sched_dl.c line 133

Quoted 6 lines
kernel/sched_dl.c new file +6 -0
+        */
+       left = dl_se->dl_deadline * dl_se->runtime;
+       right = (dl_se->deadline - t) * dl_se->dl_runtime;
+
+       return dl_time_before(left, right);
+} 

So what happens when we overflow u64?

Is the resolution in nanosecs starting from zero? If so, then we don't need to worry about overflow for 583 years? And that is only if the difference in time is greater than 292 years since dl_time_before() does a:

(s64)(a - b) < 0

The (s64)(a - b) returns the difference even on overflow as long as the difference is not greater than 2^63

-- Steve

maintainer
#8 lore raw

Re: [RFC][PATCH 02/11] sched: SCHED_DEADLINE policy implementation.

Quoted 33 lines · Steven Rostedt
Quoted 18 lines · Peter Zijlstra
Quoted 17 lines · Raistlin
kernel/sched_dl.c new file +17 -0
+/*
+ * Here we check if --at time t-- a task (which is probably being
+ * [re]activated or, in general, enqueued) can use its remaining runtime
+ * and its current deadline _without_ exceeding the bandwidth it is
+ * assigned (function returns true if it can).
+ *
+ * For this to hold, we must check if:
+ *   runtime / (deadline - t) < dl_runtime / dl_deadline .
+ */
+static bool dl_check_bandwidth(struct sched_dl_entity *dl_se, u64 t)
+{
+       u64 left, right;
+
+       /*
+        * left and right are the two sides of the equation above,
+        * after a bit of shuffling to use multiplications instead
+        * of divisions.
Quoted 8 lines

kernel/sched_dl.c line 133

Quoted 6 lines
kernel/sched_dl.c new file +6 -0
+        */
+       left = dl_se->dl_deadline * dl_se->runtime;
+       right = (dl_se->deadline - t) * dl_se->dl_runtime;
+
+       return dl_time_before(left, right);
+} 

So what happens when we overflow u64?

Is the resolution in nanosecs starting from zero? If so, then we don't need to worry about overflow for 583 years? And that is only if the difference in time is greater than 292 years since dl_time_before() does a:

Quoted 4 lines

(s64)(a - b) < 0

The (s64)(a - b) returns the difference even on overflow as long as the difference is not greater than 2^63

Its a multiplication of two u64, that's a lot easier to overflow.

maintainer
#9 lore raw

Re: [RFC][PATCH 02/11] sched: SCHED_DEADLINE policy implementation.

In reply to Raistlin
Quoted 19 lines · Raistlin

+++ b/kernel/fork.c

kernel/fork.c +10 -0
@@ -937,6 +937,16 @@ SYSCALL_DEFINE1(set_tid_address, int __user *, tidptr)
        return task_pid_vnr(current);
 }
 
+static void init_task_dl_entity(struct task_struct *p)
+{
+       RB_CLEAR_NODE(&p->dl.rb_node);
+       hrtimer_init(&p->dl.dl_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
+
+       p->dl.dl_runtime = p->dl.runtime = 0;
+       p->dl.dl_deadline = p->dl.deadline = 0;
+       p->dl.flags = 0;
+}
+
 static void rt_mutex_init_task(struct task_struct *p)
 {
        raw_spin_lock_init(&p->pi_lock);

kernel/fork.c static struct task_struct *copy_process(unsigned long clone_flags, · line 1041

Quoted 7 lines
kernel/fork.c +2 -0
@@ -1025,6 +1035,8 @@ static struct task_struct *copy_process(unsigned long clone_flags,
 
        ftrace_graph_init_task(p);
 
+       init_task_dl_entity(p);
+
        rt_mutex_init_task(p);
 

Why doesn't that live in/use sched_fork()?

author
#10 lore raw

RFC PATCH 3/11 sched: add extended scheduling interface.

In reply to Raistlin

Add the interface bits needed for supporting scheduling algorithms with extended parameters (e.g., SCHED_DEADLINE).
In fact, specifying a periodic/sporadic task that executes for a given amount of runtime at each instance, and that is scheduled according to the usrgency of their own timing constraints needs, in general:
- a (maximum/typical) instance execution time,
- a minimum interval between consecutive instances,
- a time constraint by which each instance must be completed.

In order of this model to be useable, both the data structure that holds the scheduling parameter of tasks and the system calls that deal with them have to be extended.
Unfortunately, modifying the existing struct sched_param would break the ABI and result in potentially serious compatibility issues with legacy binary code.

For these reasons, this patch:
- defines the new struct sched_param_ex, containing all the fields that are necessary for specifying a task in the computational model described above;
- defines and implements the new scheduling related syscalls that manipulate it, i.e., sched_setscheduler_ex(), sched_setparam_ex() and sched_getparam_ex().

Syscalls are introduced for x86 (32 and 64 bits) and ARM only, as a proof of concept and for developing and testing purposes. However, making them available on other archs is straightforward.

The SCHED_DEADLINE policy is, as of now, the only user of this extended interface.

---
 arch/arm/include/asm/unistd.h      |    3 +
 arch/arm/kernel/calls.S            |    3 +
 arch/x86/ia32/ia32entry.S          |    3 +
 arch/x86/include/asm/unistd_32.h   |    5 +-
 arch/x86/include/asm/unistd_64.h   |    6 ++
 arch/x86/kernel/syscall_table_32.S |    3 +
 include/linux/sched.h              |   54 +++++++++++
 include/linux/syscalls.h           |    7 ++
 kernel/sched.c                     |  176 +++++++++++++++++++++++++++++++++++-
 9 files changed, 254 insertions(+), 6 deletions(-)
arch/arm/include/asm/unistd.h +3 -0
index cf9cdaa..e741cd6 100644
@@ -392,6 +392,9 @@
 #define __NR_rt_tgsigqueueinfo		(__NR_SYSCALL_BASE+363)
 #define __NR_perf_event_open		(__NR_SYSCALL_BASE+364)
 #define __NR_recvmmsg			(__NR_SYSCALL_BASE+365)
+#define __NR_sched_setscheduler_ex	(__NR_SYSCALL_BASE+366)
+#define __NR_sched_setparam_ex		(__NR_SYSCALL_BASE+367)
+#define __NR_sched_getparam_ex		(__NR_SYSCALL_BASE+368)
 
 /*
  * The following SWIs are ARM private.
arch/arm/kernel/calls.S +3 -0
index 9314a2d..8eeb552 100644
@@ -375,6 +375,9 @@
 		CALL(sys_rt_tgsigqueueinfo)
 		CALL(sys_perf_event_open)
 /* 365 */	CALL(sys_recvmmsg)
+		CALL(sys_sched_setscheduler_ex)
+		CALL(sys_sched_setparam_ex)
+		CALL(sys_sched_getparam_ex)
 #ifndef syscalls_counted
 .equ syscalls_padding, ((NR_syscalls + 3) & ~3) - NR_syscalls
 #define syscalls_counted
arch/x86/ia32/ia32entry.S +3 -0
index 53147ad..f24e9fa 100644
@@ -842,4 +842,7 @@ ia32_sys_call_table:
 	.quad compat_sys_rt_tgsigqueueinfo	/* 335 */
 	.quad sys_perf_event_open
 	.quad compat_sys_recvmmsg
+	.quad sys_sched_setscheduler_ex
+	.quad sys_sched_setparam_ex
+	.quad sys_sched_getparam_ex		/* 340 */
 ia32_syscall_end:
arch/x86/include/asm/unistd_32.h +4 -1
index 3baf379..1db148b 100644
@@ -343,10 +343,13 @@
 #define __NR_rt_tgsigqueueinfo	335
 #define __NR_perf_event_open	336
 #define __NR_recvmmsg		337
+#define __NR_sched_setscheduler_ex	338
+#define __NR_sched_setparam_ex		339
+#define __NR_sched_getparam_ex		340
 
 #ifdef __KERNEL__
 
-#define NR_syscalls 338
+#define NR_syscalls 341
 
 #define __ARCH_WANT_IPC_PARSE_VERSION
 #define __ARCH_WANT_OLD_READDIR
arch/x86/include/asm/unistd_64.h +6 -0
index 4843f7b..d254154 100644
@@ -663,6 +663,12 @@ __SYSCALL(__NR_rt_tgsigqueueinfo, sys_rt_tgsigqueueinfo)
 __SYSCALL(__NR_perf_event_open, sys_perf_event_open)
 #define __NR_recvmmsg				299
 __SYSCALL(__NR_recvmmsg, sys_recvmmsg)
+#define __NR_sched_setscheduler_ex		300
+__SYSCALL(__NR_sched_setscheduler_ex, sys_sched_setscheduler_ex)
+#define __NR_sched_setparam_ex			301
+__SYSCALL(__NR_sched_setparam_ex, sys_sched_setparam_ex)
+#define __NR_sched_getparam_ex			302
+__SYSCALL(__NR_sched_getparam_ex, sys_sched_getparam_ex)
 
 #ifndef __NO_STUBS
 #define __ARCH_WANT_OLD_READDIR
arch/x86/kernel/syscall_table_32.S +3 -0
index 15228b5..e27e002 100644
@@ -337,3 +337,6 @@ ENTRY(sys_call_table)
 	.long sys_rt_tgsigqueueinfo	/* 335 */
 	.long sys_perf_event_open
 	.long sys_recvmmsg
+	.long sys_sched_setscheduler_ex
+	.long sys_sched_setparam_ex
+	.long sys_sched_getparam_ex	/* 340 */
include/linux/sched.h +54 -0

66 lines not on this page · raw message

include/linux/syscalls.h +7 -0
index 207466a..9e3ad66 100644
@@ -34,6 +34,7 @@ struct pollfd;
 struct rlimit;
 struct rusage;
 struct sched_param;
+struct sched_param_ex;
 struct semaphore;
 struct sembuf;
 struct shmid_ds;
@@ -340,11 +341,17 @@ asmlinkage long sys_clock_nanosleep(clockid_t which_clock, int flags,
 asmlinkage long sys_nice(int increment);
 asmlinkage long sys_sched_setscheduler(pid_t pid, int policy,
 					struct sched_param __user *param);
+asmlinkage long sys_sched_setscheduler_ex(pid_t pid, int policy, unsigned len,
+					struct sched_param_ex __user *param);
 asmlinkage long sys_sched_setparam(pid_t pid,
 					struct sched_param __user *param);
+asmlinkage long sys_sched_setparam_ex(pid_t pid, unsigned len,
+					struct sched_param_ex __user *param);
 asmlinkage long sys_sched_getscheduler(pid_t pid);
 asmlinkage long sys_sched_getparam(pid_t pid,
 					struct sched_param __user *param);
+asmlinkage long sys_sched_getparam_ex(pid_t pid, unsigned len,
+					struct sched_param_ex __user *param);
 asmlinkage long sys_sched_setaffinity(pid_t pid, unsigned int len,
 					unsigned long __user *user_mask_ptr);
 asmlinkage long sys_sched_getaffinity(pid_t pid, unsigned int len,
kernel/sched.c +171 -5

245 lines not on this page · raw message

Signature · 9 lines
1.7.0

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
author
#11 lore raw

RFC PATCH 4/11 sched: add resource limits for -deadline tasks.

In reply to Raistlin

Add resource limits for non-root tasks in using the SCHED_DEADLINE policy, very similarly to what already exists for RT policies.

In fact, this patch:
- adds the resource limit RLIMIT_DLDLINE, which is the minimum value a user task can use as its own deadline;
- adds the resource limit RLIMIT_DLRTIME, which is the maximum value a user task can use as it own runtime.

Notice that to exploit these, a modified version of the ulimit utility and a modified resource.h header file are needed. They both will be available on the website of the project.

---
 include/asm-generic/resource.h |    7 ++++++-
 kernel/sched.c                 |   25 +++++++++++++++++++++++++
 2 files changed, 31 insertions(+), 1 deletions(-)
include/asm-generic/resource.h +6 -1
index 587566f..4a1d0e2 100644
@@ -45,7 +45,10 @@
 					   0-39 for nice level 19 .. -20 */
 #define RLIMIT_RTPRIO		14	/* maximum realtime priority */
 #define RLIMIT_RTTIME		15	/* timeout for RT tasks in us */
-#define RLIM_NLIMITS		16
+
+#define RLIMIT_DLDLINE		16	/* minimum deadline in us */
+#define RLIMIT_DLRTIME		17	/* maximum runtime in us */
+#define RLIM_NLIMITS		18
 
 /*
  * SuS says limits have to be unsigned.
@@ -87,6 +90,8 @@
 	[RLIMIT_NICE]		= { 0, 0 },				\
 	[RLIMIT_RTPRIO]		= { 0, 0 },				\
 	[RLIMIT_RTTIME]		= {  RLIM_INFINITY,  RLIM_INFINITY },	\
+	[RLIMIT_DLDLINE]	= { ULONG_MAX, ULONG_MAX },		\
+	[RLIMIT_DLRTIME]	= { 0, 0 },				\
 }
 
 #endif	/* __KERNEL__ */
kernel/sched.c +25 -0
index 19e90fc..61b1561 100644
@@ -6407,6 +6407,31 @@ recheck:
 	 * Allow unprivileged RT tasks to decrease priority:
 	 */
 	if (user && !capable(CAP_SYS_NICE)) {
+		if (dl_policy(policy)) {
+			u64 rlim_dline, rlim_rtime;
+			u64 dline, rtime;
+
+			if (!lock_task_sighand(p, &flags))
+				return -ESRCH;
+			rlim_dline = p->signal->rlim[RLIMIT_DLDLINE].rlim_cur;
+			rlim_rtime = p->signal->rlim[RLIMIT_DLRTIME].rlim_cur;
+			unlock_task_sighand(p, &flags);
+
+			/* can't set/change -deadline policy */
+			if (policy != p->policy && !rlim_rtime)
+				return -EPERM;
+
+			/* can't decrease the deadline */
+			rlim_dline *= NSEC_PER_USEC;
+			dline = timespec_to_ns(&param_ex->sched_deadline);
+			if (dline < p->dl.dl_deadline && dline < rlim_dline)
+				return -EPERM;
+			/* can't increase the runtime */
+			rlim_rtime *= NSEC_PER_USEC;
+			rtime = timespec_to_ns(&param_ex->sched_runtime);
+			if (rtime > p->dl.dl_runtime && rtime > rlim_rtime)
+				return -EPERM;
+		}
 		if (rt_policy(policy)) {
 			unsigned long rlim_rtprio;
 
Signature · 9 lines
1.7.0

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
author
#12 lore raw

RFC PATCH 5/11 sched: add a syscall to wait for the next instance.

In reply to Raistlin

Introduce sched_wait_interval() syscall (and scheduling class interface call). In general, this aims at providing each scheduling class with a mean of making one of its own task sleep for some time according to some specific rule of the scheduling class itself.

As of now, the sched_dl scheduling class is the only one that needs this kind of service, and thus the only one that implements the class-specific logic. For other classes, calling it will result in the same effect than calling clock_nanosleep with CLOCK_MONOTONIC clockid and the TIMER_ABSTIME flag on.

For -deadline task, the idea is to give them the possibility of notifying the scheduler a periodic/sporadic instance just ended and ask it to wake up them at the beginning of the next one, with:
- fully replenished runtime and
- the absolute deadline set just one relative deadline interval away from the wakeup time.
This is an effective mean of synchronizing the task's behaviour with the scheduler one, which might be useful in some situations.

This patch:
- adds the new syscall (x83-32, x86-64 and ARM, but extension to all archs is strightforward);
- implements the class-specific logic for -deadline tasks, making it impossible for them to exploit this call to use more bandwidth than they are given.

---
 arch/arm/include/asm/unistd.h      |    1 +
 arch/arm/kernel/calls.S            |    1 +
 arch/x86/ia32/ia32entry.S          |    1 +
 arch/x86/include/asm/unistd_32.h   |    3 +-
 arch/x86/include/asm/unistd_64.h   |    2 +
 arch/x86/kernel/syscall_table_32.S |    1 +
 include/linux/sched.h              |    2 +
 include/linux/syscalls.h           |    2 +
 kernel/sched.c                     |   39 +++++++++++++++++++
 kernel/sched_dl.c                  |   74 +++++++++++++++++++++++++++++++++++-
 10 files changed, 124 insertions(+), 2 deletions(-)
arch/arm/include/asm/unistd.h +1 -0
index e741cd6..8ca0ece 100644
@@ -395,6 +395,7 @@
 #define __NR_sched_setscheduler_ex	(__NR_SYSCALL_BASE+366)
 #define __NR_sched_setparam_ex		(__NR_SYSCALL_BASE+367)
 #define __NR_sched_getparam_ex		(__NR_SYSCALL_BASE+368)
+#define __NR_sched_wait_interval	(__NR_SYSCALL_BASE+369)
 
 /*
  * The following SWIs are ARM private.
arch/arm/kernel/calls.S +1 -0
index 8eeb552..6cb3842 100644
@@ -378,6 +378,7 @@
 		CALL(sys_sched_setscheduler_ex)
 		CALL(sys_sched_setparam_ex)
 		CALL(sys_sched_getparam_ex)
+		CALL(sys_sched_wait_interval)
 #ifndef syscalls_counted
 .equ syscalls_padding, ((NR_syscalls + 3) & ~3) - NR_syscalls
 #define syscalls_counted
arch/x86/ia32/ia32entry.S +1 -0
index f24e9fa..85d383b 100644
@@ -845,4 +845,5 @@ ia32_sys_call_table:
 	.quad sys_sched_setscheduler_ex
 	.quad sys_sched_setparam_ex
 	.quad sys_sched_getparam_ex		/* 340 */
+	.quad sys_sched_wait_interval
 ia32_syscall_end:
arch/x86/include/asm/unistd_32.h +2 -1
index 1db148b..83c8a3f 100644
@@ -346,10 +346,11 @@
 #define __NR_sched_setscheduler_ex	338
 #define __NR_sched_setparam_ex		339
 #define __NR_sched_getparam_ex		340
+#define __NR_sched_wait_interval	341
 
 #ifdef __KERNEL__
 
-#define NR_syscalls 341
+#define NR_syscalls 342
 
 #define __ARCH_WANT_IPC_PARSE_VERSION
 #define __ARCH_WANT_OLD_READDIR
arch/x86/include/asm/unistd_64.h +2 -0
index d254154..b9e3356 100644
@@ -669,6 +669,8 @@ __SYSCALL(__NR_sched_setscheduler_ex, sys_sched_setscheduler_ex)
 __SYSCALL(__NR_sched_setparam_ex, sys_sched_setparam_ex)
 #define __NR_sched_getparam_ex			302
 __SYSCALL(__NR_sched_getparam_ex, sys_sched_getparam_ex)
+#define __NR_sched_wait_interval		303
+__SYSCALL(__NR_sched_wait_interval, sys_sched_wait_interval)
 
 #ifndef __NO_STUBS
 #define __ARCH_WANT_OLD_READDIR
arch/x86/kernel/syscall_table_32.S +1 -0
index e27e002..1609ba9 100644
@@ -340,3 +340,4 @@ ENTRY(sys_call_table)
 	.long sys_sched_setscheduler_ex
 	.long sys_sched_setparam_ex
 	.long sys_sched_getparam_ex	/* 340 */
+	.long sys_sched_wait_interval
include/linux/sched.h +2 -0
index 3c466a6..e6c1cda 100644
@@ -1139,6 +1139,8 @@ struct sched_class {
 	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
 	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
 	void (*yield_task) (struct rq *rq);
+	long (*wait_interval) (struct task_struct *p, struct timespec *rqtp,
+			       struct timespec __user *rmtp);
 
 	void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
 
include/linux/syscalls.h +2 -0
index 9e3ad66..97eb7c4 100644
@@ -357,6 +357,8 @@ asmlinkage long sys_sched_setaffinity(pid_t pid, unsigned int len,
 asmlinkage long sys_sched_getaffinity(pid_t pid, unsigned int len,
 					unsigned long __user *user_mask_ptr);
 asmlinkage long sys_sched_yield(void);
+asmlinkage long sys_sched_wait_interval(const struct timespec __user *rqtp,
+					struct timespec *rmtp);
 asmlinkage long sys_sched_get_priority_max(int policy);
 asmlinkage long sys_sched_get_priority_min(int policy);
 asmlinkage long sys_sched_rr_get_interval(pid_t pid,
kernel/sched.c +39 -0
index 61b1561..d5e8b6c 100644
@@ -6966,6 +6966,45 @@ SYSCALL_DEFINE0(sched_yield)
 	return 0;
 }
 
+/**
+ * sys_sched_wait_interval - sleep according to the scheduling class rules.
+ *
+ * This function is implemented inside each scheduling class, in case it
+ * wants to provide its tasks a mean of waiting a specific instant in
+ * time, while also honouring some specific rule of itself.
+ */
+SYSCALL_DEFINE2(sched_wait_interval,
+	const struct timespec __user *, rqtp,
+	struct timespec __user *, rmtp)
+{
+	struct timespec lrq, lrm;
+	int ret;
+
+	if (rqtp != NULL) {
+		if (copy_from_user(&lrq, rqtp, sizeof(struct timespec)))
+			return -EFAULT;
+		if (!timespec_valid(&lrq))
+			return -EINVAL;
+	}
+
+	if (current->sched_class->wait_interval)
+		ret = current->sched_class->wait_interval(current,
+							  rqtp ? &lrq : NULL,
+							  &lrm);
+	else {
+		if (!rqtp)
+			return -EINVAL;
+
+		ret = hrtimer_nanosleep(&lrq, &lrm, HRTIMER_MODE_ABS,
+					CLOCK_MONOTONIC);
+	}
+
+	if (rmtp && copy_to_user(rmtp, &lrm, sizeof(struct timespec)))
+		return -EFAULT;
+
+	return ret;
+}
+
 static inline int should_resched(void)
 {
 	return need_resched() && !(preempt_count() & PREEMPT_ACTIVE);
kernel/sched_dl.c +73 -1

92 lines not on this page · raw message

Signature · 9 lines
1.7.0

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
author
#13 lore raw

RFC PATCH 6/11 sched: add the sched-debug bits for sched_dl.

In reply to Raistlin

Add the typical debugging output provided by sched_deug (if enabled) also to the sched_dl class.

---
 kernel/sched_debug.c |   33 +++++++++++++++++++++++++++++++++
 kernel/sched_dl.c    |   26 ++++++++++++++++++++++++++
 2 files changed, 59 insertions(+), 0 deletions(-)
kernel/sched_debug.c +33 -0
index 67f95aa..407a761 100644
@@ -246,6 +246,38 @@ void print_rt_rq(struct seq_file *m, int cpu, struct rt_rq *rt_rq)
 #undef P
 }
 
+void print_dl_rq(struct seq_file *m, int cpu, struct dl_rq *dl_rq)
+{
+	s64 min_deadline = -1, max_deadline = -1;
+	struct rq *rq = &per_cpu(runqueues, cpu);
+	struct sched_dl_entity *last;
+	unsigned long flags;
+
+	SEQ_printf(m, "\ndl_rq[%d]:\n", cpu);
+
+	raw_spin_lock_irqsave(&rq->lock, flags);
+	if (dl_rq->rb_leftmost)
+		min_deadline = (rb_entry(dl_rq->rb_leftmost,
+					 struct sched_dl_entity,
+					 rb_node))->deadline;
+	last = __pick_dl_last_entity(dl_rq);
+	if (last)
+		max_deadline = last->deadline;
+	raw_spin_unlock_irqrestore(&rq->lock, flags);
+
+#define P(x) \
+	SEQ_printf(m, "  .%-30s: %Ld\n", #x, (long long)(x))
+#define PN(x) \
+	SEQ_printf(m, "  .%-30s: %Ld.%06ld\n", #x, SPLIT_NS(x))
+
+	P(dl_rq->dl_nr_running);
+	PN(min_deadline);
+	PN(max_deadline);
+
+#undef PN
+#undef P
+}
+
 static void print_cpu(struct seq_file *m, int cpu)
 {
 	struct rq *rq = cpu_rq(cpu);
@@ -305,6 +337,7 @@ static void print_cpu(struct seq_file *m, int cpu)
 #endif
 	print_cfs_stats(m, cpu);
 	print_rt_stats(m, cpu);
+	print_dl_stats(m, cpu);
 
 	print_rq(m, rq, cpu);
 }
kernel/sched_dl.c +26 -0
index a1202ac..dee2668 100644
@@ -44,6 +44,9 @@ static inline int dl_time_before(u64 a, u64 b)
 	return (s64)(a - b) < 0;
 }
 
+#define for_each_leaf_dl_rq(dl_rq, rq) \
+	for (dl_rq = &rq->dl; dl_rq; dl_rq = NULL)
+
 static void enqueue_dl_entity(struct sched_dl_entity *dl_se);
 static void dequeue_dl_entity(struct sched_dl_entity *dl_se);
 static void check_dl_preempt_curr(struct task_struct *p, struct rq *rq);
@@ -512,6 +515,16 @@ static void start_hrtick_dl(struct rq *rq, struct task_struct *p)
 }
 #endif
 
+static struct sched_dl_entity *__pick_dl_last_entity(struct dl_rq *dl_rq)
+{
+	struct rb_node *last = rb_last(&dl_rq->rb_root);
+
+	if (!last)
+		return NULL;
+
+	return rb_entry(last, struct sched_dl_entity, rb_node);
+}
+
 static struct sched_dl_entity *pick_next_dl_entity(struct rq *rq,
 						   struct dl_rq *dl_rq)
 {
@@ -676,3 +689,16 @@ static const struct sched_class dl_sched_class = {
 	.switched_to		= switched_to_dl,
 };
 
+#ifdef CONFIG_SCHED_DEBUG
+extern void print_dl_rq(struct seq_file *m, int cpu, struct dl_rq *dl_rq);
+
+static void print_dl_stats(struct seq_file *m, int cpu)
+{
+	struct dl_rq *dl_rq = &cpu_rq(cpu)->dl;
+
+	rcu_read_lock();
+	for_each_leaf_dl_rq(dl_rq, cpu_rq(cpu))
+		print_dl_rq(m, cpu, dl_rq);
+	rcu_read_unlock();
+}
+#endif /* CONFIG_SCHED_DEBUG */
Signature · 9 lines
1.7.0

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
author
#14 lore raw

RFC PATCH 7/11 sched: add latency tracing for -deadline tasks.

In reply to Raistlin

It is very likely that systems that wants/needs to use the new SCHED_DEADLINE policy also want to have the scheduling latency of the -deadline tasks under control.

For this reason a new version of the scheduling wakeup latency, called "wakeup_dl", is introduced.

As a consequence of applying this patch there will be three wakeup latency tracer:
* "wakeup", that deals with all tasks in the system;
* "wakeup_rt", that deals with -rt and -deadline tasks only;
* "wakeup_dl", that deals with -deadline tasks only.

---
 kernel/trace/trace_sched_wakeup.c |   44 +++++++++++++++++++++++++++++++++---
 kernel/trace/trace_selftest.c     |   30 +++++++++++++++----------
 2 files changed, 58 insertions(+), 16 deletions(-)
kernel/trace/trace_sched_wakeup.c +40 -4
index 0271742..a02ce04 100644
@@ -27,6 +27,7 @@ static int			wakeup_cpu;
 static int			wakeup_current_cpu;
 static unsigned			wakeup_prio = -1;
 static int			wakeup_rt;
+static int			wakeup_dl;
 
 static arch_spinlock_t wakeup_lock =
 	(arch_spinlock_t)__ARCH_SPIN_LOCK_UNLOCKED;
@@ -214,9 +215,17 @@ probe_wakeup(struct rq *rq, struct task_struct *p, int success)
 	tracing_record_cmdline(p);
 	tracing_record_cmdline(current);
 
-	if ((wakeup_rt && !rt_task(p)) ||
-			p->prio >= wakeup_prio ||
-			p->prio >= current->prio)
+	/*
+	 * Semantic is like this:
+	 *  - wakeup tracer handles all tasks in the system, independently
+	 *    from their scheduling class;
+	 *  - wakeup_rt tracer handles tasks belonging to sched_dl and
+	 *    sched_rt class;
+	 *  - wakeup_dl handles tasks belonging to sched_dl class only.
+	 */
+	if ((wakeup_dl && !dl_task(p)) ||
+	    (wakeup_rt && !dl_task(p) && !rt_task(p)) ||
+	    (p->prio >= wakeup_prio || p->prio >= current->prio))
 		return;
 
 	pc = preempt_count();
@@ -228,7 +237,7 @@ probe_wakeup(struct rq *rq, struct task_struct *p, int success)
 	arch_spin_lock(&wakeup_lock);
 
 	/* check for races. */
-	if (!tracer_enabled || p->prio >= wakeup_prio)
+	if (!tracer_enabled || (!dl_task(p) && p->prio >= wakeup_prio))
 		goto out_locked;
 
 	/* reset the trace */
@@ -340,16 +349,25 @@ static int __wakeup_tracer_init(struct trace_array *tr)
 
 static int wakeup_tracer_init(struct trace_array *tr)
 {
+	wakeup_dl = 0;
 	wakeup_rt = 0;
 	return __wakeup_tracer_init(tr);
 }
 
 static int wakeup_rt_tracer_init(struct trace_array *tr)
 {
+	wakeup_dl = 0;
 	wakeup_rt = 1;
 	return __wakeup_tracer_init(tr);
 }
 
+static int wakeup_dl_tracer_init(struct trace_array *tr)
+{
+	wakeup_dl = 1;
+	wakeup_rt = 0;
+	return __wakeup_tracer_init(tr);
+}
+
 static void wakeup_tracer_reset(struct trace_array *tr)
 {
 	stop_wakeup_tracer(tr);
@@ -398,6 +416,20 @@ static struct tracer wakeup_rt_tracer __read_mostly =
 #endif
 };
 
+static struct tracer wakeup_dl_tracer __read_mostly =
+{
+	.name		= "wakeup_dl",
+	.init		= wakeup_dl_tracer_init,
+	.reset		= wakeup_tracer_reset,
+	.start		= wakeup_tracer_start,
+	.stop		= wakeup_tracer_stop,
+	.wait_pipe	= poll_wait_pipe,
+	.print_max	= 1,
+#ifdef CONFIG_FTRACE_SELFTEST
+	.selftest    = trace_selftest_startup_wakeup,
+#endif
+};
+
 __init static int init_wakeup_tracer(void)
 {
 	int ret;
@@ -410,6 +442,10 @@ __init static int init_wakeup_tracer(void)
 	if (ret)
 		return ret;
 
+	ret = register_tracer(&wakeup_dl_tracer);
+	if (ret)
+		return ret;
+
 	return 0;
 }
 device_initcall(init_wakeup_tracer);
kernel/trace/trace_selftest.c +18 -12
index 280fea4..4834411 100644
@@ -558,11 +558,17 @@ trace_selftest_startup_nop(struct tracer *trace, struct trace_array *tr)
 #ifdef CONFIG_SCHED_TRACER
 static int trace_wakeup_test_thread(void *data)
 {
-	/* Make this a RT thread, doesn't need to be too high */
-	struct sched_param param = { .sched_priority = 5 };
+	/* Make this a -deadline thread */
+	struct sched_param param = { .sched_priority = 0 };
+	struct sched_param_ex paramx = {
+		.sched_priority = 0,
+		.sched_runtime = { .tv_sec = 0, .tv_nsec = 100000 },
+		.sched_deadline = { .tv_sec = 0, .tv_nsec = 10000000 },
+		.sched_flags = 0
+	};
 	struct completion *x = data;
 
-	sched_setscheduler(current, SCHED_FIFO, &param);
+	sched_setscheduler_ex(current, SCHED_DEADLINE, &param, &paramx);
 
 	/* Make it know we have a new prio */
 	complete(x);
@@ -574,8 +580,8 @@ static int trace_wakeup_test_thread(void *data)
 	/* we are awake, now wait to disappear */
 	while (!kthread_should_stop()) {
 		/*
-		 * This is an RT task, do short sleeps to let
-		 * others run.
+		 * This will likely be the system top priority
+		 * task, do short sleeps to let others run.
 		 */
 		msleep(100);
 	}
@@ -588,21 +594,21 @@ trace_selftest_startup_wakeup(struct tracer *trace, struct trace_array *tr)
 {
 	unsigned long save_max = tracing_max_latency;
 	struct task_struct *p;
-	struct completion isrt;
+	struct completion is_ready;
 	unsigned long count;
 	int ret;
 
-	init_completion(&isrt);
+	init_completion(&is_ready);
 
-	/* create a high prio thread */
-	p = kthread_run(trace_wakeup_test_thread, &isrt, "ftrace-test");
+	/* create a -deadline thread */
+	p = kthread_run(trace_wakeup_test_thread, &is_ready, "ftrace-test");
 	if (IS_ERR(p)) {
 		printk(KERN_CONT "Failed to create ftrace wakeup test thread ");
 		return -1;
 	}
 
-	/* make sure the thread is running at an RT prio */
-	wait_for_completion(&isrt);
+	/* make sure the thread is running at -deadline policy */
+	wait_for_completion(&is_ready);
 
 	/* start the tracing */
 	ret = tracer_init(trace, tr);
@@ -614,7 +620,7 @@ trace_selftest_startup_wakeup(struct tracer *trace, struct trace_array *tr)
 	/* reset the max latency */
 	tracing_max_latency = 0;
 
-	/* sleep to let the RT thread sleep too */
+	/* sleep to let the thread sleep too */
 	msleep(100);
 
 	/*
Signature · 9 lines
1.7.0

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
author
#15 lore raw

RFC PATCH 8/11 sched: send SIGXCPU at -deadline task overruns.

In reply to Raistlin

Add to the scheduler the capability of notifying when -deadline tasks overrun their maximum runtime and/or overcome their scheduling deadline.

Runtime overruns might be quite common, e.g., due to coarse granularity execution time accounting resolution or wrong assignment of tasks' parameters (especially runtime). However, since the scheduler enforces bandwidth isolation among tasks, this is not at all a threat to other tasks' schedulability. For this reason, it is not common that a task wants to be notified about that. Moreover, if we are using the SCHED_DEADLINE policy with sporadic tasks, or to limit the bandwidth of not periodic nor sporadic ones, runtime overruns are very likely to occur at each and every instance, and again they should not be considered a problem.

On the other hand, a deadline miss in any task means that, even if we are trying at our best to keep each task isolated and to avoid reciprocal interference among them, something went very, very bad, and one task did not manage in consuming its runtime by its deadline. This is something that should happen only on an oversubscribed system, and thus being notified when it occurs could be very useful.

The user can specify the signals he wants to be sent to his task during sched_setscheduler_ex(), raising two specific flags in the sched_flags field of struct sched_param_ex:
* SCHED_SIG_RORUN (if he wants to be signaled on runtime overrun),
* SCHED_SIG_DMISS (if he wants to be signaled on deadline misses).

This patch:
- adds the logic needed to send SIGXCPU signal to a -deadline task in case its actual runtime becomes negative;
- adds the logic needed to send SIGXCPU signal to a -deadline task in case it is still being scheduled while its absolute deadline passes.

---
 include/linux/sched.h |   18 ++++++++++++++++++
 kernel/sched_dl.c     |   24 ++++++++++++++++++++++++
 2 files changed, 42 insertions(+), 0 deletions(-)
include/linux/sched.h +18 -0
index e6c1cda..64a7df2 100644
@@ -138,6 +138,7 @@ struct sched_param {
  * More information about the algorithm are available in the scheduling
  * class file or in Documentation/.
  */
+
 struct sched_param_ex {
 	int sched_priority;
 	struct timespec sched_runtime;
@@ -146,6 +147,23 @@ struct sched_param_ex {
 	unsigned int sched_flags;
 };
 
+/*
+ * User -deadline flags.
+ *
+ * These flags are exported to userspace so that tasks can try to affect
+ * the scheduler behaviour and/or specifying that they want to be informed
+ * of the occurrence of some events. There are at most 16 of them available
+ * (lowest bits), since values above 0x10000 are reserved for kernel
+ * internal flags.
+ *
+ *  @SCHED_SIG_RORUN	tells us the task wants to be notified whenever
+ *                      a runtime overrun occurs;
+ *  @SCHED_SIG_DMISS	tells us the task wants to be notified whenever
+ *                      a scheduling deadline is missed.
+ */
+#define SCHED_SIG_RORUN		0x0001
+#define SCHED_SIG_DMISS		0x0002
+
 struct exec_domain;
 struct futex_pi_state;
 struct robust_list_head;
kernel/sched_dl.c +24 -0
index dee2668..b5dde44 100644
@@ -265,6 +265,14 @@ static void init_dl_timer(struct sched_dl_entity *dl_se)
 	timer->function = dl_timer;
 }
 
+#define dl_se_signal(se, s, msg)					\
+ do {									\
+  struct task_struct *t = dl_task_of(se);				\
+  sigaddset(&t->pending.signal, s);					\
+  set_tsk_thread_flag(t, TIF_SIGPENDING);				\
+  printk(KERN_INFO msg "in %d (%s)\n", task_pid_nr(t), t->comm);	\
+ } while (0)
+
 static
 int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)
 {
@@ -283,6 +291,22 @@ int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)
 	if (dmiss)
 		dl_se->runtime -= rq->clock - dl_se->deadline;
 
+	/*
+	 * if the userspace asked for that, we notify about (scheduling)
+	 * deadline misses and runtime overruns via sending SIGXCPU to
+	 * "faulting" task.
+	 *
+	 * Note that (hopefully small) runtime overruns are very likely
+	 * to occur, mainly due to accounting resolution, while missing a
+	 * scheduling deadline should be very rare, and only happen on
+	 * an oversubscribed systems.
+	 */
+	if (unlikely(dmiss && dl_se->flags & SCHED_SIG_DMISS))
+		dl_se_signal(dl_se, SIGXCPU, "Deadline miss");
+
+	if (unlikely(rorun && dl_se->flags & SCHED_SIG_RORUN))
+		dl_se_signal(dl_se, SIGXCPU, "Runtime overrun");
+
 	dequeue_dl_entity(dl_se);
 	if (!start_dl_timer(dl_se, dl_se->deadline)) {
 		if (!rorun)
Signature · 9 lines
1.7.0

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
maintainer
#16 lore raw

Re: [RFC][PATCH 08/11] sched: send SIGXCPU at -deadline task overruns.

Quoted 83 lines · Raistlin

Add to the scheduler the capability of notifying when -deadline tasks overrun their maximum runtime and/or overcome their scheduling deadline.

Runtime overruns might be quite common, e.g., due to coarse granularity execution time accounting resolution or wrong assignment of tasks' parameters (especially runtime). However, since the scheduler enforces bandwidth isolation among tasks, this is not at all a threat to other tasks' schedulability. For this reason, it is not common that a task wants to be notified about that. Moreover, if we are using the SCHED_DEADLINE policy with sporadic tasks, or to limit the bandwidth of not periodic nor sporadic ones, runtime overruns are very likely to occur at each and every instance, and again they should not be considered a problem.

On the other hand, a deadline miss in any task means that, even if we are trying at our best to keep each task isolated and to avoid reciprocal interference among them, something went very, very bad, and one task did not manage in consuming its runtime by its deadline. This is something that should happen only on an oversubscribed system, and thus being notified when it occurs could be very useful.

The user can specify the signals he wants to be sent to his task during sched_setscheduler_ex(), raising two specific flags in the sched_flags field of struct sched_param_ex:
* SCHED_SIG_RORUN (if he wants to be signaled on runtime overrun),
* SCHED_SIG_DMISS (if he wants to be signaled on deadline misses).

This patch:
- adds the logic needed to send SIGXCPU signal to a -deadline task in case its actual runtime becomes negative;
- adds the logic needed to send SIGXCPU signal to a -deadline task in case it is still being scheduled while its absolute deadline passes.

---
 include/linux/sched.h |   18 ++++++++++++++++++
 kernel/sched_dl.c     |   24 ++++++++++++++++++++++++
 2 files changed, 42 insertions(+), 0 deletions(-)
include/linux/sched.h +18 -0
index e6c1cda..64a7df2 100644
@@ -138,6 +138,7 @@ struct sched_param {
  * More information about the algorithm are available in the scheduling
  * class file or in Documentation/.
  */
+
 struct sched_param_ex {
 	int sched_priority;
 	struct timespec sched_runtime;
@@ -146,6 +147,23 @@ struct sched_param_ex {
 	unsigned int sched_flags;
 };
 
+/*
+ * User -deadline flags.
+ *
+ * These flags are exported to userspace so that tasks can try to affect
+ * the scheduler behaviour and/or specifying that they want to be informed
+ * of the occurrence of some events. There are at most 16 of them available
+ * (lowest bits), since values above 0x10000 are reserved for kernel
+ * internal flags.
+ *
+ *  @SCHED_SIG_RORUN	tells us the task wants to be notified whenever
+ *                      a runtime overrun occurs;
+ *  @SCHED_SIG_DMISS	tells us the task wants to be notified whenever
+ *                      a scheduling deadline is missed.
+ */
+#define SCHED_SIG_RORUN		0x0001
+#define SCHED_SIG_DMISS		0x0002
+
 struct exec_domain;
 struct futex_pi_state;
 struct robust_list_head;
kernel/sched_dl.c +0 -0
index dee2668..b5dde44 100644
@@ -265,6 +265,14 @@ static void init_dl_timer(struct sched_dl_entity *dl_se)
 	timer->function = dl_timer;

kernel/sched_dl.c static void init_dl_timer(struct sched_dl_entity *dl_se) · line 275

Quoted 10 lines
kernel/sched_dl.c +8 -0
 }
 
+#define dl_se_signal(se, s, msg)					\
+ do {									\
+  struct task_struct *t = dl_task_of(se);				\
+  sigaddset(&t->pending.signal, s);					\
+  set_tsk_thread_flag(t, TIF_SIGPENDING);				\
+  printk(KERN_INFO msg "in %d (%s)\n", task_pid_nr(t), t->comm);	\
+ } while (0)
+

Can't this be a regular vararg function?

Also, I wonder, would we want to put some information in the sigaction struct to allow the user to distinguish between the various SIGXCPU signal users.

Quoted 29 lines
kernel/sched_dl.c +16 -0
 static
 int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)
 {
@@ -283,6 +291,22 @@ int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)
 	if (dmiss)
 		dl_se->runtime -= rq->clock - dl_se->deadline;
 
+	/*
+	 * if the userspace asked for that, we notify about (scheduling)
+	 * deadline misses and runtime overruns via sending SIGXCPU to
+	 * "faulting" task.
+	 *
+	 * Note that (hopefully small) runtime overruns are very likely
+	 * to occur, mainly due to accounting resolution, while missing a
+	 * scheduling deadline should be very rare, and only happen on
+	 * an oversubscribed systems.
+	 */
+	if (unlikely(dmiss && dl_se->flags & SCHED_SIG_DMISS))
+		dl_se_signal(dl_se, SIGXCPU, "Deadline miss");
+
+	if (unlikely(rorun && dl_se->flags & SCHED_SIG_RORUN))
+		dl_se_signal(dl_se, SIGXCPU, "Runtime overrun");
+
 	dequeue_dl_entity(dl_se);
 	if (!start_dl_timer(dl_se, dl_se->deadline)) {
 		if (!rorun)
Signature · 1 line
1.7.0
#17 lore raw

Re: [RFC][PATCH 08/11] sched: send SIGXCPU at -deadline task overruns.

Quoted 11 lines · Peter Zijlstra

kernel/sched_dl.c static void init_dl_timer(struct sched_dl_entity *dl_se) · line 275

Quoted 9 lines · Raistlin
kernel/sched_dl.c +8 -0
+#define dl_se_signal(se, s, msg)					\
+ do {									\
+  struct task_struct *t = dl_task_of(se);				\
+  sigaddset(&t->pending.signal, s);					\
+  set_tsk_thread_flag(t, TIF_SIGPENDING);				\
+  printk(KERN_INFO msg "in %d (%s)\n", task_pid_nr(t), t->comm);	\
+ } while (0)
+

Without ->siglock?

This is racy even if dl_task_of(se) == current, but I guess it can be !current. For example, we must never set TIF_SIGPENDING without wake_up_state(). A fatal signal should kill the whole process, etc. Even sigaddset() itself can race with tkill, it is not atomic.

Oleg.

author
#18 lore raw

RFC PATCH 9/11 sched: first draft of deadline inheritance.

In reply to Raistlin

Some method to deal with rt-mutexes and make sched_dl interact with the current PI-coded is needed. The issues this raises are not at all trivial, but a simple enough implementation is possible, avoiding completely restructuring any of the two.
Such solution, that we are proposing here, is based on two key
concepts: (i) relative deadline inheritance, and (ii) inheriting task's bandwidth boosting.

In some more details.

(i) relative deadline is representative of how "urgent" each instance of a task is and, while executing, the absolute deadline --according to which all scheduling decision are undertaken-- is calculated right by adding such value to the instance activation time. Therefore, a task inheriting a relative deadline smaller than its original one will likely have a smaller absolute deadline too, which all looks very similar to what happens when priority inheritance (e.g., because of rt-mutexes) take place among RT tasks. Moreover, relative deadline are meaningful on a per task basis independently from the CPU tasks are running on (and from any kind of clock synchronization issues among the different CPUs).
(ii) in order of having the inheriting task finishing quickly its
"operation" we also want it to be temporarily insensitive from the bandwidth enforcing mechanism, that would slow it down and provides another mean of priority inversion.
It is true that this opens the door to situations during which the system is more loaded than we expected (and perhaps even oversubscribed), but if the fundamental assumption of these time intervals being small enough, this won't be anything unbearable.

This is not 100% theoretically correct solution, although some kind of analysis can be tried. The main flaw is that it breaks the bandwidth isolation property the sched_dl policy (also) strives for. Different solutions exist, that do a better job in preserving such important feature, but they're way more complicated, and their implementation strategy is under consideration and studying.

Therefore, as of now, this patch:
- implements priority inheritance for -deadline tasks, according to what described above;
- to make this possible without rewriting outstanding chunks of code of both -deadline scheduling and existing PI, the task's relative deadline is stored in the prio field of the task_struct. This is done in such a way that:
* prio is always < 0 for -deadline tasks,
* p1->prio < p2->prio still means p1 has higher priority than p2, i.e., in our case, p1 has smaller relative deadline.
- the point above means that, since prio is of int type, a relative deadline has to be smaller than INT_MAX. This is about 2sec, which is a something (we think! :-)) we can afford, at least for now.
- disables bandwidth throttling for tasks while they are deadline boosted. It also tries to make them pay back for runtime overrun and deadline misses in this phase, but it's only "local", in the sense that instances farther than the one right next to the overrun are not going to be direcly affected.

---
 include/linux/sched.h |   30 ++++++++++++++++++++--
 kernel/sched.c        |   64 +++++++++++++++++++++++++++++--------------------
 kernel/sched_dl.c     |   57 +++++++++++++++++++++++++++++++++++++++----
 3 files changed, 116 insertions(+), 35 deletions(-)
include/linux/sched.h +27 -3
index 64a7df2..0b3a302 100644
@@ -1723,16 +1723,40 @@ static inline int rt_task(struct task_struct *p)
 	return rt_prio(p->prio);
 }
 
-static inline int dl_policy(int policy)
+/*
+ * Relative deadline of a process is a time interval representative
+ * of how "urgent" each instance of such a process is. During actual
+ * execution the absolute deadline of the process --i.e., the value
+ * according to which all scheduling decision are undertaken-- is
+ * calculated by adding to the instance activation time the process'
+ * relative deadline.
+ * Therefore, a process that inherits a smaller relative deadline will
+ * likely have a smaller absolute deadline than its original one, which
+ * means something very similar to the priority boosting that occurs
+ * when priority inheritance (e.g., because of rt-mutexes) take place
+ * among RT tasks.
+ * Thus we can somehow treat relative deadline as priorities and have all
+ * the priority inheritance seamlessy code working even for -deadline
+ * tasks.
+ *
+ * This is how the current implementation of deadline inheritance works
+ * and, in order of this to be possible, we need that the relative deadline
+ * value can be represented on the integer field "prio" of the process'
+ * task_struct.
+ */
+
+#define MAX_SCHED_DEADLINE	INT_MAX
+
+static inline int dl_prio(int prio)
 {
-	if (unlikely(policy == SCHED_DEADLINE))
+	if (unlikely(prio < 0))
 		return 1;
 	return 0;
 }
 
 static inline int dl_task(struct task_struct *p)
 {
-	return dl_policy(p->policy);
+	return dl_prio(p->prio);
 }
 
 static inline struct pid *task_pid(struct task_struct *task)
kernel/sched.c +38 -26

126 lines not on this page · raw message

kernel/sched_dl.c +51 -6

105 lines not on this page · raw message

Signature · 9 lines
1.7.0

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
maintainer
#19 lore raw

Re: [RFC][PATCH 09/11] sched: first draft of deadline inheritance.

Quoted 6 lines · Raistlin

Therefore, as of now, this patch:
- implements priority inheritance for -deadline tasks, according to what described above;
- to make this possible without rewriting outstanding chunks of code of both -deadline scheduling and existing PI, the task's relative deadline is stored in the prio field of the task_struct.

Quoted 8 lines

This is done in such a way that:
* prio is always < 0 for -deadline tasks,
* p1->prio < p2->prio still means p1 has higher priority than p2, i.e., in our case, p1 has smaller relative deadline.
- the point above means that, since prio is of int type, a relative deadline has to be smaller than INT_MAX. This is about 2sec, which is a something (we think! :-)) we can afford, at least for now.

Right, except that this makes the plist stuff O(INT_MAX) [ or rather O(nr_dl_tasks) ].

But I guess it serves for testing.

I think it would be relatively straight forward to modify the existing PI chain code to work using an RB-tree instead of the plist stuff.

An RB-tree would also make the whole ->prio mess much easier to solve, we could simply make a more complex comparison function, like:

int rt_mutex_prio_less(struct task_struct *left, struct task_struct *right)

{
	if (left->prio < right->prio)
		return 1;

	if (left->prio == right->prio && left->prio == -1) {
		if (left->deadline < right->deadline)
			return 1;
	}

	return 0;
}

Which uses the static prio -1 to represent all deadline tasks.

Quoted 6 lines

- disables bandwidth throttling for tasks while they are deadline boosted. It also tries to make them pay back for runtime overrun and deadline misses in this phase, but it's only "local", in the sense that instances farther than the one right next to the overrun are not going to be direcly affected.

Yeah, good enough to start with ;-)

maintainer
#20 lore raw

Re: [RFC][PATCH 09/11] sched: first draft of deadline inheritance.

Quoted 3 lines · Peter Zijlstra

I think it would be relatively straight forward to modify the existing PI chain code to work using an RB-tree instead of the plist stuff.

Something like the below (totally untested)

---
 include/linux/init_task.h |   10 ++++
 include/linux/rtmutex.h   |   13 +----
 include/linux/sched.h     |    3 +-
 kernel/fork.c             |    3 +-
 kernel/rtmutex-debug.c    |    8 +--
 kernel/rtmutex.c          |  121 +++++++++++++++++++++++++++++++++++---------
 kernel/rtmutex_common.h   |   21 ++++----
 kernel/sched.c            |    4 --
 8 files changed, 125 insertions(+), 58 deletions(-)
include/linux/init_task.h +10 -0
index b1ed1cd..2ee9259 100644
@@ -10,6 +10,7 @@
 #include <linux/pid_namespace.h>
 #include <linux/user_namespace.h>
 #include <linux/securebits.h>
+#include <linux/rbtree.h>
 #include <net/net_namespace.h>
 
 extern struct files_struct init_files;
@@ -103,6 +104,14 @@ extern struct cred init_cred;
 # define INIT_PERF_EVENTS(tsk)
 #endif
 
+#ifdef CONFIG_RT_MUTEXES
+# define INIT_RT_MUTEXES						\
+	.pi_waiters = RB_ROOT,						\
+	.pi_waiters_leftmost = NULL,
+#else
+# define INIT_RT_MUTEXES
+#endif
+
 /*
  *  INIT_TASK is used to set up the first task table, touch at
  * your own risk!. Base=0, limit=0x1fffff (=2MB)
@@ -172,6 +181,7 @@ extern struct cred init_cred;
 	INIT_FTRACE_GRAPH						\
 	INIT_TRACE_RECURSION						\
 	INIT_TASK_RCU_PREEMPT(tsk)					\
+	INIT_RT_MUTEXES							\
 }
 
 
include/linux/rtmutex.h +3 -10
index 8d522ff..8a68b29 100644
@@ -13,7 +13,7 @@
 #define __LINUX_RT_MUTEX_H
 
 #include <linux/linkage.h>
-#include <linux/plist.h>
+#include <linux/rbtree.h>
 #include <linux/spinlock_types.h>
 
 extern int max_lock_depth; /* for sysctl */
@@ -27,7 +27,8 @@ extern int max_lock_depth; /* for sysctl */
  */
 struct rt_mutex {
 	raw_spinlock_t		wait_lock;
-	struct plist_head	wait_list;
+	struct rb_root		waiters;
+	struct rb_node		*waiters_leftmost;
 	struct task_struct	*owner;
 #ifdef CONFIG_DEBUG_RT_MUTEXES
 	int			save_state;
@@ -98,12 +99,4 @@ extern int rt_mutex_trylock(struct rt_mutex *lock);
 
 extern void rt_mutex_unlock(struct rt_mutex *lock);
 
-#ifdef CONFIG_RT_MUTEXES
-# define INIT_RT_MUTEXES(tsk)						\
-	.pi_waiters	= PLIST_HEAD_INIT(tsk.pi_waiters, tsk.pi_lock),	\
-	INIT_RT_MUTEX_DEBUG(tsk)
-#else
-# define INIT_RT_MUTEXES(tsk)
-#endif
-
 #endif
include/linux/sched.h +2 -1
index c46b6e5..d4bf0c2 100644
@@ -1364,7 +1364,8 @@ struct task_struct {
 
 #ifdef CONFIG_RT_MUTEXES
 	/* PI waiters blocked on a rt_mutex held by this task */
-	struct plist_head pi_waiters;
+	struct rb_root pi_waiters;
+	struct rb_node *pi_waiters_leftmost;
 	/* Deadlock detection and priority inheritance handling */
 	struct rt_mutex_waiter *pi_blocked_on;
 #endif
kernel/fork.c +2 -1
index 5d3592d..23e037f 100644
@@ -918,7 +918,8 @@ static void rt_mutex_init_task(struct task_struct *p)
 {
 	raw_spin_lock_init(&p->pi_lock);
 #ifdef CONFIG_RT_MUTEXES
-	plist_head_init_raw(&p->pi_waiters, &p->pi_lock);
+	p->pi_waiters = RB_ROOT;
+	p->pi_waiters_leftmost = NULL;
 	p->pi_blocked_on = NULL;
 #endif
 }
kernel/rtmutex-debug.c +2 -6
index ddabb54..7cc8376 100644
@@ -23,7 +23,7 @@
 #include <linux/kallsyms.h>
 #include <linux/syscalls.h>
 #include <linux/interrupt.h>
-#include <linux/plist.h>
+#include <linux/rbtree.h>
 #include <linux/fs.h>
 #include <linux/debug_locks.h>
 
@@ -111,7 +111,7 @@ static void printk_lock(struct rt_mutex *lock, int print_owner)
 
 void rt_mutex_debug_task_free(struct task_struct *task)
 {
-	WARN_ON(!plist_head_empty(&task->pi_waiters));
+	WARN_ON(!RB_EMPTY_ROOT(&task->pi_waiters));
 	WARN_ON(task->pi_blocked_on);
 }
 
@@ -205,16 +205,12 @@ void debug_rt_mutex_proxy_unlock(struct rt_mutex *lock)
 void debug_rt_mutex_init_waiter(struct rt_mutex_waiter *waiter)
 {
 	memset(waiter, 0x11, sizeof(*waiter));
-	plist_node_init(&waiter->list_entry, MAX_PRIO);
-	plist_node_init(&waiter->pi_list_entry, MAX_PRIO);
 	waiter->deadlock_task_pid = NULL;
 }
 
 void debug_rt_mutex_free_waiter(struct rt_mutex_waiter *waiter)
 {
 	put_pid(waiter->deadlock_task_pid);
-	TRACE_WARN_ON(!plist_node_empty(&waiter->list_entry));
-	TRACE_WARN_ON(!plist_node_empty(&waiter->pi_list_entry));
 	TRACE_WARN_ON(waiter->task);
 	memset(waiter, 0x22, sizeof(*waiter));
 }
kernel/rtmutex.c +96 -25

221 lines not on this page · raw message

kernel/rtmutex_common.h +10 -11
index 97a2f81..b522322 100644
@@ -40,13 +40,13 @@ extern void schedule_rt_mutex_test(struct rt_mutex *lock);
  * This is the control structure for tasks blocked on a rt_mutex,
  * which is allocated on the kernel stack on of the blocked task.
  *
- * @list_entry:		pi node to enqueue into the mutex waiters list
- * @pi_list_entry:	pi node to enqueue into the mutex owner waiters list
+ * @tree_entry:		pi node to enqueue into the mutex waiters tree
+ * @pi_tree_entry:	pi node to enqueue into the mutex owner waiters tree
  * @task:		task reference to the blocked task
  */
 struct rt_mutex_waiter {
-	struct plist_node	list_entry;
-	struct plist_node	pi_list_entry;
+	struct rb_node		tree_entry;
+	struct rb_node		pi_tree_entry;
 	struct task_struct	*task;
 	struct rt_mutex		*lock;
 #ifdef CONFIG_DEBUG_RT_MUTEXES
@@ -57,11 +57,11 @@ struct rt_mutex_waiter {
 };
 
 /*
- * Various helpers to access the waiters-plist:
+ * Various helpers to access the waiters-tree:
  */
 static inline int rt_mutex_has_waiters(struct rt_mutex *lock)
 {
-	return !plist_head_empty(&lock->wait_list);
+	return !RB_EMPTY_ROOT(&lock->waiters);
 }
 
 static inline struct rt_mutex_waiter *
@@ -69,8 +69,7 @@ rt_mutex_top_waiter(struct rt_mutex *lock)
 {
 	struct rt_mutex_waiter *w;
 
-	w = plist_first_entry(&lock->wait_list, struct rt_mutex_waiter,
-			       list_entry);
+	w = rb_entry(lock->waiters_leftmost, struct rt_mutex_waiter, tree_entry);
 	BUG_ON(w->lock != lock);
 
 	return w;
@@ -78,14 +77,14 @@ rt_mutex_top_waiter(struct rt_mutex *lock)
 
 static inline int task_has_pi_waiters(struct task_struct *p)
 {
-	return !plist_head_empty(&p->pi_waiters);
+	return !RB_EMPTY_ROOT(&p->pi_waiters);
 }
 
 static inline struct rt_mutex_waiter *
 task_top_pi_waiter(struct task_struct *p)
 {
-	return plist_first_entry(&p->pi_waiters, struct rt_mutex_waiter,
-				  pi_list_entry);
+	return rb_entry(p->pi_waiters_leftmost, struct rt_mutex_waiter,
+			pi_tree_entry);
 }
 
 /*
kernel/sched.c +0 -4
index 3acf694..40b9bc5 100644
@@ -7677,10 +7677,6 @@ void __init sched_init(void)
 	open_softirq(SCHED_SOFTIRQ, run_rebalance_domains);
 #endif
 
-#ifdef CONFIG_RT_MUTEXES
-	plist_head_init_raw(&init_task.pi_waiters, &init_task.pi_lock);
-#endif
-
 	/*
 	 * The boot idle thread does lazy MMU switching as well:
 	 */
author
#21 lore raw

RFC PATCH 10/11 sched: add bandwidth management for sched_dl.

In reply to Raistlin

In order of -deaadline scheduling to be effective and useful, it is important that some method of having the allocation of the available CPU bandwidth to tasks and task groups under control.
This is usually called "admission control" and if it is not performed at all, no guarantee can be given on the actual scheduling of the -deadline tasks.

Since when RT-throttling has been introduced each task group have a bandwidth associated to itself, calculated as a certain amount of runtime over a period. Moreover, to make it possible to manipulate such bandwidth, readable/writable controls have been added to both procfs (for system wide settings) and cgroupfs (for per-group settings).
Therefore, the same interface is being used for controlling the bandwidth distrubution to -deadline tasks and task groups, i.e., new controls but with similar names, equivalent meaning and with the same usage paradigm are added.

The main differences between deadline bandwidth management and RT-throttling is that -deadline tasks have bandwidth on their own (while -rt ones doesn't!), and thus we don't need a throttling mechanism in the groups, which can be used nothing more than for admission control of tasks.

This patch:
- adds system wide deadline bandwidth management by means of:
* /proc/sys/kernel/sched_dl_runtime_us,
* /proc/sys/kernel/sched_dl_period_us,
that determine (i.e., runtime / period) the total bandwidth available on each CPU for -deadline tasks and task groups;

- adds system wide deadline bandwidth management by means of:
* /proc/sys/kernel/sched_dl_total_bw,
that --after writing to it the index of an online CPU-- tells how much of the total available bandwidth of that CPU is currently allocated.

- adds per-group deadline bandwidth management by means of:
* /cgroup/<group>/cpu.dl_runtime_us,
* /cgroup/<group>/cpu.dl_period_us,
(same as above, but per-group);

- adds per-group deadline bandwidth management by means of:
* /cgroup/<group>/cpu.dl_total_bw,
(same as above, but per-group).

- couples the RT and deadline bandwidth management (at system level only for now), i.e., the sum of how much bandwidth is being devoted to -rt entities and to -deadline tasks and task groups must stay below 100%.

---
 include/linux/sched.h |   13 +
 init/Kconfig          |   14 +
 kernel/sched.c        | 1003 ++++++++++++++++++++++++++++++++++++++++++++++++-
 kernel/sched_debug.c  |    3 +-
 kernel/sched_dl.c     |   16 +-
 kernel/sysctl.c       |   21 +
 6 files changed, 1054 insertions(+), 16 deletions(-)
include/linux/sched.h +13 -0
index 0b3a302..66f6872 100644
@@ -1329,6 +1329,7 @@ struct sched_dl_entity {
 	 */
 	u64 dl_runtime;		/* maximum runtime for each instance 	*/
 	u64 dl_deadline;	/* relative deadline of each instance	*/
+	u64 dl_bw;		/* dl_runtime / dl_deadline		*/
 
 	/*
 	 * Actual scheduling parameters. They are initialized with the
@@ -2120,6 +2121,18 @@ int sched_rt_handler(struct ctl_table *table, int write,
 		void __user *buffer, size_t *lenp,
 		loff_t *ppos);
 
+extern unsigned int sysctl_sched_dl_total_bw;
+extern unsigned int sysctl_sched_dl_period;
+extern int sysctl_sched_dl_runtime;
+
+int sched_dl_handler(struct ctl_table *table, int write,
+		void __user *buffer, size_t *lenp,
+		loff_t *ppos);
+
+int sched_dl_total_bw_handler(struct ctl_table *table, int write,
+			void __user *buffer, size_t *lenp,
+			loff_t *ppos);
+
 extern unsigned int sysctl_sched_compat_yield;
 
 #ifdef CONFIG_RT_MUTEXES
init/Kconfig +14 -0
index 1510e17..de57415 100644
@@ -473,6 +473,20 @@ config RT_GROUP_SCHED
 	  realtime bandwidth for them.
 	  See Documentation/scheduler/sched-rt-group.txt for more information.
 
+config DEADLINE_GROUP_SCHED
+	bool "Group scheduling for SCHED_DEADLINE"
+	depends on EXPERIMENTAL
+	depends on GROUP_SCHED
+	depends on CGROUPS
+	depends on !USER_SCHED
+	default n
+	help
+	  This feature lets you explicitly specify, in terms of runtime
+	  and period, the bandwidth of each task control group. This means
+	  tasks (and other groups) can be added to it only up to such
+	  "bandwidth cap", which might be useful for avoiding or
+	  controlling oversubscription.
+
 choice
 	depends on GROUP_SCHED
 	prompt "Basis for grouping tasks"
kernel/sched.c +989 -14

1,262 lines not on this page · raw message

kernel/sched_debug.c +2 -1
index 407a761..84d8d40 100644
@@ -146,7 +146,8 @@ static void print_rq(struct seq_file *m, struct rq *rq, int rq_cpu)
 }
 
 #if defined(CONFIG_CGROUP_SCHED) && \
-	(defined(CONFIG_FAIR_GROUP_SCHED) || defined(CONFIG_RT_GROUP_SCHED))
+	(defined(CONFIG_FAIR_GROUP_SCHED) || defined(CONFIG_RT_GROUP_SCHED) || \
+	 defined(CONFIG_DEADLINE_GROUP_SCHED))
 static void task_group_path(struct task_group *tg, char *buf, int buflen)
 {
 	/* may be NULL if the underlying cgroup isn't fully-created yet */
kernel/sched_dl.c +15 -1
index 3613cbd..3e466cb 100644
@@ -9,6 +9,10 @@
  * than their reserved bandwidth will be slowed down (and may potentially
  * miss some of their deadlines), and won't affect any other task.
  *
+ * Group scheduling, if configured, is utilized for admission control
+ * purposes, i.e., the sum of the bandwidth of tasks and groups belonging
+ * to group A must stays below A's own bandwidth.
+ *
  * Copyright (C) 2010 Dario Faggioli <[email protected]>,
  *                    Michael Trimarchi <[email protected]>,
  *                    Fabio Checconi <[email protected]>
@@ -658,8 +662,18 @@ static void task_fork_dl(struct task_struct *p)
 
 static void task_dead_dl(struct task_struct *p)
 {
+	struct dl_bandwidth *dl_b = task_dl_bandwidth(p);
+
+	/*
+	 * Since the task is TASK_DEAD we hope
+	 * it will not migrate or change group!
+	 */
+	raw_spin_lock_irq(&dl_b->dl_runtime_lock);
+	dl_b->dl_total_bw[task_cpu(p)] -= p->dl.dl_bw;
+	raw_spin_unlock_irq(&dl_b->dl_runtime_lock);
+
 	/*
-	 * We are not holding any lock here, so it is safe to
+	 * We are no longer holding any lock here, so it is safe to
 	 * wait for the bandwidth timer to be removed.
 	 */
 	hrtimer_cancel(&p->dl.dl_timer);
kernel/sysctl.c +21 -0
index 8a68b24..2f3cdba 100644
@@ -358,6 +358,27 @@ static struct ctl_table kern_table[] = {
 		.proc_handler	= sched_rt_handler,
 	},
 	{
+		.procname	= "sched_dl_period_us",
+		.data		= &sysctl_sched_dl_period,
+		.maxlen		= sizeof(unsigned int),
+		.mode		= 0644,
+		.proc_handler	= &sched_dl_handler,
+	},
+	{
+		.procname	= "sched_dl_runtime_us",
+		.data		= &sysctl_sched_dl_runtime,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= &sched_dl_handler,
+	},
+	{
+		.procname	= "sched_dl_total_bw",
+		.data		= &sysctl_sched_dl_total_bw,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= &sched_dl_total_bw_handler,
+	},
+	{
 		.procname	= "sched_compat_yield",
 		.data		= &sysctl_sched_compat_yield,
 		.maxlen		= sizeof(unsigned int),
Signature · 9 lines
1.7.0

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
maintainer
#22 lore raw

Re: [RFC][PATCH 10/11] sched: add bandwidth management for sched_dl.

Quoted 32 lines · Raistlin
kernel/sched.c +24 -0
@@ -2063,6 +2210,30 @@ task_hot(struct task_struct *p, u64 now, struct sched_domain *sd)
        return delta < (s64)sysctl_sched_migration_cost;
 }
 
+/*
+ * When dealing with a -deadline task, we have to check if moving it to
+ * a new CPU is possible or not. In fact, this is only true iff there
+ * is enough bandwidth available on such CPU, otherwise we want the
+ * whole migration progedure to fail over.
+ */
+static inline
+bool __set_task_cpu_dl(struct task_struct *p, unsigned int cpu)
+{
+       struct dl_bandwidth *dl_b = task_dl_bandwidth(p);
+
+       raw_spin_lock(&dl_b->dl_runtime_lock);
+       if (dl_b->dl_bw < dl_b->dl_total_bw[cpu] + p->dl.dl_bw) {
+               raw_spin_unlock(&dl_b->dl_runtime_lock);
+
+               return 0;
+       }
+       dl_b->dl_total_bw[task_cpu(p)] -= p->dl.dl_bw;
+       dl_b->dl_total_bw[cpu] += p->dl.dl_bw;
+       raw_spin_unlock(&dl_b->dl_runtime_lock);
+
+       return 1;
+}
+
 void set_task_cpu(struct task_struct *p, unsigned int new_cpu)
 {
 #ifdef CONFIG_SCHED_DEBUG

kernel/sched.c void set_task_cpu(struct task_struct *p, unsigned int new_cpu) · line 2256

Quoted 9 lines
kernel/sched.c +3 -0
@@ -2077,6 +2248,9 @@ void set_task_cpu(struct task_struct *p, unsigned int new_cpu)
        trace_sched_migrate_task(p, new_cpu);
 
        if (task_cpu(p) != new_cpu) {
+               if (task_has_dl_policy(p) && !__set_task_cpu_dl(p, new_cpu))
+                       return;
+
                p->se.nr_migrations++;
                perf_sw_event(PERF_COUNT_SW_CPU_MIGRATIONS, 1, 1, NULL, 0);
        } 

Yikes!!, I'm not sure we can sanely deal with set_task_cpu() doing that.

I'd much rather see us never attempting set_task_cpu() when we know its not going to be possible.

That also means that things like set_cpus_allowed_ptr() / sys_sched_setaffinity() will need to propagate the error back to their users, which in turn will need to be able to cope.

author
#23 lore raw

RFC PATCH 11/11 sched: add sched_dl documentation.

In reply to Raistlin

Add in Documentation/scheduler/ some hints about the design choices, the usage and the future possible developments of the sched_dl scheduling class and of the SCHED_DEADLINE policy.

---
 Documentation/scheduler/sched-deadline.txt |  188 ++++++++++++++++++++++++++++
 init/Kconfig                               |    1 +
 2 files changed, 189 insertions(+), 0 deletions(-)
Documentation/scheduler/sched-deadline.txt new file +188 -0
new file mode 100644
index 0000000..1ff0e1e
@@ -0,0 +1,188 @@
+			Deadline Task and Group Scheduling
+			----------------------------------
+
+CONTENTS
+========
+
+0. WARNING
+1. Overview
+  1.1 Task scheduling
+  1.2 Group scheduling
+2. The interface
+  2.1 System wide settings
+  2.2 Task interface
+  2.3 Group interface
+  2.4 Default behavior
+3. Future plans
+
+
+0. WARNING
+==========
+
+ Fiddling with these settings can result in an unpredictable or even unstable
+ system behavior. As for -rt (group) scheduling, it is assumed that root
+ knows what he is doing.
+
+
+1. Overview
+===========
+
+ The SCHED_DEADLINE policy contained inside the sched_dl scheduling class is
+ basically an implementation of the Earliest Deadline First (EDF) scheduling
+ algorithm, augmented with a mechanism (called Constant Bandwidth Server, CBS)
+ that make it possible to isolate the behaviour of tasks between each other.
+
+
+1.1 Task scheduling
+-------------------
+
+ The typical -deadline task will be made up of a computation phase (instance)
+ which is activated on a periodic or sporadic fashion. The expected (maximum)
+ duration of such computation is called the task's runtime; the time interval
+ by which each instance need to be completed is called the task's relative
+ deadline. The task's absolute deadline is dynamically calculated as the
+ time instant a task (better, an instance) activates plus the relative
+ deadline.
+
+ The EDF algorithms selects the task with the smallest absolute deadline as
+ the one to be executed first, while the CBS ensures each task to run for
+ at most the its runtime every (relative) deadline length time interval,
+ avoiding any interference between different tasks (bandwidth isolation).
+ Thanks to this feature, also tasks that do not strictly comply with the
+ computational model sketched above can effectively use the new policy.
+ IOW, there are no limitations on what kind of task can exploit this new
+ scheduling discipline, even if it must be said that it is particularly
+ suited for periodic or sporadic tasks that need guarantees on their
+ timing behaviour, e.g., multimedia, streaming, control applications, etc.
+
+
+1.2 Group scheduling
+----------------
+
+ In order of -deaadline scheduling to be effective and useful, it is important
+ that some method of having the allocation of the available CPU bandwidth to
+ tasks and task groups under control.
+ This is usually called "admission control" and if it is not performed at all,
+ no guarantee can be given on the actual scheduling of the -deadline tasks.
+
+ Since when RT-throttling has been introduced each task group have a bandwidth
+ associated to itself, calculated as a certain amount of runtime over a
+ period. Moreover, to make it possible to manipulate such bandwidth,
+ readable/writable controls have been added to both procfs (for system
+ wide settings) and cgroupfs (for per-group settings).
+ Therefore, the same interface is being used for controlling the bandwidth
+ distrubution to -deadline tasks and task groups, i.e., new controls but
+ with similar names, equivalent meaning and with the same usage paradigm are
+ added.
+
+ The main differences between deadline bandwidth management and RT-throttling
+ is that -deadline tasks have bandwidth on their own (while -rt ones doesn't!),
+ and thus we don't need a throttling mechanism in the groups, which can be
+ used nothing more than for admission control of tasks.
+
+ This means that what we check is the sum of the bandwidth of all the tasks
+ belonging to the group stays, on each CPU, below the bandwidth of the group
+ itself.
+
+
+2. The Interface
+================
+
+2.1 System wide settings
+------------------------
+
+The system wide settings are configured under the /proc virtual file system:
+
+ The per-group controls that are added to the cgroupfs virtual file system are:
+  * /proc/sys/kernel/sched_dl_runtime_us,
+  * /proc/sys/kernel/sched_dl_period_us,
+  * /proc/sys/kernel/sched_dl_total_bw.
+
+ The first two accepts (if written) and provides (if read) the new runtime and
+ period, respectively, for each CPU.
+ The last one accepts (if written) the index of one online CPU, and it provides
+ (if read) the total amount of bandwidth currently alloceted on that CPU.
+
+ Settings are checked against the following limit:
+
+  * for the whole system, on each CPU:
+      rt_runtime / rt_period + dl_runtime + dl_period <= 100%
+
+
+2.2 Task interface
+------------------
+
+ Specifying a periodic/sporadic task that executes for a given amount of
+ runtime at each instance, and that is scheduled according to the usrgency of
+ their own timing constraints needs, in general, a way of declaring:
+  - a (maximum/typical) instance execution time,
+  - a minimum interval between consecutive instances,
+  - a time constraint by which each instance must be completed.
+
+ Therefore:
+  * a new struct sched_param_ex, containing all the necessary fields is
+    provided;
+  * the new scheduling related syscalls that manipulate it, i.e.,
+    sched_setscheduler_ex(), sched_setparam_ex() and sched_getparam_ex()
+    are implemented.
+
+
+2.3 Group Interface
+-------------------
+
+ The per-group controls that are added to the cgroupfs virtual file system are:
+  * /cgroup/<cgroup>/cpu.dl_runtime_us,
+  * /cgroup/<cgroup>/cpu.dl_period_us,
+  * /cgroup/<cgroup>/cpu.dl_total_bw.
+
+ The first two accepts (if written) and provides (if read) the new runtime and
+ period, respectively, of the group for each CPU.
+ The last one accepts (if written) the index of one online CPU, and it provides
+ (if read) the total amount of bandwidth currently alloceted inside the group
+ on that CPU.
+
+ Group settings are checked against the following limits:
+
+  * for the root group {r}, on each CPU:
+      dl_runtime_{r} / dl_period_{r} <= dl_runtime / dl_period
+
+  * for each group {i}, subgroup of group {j}, on each CPU:
+      dl_runtime_{i} / dl_period_{i} < 100%
+      \Sum_{i} dl_runtime_{i} / dl_period_{i} <= dl_runtime_{j} / dl_period_{j}
+
+ For more information on working with control groups,
+ Documentation/cgroups/cgroups.txt should be read.
+
+
+2.4 Default behavior
+---------------------
+
+The default values for system wide and root group dl_runtime and dl_period are
+500000 over 1000000.  This means -deadline tasks and task groups can use at
+most 5% bandwidth on each CPU.
+
+When a -deadline task fork a child, its dl_runtime is set to 0, which means
+someone must call sched_setscheduler_ex() on it, or it won't even start.
+
+When a new group is created, its dl_runtime is 0, which means someone must
+(try to) increase it before tasks can be added to the group.
+
+
+3. Future plans
+===============
+
+Still Missing parts:
+
+ - bandwidth reclaiming mechanisms, i.e., methods that avoid stopping the
+   tasks until their next deadline when overrunning. There are at least
+   three of them that are very simple, and patches are on their way;
+
+ - migration of tasks throughout push and pull (as in -rt) to make it
+   possible to deploy global-EDF scheduling. Patches are ready, they're
+   just being tested and adapted to this last version;
+
+ - refinements in deadline inheritance, especially regarding the possibility
+   of retaining bandwidth isolation among non-interacting tasks. This is
+   being studied from both theoretical and practical point of views, and
+   hopefully we can have some demonstrative code soon.
+
init/Kconfig +1 -0
index de57415..377caed 100644
@@ -486,6 +486,7 @@ config DEADLINE_GROUP_SCHED
 	  tasks (and other groups) can be added to it only up to such
 	  "bandwidth cap", which might be useful for avoiding or
 	  controlling oversubscription.
+	  See Documentation/scheduler/sched-deadline.txt for more.
 
 choice
 	depends on GROUP_SCHED
Signature · 9 lines
1.7.0

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
maintainer
#24 lore raw
In reply to Raistlin

Overall very nice code, awesome!

Quoted 3 lines · Raistlin

- migration of tasks throughout push and pull (as in -rt), to make it possible to deploy global-EDF scheduling. Patches are ready, they're just being tested and adapted to this last version;

Please post a version that includes this :-)

Quoted 5 lines

- refinements in deadline inheritance, especially regarding the possibility of retaining bandwidth isolation among non-interacting tasks. This is being studied from both theoretical and practical points of view, and hopefully we can have some demonstrative code soon.

Right, I hope that with changing the PI code to use RB trees this will become much less of a kludge than fudging the ->prio field.