Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2

Peter Williams
2006-03-03T23:58:32Z

Mike Galbraith wrote:
> Greetings,
>
> Below, please find part 1 of my latest task throttling effort. I've
> very nearly completely reworked it from top to bottom, and broken it
> down into separate cleanup and a throttling diffs.
>
> Main things that this diff does:
>
> 1. Closes a generic hole in the scheduler design: due to timeslice
> sample rate of HZ, tasks can and do steal time from each other.
> Generally this is no big deal, because statistics more or less even
> things out, but tasks with a high scheduling frequency and a low
> execution duration can steal considerable time. No longer.
>
> 2. Removes overhead from the fast path. There's no need to do division
> in the fast path, it's cheaper to do it at timeslice refresh time, where
> it accomplishes the same thing at a fraction of the cost. Trades a
> subtraction for a division, and removes the obsoleted bits that led to
> the division.
>
> I have verified that the testcase sent in by David Mosberg ages ago, and
> which was the prime motivator for going to nanosecond timings in the
> scheduler in the first place, is not broken by the above changes.
>
> 3. Removes the disparity in the handling of dynamic priority for kernel
> threads verses user-land tasks.
>
> 4. Fixes a boot-time buglet where the TSC isn't synchronized yet,
> resulting in recalc_task_prio() being called with now < p->timestamp.
> If you place a WARN_ON there, the box won't even boot. With this fix,
> you'll get one warning, and then all goes fine.
>
> 5. Fixes a couple of would-be bugs if anyone ever decided to use
> TASK_NONINTERACTIVE thing along with TASK_UNINTERRUPTIBLE.
>
> 6. Removes sleep_avg multiplier. Back when we had 10s of dynamic range,
> this was needed to help get interactive tasks up to speed. The 10 time
> speedup meant that a 1s sleep put us at max priority. Worked great. As
> we speak however, we have _1_ second of dynamic range, and this gets
> compressed to 100ms by the multiplier. This is very bad, and to see how
> bad, just try a very modest parallel kernel compile in a relatively slow
> NFS mounted filesystem. In heavy testing, I can find no detriment to
> removing this anachronism.
>
> 7. Assorted cleanups to the interactivity logic.
>
> 8. Whatever I forgot to mention ;-)
>
> Comments?

If you're going to manage the time slice in nanoseconds why not do it
properly? I presume you've held back a bit in case you break something?

If it helps, the smpnice balancing code's use of static_prio_timeslice()
doesn't really care what units it's return value is in as long as
DEF_TIMESLICE is in the same units and contains the size of a time slice
allocated to a nice==0 non RT task.

