lkml.org 
[lkml]   [2010]   [Oct]   [29]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Subject[RFC][PATCH 18/22] sched: add reclaiming logic to -deadline tasks
    From
    Date
    The bandwidth enforcing mechanism implemented inside the
    SCHED_DEADLINE policy ensures that overrunning tasks are slowed
    down without interfering with well behaving ones.
    This, however, comes at the price of limiting the capability of
    a task to exploit more bandwidth than it is asigned.

    The current implementation always stops a task that is trying
    to use more than its runtime (every deadline). Something else that
    could be done is to let it continue running, but with a "decreased
    priority". This way, we can exploit full CPU bandwidth and still
    avoid interferences.

    In order of "decreasing the priority" of a deadline task, we can:
    - let it stay SCHED_DEADLINE and postpone its deadline. This way it
    will always be scheduled before -rt and -other tasks but it
    won't affect other -deadline tasks;
    - put it in SCHED_FIFO with some priority. This way it will always
    be scheduled before -other tasks but it won't affect -deadline
    tasks, nor other -rt tasks with higher priority;
    - put it in SCHED_OTHER.

    Notice also that this can be done on a per-task basis, e.g., each
    task can specify what kind of reclaiming mechanism it wants to use
    by means of the sched_flags field of sched_param_ex.

    Therefore, this patch:
    - adds the flags for specyfing DEADLINE, RT or OTHER reclaiming
    behaviour;
    - adds the logic that changes the scheduling class of a task when
    it overruns, according to the requested policy.

    Signed-off-by: Dario Faggioli <raistlin@linux.it>
    ---
    include/linux/sched.h | 25 ++++++++++++++
    kernel/hrtimer.c | 2 +-
    kernel/sched.c | 86 ++++++++++++++++++++++++++++++++-----------------
    kernel/sched_debug.c | 2 +-
    kernel/sched_dl.c | 44 +++++++++++++++++++++++--
    5 files changed, 123 insertions(+), 36 deletions(-)

    diff --git a/include/linux/sched.h b/include/linux/sched.h
    index b729f83..8806c1f 100644
    --- a/include/linux/sched.h
    +++ b/include/linux/sched.h
    @@ -172,10 +172,26 @@ struct sched_param_ex {
    * a runtime overrun occurs;
    * @SF_SIG_DMISS tells us the task wants to be notified whenever
    * a scheduling deadline is missed.
    + * @SF_BWRECL_DL tells us that the task doesn't stop when exhausting
    + * its runtime, and it remains a -deadline task, even
    + * though its deadline is postponed. This means it
    + * won't affect the scheduling of the other -deadline
    + * tasks, but if it is a CPU-hog, lower scheduling
    + * classes will starve!
    + * @SF_BWRECL_RT tells us that the task doesn't stop when exhausting
    + * its runtime, and it becomes a -rt task, with the
    + * priority specified in the sched_priority field of
    + * struct shced_param_ex.
    + * @SF_BWRECL_OTH tells us that the task doesn't stop when exhausting
    + * its runtime, and it becomes a normal task, with
    + * default priority.
    */
    #define SF_HEAD 1
    #define SF_SIG_RORUN 2
    #define SF_SIG_DMISS 4
    +#define SF_BWRECL_DL 8
    +#define SF_BWRECL_RT 16
    +#define SF_BWRECL_NR 32

    struct exec_domain;
    struct futex_pi_state;
    @@ -1694,6 +1710,15 @@ static inline int dl_task(struct task_struct *p)
    return dl_prio(p->prio);
    }

    +/*
    + * We might have temporarily dropped -deadline policy,
    + * but still be a -deadline task!
    + */
    +static inline int __dl_task(struct task_struct *p)
    +{
    + return dl_task(p) || p->policy == SCHED_DEADLINE;
    +}
    +
    static inline int rt_prio(int prio)
    {
    if (unlikely(prio >= MAX_DL_PRIO && prio < MAX_RT_PRIO))
    diff --git a/kernel/hrtimer.c b/kernel/hrtimer.c
    index 9cd8564..54277be 100644
    --- a/kernel/hrtimer.c
    +++ b/kernel/hrtimer.c
    @@ -1574,7 +1574,7 @@ long hrtimer_nanosleep(struct timespec *rqtp, struct timespec __user *rmtp,
    unsigned long slack;

    slack = current->timer_slack_ns;
    - if (dl_task(current) || rt_task(current))
    + if (__dl_task(current) || rt_task(current))
    slack = 0;

    hrtimer_init_on_stack(&t.timer, clockid, mode);
    diff --git a/kernel/sched.c b/kernel/sched.c
    index 79cac6e..4d291e3 100644
    --- a/kernel/sched.c
    +++ b/kernel/sched.c
    @@ -2235,7 +2235,7 @@ void set_task_cpu(struct task_struct *p, unsigned int new_cpu)
    #endif

    trace_sched_migrate_task(p, new_cpu);
    - if (unlikely(dl_task(p)))
    + if (unlikely(__dl_task(p)))
    trace_sched_migrate_task_dl(p, task_rq(p)->clock,
    new_cpu, cpu_rq(new_cpu)->clock);

    @@ -2983,6 +2983,16 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev)
    prev->sched_class->task_dead(prev);

    /*
    + * If we are a -deadline task, dieing while
    + * hanging out in a different scheduling class
    + * we need to manually call our own cleanup function,
    + * at least to stop the bandwidth timer.
    + */
    + if (unlikely(task_has_dl_policy(prev) &&
    + prev->sched_class != &dl_sched_class))
    + dl_sched_class.task_dead(prev);
    +
    + /*
    * Remove function-return probe instances associated with this
    * task and put them back on the free list.
    */
    @@ -3064,7 +3074,7 @@ context_switch(struct rq *rq, struct task_struct *prev,

    prepare_task_switch(rq, prev, next);
    trace_sched_switch(prev, next);
    - if (unlikely(dl_task(prev) || dl_task(next)))
    + if (unlikely(__dl_task(prev) || __dl_task(next)))
    trace_sched_switch_dl(rq->clock, prev, next);
    mm = next->mm;
    oldmm = prev->active_mm;
    @@ -4554,34 +4564,13 @@ long __sched sleep_on_timeout(wait_queue_head_t *q, long timeout)
    }
    EXPORT_SYMBOL(sleep_on_timeout);

    -#ifdef CONFIG_RT_MUTEXES
    -
    -/*
    - * rt_mutex_setprio - set the current priority of a task
    - * @p: task
    - * @prio: prio value (kernel-internal form)
    - *
    - * This function changes the 'effective' priority of a task. It does
    - * not touch ->normal_prio like __setscheduler().
    - *
    - * Used by the rt_mutex code to implement priority inheritance logic.
    - */
    -void rt_mutex_setprio(struct task_struct *p, int prio)
    +static void __setprio(struct rq *rq, struct task_struct *p, int prio)
    {
    - unsigned long flags;
    - int oldprio, on_rq, running;
    - struct rq *rq;
    - const struct sched_class *prev_class;
    -
    - BUG_ON(prio < 0 || prio > MAX_PRIO);
    + int oldprio = p->prio;
    + const struct sched_class *prev_class = p->sched_class;
    + int running = task_current(rq, p);
    + int on_rq = p->se.on_rq;

    - rq = task_rq_lock(p, &flags);
    -
    - trace_sched_pi_setprio(p, prio);
    - oldprio = p->prio;
    - prev_class = p->sched_class;
    - on_rq = p->se.on_rq;
    - running = task_current(rq, p);
    if (on_rq)
    dequeue_task(rq, p, 0);
    if (running)
    @@ -4603,6 +4592,30 @@ void rt_mutex_setprio(struct task_struct *p, int prio)

    check_class_changed(rq, p, prev_class, oldprio, running);
    }
    +}
    +
    +#ifdef CONFIG_RT_MUTEXES
    +
    +/*
    + * rt_mutex_setprio - set the current priority of a task
    + * @p: task
    + * @prio: prio value (kernel-internal form)
    + *
    + * This function changes the 'effective' priority of a task. It does
    + * not touch ->normal_prio like __setscheduler().
    + *
    + * Used by the rt_mutex code to implement priority inheritance logic.
    + */
    +void rt_mutex_setprio(struct task_struct *p, int prio)
    +{
    + unsigned long flags;
    + struct rq *rq;
    +
    + BUG_ON(prio < 0 || prio > MAX_PRIO);
    +
    + rq = task_rq_lock(p, &flags);
    + trace_sched_pi_setprio(p, prio);
    + __setprio(rq, p, prio);
    task_rq_unlock(rq, &flags);
    }

    @@ -4909,19 +4922,32 @@ recheck:
    */
    if (user && !capable(CAP_SYS_NICE)) {
    if (dl_policy(policy)) {
    - u64 rlim_dline, rlim_rtime;
    + u64 rlim_dline, rlim_rtime, rlim_rtprio;
    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;
    + rlim_rtprio = p->signal->rlim[RLIMIT_RTPRIO].rlim_cur;
    unlock_task_sighand(p, &flags);

    /* can't set/change -deadline policy */
    if (policy != p->policy && !rlim_rtime)
    return -EPERM;

    + /* can't set/change reclaiming policy to -deadline */
    + if ((param_ex->sched_flags & SF_BWRECL_DL) !=
    + (p->dl.flags & SF_BWRECL_DL))
    + return -EPERM;
    +
    + /* can't set/increase -rt reclaiming priority */
    + if (param_ex->sched_flags & SF_BWRECL_RT &&
    + (param_ex->sched_priority <= 0 ||
    + (param_ex->sched_priority > p->rt_priority &&
    + param_ex->sched_priority > rlim_rtprio)))
    + return -EPERM;
    +
    /* can't decrease the deadline */
    rlim_dline *= NSEC_PER_USEC;
    dline = timespec_to_ns(&param_ex->sched_deadline);
    @@ -8596,7 +8622,7 @@ void normalize_rt_tasks(void)
    p->se.statistics.block_start = 0;
    #endif

    - if (!dl_task(p) && !rt_task(p)) {
    + if (!__dl_task(p) && !rt_task(p)) {
    /*
    * Renice negative nice level userspace
    * tasks back to 0:
    diff --git a/kernel/sched_debug.c b/kernel/sched_debug.c
    index 4949a21..2bf4e72 100644
    --- a/kernel/sched_debug.c
    +++ b/kernel/sched_debug.c
    @@ -467,7 +467,7 @@ void proc_sched_show_task(struct task_struct *p, struct seq_file *m)
    P(se.statistics.nr_wakeups_affine_attempts);
    P(se.statistics.nr_wakeups_passive);
    P(se.statistics.nr_wakeups_idle);
    - if (dl_task(p)) {
    + if (__dl_task(p)) {
    P(dl.stats.dmiss);
    PN(dl.stats.last_dmiss);
    PN(dl.stats.dmiss_max);
    diff --git a/kernel/sched_dl.c b/kernel/sched_dl.c
    index eff183a..4d24109 100644
    --- a/kernel/sched_dl.c
    +++ b/kernel/sched_dl.c
    @@ -15,6 +15,8 @@
    * Fabio Checconi <fabio@gandalf.sssup.it>
    */

    +static const struct sched_class dl_sched_class;
    +
    static inline int dl_time_before(u64 a, u64 b)
    {
    return (s64)(a - b) < 0;
    @@ -382,6 +384,17 @@ static int start_dl_timer(struct sched_dl_entity *dl_se)
    s64 delta;

    /*
    + * If the task wants to stay -deadline even if it exhausted
    + * its runtime we allow that by not starting the timer.
    + * update_curr_dl() will thus queue it back after replenishment
    + * and deadline postponing.
    + * This won't affect the other -deadline tasks, but if we are
    + * a CPU-hog, lower scheduling classes will starve!
    + */
    + if (dl_se->flags & SF_BWRECL_DL)
    + return 0;
    +
    + /*
    * We want the timer to fire at the deadline, but considering
    * that it is actually coming from rq->clock and not from
    * hrtimer's time base reading.
    @@ -414,6 +427,8 @@ static int start_dl_timer(struct sched_dl_entity *dl_se)
    return hrtimer_active(&dl_se->dl_timer);
    }

    +static void __setprio(struct rq *rq, struct task_struct *p, int prio);
    +
    /*
    * This is the bandwidth enforcement timer callback. If here, we know
    * a task is not on its dl_rq, since the fact that the timer was running
    @@ -440,12 +455,18 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
    * We need to take care of a possible races here. In fact, the
    * task might have changed its scheduling policy to something
    * different from SCHED_DEADLINE (through sched_setscheduler()).
    + * However, if we changed scheduling class for reclaiming, it
    + * is correct to handle this replenishment, since this is what
    + * will put us back into the -deadline scheduling class.
    */
    - if (!dl_task(p))
    + if (!__dl_task(p))
    goto unlock;

    trace_sched_timer_dl(p, rq->clock, p->se.on_rq, task_current(rq, p));

    + if (unlikely(p->sched_class != &dl_sched_class))
    + __setprio(rq, p, MAX_DL_PRIO-1);
    +
    dl_se->dl_throttled = 0;
    if (p->se.on_rq) {
    enqueue_task_dl(rq, p, ENQUEUE_REPLENISH);
    @@ -530,6 +551,16 @@ int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)
    return 1;
    }

    +static inline void throttle_curr_dl(struct rq *rq, struct task_struct *curr)
    +{
    + curr->dl.dl_throttled = 1;
    +
    + if (curr->dl.flags & SF_BWRECL_RT)
    + __setprio(rq, curr, MAX_RT_PRIO-1 - curr->rt_priority);
    + else if (curr->dl.flags & SF_BWRECL_NR)
    + __setprio(rq, curr, DEFAULT_PRIO);
    +}
    +
    /*
    * Update the current task's runtime statistics (provided it is still
    * a -deadline task and has not been removed from the dl_rq).
    @@ -565,7 +596,7 @@ static void update_curr_dl(struct rq *rq)
    if (dl_runtime_exceeded(rq, dl_se)) {
    __dequeue_task_dl(rq, curr, 0);
    if (likely(start_dl_timer(dl_se)))
    - dl_se->dl_throttled = 1;
    + throttle_curr_dl(rq, curr);
    else
    enqueue_task_dl(rq, curr, ENQUEUE_REPLENISH);

    @@ -765,8 +796,10 @@ static void __dequeue_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)
    {
    - update_curr_dl(rq);
    - __dequeue_task_dl(rq, p, flags);
    + if (likely(!p->dl.dl_throttled)) {
    + update_curr_dl(rq);
    + __dequeue_task_dl(rq, p, flags);
    + }
    }

    /*
    @@ -1000,6 +1033,9 @@ struct task_struct *pick_next_task_dl(struct rq *rq)

    static void put_prev_task_dl(struct rq *rq, struct task_struct *p)
    {
    + if (unlikely(p->dl.dl_throttled))
    + return;
    +
    update_curr_dl(rq);
    p->se.exec_start = 0;

    --
    1.7.2.3


    --
    <<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 / raistlin@ekiga.net /
    dario.faggioli@jabber.org
    [unhandled content-type:application/pgp-signature]
    \
     
     \ /
      Last update: 2010-10-29 08:45    [W:0.042 / U:0.168 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site