[RFC][PATCH 0/7] sched: various updates to the scheduler

[RFC][PATCH 0/7] sched: various updates to the scheduler

[Steven Rostedt]

Peter,

Can you review these patches and give your Acked-by, or explain what
might be wrong with them. No hurry, I haven't pushed them through my
full testing yet (starting that now). But I want to push them out for
3.1.

Thanks,

-- Steve


This patch set can be found in:

  git://git.kernel.org/pub/scm/linux/kernel/git/rostedt/linux-2.6-rt.git
tip/sched/core

Head SHA1: cac554411989613131d899cfb51b622ce96d5136


Hillf Danton (5):
      sched: Fix need_resched() when checking peempt
      sched: Remove noop in next_prio()
      sched: Remove noop in lowest_flag_domain()
      sched, rt: Fix rq->rt.pushable_tasks bug in push_rt_task()
      sched: Remove resetting exec_start in put_prev_task_rt()

Steven Rostedt (2):
      sched: Balance RT tasks when forked as well
      sched: Use pushable_tasks to determine next highest prio

----
 kernel/sched_fair.c |    2 +-
 kernel/sched_rt.c   |   88 +++++++++++++++++++--------------------------------
 2 files changed, 34 insertions(+), 56 deletions(-)

[RFC][PATCH 1/7] sched: Fix need_resched() when checking peempt

[Steven Rostedt]

[-- Attachment #1: 0001-sched-Fix-need_resched-when-checking-peempt.patch --]
[-- Type: text/plain, Size: 1065 bytes --]

From: Hillf Danton <dhillf@gmail.com>

The RT preempt check tests the wrong task if NEED_RESCHED is set. It currently
checks the local CPU task. It is suppose to check the task that is running on
the run queue we are about to wake another task on.

Signed-off-by: Hillf Danton <dhillf@gmail.com>
Link: http://lkml.kernel.org/r/BANLkTi=e=69xvJZ1+56xzuFyhmdN0hZHRQ@mail.gmail.com
Reviewed-by: Yong Zhang <yong.zhang0@gmail.com>
Signed-off-by: Steven Rostedt <rostedt@goodmis.org>
---
 kernel/sched_rt.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
index 88725c9..9b8d5dc 100644
--- a/kernel/sched_rt.c
+++ b/kernel/sched_rt.c
@@ -1096,7 +1096,7 @@ static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p, int flag
 	 * to move current somewhere else, making room for our non-migratable
 	 * task.
 	 */
-	if (p->prio == rq->curr->prio && !need_resched())
+	if (p->prio == rq->curr->prio && !test_tsk_need_resched(rq->curr))
 		check_preempt_equal_prio(rq, p);
 #endif
 }
-- 
1.7.4.4

[RFC][PATCH 2/7] sched: Remove noop in next_prio()

[Steven Rostedt]

