[PATCH v4] sched/deadline: Change the time to replenish runtime for sleep tasks

[Byungchul Park]

Let's consider the following example.

                                  (N+1)th tick
                  (N)th tick                 |
                           |                 |
timeline : o...............o...o.........o...o...o..o
           ^                   ^         ^       ^  ^
           |                   |         |       |  |
       start                   |         |       |  |
                original runtime         |       |  |
                     sleep with (-)runtime       |  |
                                 original deadline  |
                                              wake up

When this task is woken up, a negative runtime should be considered,
which means that the task should get penalized when assigning runtime,
becasue it already spent more than expected. Current code handles this
by replenishing a runtime in hrtimer callback for deadline. But this
approach has room for improvement:

   We can avoid setting a deadline timer and save an interrupt if the
   task sleeps for long time so that the deadline passes, since that
   can be handled on wake-up.

So does not set a deadline timer in that case and force to replenish it
when waking it up.

Signed-off-by: Byungchul Park <byungchul.park@xxxxxxx>
---
 kernel/sched/deadline.c | 36 +++++++++++++++++++++++++++++-------
 1 file changed, 29 insertions(+), 7 deletions(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 27737f3..e7a7209 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -498,13 +498,23 @@ 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);
 
-	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
-	    dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
+	if (dl_time_before(dl_se->deadline, rq_clock(rq)))
+		replenish_dl_entity(dl_se, pi_se);
+
+	if (dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
 		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
 		dl_se->runtime = pi_se->dl_runtime;
 	}
 }
 
+static inline void stop_dl_timer(struct task_struct *p)
+{
+	struct sched_dl_entity *dl_se = &p->dl;
+	struct hrtimer *timer = &dl_se->dl_timer;
+
+	hrtimer_try_to_cancel(timer);
+}
+
 /*
  * If the entity depleted all its runtime, and if we want it to sleep
  * while waiting for some new execution time to become available, we
@@ -621,13 +631,11 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
 	 *         __dequeue_task_dl()
 	 *     prev->on_rq = 0;
 	 *
-	 * We can be both throttled and !queued. Replenish the counter
-	 * but do not enqueue -- wait for our wakeup to do that.
+	 * We can be both throttled and !queued. Wait for our wakeup to
+	 * replenish runtime and enqueue p.
 	 */
-	if (!task_on_rq_queued(p)) {
-		replenish_dl_entity(dl_se, dl_se);
+	if (!task_on_rq_queued(p))
 		goto unlock;
-	}
 
 #ifdef CONFIG_SMP
 	if (unlikely(!rq->online)) {
@@ -956,6 +964,13 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
 	if (p->dl.dl_throttled && !(flags & ENQUEUE_REPLENISH))
 		return;
 
+	/*
+	 * start_dl_timer() would do nothing if already deadline < now.
+	 * The case will be handled in update_dl_entity().
+	 */
+	if (p->dl.dl_throttled && (flags & ENQUEUE_WAKEUP))
+		start_dl_timer(p);
+
 	enqueue_dl_entity(&p->dl, pi_se, flags);
 
 	if (!task_current(rq, p) && tsk_nr_cpus_allowed(p) > 1)
@@ -964,6 +979,13 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
 
 static void __dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
 {
+	/*
+	 * Runtime will be replenished on wake-up. We can avoid
+	 * unnecessary timer interrupt in this case.
+	 */
+	if (p->dl.dl_throttled && (flags & DEQUEUE_SLEEP))
+		stop_dl_timer(p);
+
 	dequeue_dl_entity(&p->dl);
 	dequeue_pushable_dl_task(rq, p);
 }
-- 
1.9.1