Skip to contentSkip to conversation

sched: Skip looking at skip if next or last is set

PATCH In review Srikar Dronamraju 3 participants 4 messages Feb 18, 2013 – Feb 22, 2013 Scheduler

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 sched: Skip looking at skip if next or last is set

pick_next_entity() prefers next, then last. However code checks if the left entity can be skipped even if next / last is set.

Check if left entity should be skipped only if next/last is not set.

---
 kernel/sched/fair.c |   31 +++++++++++++++----------------
 1 files changed, 15 insertions(+), 16 deletions(-)
kernel/sched/fair.c +15 -16
index fdee793..cc97b12 100644
@@ -1900,27 +1900,26 @@ static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
 	struct sched_entity *left = se;
 
 	/*
-	 * Avoid running the skip buddy, if running something else can
-	 * be done without getting too unfair.
+	 * Someone really wants next to run. If it's not unfair, run it.
 	 */
-	if (cfs_rq->skip == se) {
-		struct sched_entity *second = __pick_next_entity(se);
+	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1) {
+		se = cfs_rq->next;
+	} else if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1) {
+		/*
+		 * Prefer last buddy, try to return the CPU to a preempted
+		 * task.
+		 */
+		se = cfs_rq->last;
+	} else if (cfs_rq->skip == left) {
+		/*
+		 * Avoid running the skip buddy, if running something else
+		 * can be done without getting too unfair.
+		 */
+		struct sched_entity *second = __pick_next_entity(left);
 		if (second && wakeup_preempt_entity(second, left) < 1)
 			se = second;
 	}
 
-	/*
-	 * Prefer last buddy, try to return the CPU to a preempted task.
-	 */
-	if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
-		se = cfs_rq->last;
-
-	/*
-	 * Someone really wants this to run. If it's not unfair, run it.
-	 */
-	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
-		se = cfs_rq->next;
-
 	clear_buddies(cfs_rq, se);
 
 	return se;
maintainer
#1 lore raw
Quoted 4 lines · Srikar Dronamraju

pick_next_entity() prefers next, then last. However code checks if the left entity can be skipped even if next / last is set.

Check if left entity should be skipped only if next/last is not set.

You fail to explain why its a problem and continue to make a horrid mess of the code..

Quoted 53 lines
---
 kernel/sched/fair.c |   31 +++++++++++++++----------------
 1 files changed, 15 insertions(+), 16 deletions(-)
kernel/sched/fair.c +15 -16
index fdee793..cc97b12 100644
@@ -1900,27 +1900,26 @@ static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
 	struct sched_entity *left = se;
 
 	/*
-	 * Avoid running the skip buddy, if running something else can
-	 * be done without getting too unfair.
+	 * Someone really wants next to run. If it's not unfair, run it.
 	 */
-	if (cfs_rq->skip == se) {
-		struct sched_entity *second = __pick_next_entity(se);
+	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1) {
+		se = cfs_rq->next;
+	} else if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1) {
+		/*
+		 * Prefer last buddy, try to return the CPU to a preempted
+		 * task.
+		 */
+		se = cfs_rq->last;
+	} else if (cfs_rq->skip == left) {
+		/*
+		 * Avoid running the skip buddy, if running something else
+		 * can be done without getting too unfair.
+		 */
+		struct sched_entity *second = __pick_next_entity(left);
 		if (second && wakeup_preempt_entity(second, left) < 1)
 			se = second;
 	}
 
-	/*
-	 * Prefer last buddy, try to return the CPU to a preempted task.
-	 */
-	if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
-		se = cfs_rq->last;
-
-	/*
-	 * Someone really wants this to run. If it's not unfair, run it.
-	 */
-	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
-		se = cfs_rq->next;
-
 	clear_buddies(cfs_rq, se);
 
 	return se;
#2 lore raw
Quoted 9 lines · Peter Zijlstra
Quoted 4 lines · Srikar Dronamraju

pick_next_entity() prefers next, then last. However code checks if the left entity can be skipped even if next / last is set.

Check if left entity should be skipped only if next/last is not set.

You fail to explain why its a problem and continue to make a horrid mess of the code..

If we look at the comments above pick_next_entity(), it states:
/*
* Pick the next process, keeping these things in mind, in this order:
* 1) keep things fair between processes/task groups
* 2) pick the "next" process, since someone really wants that to run
* 3) pick the "last" process, for cache locality
* 4) do not run the "skip" process, if something else is available */

Currently the code checks in the reverse order, though the preference is correctly maintained as listed in comments. But in some cases, we might be doing redundant checks. Lets assume next is set, then we should avoid checking for skip, last and their fairness with left.

So what I intended to do was change the order, i.e check for last only if next is not set (or was picking next was unfair wrt left) and check for "something else (second from left)" if last is not set (or picking last was unfair wrt left).

However after sending the patch, I stumbled across these links.
https://lkml.org/lkml/2012/1/16/500 and https://lkml.org/lkml/2012/1/25/195