[-- Attachment #1: 0002-sched-Remove-noop-in-next_prio.patch --]
[-- Type: text/plain, Size: 949 bytes --]

From: Hillf Danton <dhillf@gmail.com>

When computing the next priority for a given run-queue, the check for
RT priority of the task determined by the pick_next_highest_task_rt()
function could be removed, since only RT tasks are returned by the
function.

Reviewed-by: Yong Zhang <yong.zhang0@gmail.com>
Signed-off-by: Hillf Danton <dhillf@gmail.com>
Link: http://lkml.kernel.org/r/BANLkTimxmWiof9s5AvS3v_0X+sMiE=0x5g@mail.gmail.com
Signed-off-by: Steven Rostedt <rostedt@goodmis.org>
---
 kernel/sched_rt.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
index 9b8d5dc..a6f1f64 100644
--- a/kernel/sched_rt.c
+++ b/kernel/sched_rt.c
@@ -692,7 +692,7 @@ static inline int next_prio(struct rq *rq)
 {
 	struct task_struct *next = pick_next_highest_task_rt(rq, rq->cpu);
 
-	if (next && rt_prio(next->prio))
+	if (next)
 		return next->prio;
 	else
 		return MAX_RT_PRIO;
-- 
1.7.4.4

[RFC][PATCH 3/7] sched: Remove noop in lowest_flag_domain()

[Steven Rostedt]

[-- Attachment #1: 0003-sched-Remove-noop-in-lowest_flag_domain.patch --]
[-- Type: text/plain, Size: 795 bytes --]

From: Hillf Danton <dhillf@gmail.com>

Checking for the validity of sd is removed, since it is already
checked by the for_each_domain macro.

Signed-off-by: Hillf Danton <dhillf@gmail.com>
Link: http://lkml.kernel.org/r/BANLkTimT+Tut-3TshCDm-NiLLXrOznibNA@mail.gmail.com
Signed-off-by: Steven Rostedt <rostedt@goodmis.org>
---
 kernel/sched_fair.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c
index 433491c..47f79d0 100644
--- a/kernel/sched_fair.c
+++ b/kernel/sched_fair.c
@@ -3655,7 +3655,7 @@ static inline struct sched_domain *lowest_flag_domain(int cpu, int flag)
 	struct sched_domain *sd;
 
 	for_each_domain(cpu, sd)
-		if (sd && (sd->flags & flag))
+		if (sd->flags & flag)
 			break;
 
 	return sd;
-- 
1.7.4.4

[RFC][PATCH 4/7] sched, rt: Fix rq->rt.pushable_tasks bug in push_rt_task()

[Steven Rostedt]

[-- Attachment #1: 0004-sched-rt-Fix-rq-rt.pushable_tasks-bug-in-push_rt_tas.patch --]
[-- Type: text/plain, Size: 2139 bytes --]

From: Hillf Danton <dhillf@gmail.com>

Do not call dequeue_pushable_task() when failing to push an eligible
task, as it remains pushable, merely not at this particular moment.

Cc: Yong Zhang <yong.zhang0@gmail.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Hillf Danton <dhillf@gmail.com>
Signed-off-by: Mike Galbraith <mgalbraith@gmx.de>
Link: http://lkml.kernel.org/r/1306895385.4791.26.camel@marge.simson.net
Signed-off-by: Steven Rostedt <rostedt@goodmis.org>
---
 kernel/sched_rt.c |   15 ++++++++-------
 1 files changed, 8 insertions(+), 7 deletions(-)

diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
index a6f1f64..7737d41 100644
--- a/kernel/sched_rt.c
+++ b/kernel/sched_rt.c
@@ -1378,6 +1378,7 @@ static int push_rt_task(struct rq *rq)
 {
 	struct task_struct *next_task;
 	struct rq *lowest_rq;
+	int ret = 0;
 
 	if (!rq->rt.overloaded)
 		return 0;
@@ -1410,7 +1411,7 @@ retry:
 	if (!lowest_rq) {
 		struct task_struct *task;
 		/*
-		 * find lock_lowest_rq releases rq->lock
+		 * find_lock_lowest_rq releases rq->lock
 		 * so it is possible that next_task has migrated.
 		 *
 		 * We need to make sure that the task is still on the same
@@ -1420,12 +1421,11 @@ retry:
 		task = pick_next_pushable_task(rq);
 		if (task_cpu(next_task) == rq->cpu && task == next_task) {
 			/*
-			 * If we get here, the task hasn't moved at all, but
-			 * it has failed to push.  We will not try again,
-			 * since the other cpus will pull from us when they
-			 * are ready.
+			 * The task hasn't migrated, and is still the next
+			 * eligible task, but we failed to find a run-queue
+			 * to push it to.  Do not retry in this case, since
+			 * other cpus will pull from us when ready.
 			 */
-			dequeue_pushable_task(rq, next_task);
 			goto out;
 		}
 
@@ -1444,6 +1444,7 @@ retry:
 	deactivate_task(rq, next_task, 0);
 	set_task_cpu(next_task, lowest_rq->cpu);
 	activate_task(lowest_rq, next_task, 0);
+	ret = 1;
 
 	resched_task(lowest_rq->curr);
 
@@ -1452,7 +1453,7 @@ retry:
 out:
 	put_task_struct(next_task);
 
-	return 1;
+	return ret;
 }
 
 static void push_rt_tasks(struct rq *rq)
-- 
1.7.4.4

Re: [RFC][PATCH 4/7] sched, rt: Fix rq->rt.pushable_tasks bug in push_rt_task()

[Mike Galbraith]

On Thu, 2011-06-16 at 21:55 -0400, Steven Rostedt wrote:
> plain text document attachment
> (0004-sched-rt-Fix-rq-rt.pushable_tasks-bug-in-push_rt_tas.patch)
> From: Hillf Danton <dhillf@gmail.com>
> 
> Do not call dequeue_pushable_task() when failing to push an eligible
> task, as it remains pushable, merely not at this particular moment.
> 
> Cc: Yong Zhang <yong.zhang0@gmail.com>
> Cc: Peter Zijlstra <peterz@infradead.org>
> Signed-off-by: Hillf Danton <dhillf@gmail.com>
> Signed-off-by: Mike Galbraith <mgalbraith@gmx.de>

Mixing addresses doesn't work.  Less bouncy SOB.

Signed-off-by: Mike Galbraith <efault@gmx.de>


> Link: http://lkml.kernel.org/r/1306895385.4791.26.camel@marge.simson.net
> Signed-off-by: Steven Rostedt <rostedt@goodmis.org>
> ---
>  kernel/sched_rt.c |   15 ++++++++-------
>  1 files changed, 8 insertions(+), 7 deletions(-)
> 
> diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
> index a6f1f64..7737d41 100644
> --- a/kernel/sched_rt.c
> +++ b/kernel/sched_rt.c
> @@ -1378,6 +1378,7 @@ static int push_rt_task(struct rq *rq)
>  {
>  	struct task_struct *next_task;
>  	struct rq *lowest_rq;
> +	int ret = 0;
>  
>  	if (!rq->rt.overloaded)
>  		return 0;
> @@ -1410,7 +1411,7 @@ retry:
>  	if (!lowest_rq) {
>  		struct task_struct *task;
>  		/*
> -		 * find lock_lowest_rq releases rq->lock
> +		 * find_lock_lowest_rq releases rq->lock
>  		 * so it is possible that next_task has migrated.
>  		 *
>  		 * We need to make sure that the task is still on the same
> @@ -1420,12 +1421,11 @@ retry:
>  		task = pick_next_pushable_task(rq);
>  		if (task_cpu(next_task) == rq->cpu && task == next_task) {
>  			/*
> -			 * If we get here, the task hasn't moved at all, but
> -			 * it has failed to push.  We will not try again,
> -			 * since the other cpus will pull from us when they
> -			 * are ready.
> +			 * The task hasn't migrated, and is still the next
> +			 * eligible task, but we failed to find a run-queue
> +			 * to push it to.  Do not retry in this case, since
> +			 * other cpus will pull from us when ready.
>  			 */
> -			dequeue_pushable_task(rq, next_task);
>  			goto out;
>  		}
>  
> @@ -1444,6 +1444,7 @@ retry:
>  	deactivate_task(rq, next_task, 0);
>  	set_task_cpu(next_task, lowest_rq->cpu);
>  	activate_task(lowest_rq, next_task, 0);
> +	ret = 1;
>  
>  	resched_task(lowest_rq->curr);
>  
> @@ -1452,7 +1453,7 @@ retry:
>  out:
>  	put_task_struct(next_task);
>  
> -	return 1;
> +	return ret;
>  }
>  
>  static void push_rt_tasks(struct rq *rq)

Re: [RFC][PATCH 4/7] sched, rt: Fix rq->rt.pushable_tasks bug in push_rt_task()

[Steven Rostedt]

On Fri, 2011-06-17 at 04:33 +0200, Mike Galbraith wrote:
> On Thu, 2011-06-16 at 21:55 -0400, Steven Rostedt wrote:
> > plain text document attachment
> > (0004-sched-rt-Fix-rq-rt.pushable_tasks-bug-in-push_rt_tas.patch)
> > From: Hillf Danton <dhillf@gmail.com>
> > 
> > Do not call dequeue_pushable_task() when failing to push an eligible
> > task, as it remains pushable, merely not at this particular moment.
> > 
> > Cc: Yong Zhang <yong.zhang0@gmail.com>
> > Cc: Peter Zijlstra <peterz@infradead.org>
> > Signed-off-by: Hillf Danton <dhillf@gmail.com>
> > Signed-off-by: Mike Galbraith <mgalbraith@gmx.de>
> 
> Mixing addresses doesn't work.  Less bouncy SOB.
> 
> Signed-off-by: Mike Galbraith <efault@gmx.de>
> 

Thanks! I'm going to rebase these patches anyway. I'll update it when I
do that.

-- Steve

[RFC][PATCH 5/7] sched: Remove resetting exec_start in put_prev_task_rt()

[Steven Rostedt]

[-- Attachment #1: 0005-sched-Remove-resetting-exec_start-in-put_prev_task_r.patch --]
[-- Type: text/plain, Size: 1031 bytes --]

From: Hillf Danton <dhillf@gmail.com>

There's no reason to clean the exec_start in put_prev_task_rt() as it is reset
when the task gets back to the run queue. This saves us doing a store() in the
fast path.

Cc: Mike Galbraith <efault@gmx.de>
Cc: Yong Zhang <yong.zhang0@gmail.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Hillf Danton <dhillf@gmail.com>
Link: http://lkml.kernel.org/r/BANLkTimqWD=q6YnSDi-v9y=LMWecgEzEWg@mail.gmail.com
Signed-off-by: Steven Rostedt <rostedt@goodmis.org>
---
 kernel/sched_rt.c |    1 -
 1 files changed, 0 insertions(+), 1 deletions(-)

diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
index 7737d41..1546c1c 100644
--- a/kernel/sched_rt.c
+++ b/kernel/sched_rt.c
@@ -1166,7 +1166,6 @@ static struct task_struct *pick_next_task_rt(struct rq *rq)
 static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
 {
 	update_curr_rt(rq);
-	p->se.exec_start = 0;
 
 	/*
 	 * The previous task needs to be made eligible for pushing
-- 
1.7.4.4

[RFC][PATCH 6/7] sched: Balance RT tasks when forked as well

[Steven Rostedt]

[-- Attachment #1: 0006-sched-Balance-RT-tasks-when-forked-as-well.patch --]
[-- Type: text/plain, Size: 1852 bytes --]

From: Steven Rostedt <srostedt@redhat.com>

When a new task is woken, the code to balance the RT task is currently
skipped in the select_task_rq() call. But it will be pushed if the rq
is currently overloaded with RT tasks anyway. The issue is that we
already queued the task, and if it does get pushed, it will have to
be dequeued and requeued on the new run queue. The advantage with
pushing it first is that we avoid this requeuing as we are pushing it
off before the task is ever queued.

See commit: 318e0893ce3f524ca045f9fd9dfd567c0a6f9446 for more details.
    (sched: pre-route RT tasks on wakeup)

The return of select_task_rq() when it is not a wake up has also been
changed to return task_cpu() instead of smp_processor_id(). This is more
of a sanity because the current only other user of select_task_rq()
besides wake ups, is an exec, where task_cpu() should also be the same
as smp_processor_id(). But if it is used for other purposes, lets keep
the task on the same CPU. Why would we mant to migrate it to the current
CPU?

Signed-off-by: Steven Rostedt <rostedt@goodmis.org>
---
 kernel/sched_rt.c |    9 ++++++---
 1 files changed, 6 insertions(+), 3 deletions(-)

diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
index 1546c1c..33636d2 100644
--- a/kernel/sched_rt.c
+++ b/kernel/sched_rt.c
@@ -1005,10 +1005,12 @@ select_task_rq_rt(struct task_struct *p, int sd_flag, int flags)
 	struct rq *rq;
 	int cpu;
 
-	if (sd_flag != SD_BALANCE_WAKE)
-		return smp_processor_id();
-
 	cpu = task_cpu(p);
+
+	/* For anything but wake ups, just return the task_cpu */
+	if (sd_flag != SD_BALANCE_WAKE || sd_flag != SD_BALANCE_FORK)
+		goto out;
+
 	rq = cpu_rq(cpu);
 
 	rcu_read_lock();
@@ -1047,6 +1049,7 @@ select_task_rq_rt(struct task_struct *p, int sd_flag, int flags)
 	}
 	rcu_read_unlock();
 
+out:
 	return cpu;
 }
 
-- 
1.7.4.4

Re: [RFC][PATCH 6/7] sched: Balance RT tasks when forked as well

[Peter Zijlstra]

On Thu, 2011-06-16 at 21:55 -0400, Steven Rostedt wrote:
> +       /* For anything but wake ups, just return the task_cpu */
> +       if (sd_flag != SD_BALANCE_WAKE || sd_flag != SD_BALANCE_FORK) 

So we call select_task_rq() with SD_BALANCE_{WAKE,EXEC,FORK}, 

	(WAKE != WAKE -> 0 || WAKE != FORK -> 1) -> 1
	(EXEC != WAKE -> 1 ) -> 1
	(FORK != WAKE -> 1 ) -> 1

IOW, you never end up doing anything now.. surely you didn't mean that?!

Re: [RFC][PATCH 6/7] sched: Balance RT tasks when forked as well

[Steven Rostedt]

On Tue, 2011-07-26 at 14:25 +0200, Peter Zijlstra wrote:
> On Thu, 2011-06-16 at 21:55 -0400, Steven Rostedt wrote:
> > +       /* For anything but wake ups, just return the task_cpu */
> > +       if (sd_flag != SD_BALANCE_WAKE || sd_flag != SD_BALANCE_FORK) 
> 
> So we call select_task_rq() with SD_BALANCE_{WAKE,EXEC,FORK}, 
> 
> 	(WAKE != WAKE -> 0 || WAKE != FORK -> 1) -> 1
> 	(EXEC != WAKE -> 1 ) -> 1
> 	(FORK != WAKE -> 1 ) -> 1
> 
> IOW, you never end up doing anything now.. surely you didn't mean that?!

Bah!

s/||/&&/

:-p

Thanks!

-- Steve

Re: [RFC][PATCH 6/7] sched: Balance RT tasks when forked as well

[Peter Zijlstra]

On Tue, 2011-07-26 at 08:35 -0400, Steven Rostedt wrote:
> On Tue, 2011-07-26 at 14:25 +0200, Peter Zijlstra wrote:
> > On Thu, 2011-06-16 at 21:55 -0400, Steven Rostedt wrote:
> > > +       /* For anything but wake ups, just return the task_cpu */
> > > +       if (sd_flag != SD_BALANCE_WAKE || sd_flag != SD_BALANCE_FORK) 
> > 
> > So we call select_task_rq() with SD_BALANCE_{WAKE,EXEC,FORK}, 
> > 
> > 	(WAKE != WAKE -> 0 || WAKE != FORK -> 1) -> 1
> > 	(EXEC != WAKE -> 1 ) -> 1
> > 	(FORK != WAKE -> 1 ) -> 1
> > 
> > IOW, you never end up doing anything now.. surely you didn't mean that?!
> 
> Bah!
> 
> s/||/&&/

So you only want to rebalance on EXEC? The comment says you want to
balance on wakeups. Please as to unconfuse!?

Re: [RFC][PATCH 6/7] sched: Balance RT tasks when forked as well

[Steven Rostedt]

On Tue, 2011-07-26 at 14:36 +0200, Peter Zijlstra wrote:
> On Tue, 2011-07-26 at 08:35 -0400, Steven Rostedt wrote:
> > On Tue, 2011-07-26 at 14:25 +0200, Peter Zijlstra wrote:
> > > On Thu, 2011-06-16 at 21:55 -0400, Steven Rostedt wrote:
> > > > +       /* For anything but wake ups, just return the task_cpu */
> > > > +       if (sd_flag != SD_BALANCE_WAKE || sd_flag != SD_BALANCE_FORK) 
> > > 
> > > So we call select_task_rq() with SD_BALANCE_{WAKE,EXEC,FORK}, 
> > > 
> > > 	(WAKE != WAKE -> 0 || WAKE != FORK -> 1) -> 1
> > > 	(EXEC != WAKE -> 1 ) -> 1
> > > 	(FORK != WAKE -> 1 ) -> 1
> > > 
> > > IOW, you never end up doing anything now.. surely you didn't mean that?!
> > 
> > Bah!
> > 
> > s/||/&&/
> 
> So you only want to rebalance on EXEC? The comment says you want to
> balance on wakeups. Please as to unconfuse!?

The patch is (with fixup):

+       /* For anything but wake ups, just return the task_cpu */
+       if (sd_flag != SD_BALANCE_WAKE && sd_flag != SD_BALANCE_FORK)
+               goto out;

In other words, if it isn't a WAKE or FORK (FORK being new task wakeup)
then exit the routine.

EXEC should not rebalance.

-- Steve

[tip:sched/core] sched: Balance RT tasks when forked as well

[tip-bot for Steven Rostedt]

Commit-ID:  c37495fd0f64fc139b5a07d242bcb485174d1206
Gitweb:     http://git.kernel.org/tip/c37495fd0f64fc139b5a07d242bcb485174d1206
Author:     Steven Rostedt <srostedt@redhat.com>
AuthorDate: Thu, 16 Jun 2011 21:55:22 -0400
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Sun, 14 Aug 2011 12:00:52 +0200

sched: Balance RT tasks when forked as well

When a new task is woken, the code to balance the RT task is currently
skipped in the select_task_rq() call. But it will be pushed if the rq
is currently overloaded with RT tasks anyway. The issue is that we
already queued the task, and if it does get pushed, it will have to
be dequeued and requeued on the new run queue. The advantage with
pushing it first is that we avoid this requeuing as we are pushing it
off before the task is ever queued.

See commit 318e0893ce3f524 ("sched: pre-route RT tasks on wakeup")
for more details.

The return of select_task_rq() when it is not a wake up has also been
changed to return task_cpu() instead of smp_processor_id(). This is more
of a sanity because the current only other user of select_task_rq()
besides wake ups, is an exec, where task_cpu() should also be the same
as smp_processor_id(). But if it is used for other purposes, lets keep
the task on the same CPU. Why would we mant to migrate it to the current
CPU?

Signed-off-by: Steven Rostedt <rostedt@goodmis.org>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Hillf Danton <dhillf@gmail.com>
Link: http://lkml.kernel.org/r/20110617015919.832743148@goodmis.org
Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
 kernel/sched_rt.c |    9 ++++++---
 1 files changed, 6 insertions(+), 3 deletions(-)

diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
index 70107a3..2153a87 100644
--- a/kernel/sched_rt.c
+++ b/kernel/sched_rt.c
@@ -1017,10 +1017,12 @@ select_task_rq_rt(struct task_struct *p, int sd_flag, int flags)
 	struct rq *rq;
 	int cpu;
 
-	if (sd_flag != SD_BALANCE_WAKE)
-		return smp_processor_id();
-
 	cpu = task_cpu(p);
+
+	/* For anything but wake ups, just return the task_cpu */
+	if (sd_flag != SD_BALANCE_WAKE && sd_flag != SD_BALANCE_FORK)
+		goto out;
+
 	rq = cpu_rq(cpu);
 
 	rcu_read_lock();
@@ -1059,6 +1061,7 @@ select_task_rq_rt(struct task_struct *p, int sd_flag, int flags)
 	}
 	rcu_read_unlock();
 
+out:
 	return cpu;
 }
 

[RFC][PATCH 7/7] sched: Use pushable_tasks to determine next highest prio

[Steven Rostedt]

[-- Attachment #1: 0007-sched-Use-pushable_tasks-to-determine-next-highest-p.patch --]
[-- Type: text/plain, Size: 5933 bytes --]

From: Steven Rostedt <srostedt@redhat.com>

Hillf Danton proposed a patch (see link) that cleaned up the
sched_rt code that calculates the priority of the next highest priority
task to be used in finding run queues to pull from.

His patch removed the calculating of the next prio to just use the current
prio when deteriming if we should examine a run queue to pull from. The problem
with his patch was that it caused more false checks. Because we check a run
queue for pushable tasks if the current priority of that run queue is higher
in priority than the task about to run on our run queue. But after grabbing
the locks and doing the real check, we find that there may not be a task
that has a higher prio task to pull. Thus the locks were taken with nothing to
do.

I added some trace_printks() to record when and how many times the run queue
locks were taken to check for pullable tasks, compared to how many times we
pulled a task.

With the current method, it was:

  3806 locks taken vs 2812 pulled tasks

With Hillf's patch:

  6728 locks taken vs 2804 pulled tasks

The number of times locks were taken to pull a task went up almost double with
no more success rate.

But his patch did get me thinking. When we look at the priority of the highest
task to consider taking the locks to do a pull, a failure to pull can be one
of the following: (in order of most likely)

 o RT task was pushed off already between the check and taking the lock
 o Waiting RT task can not be migrated
 o RT task's CPU affinity does not include the target run queue's CPU
 o RT task's priority changed between the check and taking the lock

And with Hillf's patch, the thing that caused most of the failures, is
the RT task to pull was not at the right priority to pull (not greater than
the current RT task priority on the target run queue).

Most of the above cases we can't help. But the current method does not check
if the next highest prio RT task can be migrated or not, and if it can not,
we still grab the locks to do the test (we don't find out about this fact until
after we have the locks). I thought about this case, and realized that the
pushable task plist that is maintained only holds RT tasks that can migrate.
If we move the calculating of the next highest prio task from the inc/dec_rt_task()
functions into the queuing of the pushable tasks, then we only measure the
priorities of those tasks that we push, and we get this basically for free.

Not only does this patch make the code a little more efficient, it cleans it
up and makes it a little simpler.

Thanks to Hillf Danton for inspiring me on this patch.

Cc: Hillf Danton <dhillf@gmail.com>
Cc: Gregory Haskins <ghaskins@novell.com>
Link: http://lkml.kernel.org/r/BANLkTimQ67180HxCx5vgMqumqw1EkFh3qg@mail.gmail.com
Signed-off-by: Steven Rostedt <rostedt@goodmis.org>
---
 kernel/sched_rt.c |   61 +++++++++++++++-------------------------------------
 1 files changed, 18 insertions(+), 43 deletions(-)

diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
index 33636d2..19abd04 100644
--- a/kernel/sched_rt.c
+++ b/kernel/sched_rt.c
@@ -124,21 +124,33 @@ static void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
 	update_rt_migration(rt_rq);
 }
 
+static inline int has_pushable_tasks(struct rq *rq)
+{
+	return !plist_head_empty(&rq->rt.pushable_tasks);
+}
+
 static void enqueue_pushable_task(struct rq *rq, struct task_struct *p)
 {
 	plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks);
 	plist_node_init(&p->pushable_tasks, p->prio);
 	plist_add(&p->pushable_tasks, &rq->rt.pushable_tasks);
+
+	/* Update the highest prio pushable task */
+	if (p->prio < rq->rt.highest_prio.next)
+		rq->rt.highest_prio.next = p->prio;
 }
 
 static void dequeue_pushable_task(struct rq *rq, struct task_struct *p)
 {
 	plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks);
-}
 
