[PATCH] sched: avoid overpull when pulling RT task

[PATCH] sched: avoid overpull when pulling RT task

[Hillf Danton]

When pulling RT task for a given runqueue, pulling is continued even
after certain RT tasks get pulled, in case there are still higher
priority tasks on other runqueues, though it is low likelihood as the
comment says. The load of of this runqueue, on other hand, should also
be concerned. If it is overloaded, the low likelihood should be
abandoned to avoid overpull.

Signed-off-by: Hillf Danton <dhillf@gmail.com>
---
 kernel/sched_rt.c |    5 +++++
 1 files changed, 5 insertions(+), 0 deletions(-)

diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
index 14c764b..b425ca1 100644
--- a/kernel/sched_rt.c
+++ b/kernel/sched_rt.c
@@ -1508,6 +1508,11 @@ static int pull_rt_task(struct rq *this_rq)
 		}
 skip:
 		double_unlock_balance(this_rq, src_rq);
+
+		/* if pulled we have to also avoid overpull */
+		if (ret == 1)
+			if (likely(rt_overloaded(this_rq)))
+				break;
 	}

 	return ret;

Re: [PATCH] sched: avoid overpull when pulling RT task

[Mike Galbraith]

On Sun, 2011-05-15 at 12:35 +0800, Hillf Danton wrote:
> When pulling RT task for a given runqueue, pulling is continued even
> after certain RT tasks get pulled, in case there are still higher
> priority tasks on other runqueues, though it is low likelihood as the
> comment says. The load of of this runqueue, on other hand, should also
> be concerned. If it is overloaded, the low likelihood should be
> abandoned to avoid overpull.
> 
> Signed-off-by: Hillf Danton <dhillf@gmail.com>
> ---
>  kernel/sched_rt.c |    5 +++++
>  1 files changed, 5 insertions(+), 0 deletions(-)
> 
> diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
> index 14c764b..b425ca1 100644
> --- a/kernel/sched_rt.c
> +++ b/kernel/sched_rt.c
> @@ -1508,6 +1508,11 @@ static int pull_rt_task(struct rq *this_rq)
>  		}
>  skip:
>  		double_unlock_balance(this_rq, src_rq);
> +
> +		/* if pulled we have to also avoid overpull */
> +		if (ret == 1)
> +			if (likely(rt_overloaded(this_rq)))
> +				break;
>  	}
> 
>  	return ret;

Hm.

It looks to me like you should remove the rt_overloaded() test (and
function) entirely instead.  If you look at pull usage, the intent is
that system wide, higher priority tasks run before lower.

I don't think it matters much if we pull too much, since what we pull
while traversing is ever increasing in priority _and waiting_ anyway.
We may do a bit more work than strictly necessary on the way to the
highest priority runnable task, but what matters most is that highest
priority gets to the CPU first, which testing for overload can stymie.

(seems pulling more than one could turn out either good or bad for any
but the highest priority task though, lacking crystal ball)

	-Mike

Re: [PATCH] sched: avoid overpull when pulling RT task

[Hillf Danton]

