Skip to contentSkip to conversation

Prevent immediate process rescheduling

PATCH In review Mark Langsdorf 5 participants 9 messages Sep 18, 2009 – Sep 20, 2009

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Prevent immediate process rescheduling

Prevent the scheduler from immediately rescheduling a process that just yielded if there is another process available.

Originally suggested by Mike Galbraith ([email protected]).

---
 kernel/sched_fair.c |   16 +++++++++++++++-
 1 files changed, 15 insertions(+), 1 deletions(-)
kernel/sched_fair.c +15 -1
index 652e8bd..4fad08f 100644
@@ -353,11 +353,25 @@ static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
 {
 	struct rb_node *left = cfs_rq->rb_leftmost;
+	struct sched_entity *se, *curr;
 
 	if (!left)
 		return NULL;
 
-	return rb_entry(left, struct sched_entity, run_node);
+	se = rb_entry(left, struct sched_entity, run_node);
+	curr = &current->se;
+
+	/* 
+	 * Don't select the entity who just tried to schedule away
+	 * if there's another entity available.
+	 */
+	if (unlikely(se == curr && cfs_rq->nr_running > 1)) {
+		struct rb_node *next_node = rb_next(&curr->run_node);
+		if (next_node)
+			se = rb_entry(next_node, struct sched_entity, run_node);
+	}
+
+	return se;
 }
 
 static struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
Signature · 1 line
1.6.0.2
#1 lore raw

(fixed the Cc: lines)

Quoted 29 lines · Mark Langsdorf

Prevent the scheduler from immediately rescheduling a process that just yielded if there is another process available.

Originally suggested by Mike Galbraith ([email protected]).

---
 kernel/sched_fair.c |   16 +++++++++++++++-
 1 files changed, 15 insertions(+), 1 deletions(-)
kernel/sched_fair.c +6 -1
index 652e8bd..4fad08f 100644
@@ -353,11 +353,25 @@ static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
 {
 	struct rb_node *left = cfs_rq->rb_leftmost;
+	struct sched_entity *se, *curr;
 
 	if (!left)
 		return NULL;
 
-	return rb_entry(left, struct sched_entity, run_node);
+	se = rb_entry(left, struct sched_entity, run_node);
+	curr = &current->se;
+
+	/* 
+	 * Don't select the entity who just tried to schedule away

kernel/sched_fair.c static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) · line 375

Quoted 10 lines
kernel/sched_fair.c +9 -0
+	 * if there's another entity available.
+	 */
+	if (unlikely(se == curr && cfs_rq->nr_running > 1)) {
+		struct rb_node *next_node = rb_next(&curr->run_node);
+		if (next_node)
+			se = rb_entry(next_node, struct sched_entity, run_node);
+	}
+
+	return se;
 }

I suspect some real workload is the motivation of this - what is that workload?

Ingo

#2 lore raw
Quoted 52 lines

-----Original Message-----
From: Ingo Molnar [mailto:[email protected]]
Sent: Friday, September 18, 2009 2:55 PM
To: Langsdorf, Mark; Peter Zijlstra; Mike Galbraith
Cc: [email protected]
Subject: Re: [PATCH] Prevent immediate process rescheduling

(fixed the Cc: lines)