-static inline int has_pushable_tasks(struct rq *rq)
-{
-	return !plist_head_empty(&rq->rt.pushable_tasks);
+	/* Update the new highest prio pushable task */
+	if (has_pushable_tasks(rq)) {
+		p = plist_first_entry(&rq->rt.pushable_tasks,
+				      struct task_struct, pushable_tasks);
+		rq->rt.highest_prio.next = p->prio;
+	} else
+		rq->rt.highest_prio.next = MAX_RT_PRIO;
 }
 
 #else
@@ -686,47 +698,13 @@ static void update_curr_rt(struct rq *rq)
 
 #if defined CONFIG_SMP
 
-static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu);
-
-static inline int next_prio(struct rq *rq)
-{
-	struct task_struct *next = pick_next_highest_task_rt(rq, rq->cpu);
-
-	if (next)
-		return next->prio;
-	else
-		return MAX_RT_PRIO;
-}
-
 static void
 inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
 {
 	struct rq *rq = rq_of_rt_rq(rt_rq);
 
-	if (prio < prev_prio) {
-
-		/*
-		 * If the new task is higher in priority than anything on the
-		 * run-queue, we know that the previous high becomes our
-		 * next-highest.
-		 */
-		rt_rq->highest_prio.next = prev_prio;
-
-		if (rq->online)
-			cpupri_set(&rq->rd->cpupri, rq->cpu, prio);
-
-	} else if (prio == rt_rq->highest_prio.curr)
-		/*
-		 * If the next task is equal in priority to the highest on
-		 * the run-queue, then we implicitly know that the next highest
-		 * task cannot be any lower than current
-		 */
-		rt_rq->highest_prio.next = prio;
-	else if (prio < rt_rq->highest_prio.next)
-		/*
-		 * Otherwise, we need to recompute next-highest
-		 */
-		rt_rq->highest_prio.next = next_prio(rq);
+	if (rq->online && prio < prev_prio)
+		cpupri_set(&rq->rd->cpupri, rq->cpu, prio);
 }
 
 static void
