lkml.org 
[lkml]   [2008]   [Jul]   [3]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH] sched: fix unfairness when upgrade weight
Peter,

In the scenarios below, processes are changing weights. In the
scheduling literature, people instead talk about processes leaving and
joining the system. A weight change is viewed as a special case where
a process leaves with its old weight and re-joins with its new weight.
It is well known that allowing tasks with non-zero lag to leave causes
the sorts of problems you are observing -- in fact, this is one of the
"classic" issues people have looked at w.r.t. fairness. We have looked
at this extensively on multiprocessors. However, your scenarios (as I
understand them) really involve just a single processor. The most
accessible resource I know on this issue that just focuses on
uniprocessors is:

A Proportional Share Resource Allocation Algorithm For Real-Time,
Time-Shared Systems
IEEE Real-Time Systems Symposium, December 1996.
http://www.cs.unc.edu/~jeffay/papers/RTSS-96a.pdf

A slightly longer version of this paper exists that contains some of
the missing proofs, but I always have trouble locating it on-line (it's
in a non-obvious place, I think). I've cc'ed Kevin Jeffay, one of the
co-authors. Maybe he can point you to the longer version.

BTW, if I recall correctly, the very lag scaling idea you mentioned is
discussed in Kevin's paper.

Hope this helps.

-Jim Anderson


Quoting Peter Zijlstra <peterz@infradead.org>:

> Hi Lai,
>
> On Mon, 2008-06-30 at 14:27 +0800, Lai Jiangshan wrote:
>> When two or more process upgrade their priority,
>> unfairness will happen, several of them may get all cpu-usage,
>> and the other cannot be scheduled to run for a long time.
>>
>> example:
>> # (create 2 processes and set affinity to cpu#0)
>> # renice 19 pid1 pid2
>> # renice -19 pid1 pid2
>>
>> step3 upgrade the 2 processes' weight, these 2 processes should
>> share the cpu#0 as soon as possible after step3, and any of them
>> should get 50% cpu-usage. But sometimes one of them gets all cpu-usage
>> for tens of seconds before they share the cpu#0.
>>
>> fair-group example:
>> # mkdir 1 2 (create 2 fair-groups)
>> # (create 2 processes and set affinity to cpu#0)
>> # echo pid1 > 1/tasks ; echo pid2 > 2/tasks
>> # echo 2 > 1/cpu.shares ; echo 2 > 2/cpu.shares
>> # echo $((2**18)) > 1/cpu.shares ; echo $((2**18)) > 2/cpu.shares
>>
>> The reason why such unfairness happened:
>>
>> When a sched_entity is running, if its weight is low, its vruntime
>> increases by a large value every time and if its weight
>> is high, its vruntime increases by a small value.
>>
>> So when the two sched_entity's weight is low, they will still
>> fairness even if difference of their vruntime is large, but if
>> their weight are upgraded, this large difference of vruntime
>> will bring unfairness.
>>
>> example:
>> se1's vruntime se2's vruntime
>> 1000M (R) 1020M
>> (assume vruntime is increases by about 50M every time)
>> (R) 1050M 1020M
>> 1050M (R) 1070M
>> (R) 1100M 1070M
>> 1100M (R) 1120M
>> (fairness, even if difference of their vruntime is large)
>> (upgrade their weight, vruntime is increases by about 10K)
>> (R) 1100M+10K 1120M
>> (R) 1100M+20K 1120M
>> (R) 1100M+30K 1120M
>> (R) 1100M+40K 1120M
>> (R) 1100M+50K 1120M
>> (se1 gets all cpu-usage for long time (mybe about tens
>> of seconds))
>> (unfairness, difference=20M is too large for new weight)
>
> My initial response to this email was: sure, that's because you cannot
> renice two tasks atomically - we'll just have to live with that.
>
> However after a bit more thought it occurred to me this is because we're
> changing the weight of a task with non-zero lag.
>
> I think the proper solution to this problem is to scale the lag
> according to the change in weights. But lets ask James, who is an expert
> in this area.
>
>
> So while I think you're right in that we have an issue, I don't like
> your solution.
>
> How about something like these patches (compile tested only).
>
> ---
> Subject: sched: fair: avg_vruntime
> From: Peter Zijlstra <a.p.zijlstra@chello.nl>
>
> In order to implement a deadline scheduler we need to be able to test
> eligibility. This requires knowing the current virtual time. We use a
> property
> of fair schedulers to determine this in an numerically stable way, namely the
> sum of all lags is 0. Therefore the average of all virtual times is the
> position of lag=0.
>
> We can't just take the average of vruntime - as it will use the full range
> of its u64 and will wrap around. Instead we'll use the average of
> (vruntime - min_vruntime)
>
> \Sum_{i}^{n} 1/n (v_{i} - v) = 1/n (\Sum_{i}^{n} v_{i}) - vn
>
> By factoring out the 1/n (never storing that) we avoid rounding, which
> would bring an accumulating error.
>
> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
> ---
> kernel/sched.c | 3 ++
> kernel/sched_debug.c | 3 ++
> kernel/sched_fair.c | 68
> ++++++++++++++++++++++++++++++++++++++++++---------
> 3 files changed, 62 insertions(+), 12 deletions(-)
>
> Index: linux-2.6/kernel/sched.c
> ===================================================================
> --- linux-2.6.orig/kernel/sched.c 2008-07-02 17:56:31.000000000 +0200
> +++ linux-2.6/kernel/sched.c 2008-07-02 23:43:44.000000000 +0200
> @@ -377,6 +377,9 @@ struct cfs_rq {
> struct load_weight load;
> unsigned long nr_running;
>
> + long nr_queued;
> + s64 avg_vruntime;
> +
> u64 exec_clock;
> u64 min_vruntime;
> u64 pair_start;
> Index: linux-2.6/kernel/sched_debug.c
> ===================================================================
> --- linux-2.6.orig/kernel/sched_debug.c 2008-07-02 17:56:30.000000000 +0200
> +++ linux-2.6/kernel/sched_debug.c 2008-07-02 23:36:09.000000000 +0200
> @@ -161,6 +161,9 @@ void print_cfs_rq(struct seq_file *m, in
> SPLIT_NS(spread0));
> SEQ_printf(m, " .%-30s: %ld\n", "nr_running", cfs_rq->nr_running);
> SEQ_printf(m, " .%-30s: %ld\n", "load", cfs_rq->load.weight);
> + SEQ_printf(m, " .%-30s: %Ld.%06ld\n", "avg_vruntime",
> + SPLIT_NS(avg_vruntime(cfs_rq)));
> +
> #ifdef CONFIG_SCHEDSTATS
> #define P(n) SEQ_printf(m, " .%-30s: %d\n", #n, rq->n);
>
> Index: linux-2.6/kernel/sched_fair.c
> ===================================================================
> --- linux-2.6.orig/kernel/sched_fair.c 2008-07-02 17:56:30.000000000 +0200
> +++ linux-2.6/kernel/sched_fair.c 2008-07-02 23:43:44.000000000 +0200
> @@ -221,6 +221,55 @@ static inline s64 entity_key(struct cfs_
> return se->vruntime - cfs_rq->min_vruntime;
> }
>
> +static void
> +avg_vruntime_add(struct cfs_rq *cfs_rq, struct sched_entity *se)
> +{
> + s64 key = entity_key(cfs_rq, se);
> + cfs_rq->avg_vruntime += key;
> + cfs_rq->nr_queued++;
> +}
> +
> +static void
> +avg_vruntime_sub(struct cfs_rq *cfs_rq, struct sched_entity *se)
> +{
> + s64 key = entity_key(cfs_rq, se);
> + cfs_rq->avg_vruntime -= key;
> + cfs_rq->nr_queued--;
> +}
> +
> +static inline
> +void avg_vruntime_update(struct cfs_rq *cfs_rq, s64 delta)
> +{
> + cfs_rq->avg_vruntime -= cfs_rq->nr_queued * delta;
> +}
> +
> +static u64 avg_vruntime(struct cfs_rq *cfs_rq)
> +{
> + s64 avg = cfs_rq->avg_vruntime;
> +
> + if (cfs_rq->nr_queued)
> + avg = div_s64(avg, cfs_rq->nr_queued);
> +
> + return cfs_rq->min_vruntime + avg;
> +}
> +
> +/*
> + * maintain cfs_rq->min_vruntime to be a monotonic increasing
> + * value tracking the leftmost vruntime in the tree.
> + */
> +static void
> +update_min_vruntime(struct cfs_rq *cfs_rq, struct sched_entity *se)
> +{
> + /*
> + * open coded max_vruntime() to allow updating avg_vruntime
> + */
> + s64 delta = (s64)(se->vruntime - cfs_rq->min_vruntime);
> + if (delta > 0) {
> + avg_vruntime_update(cfs_rq, delta);
> + cfs_rq->min_vruntime = se->vruntime;
> + }
> +}
> +
> /*
> * Enqueue an entity into the rb-tree:
> */
> @@ -232,6 +281,8 @@ static void __enqueue_entity(struct cfs_
> s64 key = entity_key(cfs_rq, se);
> int leftmost = 1;
>
> + avg_vruntime_add(cfs_rq, se);
> +
> /*
> * Find the right place in the rbtree:
> */
> @@ -256,12 +307,7 @@ static void __enqueue_entity(struct cfs_
> */
> if (leftmost) {
> cfs_rq->rb_leftmost = &se->run_node;
> - /*
> - * maintain cfs_rq->min_vruntime to be a monotonic increasing
> - * value tracking the leftmost vruntime in the tree.
> - */
> - cfs_rq->min_vruntime =
> - max_vruntime(cfs_rq->min_vruntime, se->vruntime);
> + update_min_vruntime(cfs_rq, se);
> }
>
> rb_link_node(&se->run_node, parent, link);
> @@ -272,17 +318,13 @@ static void __dequeue_entity(struct cfs_
> {
> if (cfs_rq->rb_leftmost == &se->run_node) {
> struct rb_node *next_node;
> - struct sched_entity *next;
>
> next_node = rb_next(&se->run_node);
> cfs_rq->rb_leftmost = next_node;
>
> if (next_node) {
> - next = rb_entry(next_node,
> - struct sched_entity, run_node);
> - cfs_rq->min_vruntime =
> - max_vruntime(cfs_rq->min_vruntime,
> - next->vruntime);
> + update_min_vruntime(cfs_rq, rb_entry(next_node,
> + struct sched_entity, run_node));
> }
> }
>
> @@ -290,6 +332,8 @@ static void __dequeue_entity(struct cfs_
> cfs_rq->next = NULL;
>
> rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
> +
> + avg_vruntime_sub(cfs_rq, se);
> }
>
> static inline struct rb_node *first_fair(struct cfs_rq *cfs_rq)
>
>
> ---
> Subject: sched: non-zero lag renice
> From: Peter Zijlstra <a.p.zijlstra@chello.nl>
>
> In the case where we renice a task which has non-zero lag, its not clear
> what needs to be done, as it has a deviation from fairness.
>
> Try to compensate this by scaling the lag (deviation from fairness) by the
> change in weights.
>
> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
> ---
> kernel/sched.c | 14 +++++++-------
> kernel/sched_fair.c | 26 ++++++++++++++++++++++++++
> 2 files changed, 33 insertions(+), 7 deletions(-)
>
> Index: linux-2.6/kernel/sched.c
> ===================================================================
> --- linux-2.6.orig/kernel/sched.c 2008-07-02 23:35:24.000000000 +0200
> +++ linux-2.6/kernel/sched.c 2008-07-02 23:40:12.000000000 +0200
> @@ -4780,12 +4780,9 @@ void set_user_nice(struct task_struct *p
>
> if (on_rq) {
> enqueue_task(rq, p, 0);
> - /*
> - * If the task increased its priority or is running and
> - * lowered its priority, then reschedule its CPU:
> - */
> - if (delta < 0 || (delta > 0 && task_running(rq, p)))
> - resched_task(rq->curr);
> +
> + check_class_changed(rq, p, p->sched_class, old_prio,
> + task_running(rq, p));
> }
> out_unlock:
> task_rq_unlock(rq, &flags);
> @@ -8527,6 +8524,7 @@ void sched_move_task(struct task_struct
> static void __set_se_shares(struct sched_entity *se, unsigned long shares)
> {
> struct cfs_rq *cfs_rq = se->cfs_rq;
> + unsigned long old_weight = se->load.weight;
> int on_rq;
>
> on_rq = se->on_rq;
> @@ -8536,8 +8534,10 @@ static void __set_se_shares(struct sched
> se->load.weight = shares;
> se->load.inv_weight = 0;
>
> - if (on_rq)
> + if (on_rq) {
> enqueue_entity(cfs_rq, se, 0);
> + prio_changed_entity(cfs_rq, se, old_weight, shares);
> + }
> }
>
> static void set_se_shares(struct sched_entity *se, unsigned long shares)
> Index: linux-2.6/kernel/sched_fair.c
> ===================================================================
> --- linux-2.6.orig/kernel/sched_fair.c 2008-07-02 23:35:37.000000000 +0200
> +++ linux-2.6/kernel/sched_fair.c 2008-07-02 23:36:37.000000000 +0200
> @@ -1680,6 +1680,28 @@ static void task_new_fair(struct rq *rq,
> resched_task(rq->curr);
> }
>
> +static void prio_changed_entity(struct cfs_rq *cfs_rq, struct
> sched_entity *se,
> + unsigned long old_weight, unsigned long new_weight)
> +{
> + u64 avg;
> + s64 lag;
> +
> + if (old_weight == new_weight)
> + return;
> +
> + dequeue_entity(cfs_rq, se, 0);
> +
> + avg = avg_vruntime(cfs_rq);
> + lag = (s64)(se->vruntime - avg);
> +
> + lag *= new_weight;
> + lag = div_s64(lag, old_weight);
> +
> + se->vruntime = avg + lag;
> +
> + enqueue_entity(cfs_rq, se, 0);
> +}
> +
> /*
> * Priority of the task has changed. Check to see if we preempt
> * the current task.
> @@ -1687,6 +1709,10 @@ static void task_new_fair(struct rq *rq,
> static void prio_changed_fair(struct rq *rq, struct task_struct *p,
> int oldprio, int running)
> {
> + prio_changed_entity(&rq->cfs, &p->se,
> + prio_to_weight[USER_PRIO(oldprio)],
> + prio_to_weight[USER_PRIO(p->prio)]);
> +
> /*
> * Reschedule if we are currently running on this runqueue and
> * our priority decreased, or if we are not currently running on
>
>
>




\
 
 \ /
  Last update: 2008-07-03 14:55    [W:0.073 / U:0.988 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site