[RFC] sched: use plist in pulling RT task

[RFC] sched: use plist in pulling RT task

[Hillf Danton]

Hi Steven

It is pushable tasks that are pulled, and they are maintained by runqueue with
plist, so the plist can be also used by puller for free.

Thanks

Hillf
---
 kernel/sched_rt.c |   35 ++++++++++++++++++++++-------------
 1 files changed, 22 insertions(+), 13 deletions(-)

diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
index b03cd89..f4eecf9 100644
--- a/kernel/sched_rt.c
+++ b/kernel/sched_rt.c
@@ -1471,6 +1471,7 @@ static int pull_rt_task(struct rq *this_rq)
 	int this_cpu = this_rq->cpu, ret = 0, cpu;
 	struct task_struct *p;
 	struct rq *src_rq;
+	int pulled_prio = MAX_RT_PRIO;

 	if (likely(!rt_overloaded(this_rq)))
 		return 0;
@@ -1481,6 +1482,8 @@ static int pull_rt_task(struct rq *this_rq)

 		src_rq = cpu_rq(cpu);

+		if (src_rq->rt.highest_prio.next >= pulled_prio)
+			continue;
 		/*
 		 * Don't bother taking the src_rq->lock if the next highest
 		 * task is known to be lower-priority than our current task.
@@ -1502,18 +1505,19 @@ static int pull_rt_task(struct rq *this_rq)
 		/*
 		 * Are there still pullable RT tasks?
 		 */
-		if (src_rq->rt.rt_nr_running <= 1)
+		if (! has_pushable_tasks(src_rq))
 			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->on_rq);
+		plist_for_each_entry(p, &src_rq->rt.pushable_tasks,
+						    pushable_tasks) {
+			if (p->prio >= pulled_prio)
+				break;
+			if (! (p->prio < this_rq->rt.highest_prio.curr))
+				break;

 			/*
 			 * There's a chance that p is higher in priority
@@ -1524,22 +1528,27 @@ static int pull_rt_task(struct rq *this_rq)
 			 * current task on the run queue
 			 */
 			if (p->prio < src_rq->curr->prio)
-				goto skip;
+				continue;
+
+			if (! cpumask_test_cpu(this_cpu, &p->cpus_allowed))
+				continue;

+			pulled_prio = p->prio;
 			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)
-			 */
+			break;
 		}
 skip:
 		double_unlock_balance(this_rq, src_rq);
+		/*
+		 * We continue with the search, just in
+		 * case there's an even higher prio task
+		 * in another runqueue. (low likelihood
+		 * but possible)
+		 */
 	}

 	return ret;

Re: [RFC] sched: use plist in pulling RT task

[Steven Rostedt]

On Fri, 2011-06-24 at 20:53 +0800, Hillf Danton wrote:
> Hi Steven
> 
> It is pushable tasks that are pulled, and they are maintained by runqueue with
> plist, so the plist can be also used by puller for free.
> 
> Thanks
> 
> Hillf
> ---
>  kernel/sched_rt.c |   35 ++++++++++++++++++++++-------------
>  1 files changed, 22 insertions(+), 13 deletions(-)
> 
> diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
> index b03cd89..f4eecf9 100644
> --- a/kernel/sched_rt.c
> +++ b/kernel/sched_rt.c
> @@ -1471,6 +1471,7 @@ static int pull_rt_task(struct rq *this_rq)
>  	int this_cpu = this_rq->cpu, ret = 0, cpu;
>  	struct task_struct *p;
>  	struct rq *src_rq;
> +	int pulled_prio = MAX_RT_PRIO;

Set pulled_prio = this_rq->rt.highest_prio.curr

> 
>  	if (likely(!rt_overloaded(this_rq)))
>  		return 0;
> @@ -1481,6 +1482,8 @@ static int pull_rt_task(struct rq *this_rq)
> 
>  		src_rq = cpu_rq(cpu);
> 
> +		if (src_rq->rt.highest_prio.next >= pulled_prio)
> +			continue;