kernel/sched_fair.c static void __dequeue_entity(struct

Quoted 15 lines · Mark Langsdorf

Prevent the scheduler from immediately rescheduling a process that just yielded if there is another process available.

Originally suggested by Mike Galbraith ([email protected]).

---
 kernel/sched_fair.c |   16 +++++++++++++++-
 1 files changed, 15 insertions(+), 1 deletions(-)
kernel/sched_fair.c +0 -0
index 652e8bd..4fad08f 100644
@@ -353,11 +353,25 @@ static void __dequeue_entity(struct 

cfs_rq *cfs_rq, struct sched_entity *se)

kernel/sched_fair.c static void __dequeue_entity(struct · line 353

Quoted 1 line
kernel/sched_fair.c +0 -0
 static struct sched_entity *__pick_next_entity(struct 

cfs_rq *cfs_rq)

Quoted 9 lines
kernel/sched_fair.c +2 -1
 {
 	struct rb_node *left = cfs_rq->rb_leftmost;
+	struct sched_entity *se, *curr;
 
 	if (!left)
 		return NULL;
 
-	return rb_entry(left, struct sched_entity, run_node);
+	se = rb_entry(left, struct sched_entity, run_node);

kernel/sched_fair.c static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)

Quoted 10 lines
kernel/sched_fair.c +10 -0
+	curr = &current->se;
+
+	/* 
+	 * Don't select the entity who just tried to schedule away
+	 * if there's another entity available.
+	 */
+	if (unlikely(se == curr && cfs_rq->nr_running > 1)) {
+		struct rb_node *next_node = rb_next(&curr->run_node);
+		if (next_node)
+			se = rb_entry(next_node, struct 

sched_entity, run_node);

Quoted 7 lines

kernel/sched_fair.c static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) · line 375

Quoted 4 lines
kernel/sched_fair.c +3 -0
+	}
+
+	return se;
 }

I suspect some real workload is the motivation of this - what is that workload?

Thanks for fixing the cc lines.

The next patch I submitted enables the Pause Filter feature from the most recent AMD Operton processors. Pause Filter lets us detect when a KVM guest VCPU is spinning useless on a contended lock because the lockholder VCPU isn't scheduled. Ideally, we'd like to switch to that VCPU thread, but at a minimum, we'd like to meaningful yield the contending VCPU. This patch prevents schedule() from just rescheduling the thread that is trying to yield, and didn't have any performance regressions in my tests.

-Mark Langsdorf
Operating System Research Center
AMD

#3 lore raw
In reply to Ingo Molnar
Quoted 13 lines · Ingo Molnar
Quoted 13 lines
kernel/sched_fair.c +1 -0
index 652e8bd..4fad08f 100644
@@ -353,11 +353,25 @@ static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
 {
 	struct rb_node *left = cfs_rq->rb_leftmost;
+	struct sched_entity *se, *curr;
 
 	if (!left)
 		return NULL;
 
Quoted 16 lines
Quoted 6 lines
kernel/sched_fair.c +5 -1
-	return rb_entry(left, struct sched_entity, run_node);
+	se = rb_entry(left, struct sched_entity, run_node);
+	curr = &current->se;
+
+	/* 
+	 * Don't select the entity who just tried to schedule away

kernel/sched_fair.c static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) · line 375

Quoted 10 lines
kernel/sched_fair.c +9 -0
+	 * if there's another entity available.
+	 */
+	if (unlikely(se == curr && cfs_rq->nr_running > 1)) {
+		struct rb_node *next_node = rb_next(&curr->run_node);
+		if (next_node)
+			se = rb_entry(next_node, struct sched_entity, run_node);
+	}
+
+	return se;
 }

Really hate this change though,. doesn't seem right to not pick the same task again if its runnable. Bad for cache footprint.

The scenario is quite common for stuff like:

CPU0 CPU1

set_task_state(TASK_INTERRUPTIBLE)

if (cond)

  goto out;
                                     <--- ttwu()

schedule();

#4 lore raw
Quoted 5 lines · Peter Zijlstra

Really hate this change though,. doesn't seem right to not pick the same task again if its runnable. Bad for cache footprint.

The scenario is quite common for stuff like:

Quoted 8 lines

CPU0 CPU1

set_task_state(TASK_INTERRUPTIBLE)

if (cond)

  goto out;
                                     <--- ttwu()

schedule();

It also resists the scheduler's built in need to close spread, too much of which can seriously damage latency for others later when the friendly task later decides it wants to run hard. OTOH, when it is a voluntary schedule, not selecting another task is resisting the programmer.

Conundrum.

Another problem with that change is that it doesn't do diddly spit if the top two are trying to yield, they'll just spin together.