On Sun, May 15, 2011 at 2:35 PM, Mike Galbraith <efault@gmx.de> wrote:
> On Sun, 2011-05-15 at 12:35 +0800, Hillf Danton wrote:
>> When pulling RT task for a given runqueue, pulling is continued even
>> after certain RT tasks get pulled, in case there are still higher
>> priority tasks on other runqueues, though it is low likelihood as the
>> comment says. The load of of this runqueue, on other hand, should also
>> be concerned. If it is overloaded, the low likelihood should be
>> abandoned to avoid overpull.
>>
>> Signed-off-by: Hillf Danton <dhillf@gmail.com>
>> ---
>>  kernel/sched_rt.c |    5 +++++
>>  1 files changed, 5 insertions(+), 0 deletions(-)
>>
>> diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
>> index 14c764b..b425ca1 100644
>> --- a/kernel/sched_rt.c
>> +++ b/kernel/sched_rt.c
>> @@ -1508,6 +1508,11 @@ static int pull_rt_task(struct rq *this_rq)
>>               }
>>  skip:
>>               double_unlock_balance(this_rq, src_rq);
>> +
>> +             /* if pulled we have to also avoid overpull */
>> +             if (ret == 1)
>> +                     if (likely(rt_overloaded(this_rq)))
>> +                             break;
>>       }
>>
>>       return ret;
>
> Hm.
>
> It looks to me like you should remove the rt_overloaded() test (and
> function) entirely instead.  If you look at pull usage, the intent is
> that system wide, higher priority tasks run before lower.
>
> I don't think it matters much if we pull too much, since what we pull
> while traversing is ever increasing in priority _and waiting_ anyway.
> We may do a bit more work than strictly necessary on the way to the
> highest priority runnable task, but what matters most is that highest
> priority gets to the CPU first, which testing for overload can stymie.
>
> (seems pulling more than one could turn out either good or bad for any
> but the highest priority task though, lacking crystal ball)
>
Hi Mike

It is solid reason that the highest priority should get CPU, and along
this direction the info about the highest priority is add in struct root_domain,
then the overpull looks relieved, though not cured, please review again.

thanks
Hillf
---

--- a/kernel/sched.c	2011-04-27 11:48:50.000000000 +0800
+++ b/kernel/sched.c	2011-05-15 18:54:28.000000000 +0800
@@ -426,6 +426,8 @@ struct root_domain {
 	 */
 	cpumask_var_t rto_mask;
 	atomic_t rto_count;
+	/* the highest prio in rto_mask */
+	int rto_prio;
 	struct cpupri cpupri;
 };

