Re: [PATCH 13/16] sched: drafted deadline inheritance logic.

From: Juri Lelli
Date: Sun Apr 22 2012 - 10:04:44 EST

On 04/12/2012 04:42 AM, Steven Rostedt wrote:
On Fri, 2012-04-06 at 09:14 +0200, Juri Lelli wrote:
From: Dario Faggioli<raistlin@xxxxxxxx>

Some method to deal with rt-mutexes and make sched_dl interact with
the current PI-coded is needed, raising all but trivial issues, that
needs (according to us) to be solved with some restructuring of
the pi-code (i.e., going toward a proxy execution-ish implementation).

I also would like to point out that this is probably only for -rt? Or is
this for PI futexes as well?

Well, this directly affects rtmutex.c only. But, as soon as a PI-enabled
user-space mutex fails the fastpath all returns to rtmutex machinery, right?
So, I would say that this apply to PI futexes as well :-|.

Note, non-proxy version of this code may be an issue. Could a process
force more bandwidth than was allowed by rlimit if the process used PI
futexes forced a behavior that PI waiters were waiting on another
process while it held the PI futex? The process that held the futex may
get more bandwidth if it never lets go of the futex, right?

Yes, I would remark that this is a needed _temporary_ solution (just to not
delay further the release post). I tried to remain simple as to not prevent
any fast shift in the way we want to resolve this problem. Anyway, it would
be great if some discussion on this point could re-start :-).

This is under development, in the meanwhile, as a temporary solution,
what this commits does is:
- ensure a pi-lock owner with waiters is never throttled down. Instead,
when it runs out of runtime, it immediately gets replenished and it's
deadline is postponed;
- the scheduling parameters (relative deadline and default runtime)
used for that replenishments --during the whole period it holds the
pi-lock-- are the ones of the waiting task with earliest deadline.

This sounds similar to what I implemented for a company back in 2005.

Acting this way, we provide some kind of boosting to the lock-owner,
still by using the existing (actually, slightly modified by the previous
commit) pi-architecture.

We would stress the fact that this is only a surely needed, all but
clean solution to the problem. In the end it's only a way to re-start
discussion within the community. So, as always, comments, ideas, rants,
etc.. are welcome! :-)

Signed-off-by: Dario Faggioli<raistlin@xxxxxxxx>
Signed-off-by: Juri Lelli<juri.lelli@xxxxxxxxx>
include/linux/sched.h | 9 +++++-
kernel/fork.c | 1 +
kernel/rtmutex.c | 13 +++++++-
kernel/sched.c | 34 ++++++++++++++++++---
kernel/sched_dl.c | 77 +++++++++++++++++++++++++++++++++---------------
5 files changed, 102 insertions(+), 32 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 5ef7bb6..ca45db4 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1309,8 +1309,12 @@ struct sched_dl_entity {
* @dl_new tells if a new instance arrived. If so we must
* start executing it with full runtime and reset its absolute
* deadline;
+ *
+ * @dl_boosted tells if we are boosted due to DI. If so we are


DI = Deadline Inheritance. Even if not strictly correct in the definition,
when you're boosted you inherit highest priority waiter's parameters, among
which deadline. In fact you inherit its budget.

+ * outside bandwidth enforcement mechanism (but only until we
+ * exit the critical section).
- int dl_throttled, dl_new;
+ int dl_throttled, dl_new, dl_boosted;

* Bandwidth enforcement timer. Each -deadline task has its
@@ -1556,6 +1560,8 @@ struct task_struct {
struct rb_node *pi_waiters_leftmost;
/* Deadlock detection and priority inheritance handling */
struct rt_mutex_waiter *pi_blocked_on;
+ /* Top pi_waiters task */
+ struct task_struct *pi_top_task;

Sorry for the delayed reply, I was really busy for the last two
weeks :-\.

Thanks and Regards,

- Juri
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at
Please read the FAQ at