Sounds like Mark's case really needs a gentle_yield() that moves the task behind next, and slightly beyond if they are too close, but which also ignores the request entirely if the gap is too large.

-Mike

#6 lore raw
In reply to Peter Zijlstra
Quoted 38 lines · Peter Zijlstra
Quoted 22 lines · Ingo Molnar
Quoted 22 lines
kernel/sched_fair.c +9 -1
index 652e8bd..4fad08f 100644
@@ -353,11 +353,25 @@ static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
  static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
  {
  	struct rb_node *left = cfs_rq->rb_leftmost;
+	struct sched_entity *se, *curr;
 
  	if (!left)
  		return NULL;
 
-	return rb_entry(left, struct sched_entity, run_node);
+	se = rb_entry(left, struct sched_entity, run_node);
+	curr =&current->se;
+
+	/*
+	 * Don't select the entity who just tried to schedule away
+	 * if there's another entity available.
+	 */
+	if (unlikely(se == curr&&  cfs_rq->nr_running>  1)) {
Quoted 8 lines

kernel/sched_fair.c static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) · line 376

Quoted 8 lines
kernel/sched_fair.c +6 -0
+		struct rb_node *next_node = rb_next(&curr->run_node);
+		if (next_node)
+			se = rb_entry(next_node, struct sched_entity, run_node);
+	}
+
+	return se;
  }
 

Really hate this change though,. doesn't seem right to not pick the same task again if its runnable. Bad for cache footprint.

The scenario is quite common for stuff like:

Quoted 10 lines

CPU0 CPU1

set_task_state(TASK_INTERRUPTIBLE)

if (cond)

   goto out;
                                      <--- ttwu()

schedule();

I agree, yielding should be explicitly requested.

Also, on a heavily overcommitted box an undirected yield might take quite a long time to find the thread that's holding the lock. I think a yield_to() will be a lot better:

- we can pick one of the vcpus belonging to the same guest to improve the probability that the lock actually get released
- we avoid an issue when the other vcpus are on different runqueues (in which case the current patch does nothing)
- we can fix the accounting by donating vruntime from current to the yielded-to vcpu

Signature · 1 line
Do not meddle in the internals of kernels, for they are subtle and quick to panic.
#5 lore raw
In reply to Mike Galbraith
Quoted 3 lines · Mike Galbraith

Sounds like Mark's case really needs a gentle_yield() that moves the task behind next, and slightly beyond if they are too close, but which also ignores the request entirely if the gap is too large.

Did that, it sucks. (not surprising really, yield _always_ sucked;)

-Mike

#7 lore raw
In reply to Avi Kivity
Quoted 6 lines
Quoted 1 line

Really hate this change though,. doesn't seem right to not

pick the same

Quoted 1 line

task again if its runnable. Bad for cache footprint.

I agree, yielding should be explicitly requested.

Quoted 7 lines

Also, on a heavily overcommitted box an undirected yield might take quite a long time to find the thread that's holding the lock.
I think a
yield_to() will be a lot better:

- we can pick one of the vcpus belonging to the same guest to improve the probability that the lock actually get released

Is there a way to find the other vcpus belonging to the same guest? I poked around at that, but couldn't find one.

Quoted 4 lines

- we avoid an issue when the other vcpus are on different runqueues (in which case the current patch does nothing)
- we can fix the accounting by donating vruntime from current to the yielded-to vcpu

I may need someone to walk me through the vruntime donation but that's secondary to finding the other vcpus.

-Mark Langsdorf
Operating System Research Center
AMD

#8 lore raw
Quoted 7 lines · Mark
Quoted 3 lines

- we can pick one of the vcpus belonging to the same guest to improve the probability that the lock actually get released

Is there a way to find the other vcpus belonging to the same guest? I poked around at that, but couldn't find one.

vcpu->kvm->vcpus[]. It doesn't give you the task_struct, but we can easily save it in vcpu_load() and release it in vcpu_put().

Signature · 1 line
Do not meddle in the internals of kernels, for they are subtle and quick to panic.