@@ -6634,6 +6636,8 @@ static int init_rootdomain(struct root_d

 	if (cpupri_init(&rd->cpupri) != 0)
 		goto free_rto_mask;
+
+	rd->rto_prio = MAX_RT_PRIO;
 	return 0;

 free_rto_mask:
--- b/kernel/sched_rt.c	2011-04-27 11:48:50.000000000 +0800
+++ b/kernel/sched_rt.c	2011-05-15 19:02:50.000000000 +0800
@@ -108,6 +108,10 @@ static void inc_rt_migration(struct sche
 		rt_rq->rt_nr_migratory++;

 	update_rt_migration(rt_rq);
+
+	if (rt_rq->overloaded &&
+	    rq_of_rt_rq(rt_rq)->rd->rto_prio > rt_task_of(rt_se)->prio)
+		rq_of_rt_rq(rt_rq)->rd->rto_prio = rt_task_of(rt_se)->prio;
 }

 static void dec_rt_migration(struct sched_rt_entity *rt_se, struct
rt_rq *rt_rq)
@@ -1425,9 +1429,7 @@ static int pull_rt_task(struct rq *this_
 	int this_cpu = this_rq->cpu, ret = 0, cpu;
 	struct task_struct *p;
 	struct rq *src_rq;
-
-	if (likely(!rt_overloaded(this_rq)))
-		return 0;
+	int rto_prio_pulled = 0;

 	for_each_cpu(cpu, this_rq->rd->rto_mask) {
 		if (this_cpu == cpu)
@@ -1481,6 +1483,8 @@ static int pull_rt_task(struct rq *this_
 				goto skip;

 			ret = 1;
+			if (p->prio <= this_rq->rd->rto_prio)
+				rto_prio_pulled = 1;

 			deactivate_task(src_rq, p, 0);
 			set_task_cpu(p, this_cpu);
@@ -1494,6 +1498,9 @@ static int pull_rt_task(struct rq *this_
 		}
 skip:
 		double_unlock_balance(this_rq, src_rq);
+
+		if (rto_prio_pulled)
+			break;
 	}

 	return ret;

Re: [PATCH] sched: avoid overpull when pulling RT task

[Hillf Danton]

On Sun, May 15, 2011 at 2:35 PM, Mike Galbraith <efault@gmx.de> wrote:
> On Sun, 2011-05-15 at 12:35 +0800, Hillf Danton wrote:
>> When pulling RT task for a given runqueue, pulling is continued even
>> after certain RT tasks get pulled, in case there are still higher
>> priority tasks on other runqueues, though it is low likelihood as the
>> comment says. The load of of this runqueue, on other hand, should also
>> be concerned. If it is overloaded, the low likelihood should be
>> abandoned to avoid overpull.
>>
>> Signed-off-by: Hillf Danton <dhillf@gmail.com>
>> ---
>>  kernel/sched_rt.c |    5 +++++
>>  1 files changed, 5 insertions(+), 0 deletions(-)
>>
>> diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
>> index 14c764b..b425ca1 100644
>> --- a/kernel/sched_rt.c
>> +++ b/kernel/sched_rt.c
>> @@ -1508,6 +1508,11 @@ static int pull_rt_task(struct rq *this_rq)
>>               }
>>  skip:
>>               double_unlock_balance(this_rq, src_rq);
>> +
>> +             /* if pulled we have to also avoid overpull */
>> +             if (ret == 1)
>> +                     if (likely(rt_overloaded(this_rq)))
>> +                             break;
>>       }
>>
>>       return ret;
>
> Hm.
>
> It looks to me like you should remove the rt_overloaded() test (and
> function) entirely instead.  If you look at pull usage, the intent is
> that system wide, higher priority tasks run before lower.
>
> I don't think it matters much if we pull too much, since what we pull
> while traversing is ever increasing in priority _and waiting_ anyway.
> We may do a bit more work than strictly necessary on the way to the
> highest priority runnable task, but what matters most is that highest
> priority gets to the CPU first, which testing for overload can stymie.
>
> (seems pulling more than one could turn out either good or bad for any
> but the highest priority task though, lacking crystal ball)
>
Hi Mike

To win the crystal ball, I take another try.

In the following patch, pulling is played in two rounds. In the first round,
the highest priority task is determined with no pull operation. Pulling is
carried out in the second round, and if the highest priority task is pulled,
pulling could be stopped when overload detected, to relieve overpull.

Please review again, thanks.

Hillf
---

--- a/kernel/sched_rt.c	2011-04-27 11:48:50.000000000 +0800
+++ b/kernel/sched_rt.c	2011-05-16 20:42:18.000000000 +0800
@@ -1425,10 +1425,11 @@ static int pull_rt_task(struct rq *this_
 	int this_cpu = this_rq->cpu, ret = 0, cpu;
 	struct task_struct *p;
 	struct rq *src_rq;
+	int highest_prio = MAX_RT_PRIO;
+	int highest_pulled = 0;
+	int first_round = 1;

-	if (likely(!rt_overloaded(this_rq)))
-		return 0;
-
+again:
 	for_each_cpu(cpu, this_rq->rd->rto_mask) {
 		if (this_cpu == cpu)
 			continue;
@@ -1480,6 +1481,18 @@ static int pull_rt_task(struct rq *this_
 			if (p->prio < src_rq->curr->prio)
 				goto skip;

+			/*
+			 * To avoid overpull, we play pulling in two rounds,and
+			 * the highest task is determined in the first round.
+			 */
+			if (first_round) {
+				if (p->prio < highest_prio)
+					highest_prio = p->prio;
+				goto skip;
+			}
+			if (p->prio <= highest_prio)
+				highest_pulled = 1;
+
 			ret = 1;

 			deactivate_task(src_rq, p, 0);
@@ -1494,6 +1507,15 @@ static int pull_rt_task(struct rq *this_
 		}
 skip:
 		double_unlock_balance(this_rq, src_rq);
+
+		if (highest_pulled && rt_overloaded(this_rq))
+			break;
+	}
+
+	if (first_round && highest_prio != MAX_RT_PRIO) {
+		/* try to pull higher tasks on other RQs */
+		first_round = 0;
+		goto again;
 	}

 	return ret;

Re: [PATCH] sched: avoid overpull when pulling RT task

[Mike Galbraith]

On Mon, 2011-05-16 at 21:14 +0800, Hillf Danton wrote:

> In the following patch, pulling is played in two rounds. In the first round,
> the highest priority task is determined with no pull operation. Pulling is
> carried out in the second round, and if the highest priority task is pulled,
> pulling could be stopped when overload detected, to relieve overpull.
> 
> Please review again, thanks.

Traversing runqueues twice to avoid some potential task bouncing during
overload situation seems like a really bad trade.  Not to mention that
between pass one and pass two, the world turns under your feet.

You could do it in one pass by leaving the victim's runqueue locked
unless you find a better victim I suppose.  Dunno, guess it all depends
on how much benefit the is to pulling only highest, which I can't answer
(my gut says "none, only more pain to be had here").

	-Mike

Re: [PATCH] sched: avoid overpull when pulling RT task

[Hillf Danton]

On Mon, May 16, 2011 at 10:11 PM, Mike Galbraith <efault@gmx.de> wrote:
> On Mon, 2011-05-16 at 21:14 +0800, Hillf Danton wrote:
>
>> In the following patch, pulling is played in two rounds. In the first round,
>> the highest priority task is determined with no pull operation. Pulling is
>> carried out in the second round, and if the highest priority task is pulled,
>> pulling could be stopped when overload detected, to relieve overpull.
>>
>> Please review again, thanks.
>
> Traversing runqueues twice to avoid some potential task bouncing during
> overload situation seems like a really bad trade.  Not to mention that
> between pass one and pass two, the world turns under your feet.
>
> You could do it in one pass by leaving the victim's runqueue locked
> unless you find a better victim I suppose.  Dunno, guess it all depends
> on how much benefit the is to pulling only highest, which I can't answer
> (my gut says "none, only more pain to be had here").
>
Hi Mike

Efforts are put on the puller's side, but bad result is reached:(

Another patch is prepared, in which pusher is asked to do the hard works,
say pushees and tasks are selected.

Unlike puller who only concerns one runqueue that accepts the pulled tasks,
pusher delivers tasks to more runqueues, so the overpull could get bigger.

Please review again, thanks.

Hillf
---

--- a/kernel/sched_rt.c	2011-04-27 11:48:50.000000000 +0800
+++ b/kernel/sched_rt.c	2011-05-17 22:18:20.000000000 +0800
@@ -51,11 +51,6 @@ static inline struct rt_rq *rt_rq_of_se(

 #ifdef CONFIG_SMP

-static inline int rt_overloaded(struct rq *rq)
-{
-	return atomic_read(&rq->rd->rto_count);
-}
-
 static inline void rt_set_overload(struct rq *rq)
 {
 	if (!rq->online)
@@ -1420,83 +1415,14 @@ static void push_rt_tasks(struct rq *rq)
 		;
 }

-static int pull_rt_task(struct rq *this_rq)
+static void pull_rt_task(struct rq *this_rq)
 {
-	int this_cpu = this_rq->cpu, ret = 0, cpu;
-	struct task_struct *p;
-	struct rq *src_rq;
-
-	if (likely(!rt_overloaded(this_rq)))
-		return 0;
+	int this_cpu = this_rq->cpu, cpu;

 	for_each_cpu(cpu, this_rq->rd->rto_mask) {
-		if (this_cpu == cpu)
-			continue;
-
-		src_rq = cpu_rq(cpu);
-
-		/*
-		 * Don't bother taking the src_rq->lock if the next highest
-		 * task is known to be lower-priority than our current task.
-		 * This may look racy, but if this value is about to go
-		 * logically higher, the src_rq will push this task away.
-		 * And if its going logically lower, we do not care
-		 */
-		if (src_rq->rt.highest_prio.next >=
-		    this_rq->rt.highest_prio.curr)
-			continue;
-
-		/*
-		 * We can potentially drop this_rq's lock in
-		 * double_lock_balance, and another CPU could
-		 * alter this_rq
-		 */
-		double_lock_balance(this_rq, src_rq);
-
-		/*
-		 * Are there still pullable RT tasks?
-		 */
-		if (src_rq->rt.rt_nr_running <= 1)
-			goto skip;
-
-		p = pick_next_highest_task_rt(src_rq, this_cpu);
-
-		/*
-		 * Do we have an RT task that preempts
-		 * the to-be-scheduled task?
-		 */
-		if (p && (p->prio < this_rq->rt.highest_prio.curr)) {
-			WARN_ON(p == src_rq->curr);
-			WARN_ON(!p->se.on_rq);
-
-			/*
-			 * There's a chance that p is higher in priority
-			 * than what's currently running on its cpu.
-			 * This is just that p is wakeing up and hasn't
-			 * had a chance to schedule. We only pull
-			 * p if it is lower in priority than the
-			 * current task on the run queue
-			 */
-			if (p->prio < src_rq->curr->prio)
-				goto skip;
-
-			ret = 1;
-
-			deactivate_task(src_rq, p, 0);
-			set_task_cpu(p, this_cpu);
-			activate_task(this_rq, p, 0);
-			/*
-			 * We continue with the search, just in
-			 * case there's an even higher prio task
-			 * in another runqueue. (low likelihood
-			 * but possible)
-			 */
-		}
-skip:
-		double_unlock_balance(this_rq, src_rq);
+		if (cpu != this_cpu)
+			push_rt_tasks(cpu_rq(cpu));
 	}
-
-	return ret;
 }

 static void pre_schedule_rt(struct rq *rq, struct task_struct *prev)

Re: [PATCH] sched: avoid overpull when pulling RT task

[Mike Galbraith]

On Tue, 2011-05-17 at 22:25 +0800, Hillf Danton wrote:
> On Mon, May 16, 2011 at 10:11 PM, Mike Galbraith <efault@gmx.de> wrote:
> > On Mon, 2011-05-16 at 21:14 +0800, Hillf Danton wrote:
> >
> >> In the following patch, pulling is played in two rounds. In the first round,
> >> the highest priority task is determined with no pull operation. Pulling is
> >> carried out in the second round, and if the highest priority task is pulled,
> >> pulling could be stopped when overload detected, to relieve overpull.
> >>
> >> Please review again, thanks.
> >
> > Traversing runqueues twice to avoid some potential task bouncing during
> > overload situation seems like a really bad trade.  Not to mention that
> > between pass one and pass two, the world turns under your feet.
> >
> > You could do it in one pass by leaving the victim's runqueue locked
> > unless you find a better victim I suppose.  Dunno, guess it all depends
> > on how much benefit the is to pulling only highest, which I can't answer
> > (my gut says "none, only more pain to be had here").
> >
> Hi Mike
> 
> Efforts are put on the puller's side, but bad result is reached:(

Don't be discouraged by bad results, they're unavoidable.  Keep on
looking, thinking and poking.

> Another patch is prepared, in which pusher is asked to do the hard works,
> say pushees and tasks are selected.
> 
> Unlike puller who only concerns one runqueue that accepts the pulled tasks,
> pusher delivers tasks to more runqueues, so the overpull could get bigger.
> 
> Please review again, thanks.

Sorry, but I don't have any free time atm, my cup runneth over bigtime.
Best suggestion I can offer is measure, and measure again.  No theory
can compete with cold hard numbers.

	-Mike

Re: [PATCH] sched: avoid overpull when pulling RT task

[Steven Rostedt]

On Tue, May 17, 2011 at 10:25:54PM +0800, Hillf Danton wrote:
> 
> Efforts are put on the puller's side, but bad result is reached:(
> 
> Another patch is prepared, in which pusher is asked to do the hard works,
> say pushees and tasks are selected.
> 
> Unlike puller who only concerns one runqueue that accepts the pulled tasks,
> pusher delivers tasks to more runqueues, so the overpull could get bigger.
> 
> Please review again, thanks.
> 

Have you actually observed an overpull? And if so, how bad was it?

I hate to be fixing bugs that don't really exist.

-- Steve