Have this replace the if statement below the following comment. Keep the
comment though (move it above this if statement).

>  		/*
>  		 * Don't bother taking the src_rq->lock if the next highest
>  		 * task is known to be lower-priority than our current task.
> @@ -1502,18 +1505,19 @@ static int pull_rt_task(struct rq *this_rq)
>  		/*
>  		 * Are there still pullable RT tasks?
>  		 */
> -		if (src_rq->rt.rt_nr_running <= 1)
> +		if (! has_pushable_tasks(src_rq))
                       ^
                       |
                Stop putting in these spaces, they don't belong.


>  			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->on_rq);
> +		plist_for_each_entry(p, &src_rq->rt.pushable_tasks,
> +						    pushable_tasks) {
> +			if (p->prio >= pulled_prio)
> +				break;
> +			if (! (p->prio < this_rq->rt.highest_prio.curr))

Again, remove the space after the '!'. Better yet, why the '!'? A more
readable statement would be (p->prio >= this_rq->rt.highest_prio.curr).
But because you'll change pulled_prio to start at curr anyway, we can
remove this second condition altogether.

> +				break;
> 
>  			/*
>  			 * There's a chance that p is higher in priority
> @@ -1524,22 +1528,27 @@ static int pull_rt_task(struct rq *this_rq)
>  			 * current task on the run queue
>  			 */
>  			if (p->prio < src_rq->curr->prio)
> -				goto skip;
> +				continue;

The above will take some testing. Keep it out for now and add it as a
second patch. If a higher RT task is about to run, it will soon
schedule, and if there's more RT tasks, it will do the pushing. Lets let
the other rq do the work. But it may end up being that doing it now may
be better. This is something that will require testing and benchmarking
to figure out what to do.

> +
> +			if (! cpumask_test_cpu(this_cpu, &p->cpus_allowed))
> +				continue;
> 
> +			pulled_prio = p->prio;
>  			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)
> -			 */
> +			break;
>  		}
>  skip:
>  		double_unlock_balance(this_rq, src_rq);
> +		/*
> +		 * We continue with the search, just in
> +		 * case there's an even higher prio task
> +		 * in another runqueue. (low likelihood
> +		 * but possible)

Since the above comment is no longer indented, fix it to not be so
condensed.

-- Steve

> +		 */
>  	}
> 
>  	return ret;

Re: [RFC] sched: use plist in pulling RT task

[Hillf Danton]

Hi Steven

It is reprepared according to your comments, difference from the last version
is the following,
1, pulled_prio is dropped since it is no more than the highest curr,
2, test p->prio < src_rq->curr->prio is kept as it was,
3, cleanup of a few typo.

Thanks

Hillf
---
 kernel/sched_rt.c |   21 +++++++++------------
 1 files changed, 9 insertions(+), 12 deletions(-)

diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
index b03cd89..b5aca9c 100644
--- a/kernel/sched_rt.c
+++ b/kernel/sched_rt.c
@@ -1502,18 +1502,17 @@ static int pull_rt_task(struct rq *this_rq)
 		/*
 		 * Are there still pullable RT tasks?
 		 */
-		if (src_rq->rt.rt_nr_running <= 1)
+		if (!has_pushable_tasks(src_rq))
 			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->on_rq);
+		plist_for_each_entry(p, &src_rq->rt.pushable_tasks,
+						    pushable_tasks) {
+			if (p->prio >= this_rq->rt.highest_prio.curr)
+				break;

 			/*
 			 * There's a chance that p is higher in priority
@@ -1526,17 +1525,15 @@ static int pull_rt_task(struct rq *this_rq)
 			if (p->prio < src_rq->curr->prio)
 				goto skip;

+			if (!cpumask_test_cpu(this_cpu, &p->cpus_allowed))
+				continue;
+
 			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)
-			 */
+			break;
 		}
 skip:
 		double_unlock_balance(this_rq, src_rq);