lkml.org 
[lkml]   [2006]   [May]   [27]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [RFC 2/5] sched: Add CPU rate soft caps
On 5/26/06, Peter Williams <pwil3058@bigpond.net.au> wrote:
<snip>
>
> Notes:
>
> 1. To minimize the overhead incurred when testing to skip caps processing for
> uncapped tasks a new flag PF_HAS_CAP has been added to flags.
>
> 2. The implementation involves the addition of two priority slots to the
> run queue priority arrays and this means that MAX_PRIO no longer
> represents the scheduling priority of the idle process and can't be used to
> test whether priority values are in the valid range. To alleviate this
> problem a new function sched_idle_prio() has been provided.

I am a little confused by this. Why link the bandwidth expired tasks a
cpu (its caps) to a priority slot? Is this a hack to conitnue using
the prio_array? why not move such tasks to the expired array?

<snip>
> /*
> * Some day this will be a full-fledged user tracking system..
> */
> @@ -787,6 +793,10 @@ struct task_struct {
> unsigned long sleep_avg;
> unsigned long long timestamp, last_ran;
> unsigned long long sched_time; /* sched_clock time spent running */
> +#ifdef CONFIG_CPU_RATE_CAPS
> + unsigned long long avg_cpu_per_cycle, avg_cycle_length;
> + unsigned int cpu_rate_cap;
> +#endif

How is a cycle defined? What are the units of a cycle? Could we please
document the units for the declarations above

> enum sleep_type sleep_type;
>
> unsigned long policy;
> @@ -981,6 +991,11 @@ struct task_struct {
> #endif
> };
>
> +#ifdef CONFIG_CPU_RATE_CAPS
> +unsigned int get_cpu_rate_cap(const struct task_struct *);
> +int set_cpu_rate_cap(struct task_struct *, unsigned int);
> +#endif
> +
> static inline pid_t process_group(struct task_struct *tsk)
> {
> return tsk->signal->pgrp;
> @@ -1040,6 +1055,7 @@ static inline void put_task_struct(struc
> #define PF_SPREAD_SLAB 0x08000000 /* Spread some slab caches over cpuset */
> #define PF_MEMPOLICY 0x10000000 /* Non-default NUMA mempolicy */
> #define PF_MUTEX_TESTER 0x02000000 /* Thread belongs to the rt mutex tester */
> +#define PF_HAS_CAP 0x20000000 /* Has a CPU rate cap */
>
> /*
> * Only the _current_ task can read/write to tsk->flags, but other
> Index: MM-2.6.17-rc4-mm3/init/Kconfig
> ===================================================================
> --- MM-2.6.17-rc4-mm3.orig/init/Kconfig 2006-05-26 10:39:59.000000000 +1000
> +++ MM-2.6.17-rc4-mm3/init/Kconfig 2006-05-26 10:45:26.000000000 +1000
> @@ -286,6 +286,8 @@ config RELAY
>
> If unsure, say N.
>
> +source "kernel/Kconfig.caps"
> +
> source "usr/Kconfig"
>
> config UID16
> Index: MM-2.6.17-rc4-mm3/kernel/Kconfig.caps
> ===================================================================
> --- /dev/null 1970-01-01 00:00:00.000000000 +0000
> +++ MM-2.6.17-rc4-mm3/kernel/Kconfig.caps 2006-05-26 10:45:26.000000000 +1000
> @@ -0,0 +1,13 @@
> +#
> +# CPU Rate Caps Configuration
> +#
> +
> +config CPU_RATE_CAPS
> + bool "Support (soft) CPU rate caps"
> + default n
> + ---help---
> + Say y here if you wish to be able to put a (soft) upper limit on
> + the rate of CPU usage by individual tasks. A task which has been
> + allocated a soft CPU rate cap will be limited to that rate of CPU
> + usage unless there is spare CPU resources available after the needs
> + of uncapped tasks are met.
> Index: MM-2.6.17-rc4-mm3/kernel/sched.c
> ===================================================================
> --- MM-2.6.17-rc4-mm3.orig/kernel/sched.c 2006-05-26 10:44:51.000000000 +1000
> +++ MM-2.6.17-rc4-mm3/kernel/sched.c 2006-05-26 11:00:02.000000000 +1000
> @@ -57,6 +57,19 @@
>
> #include <asm/unistd.h>
>
> +#ifdef CONFIG_CPU_RATE_CAPS
> +#define IDLE_PRIO (MAX_PRIO + 2)
> +#else
> +#define IDLE_PRIO MAX_PRIO
> +#endif
> +#define BGND_PRIO (IDLE_PRIO - 1)
> +#define CAPPED_PRIO (IDLE_PRIO - 2)
> +
> +int sched_idle_prio(void)
> +{
> + return IDLE_PRIO;
> +}
> +
> /*
> * Convert user-nice values [ -20 ... 0 ... 19 ]
> * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
> @@ -186,6 +199,149 @@ static inline unsigned int task_timeslic
> return static_prio_timeslice(p->static_prio);
> }
>
> +#ifdef CONFIG_CPU_RATE_CAPS
> +#define CAP_STATS_OFFSET 8
> +#define task_has_cap(p) unlikely((p)->flags & PF_HAS_CAP)
> +/* this assumes that p is not a real time task */
> +#define task_is_background(p) unlikely((p)->cpu_rate_cap == 0)
> +#define task_being_capped(p) unlikely((p)->prio >= CAPPED_PRIO)
> +#define cap_load_weight(p) (((p)->cpu_rate_cap * SCHED_LOAD_SCALE) / 1000)

Could we please use a const or #define'd name instead of 1000. How
about TOTAL_CAP_IN_PARTS? It would make the code easier to read and
maintain.

> +
> +static void init_cpu_rate_caps(task_t *p)
> +{
> + p->cpu_rate_cap = 1000;
> + p->flags &= ~PF_HAS_CAP;
> +}
> +
> +static inline void set_cap_flag(task_t *p)
> +{
> + if (p->cpu_rate_cap < 1000 && !has_rt_policy(p))
> + p->flags |= PF_HAS_CAP;
> + else
> + p->flags &= ~PF_HAS_CAP;
> +}

Why don't you re-use RLIMIT_INFINITY?

> +
> +static inline int task_exceeding_cap(const task_t *p)
> +{
> + return (p->avg_cpu_per_cycle * 1000) > (p->avg_cycle_length * p->cpu_rate_cap);
> +}
> +
> +#ifdef CONFIG_SCHED_SMT
> +static unsigned int smt_timeslice(task_t *p)
> +{
> + if (task_has_cap(p) && task_being_capped(p))
> + return 0;
> +
> + return task_timeslice(p);
> +}
> +
> +static int task_priority_gt(const task_t *thisp, const task_t *thatp)
> +{
> + if (task_has_cap(thisp) && (task_being_capped(thisp)))
> + return 0;
> +
> + if (task_has_cap(thatp) && (task_being_capped(thatp)))
> + return 1;
> +
> + return thisp->static_prio < thatp->static_prio;
> +}

This function needs some comments. At least with respect to what is
thisp and thatp

> +#endif
> +
> +/*
> + * Update usage stats to "now" before making comparison
> + * Assume: task is actually on a CPU
> + */
> +static int task_exceeding_cap_now(const task_t *p, unsigned long long now)
> +{
> + unsigned long long delta, lhs, rhs;
> +
> + delta = (now > p->timestamp) ? (now - p->timestamp) : 0;
> + lhs = (p->avg_cpu_per_cycle + delta) * 1000;
> + rhs = (p->avg_cycle_length + delta) * p->cpu_rate_cap;
> +
> + return lhs > rhs;
> +}
> +
> +static inline void init_cap_stats(task_t *p)
> +{
> + p->avg_cpu_per_cycle = 0;
> + p->avg_cycle_length = 0;
> +}
> +
> +static inline void inc_cap_stats_cycle(task_t *p, unsigned long long now)
> +{
> + unsigned long long delta;
> +
> + delta = (now > p->timestamp) ? (now - p->timestamp) : 0;
> + p->avg_cycle_length += delta;
> +}
> +
> +static inline void inc_cap_stats_both(task_t *p, unsigned long long now)
> +{
> + unsigned long long delta;
> +
> + delta = (now > p->timestamp) ? (now - p->timestamp) : 0;
> + p->avg_cycle_length += delta;
> + p->avg_cpu_per_cycle += delta;
> +}
> +
> +static inline void decay_cap_stats(task_t *p)
> +{
> + p->avg_cycle_length *= ((1 << CAP_STATS_OFFSET) - 1);
> + p->avg_cycle_length >>= CAP_STATS_OFFSET;
> + p->avg_cpu_per_cycle *= ((1 << CAP_STATS_OFFSET) - 1);
> + p->avg_cpu_per_cycle >>= CAP_STATS_OFFSET;
> +}
> +#else
> +#define task_has_cap(p) 0
> +#define task_is_background(p) 0
> +#define task_being_capped(p) 0
> +#define cap_load_weight(p) SCHED_LOAD_SCALE
> +
> +static inline void init_cpu_rate_caps(task_t *p)
> +{
> +}
> +
> +static inline void set_cap_flag(task_t *p)
> +{
> +}
> +
> +static inline int task_exceeding_cap(const task_t *p)
> +{
> + return 0;
> +}
> +
> +#ifdef CONFIG_SCHED_SMT
> +#define smt_timeslice(p) task_timeslice(p)
> +
> +static inline int task_priority_gt(const task_t *thisp, const task_t *thatp)
> +{
> + return thisp->static_prio < thatp->static_prio;
> +}
> +#endif
> +
> +static inline int task_exceeding_cap_now(const task_t *p, unsigned long long now)
> +{
> + return 0;
> +}
> +
> +static inline void init_cap_stats(task_t *p)
> +{
> +}
> +
> +static inline void inc_cap_stats_cycle(task_t *p, unsigned long long now)
> +{
> +}
> +
> +static inline void inc_cap_stats_both(task_t *p, unsigned long long now)
> +{
> +}
> +
> +static inline void decay_cap_stats(task_t *p)
> +{
> +}
> +#endif
> +
> #define task_hot(p, now, sd) ((long long) ((now) - (p)->last_ran) \
> < (long long) (sd)->cache_hot_time)
>
> @@ -197,8 +353,8 @@ typedef struct runqueue runqueue_t;
>
> struct prio_array {
> unsigned int nr_active;
> - DECLARE_BITMAP(bitmap, MAX_PRIO+1); /* include 1 bit for delimiter */
> - struct list_head queue[MAX_PRIO];
> + DECLARE_BITMAP(bitmap, IDLE_PRIO+1); /* include 1 bit for delimiter */
> + struct list_head queue[IDLE_PRIO];
> };
>
> /*
> @@ -710,6 +866,10 @@ static inline int __normal_prio(task_t *
> {
> int bonus, prio;
>
> + /* Ensure that background tasks stay at BGND_PRIO */
> + if (task_is_background(p))
> + return BGND_PRIO;
> +
> bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;
>
> prio = p->static_prio - bonus;
> @@ -786,6 +946,8 @@ static inline int expired_starving(runqu
>
> static void set_load_weight(task_t *p)
> {
> + set_cap_flag(p);
> +
> if (has_rt_policy(p)) {
> #ifdef CONFIG_SMP
> if (p == task_rq(p)->migration_thread)
> @@ -798,8 +960,22 @@ static void set_load_weight(task_t *p)
> else
> #endif
> p->load_weight = RTPRIO_TO_LOAD_WEIGHT(p->rt_priority);
> - } else
> + } else {
> p->load_weight = PRIO_TO_LOAD_WEIGHT(p->static_prio);
> +
> + /*
> + * Reduce the probability of a task escaping its CPU rate cap
> + * due to load balancing leaving it on a lighly used CPU
> + * This will be optimized away if rate caps aren't configured
> + */
> + if (task_has_cap(p)) {
> + unsigned int clw; /* load weight based on cap */
> +
> + clw = cap_load_weight(p);
> + if (clw < p->load_weight)
> + p->load_weight = clw;
> + }

You could use
p->load_weight = min(cap_load_weight(p), p->load_weight);


> + }
> }
>
> static inline void inc_raw_weighted_load(runqueue_t *rq, const task_t *p)
> @@ -869,7 +1045,8 @@ static void __activate_task(task_t *p, r
> {
> prio_array_t *target = rq->active;
>
> - if (unlikely(batch_task(p) || (expired_starving(rq) && !rt_task(p))))
> + if (unlikely(batch_task(p) || (expired_starving(rq) && !rt_task(p)) ||
> + task_being_capped(p)))
> target = rq->expired;
> enqueue_task(p, target);
> inc_nr_running(p, rq);
> @@ -975,8 +1152,30 @@ static void activate_task(task_t *p, run
> #endif
>
> if (!rt_task(p))
> + /*
> + * We want to do the recalculation even if we're exceeding
> + * a cap so that everything still works when we stop
> + * exceeding our cap.
> + */
> p->prio = recalc_task_prio(p, now);
>
> + if (task_has_cap(p)) {
> + inc_cap_stats_cycle(p, now);
> + /* Background tasks are handled in effective_prio()
> + * in order to ensure that they stay at BGND_PRIO
> + * but we need to be careful that we don't override
> + * it here
> + */
> + if (task_exceeding_cap(p) && !task_is_background(p)) {
> + p->normal_prio = CAPPED_PRIO;
> + /*
> + * Don't undo any priority ineheritance
> + */
> + if (!rt_task(p))
> + p->prio = CAPPED_PRIO;
> + }
> + }

Within all tasks at CAPPED_PRIO, is priority of the task used for scheduling?

<snip>

Cheers,
Balbir
Linux Technology Center
IBM ISoftware Labs
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2006-05-27 08:33    [W:1.525 / U:0.124 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site