@@ -734,9 +712,6 @@ dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
 {
 	struct rq *rq = rq_of_rt_rq(rt_rq);
 
-	if (rt_rq->rt_nr_running && (prio <= rt_rq->highest_prio.next))
-		rt_rq->highest_prio.next = next_prio(rq);
-
 	if (rq->online && rt_rq->highest_prio.curr != prev_prio)
 		cpupri_set(&rq->rd->cpupri, rq->cpu, rt_rq->highest_prio.curr);
 }
-- 
1.7.4.4

Re: [RFC][PATCH 0/7] sched: various updates to the scheduler

[Steven Rostedt]

On Thu, 2011-06-16 at 21:55 -0400, Steven Rostedt wrote:
> Peter,
> 
> Can you review these patches and give your Acked-by, or explain what
> might be wrong with them. No hurry, I haven't pushed them through my
> full testing yet (starting that now). But I want to push them out for
> 3.1.
> 
> Thanks,
> 
> -- Steve
> 
> 
> This patch set can be found in:
> 
>   git://git.kernel.org/pub/scm/linux/kernel/git/rostedt/linux-2.6-rt.git
> tip/sched/core
> 
> Head SHA1: cac554411989613131d899cfb51b622ce96d5136
> 
> 
> Hillf Danton (5):
>       sched: Fix need_resched() when checking peempt

You don't need to review this one. I just realized that I pushed that
already for 3.0 pull.

Thanks!

-- Steve



>       sched: Remove noop in next_prio()
>       sched: Remove noop in lowest_flag_domain()
>       sched, rt: Fix rq->rt.pushable_tasks bug in push_rt_task()
>       sched: Remove resetting exec_start in put_prev_task_rt()
> 
> Steven Rostedt (2):
>       sched: Balance RT tasks when forked as well
>       sched: Use pushable_tasks to determine next highest prio
> 
> ----
>  kernel/sched_fair.c |    2 +-
>  kernel/sched_rt.c   |   88 +++++++++++++++++++--------------------------------
>  2 files changed, 34 insertions(+), 56 deletions(-)