Quoted 55 lines
Quoted 53 lines
---
 kernel/sched/fair.c |   31 +++++++++++++++----------------
 1 files changed, 15 insertions(+), 16 deletions(-)
kernel/sched/fair.c +15 -16
index fdee793..cc97b12 100644
@@ -1900,27 +1900,26 @@ static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
 	struct sched_entity *left = se;
 
 	/*
-	 * Avoid running the skip buddy, if running something else can
-	 * be done without getting too unfair.
+	 * Someone really wants next to run. If it's not unfair, run it.
 	 */
-	if (cfs_rq->skip == se) {
-		struct sched_entity *second = __pick_next_entity(se);
+	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1) {
+		se = cfs_rq->next;
+	} else if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1) {
+		/*
+		 * Prefer last buddy, try to return the CPU to a preempted
+		 * task.
+		 */
+		se = cfs_rq->last;
+	} else if (cfs_rq->skip == left) {
+		/*
+		 * Avoid running the skip buddy, if running something else
+		 * can be done without getting too unfair.
+		 */
+		struct sched_entity *second = __pick_next_entity(left);
 		if (second && wakeup_preempt_entity(second, left) < 1)
 			se = second;
 	}
 
-	/*
-	 * Prefer last buddy, try to return the CPU to a preempted task.
-	 */
-	if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
-		se = cfs_rq->last;
-
-	/*
-	 * Someone really wants this to run. If it's not unfair, run it.
-	 */
-	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
-		se = cfs_rq->next;
-
 	clear_buddies(cfs_rq, se);
 
 	return se;
Signature · 2 lines
Thanks and Regards
Srikar Dronamraju
#3 lore raw
Quoted 26 lines · Srikar Dronamraju
Quoted 9 lines · Peter Zijlstra
Quoted 4 lines · Srikar Dronamraju

pick_next_entity() prefers next, then last. However code checks if the left entity can be skipped even if next / last is set.

Check if left entity should be skipped only if next/last is not set.

You fail to explain why its a problem and continue to make a horrid mess of the code..

If we look at the comments above pick_next_entity(), it states:
/*
* Pick the next process, keeping these things in mind, in this order:
* 1) keep things fair between processes/task groups
* 2) pick the "next" process, since someone really wants that to run
* 3) pick the "last" process, for cache locality
* 4) do not run the "skip" process, if something else is available */

Currently the code checks in the reverse order, though the preference is correctly maintained as listed in comments. But in some cases, we might be doing redundant checks. Lets assume next is set, then we should avoid checking for skip, last and their fairness with left.

Quoted 7 lines

So what I intended to do was change the order, i.e check for last only if next is not set (or was picking next was unfair wrt left) and check for "something else (second from left)" if last is not set (or picking last was unfair wrt left).

However after sending the patch, I stumbled across these links.
https://lkml.org/lkml/2012/1/16/500 and https://lkml.org/lkml/2012/1/25/195

Hi, Srikar

That drag me back to the time when I'm starting to look at scheduler ;-)

Actually I give up this idea since I missed one point that the code will be optimized by the compiler, and usually it will become some logical we could not image.

My patch is correct logically, but it may not benefit scheduler a lot, I don't think there will be a benchmark show us better results, and in scheduler world, benchmark talks...

Regards,
Michael Wang

Quoted 57 lines
Quoted 56 lines
Quoted 54 lines
---
 kernel/sched/fair.c |   31 +++++++++++++++----------------
 1 files changed, 15 insertions(+), 16 deletions(-)
kernel/sched/fair.c +15 -16
index fdee793..cc97b12 100644
@@ -1900,27 +1900,26 @@ static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
 	struct sched_entity *left = se;
 
 	/*
-	 * Avoid running the skip buddy, if running something else can
-	 * be done without getting too unfair.
+	 * Someone really wants next to run. If it's not unfair, run it.
 	 */
-	if (cfs_rq->skip == se) {
-		struct sched_entity *second = __pick_next_entity(se);
+	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1) {
+		se = cfs_rq->next;
+	} else if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1) {
+		/*
+		 * Prefer last buddy, try to return the CPU to a preempted
+		 * task.
+		 */
+		se = cfs_rq->last;
+	} else if (cfs_rq->skip == left) {
+		/*
+		 * Avoid running the skip buddy, if running something else
+		 * can be done without getting too unfair.
+		 */
+		struct sched_entity *second = __pick_next_entity(left);
 		if (second && wakeup_preempt_entity(second, left) < 1)
 			se = second;
 	}
 
-	/*
-	 * Prefer last buddy, try to return the CPU to a preempted task.
-	 */
-	if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
-		se = cfs_rq->last;
-
-	/*
-	 * Someone really wants this to run. If it's not unfair, run it.
-	 */
-	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
-		se = cfs_rq->next;
-
 	clear_buddies(cfs_rq, se);
 
 	return se;