lkml.org 
[lkml]   [2016]   [Nov]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
SubjectRe: [RFC v3 2/6] Improve the tracking of active utilisation
Hi,

On 24/10/16 16:06, Luca Abeni wrote:
> This patch implements a more theoretically sound algorithm for
> thracking the active utilisation: instead of decreasing it when a

s/thracking/tracking/
s/the//

> task blocks, use a timer (the "inactive timer", named after the
> "Inactive" task state of the GRUB algorithm) to decrease the
> active utilisaation at the so called "0-lag time".

s/utilisaation/utilisation/

>
> Signed-off-by: Luca Abeni <luca.abeni@unitn.it>
> ---
> include/linux/sched.h | 1 +
> kernel/sched/core.c | 1 +
> kernel/sched/deadline.c | 139 ++++++++++++++++++++++++++++++++++++++++++------
> kernel/sched/sched.h | 1 +
> 4 files changed, 126 insertions(+), 16 deletions(-)
>
> diff --git a/include/linux/sched.h b/include/linux/sched.h
> index 348f51b..22543c6 100644
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -1433,6 +1433,7 @@ struct sched_dl_entity {
> * own bandwidth to be enforced, thus we need one timer per task.
> */
> struct hrtimer dl_timer;
> + struct hrtimer inactive_timer;
> };
>
> union rcu_special {
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 94732d1..664c618 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -2217,6 +2217,7 @@ static void __sched_fork(unsigned long clone_flags, struct task_struct *p)
>
> RB_CLEAR_NODE(&p->dl.rb_node);
> init_dl_task_timer(&p->dl);
> + init_inactive_task_timer(&p->dl);
> __dl_clear_params(p);
>
> INIT_LIST_HEAD(&p->rt.run_list);
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 3d95c1d..80d1541 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -47,6 +47,7 @@ static void add_running_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
> {
> u64 se_bw = dl_se->dl_bw;
>
> + lockdep_assert_held(&(rq_of_dl_rq(dl_rq))->lock);

This and the one below go in 1/6.

> dl_rq->running_bw += se_bw;
> }
>
> @@ -54,11 +55,52 @@ static void sub_running_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
> {
> u64 se_bw = dl_se->dl_bw;
>
> + lockdep_assert_held(&(rq_of_dl_rq(dl_rq))->lock);
> dl_rq->running_bw -= se_bw;
> if (WARN_ON(dl_rq->running_bw < 0))
> dl_rq->running_bw = 0;
> }
>
> +static void task_go_inactive(struct task_struct *p)
> +{
> + struct sched_dl_entity *dl_se = &p->dl;
> + struct hrtimer *timer = &dl_se->inactive_timer;
> + struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
> + struct rq *rq = rq_of_dl_rq(dl_rq);
> + s64 zerolag_time;
> +
> + WARN_ON(dl_se->dl_runtime == 0);
> +
> + /* If the inactive timer is already armed, return immediately */
> + if (hrtimer_active(&dl_se->inactive_timer))
> + return;
> +
> + zerolag_time = dl_se->deadline -
> + div64_long((dl_se->runtime * dl_se->dl_period),
> + dl_se->dl_runtime);
> +
> + /*
> + * Using relative times instead of the absolute "0-lag time"
> + * allows to simplify the code
> + */
> + zerolag_time -= rq_clock(rq);
> +
> + /*
> + * If the "0-lag time" already passed, decrease the active
> + * utilization now, instead of starting a timer
> + */
> + if (zerolag_time < 0) {
> + sub_running_bw(dl_se, dl_rq);
> + if (!dl_task(p))
> + __dl_clear_params(p);
> +
> + return;
> + }
> +
> + get_task_struct(p);
> + hrtimer_start(timer, ns_to_ktime(zerolag_time), HRTIMER_MODE_REL);
> +}
> +
> static inline int is_leftmost(struct task_struct *p, struct dl_rq *dl_rq)
> {
> struct sched_dl_entity *dl_se = &p->dl;
> @@ -514,7 +556,20 @@ 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);
>
> - add_running_bw(dl_se, dl_rq);
> + if (hrtimer_is_queued(&dl_se->inactive_timer)) {
> + hrtimer_try_to_cancel(&dl_se->inactive_timer);

Why we are OK with just trying to cancel the inactive timer?

> + WARN_ON(dl_task_of(dl_se)->nr_cpus_allowed > 1);

What's wrong with nr_cpus_allowed > 1 tasks?

> + } else {
> + /*
> + * The "inactive timer" has been cancelled in
> + * select_task_rq_dl() (and the acvive utilisation has
> + * been decreased). So, increase the active utilisation.
> + * If select_task_rq_dl() could not cancel the timer,
> + * inactive_task_timer() will * find the task state as
> + * TASK_RUNNING, and will do nothing, so we are still safe.
> + */
> + add_running_bw(dl_se, dl_rq);
> + }
>
> if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
> dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
> @@ -602,14 +657,8 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
>
> rq = task_rq_lock(p, &rf);
>
> - /*
> - * The task might have changed its scheduling policy to something
> - * different than SCHED_DEADLINE (through switched_fromd_dl()).
> - */
> - if (!dl_task(p)) {
> - __dl_clear_params(p);
> + if (!dl_task(p))
> goto unlock;
> - }
>
> /*
> * The task might have been boosted by someone else and might be in the
> @@ -796,6 +845,44 @@ static void update_curr_dl(struct rq *rq)
> }
> }
>
> +static enum hrtimer_restart inactive_task_timer(struct hrtimer *timer)
> +{
> + struct sched_dl_entity *dl_se = container_of(timer,
> + struct sched_dl_entity,
> + inactive_timer);
> + struct task_struct *p = dl_task_of(dl_se);
> + struct rq_flags rf;
> + struct rq *rq;
> +
> + rq = task_rq_lock(p, &rf);
> +
> + if (!dl_task(p)) {
> + __dl_clear_params(p);
> +
> + goto unlock;
> + }
> + if (p->state == TASK_RUNNING)
> + goto unlock;
> +
> + sched_clock_tick();
> + update_rq_clock(rq);
> +
> + sub_running_bw(dl_se, &rq->dl);
> +unlock:
> + task_rq_unlock(rq, p, &rf);
> + put_task_struct(p);
> +
> + return HRTIMER_NORESTART;
> +}
> +
> +void init_inactive_task_timer(struct sched_dl_entity *dl_se)
> +{
> + struct hrtimer *timer = &dl_se->inactive_timer;
> +
> + hrtimer_init(timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
> + timer->function = inactive_task_timer;
> +}
> +
> #ifdef CONFIG_SMP
>
> static void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
> @@ -1000,7 +1087,7 @@ static void dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
> sub_running_bw(&p->dl, &rq->dl);
>
> if (flags & DEQUEUE_SLEEP)
> - sub_running_bw(&p->dl, &rq->dl);
> + task_go_inactive(p);
> }
>
> /*
> @@ -1074,6 +1161,14 @@ select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)
> }
> rcu_read_unlock();
>
> + rq = task_rq(p);
> + raw_spin_lock(&rq->lock);
> + if (hrtimer_active(&p->dl.inactive_timer)) {
> + sub_running_bw(&p->dl, &rq->dl);
> + hrtimer_try_to_cancel(&p->dl.inactive_timer);

Can't we subtract twice if it happens that after we grabbed rq_lock the timer
fired, so it's now waiting for that lock and it goes ahead and sub_running_bw
again after we release the lock?

> + }
> + raw_spin_unlock(&rq->lock);
> +
> out:
> return cpu;
> }
> @@ -1244,6 +1339,11 @@ static void task_dead_dl(struct task_struct *p)
> /* XXX we should retain the bw until 0-lag */
> dl_b->total_bw -= p->dl.dl_bw;
> raw_spin_unlock_irq(&dl_b->lock);
> + if (hrtimer_active(&p->dl.inactive_timer)) {
> + raw_spin_lock_irq(&task_rq(p)->lock);
> + sub_running_bw(&p->dl, dl_rq_of_se(&p->dl));

Don't we still need to wait for the 0-lag? Or maybe since the task is dying we
can release it's bw instantaneously? In this case I'd add a comment about it.

> + raw_spin_unlock_irq(&task_rq(p)->lock);
> + }
> }
>
> static void set_curr_task_dl(struct rq *rq)
> @@ -1720,15 +1820,22 @@ void __init init_sched_dl_class(void)
> static void switched_from_dl(struct rq *rq, struct task_struct *p)
> {
> /*
> - * Start the deadline timer; if we switch back to dl before this we'll
> - * continue consuming our current CBS slice. If we stay outside of
> - * SCHED_DEADLINE until the deadline passes, the timer will reset the
> - * task.
> + * task_go_inactive() can start the "inactive timer" (if the 0-lag
> + * time is in the future). If the task switches back to dl before
> + * the "inactive timer" fires, it can continue to consume its current
> + * runtime using its current deadline. If it stays outside of
> + * SCHED_DEADLINE until the 0-lag time passes, inactive_task_timer()
> + * will reset the task parameters.
> */
> - if (!start_dl_timer(p))
> - __dl_clear_params(p);
> + if (task_on_rq_queued(p) && p->dl.dl_runtime)
> + task_go_inactive(p);
>
> - if (task_on_rq_queued(p))
> + /*
> + * We cannot use inactive_task_timer() to invoke sub_running_bw()
> + * at the 0-lag time, because the task could have been migrated
> + * while SCHED_OTHER in the meanwhile.

But, from a theoretical pow, we very much should, right?
Is this taken care of in next patch?

> + */
> + if (hrtimer_is_queued(&p->dl.inactive_timer))
> sub_running_bw(&p->dl, &rq->dl);
>

Thanks,

- Juri

\
 
 \ /
  Last update: 2016-11-01 17:46    [W:0.179 / U:0.188 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site