>
> -Mike
>
> Signed-off-by Mike Galbraith <efault@gmx.de>
>
> include/linux/sched.h | 3 -
> kernel/sched.c | 136 +++++++++++++++++++++++++++++---------------------
> 2 files changed, 82 insertions(+), 57 deletions(-)
>
> --- linux-2.6.16-rc5-mm2/include/linux/sched.h.org 2006-03-01 15:06:22.000000000 +0100
> +++ linux-2.6.16-rc5-mm2/include/linux/sched.h 2006-03-02 08:33:12.000000000 +0100
> @@ -720,7 +720,8 @@
>
> unsigned long policy;
> cpumask_t cpus_allowed;
> - unsigned int time_slice, first_time_slice;
> + int time_slice;
> + unsigned int first_time_slice;
>
> #ifdef CONFIG_SCHEDSTATS
> struct sched_info sched_info;
> --- linux-2.6.16-rc5-mm2/kernel/sched.c.org 2006-03-01 15:05:56.000000000 +0100
> +++ linux-2.6.16-rc5-mm2/kernel/sched.c 2006-03-02 10:05:47.000000000 +0100
> @@ -99,6 +99,10 @@
> #define MAX_SLEEP_AVG (DEF_TIMESLICE * MAX_BONUS)
> #define STARVATION_LIMIT (MAX_SLEEP_AVG)
> #define NS_MAX_SLEEP_AVG (JIFFIES_TO_NS(MAX_SLEEP_AVG))
> +#define NS_MAX_SLEEP_AVG_PCNT (NS_MAX_SLEEP_AVG / 100)
> +#define PCNT_PER_DYNPRIO (100 / MAX_BONUS)
> +#define NS_PER_DYNPRIO (PCNT_PER_DYNPRIO * NS_MAX_SLEEP_AVG_PCNT)
> +#define NS_TICK (JIFFIES_TO_NS(1))
>
> /*
> * If a task is 'interactive' then we reinsert it in the active
> @@ -153,9 +157,25 @@
> #define TASK_INTERACTIVE(p) \
> ((p)->prio <= (p)->static_prio - DELTA(p))
>
> -#define INTERACTIVE_SLEEP(p) \
> - (JIFFIES_TO_NS(MAX_SLEEP_AVG * \
> - (MAX_BONUS / 2 + DELTA((p)) + 1) / MAX_BONUS - 1))
> +#define SLEEP_AVG_DIVISOR(p) (1 + CURRENT_BONUS(p))
> +
> +#define INTERACTIVE_SLEEP_AVG(p) \
> + (min(JIFFIES_TO_NS(MAX_SLEEP_AVG * (MAX_BONUS / 2 + DELTA(p)) / \
> + MAX_BONUS), NS_MAX_SLEEP_AVG))
> +
> +/*
> + * Returns whether a task has been asleep long enough to be considered idle.
> + * The metric is whether this quantity of sleep would promote the task more
> + * than one priority beyond marginally interactive.
> + */
> +static int task_interactive_idle(task_t *p, unsigned long sleep_time)
> +{
> + unsigned long ceiling = (CURRENT_BONUS(p) + 2) * NS_PER_DYNPRIO;
> +
> + if (p->sleep_avg + sleep_time < ceiling)
> + return 0;
> + return p->sleep_avg + sleep_time >= INTERACTIVE_SLEEP_AVG(p);
> +}
>
> #define TASK_PREEMPTS_CURR(p, rq) \
> ((p)->prio < (rq)->curr->prio)
> @@ -182,7 +202,7 @@
>
> static inline unsigned int task_timeslice(task_t *p)
> {
> - return static_prio_timeslice(p->static_prio);
> + return JIFFIES_TO_NS(static_prio_timeslice(p->static_prio));
> }
>
> #define task_hot(p, now, sd) ((long long) ((now) - (p)->last_ran) \
> @@ -240,6 +260,7 @@
>
> unsigned long expired_timestamp;
> unsigned long long timestamp_last_tick;
> + unsigned long long timestamp_last_switch;
> task_t *curr, *idle;
> struct mm_struct *prev_mm;
> prio_array_t *active, *expired, arrays[2];
> @@ -777,6 +798,9 @@
> unsigned long long __sleep_time = now - p->timestamp;
> unsigned long sleep_time;
>
> + if (unlikely(now < p->timestamp))
> + __sleep_time = 0ULL;
> +
> if (unlikely(p->policy == SCHED_BATCH))
> sleep_time = 0;
> else {
> @@ -788,32 +812,32 @@
>
> if (likely(sleep_time > 0)) {
> /*
> - * User tasks that sleep a long time are categorised as
> - * idle. They will only have their sleep_avg increased to a
> + * Tasks that sleep a long time are categorised as idle.
> + * They will only have their sleep_avg increased to a
> * level that makes them just interactive priority to stay
> * active yet prevent them suddenly becoming cpu hogs and
> * starving other processes.
> */
> - if (p->mm && sleep_time > INTERACTIVE_SLEEP(p)) {
> - unsigned long ceiling;
> -
> - ceiling = JIFFIES_TO_NS(MAX_SLEEP_AVG -
> - DEF_TIMESLICE);
> - if (p->sleep_avg < ceiling)
> - p->sleep_avg = ceiling;
> - } else {
> + if (task_interactive_idle(p, sleep_time)) {
> + unsigned long ceiling = INTERACTIVE_SLEEP_AVG(p);
>
> /*
> - * The lower the sleep avg a task has the more
> - * rapidly it will rise with sleep time. This enables
> - * tasks to rapidly recover to a low latency priority.
> - * If a task was sleeping with the noninteractive
> - * label do not apply this non-linear boost
> + * Promote previously interactive task.
> */
> - if (p->sleep_type != SLEEP_NONINTERACTIVE || !p->mm)
> - sleep_time *=
> - (MAX_BONUS - CURRENT_BONUS(p)) ? : 1;
> + if (p->sleep_avg > ceiling) {
> + ceiling = p->sleep_avg / NS_PER_DYNPRIO;
> + if (ceiling < MAX_BONUS)
> + ceiling++;
> + ceiling *= NS_PER_DYNPRIO;
> + } else {
> + ceiling += p->time_slice >> 2;
> + if (ceiling > NS_MAX_SLEEP_AVG)
> + ceiling = NS_MAX_SLEEP_AVG;
> + }
>
> + if (p->sleep_avg < ceiling)
> + p->sleep_avg = ceiling;
> + } else {
> /*
> * This code gives a bonus to interactive tasks.
> *
> @@ -1367,7 +1391,8 @@
>
> out_activate:
> #endif /* CONFIG_SMP */
> - if (old_state == TASK_UNINTERRUPTIBLE) {
> +
> + if (old_state & TASK_UNINTERRUPTIBLE) {
> rq->nr_uninterruptible--;
> /*
> * Tasks waking from uninterruptible sleep are likely
> @@ -1461,6 +1486,8 @@
> */
> local_irq_disable();
> p->time_slice = (current->time_slice + 1) >> 1;
> + if (unlikely(p->time_slice < NS_TICK))
> + p->time_slice = NS_TICK;
> /*
> * The remainder of the first timeslice might be recovered by
> * the parent if the child exits early enough.
> @@ -1468,13 +1495,12 @@
> p->first_time_slice = 1;
> current->time_slice >>= 1;
> p->timestamp = sched_clock();
> - if (unlikely(!current->time_slice)) {
> + if (unlikely(current->time_slice < NS_TICK)) {
> /*
> * This case is rare, it happens when the parent has only
> * a single jiffy left from its timeslice. Taking the
> * runqueue lock is not a problem.
> */
> - current->time_slice = 1;
> scheduler_tick();
> }
> local_irq_enable();
> @@ -2586,6 +2612,7 @@
> {
> unsigned long long last = max(p->timestamp, rq->timestamp_last_tick);
> p->sched_time += now - last;
> + p->time_slice -= now - last;
> }
>
> /*
> @@ -2735,8 +2762,8 @@
> * RR tasks need a special form of timeslice management.
> * FIFO tasks have no timeslices.
> */
> - if ((p->policy == SCHED_RR) && !--p->time_slice) {
> - p->time_slice = task_timeslice(p);
> + if ((p->policy == SCHED_RR) && p->time_slice < NS_TICK) {
> + p->time_slice += task_timeslice(p);
> p->first_time_slice = 0;
> set_tsk_need_resched(p);
>
> @@ -2745,11 +2772,21 @@
> }
> goto out_unlock;
> }
> - if (!--p->time_slice) {
> + if (p->time_slice < NS_TICK) {
> + int time_slice = task_timeslice(p);
> + int run_time = time_slice - p->time_slice;
> dequeue_task(p, rq->active);
> set_tsk_need_resched(p);
> + p->time_slice += time_slice;
> + /*
> + * Tasks are charged proportionately less run_time at high
> + * sleep_avg to delay them losing their interactive status
> + */
> + run_time /= SLEEP_AVG_DIVISOR(p);
> + p->sleep_avg -= run_time;
> + if ((long)p->sleep_avg < 0)
> + p->sleep_avg = 0;
> p->prio = effective_prio(p);
> - p->time_slice = task_timeslice(p);
> p->first_time_slice = 0;
>
> if (!rq->expired_timestamp)
> @@ -2777,13 +2814,17 @@
> * This only applies to tasks in the interactive
> * delta range with at least TIMESLICE_GRANULARITY to requeue.
> */
> - if (TASK_INTERACTIVE(p) && !((task_timeslice(p) -
> - p->time_slice) % TIMESLICE_GRANULARITY(p)) &&
> - (p->time_slice >= TIMESLICE_GRANULARITY(p)) &&
> - (p->array == rq->active)) {
> + if (p->array == rq->active) {
> + unsigned long runtime, period;
>
> - requeue_task(p, rq->active);
> - set_tsk_need_resched(p);
> + runtime = now - rq->timestamp_last_switch;
> + period = JIFFIES_TO_NS(TIMESLICE_GRANULARITY(p));
> +
> + if (runtime >= period && p->time_slice >> 1 >= period) {
> + requeue_task(p, rq->active);
> + set_tsk_need_resched(p);
> + rq->timestamp_last_switch = now;
> + }
> }
> }
> out_unlock:
> @@ -2851,7 +2892,8 @@
> */
> static inline unsigned long smt_slice(task_t *p, struct sched_domain *sd)
> {
> - return p->time_slice * (100 - sd->per_cpu_gain) / 100;
> + int time_slice = NS_TO_JIFFIES(p->time_slice) ? : 1;
> + return time_slice * (100 - sd->per_cpu_gain) / 100;
> }
>
> static int dependent_sleeper(int this_cpu, runqueue_t *this_rq)
> @@ -3014,7 +3056,6 @@
> prio_array_t *array;
> struct list_head *queue;
> unsigned long long now;
> - unsigned long run_time;
> int cpu, idx, new_prio;
>
> /*
> @@ -3050,19 +3091,6 @@
>
> schedstat_inc(rq, sched_cnt);
> now = sched_clock();
> - if (likely((long long)(now - prev->timestamp) < NS_MAX_SLEEP_AVG)) {
> - run_time = now - prev->timestamp;
> - if (unlikely((long long)(now - prev->timestamp) < 0))
> - run_time = 0;
> - } else
> - run_time = NS_MAX_SLEEP_AVG;
> -
> - /*
> - * Tasks charged proportionately less run_time at high sleep_avg to
> - * delay them losing their interactive status
> - */
> - run_time /= (CURRENT_BONUS(prev) ? : 1);
> -
> spin_lock_irq(&rq->lock);
>
> if (unlikely(prev->flags & PF_DEAD))
> @@ -3075,7 +3103,7 @@
> unlikely(signal_pending(prev))))
> prev->state = TASK_RUNNING;
> else {
> - if (prev->state == TASK_UNINTERRUPTIBLE)
> + if (prev->state & TASK_UNINTERRUPTIBLE)
> rq->nr_uninterruptible++;
> deactivate_task(prev, rq);
> }
> @@ -3136,7 +3164,6 @@
> if (next->sleep_type == SLEEP_INTERACTIVE)
> delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;
>
> - array = next->array;
> new_prio = recalc_task_prio(next, next->timestamp + delta);
>
> if (unlikely(next->prio != new_prio)) {
> @@ -3156,14 +3183,11 @@
>
> update_cpu_clock(prev, rq, now);
>
> - prev->sleep_avg -= run_time;
> - if ((long)prev->sleep_avg <= 0)
> - prev->sleep_avg = 0;
> prev->timestamp = prev->last_ran = now;
>
> sched_info_switch(prev, next);
> if (likely(prev != next)) {
> - next->timestamp = now;
> + next->timestamp = rq->timestamp_last_switch = now;
> rq->nr_switches++;
> rq->curr = next;
> ++*switch_count;
>

--
Peter Williams pwil3058@bigpond.net.au

"Learning, n. The kind of ignorance distinguishing the studious."
-- Ambrose Bierce