CPU scheduler: Simplified interactive bonus mechanism

This patch implements a prototype version of a simplified interactive bonus mechanism. The mechanism does not attempt to identify interactive tasks and give them a bonus (like the current mechanism does) but instead attacks the problem that the bonuses are supposed to fix, unacceptable interactive latency, directly.

It does this by measuring every interactive latency and using a Kalman filter to estimate a running average of each tasks' interactive latency.
This average is then compared to an "unacceptable interactive latency"
value and if it is above this the task's interactive bonus is increased and otherwise it is compared to an "acceptable interactive latency" value and if it is above this value the task's interactive bonus is decreased. This results in the the task's tending to stabilize at a value that keeps its interactive latency between the two limits.

As a first approximation this mechanism assumes that all uninterruptible sleeps are not interactive and that all interruptible sleeps are unless they are tagged with the TASK_NONINTERACTIVE flag.

Advantages:

1. Simple and (arguably) easy to understand mechanism.
2. Tasks only get interactive bonuses when they need them and this should reduce the amount of preemption that occurs which in turn should reduce the context switching rate.
3. It seems to work (at least for me).

Problems addressed:

1. If a task that has acquired an interactive bonus suddenly becomes CPU bound and interactive bonuses are only assessed at wake up they will retain their bonus. This problem is addressed by decrementing all tasks interactive bonuses at the end of their time slice.

Problems not addressed:

1. Like the current mechanism, this mechanism is sub optimal if non interactive sleeps are identified as interactive. This problem be fixed with more widespread (but judicious) use of TASK_INTERACTIVE.

Things that could be better:

1. The mechanism for decreasing interactive bonuses for CPU bound tasks could be better targetted.

Possible Modifications:

1. Increase the maximum available interactive bonus to 19.
2. Do not award interactive bonuses to tasks with nice values greater than zero on the assumption that this is a declaration that interactive latency is not an issue for these tasks.
3. Move the smoothing from the interactive latency to the interactive bonus. I.e. use the raw interactive latency to decide whether the current bonus is increased, decreased or left alone but use a Kalman filter to smooth the bonus value.

---

Your comments on this proposal are requested.

---
  fs/proc/array.c       |    4
  include/linux/sched.h |   19 ++
  kernel/sched.c        |  259 +++++++++++-----------------------------
  3 files changed, 90 insertions(+), 192 deletions(-)

Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
  -- Ambrose Bierce

Index: GIT_lial/fs/proc/array.c
===================================================================
@@ -165,7 +165,7 @@ static inline char * task_state(struct t
 	read_lock(&tasklist_lock);
 	buffer += sprintf(buffer,
 		"State:\t%s\n"
-		"SleepAVG:\t%lu%%\n"
+		"IALatencyAVG:\t%llu nsec\n"
 		"Tgid:\t%d\n"
 		"Pid:\t%d\n"
 		"PPid:\t%d\n"

@@ -173,7 +173,7 @@ static inline char * task_state(struct t
 		"Uid:\t%d\t%d\t%d\t%d\n"
 		"Gid:\t%d\t%d\t%d\t%d\n",
 		get_task_state(p),
-		(p->sleep_avg/1024)*100/(1020000000/1024),
+		IAL_AVG_RND(p->avg_ia_latency),
 	       	p->tgid,
 		p->pid, pid_alive(p) ? p->group_leader->real_parent->tgid : 0,
 		pid_alive(p) && p->ptrace ? p->parent->pid : 0,

Index: GIT_lial/include/linux/sched.h
===================================================================
@@ -683,6 +683,19 @@ static inline void prefetch_stack(struct
 struct audit_context;		/* See audit.c */
 struct mempolicy;
 
+/*
+ * Fixed denominator rational numbers for use estimating task's average
+ * interactive latency
+ */
+#define IAL_AVG_OFFSET 4
+/*
+ * Get the rounded integer value of a scheduling statistic average field
+ * Needs to be public for printing average interactive latency in
+ * fs/proc/array.c
+ */
+#define IAL_AVG_RND(x) \
+	(((x) + (1 << (IAL_AVG_OFFSET - 1))) >> (IAL_AVG_OFFSET))
+
 struct task_struct {
 	volatile long state;	/* -1 unrunnable, 0 runnable, >0 stopped */
 	struct thread_info *thread_info;

@@ -695,16 +708,15 @@ struct task_struct {
 #if defined(CONFIG_SMP) && defined(__ARCH_WANT_UNLOCKED_CTXSW)
 	int oncpu;
 #endif
-	int prio, static_prio;
+	int prio, static_prio, ia_bonus;
 	struct list_head run_list;
 	prio_array_t *array;
 
 	unsigned short ioprio;
 
-	unsigned long sleep_avg;
+	unsigned long long avg_ia_latency;
 	unsigned long long timestamp, last_ran;
 	unsigned long long sched_time; /* sched_clock time spent running */
-	int activated;
 
 	unsigned long policy;
 	cpumask_t cpus_allowed;

@@ -908,6 +920,7 @@ do { if (atomic_dec_and_test(&(tsk)->usa
 #define PF_SYNCWRITE	0x00200000	/* I am doing a sync write */
 #define PF_BORROWED_MM	0x00400000	/* I am a kthread doing use_mm */
 #define PF_RANDOMIZE	0x00800000	/* randomize virtual address space */
+#define PF_IA_WAKE_UP   0x01000000      /* just woken from an interactive sleep */
 
 /*
  * Only the _current_ task can read/write to tsk->flags, but other

If we're going to redo the interactivity estimator I happen to have a whole cpu scheduler design that is interactive by design without being a state machine that I've been hacking / maintining / debugging for 2 years that many people are already using in production...

Cheers,
Con

What do you mean interactive by design (presumably as opposed to the current scheduler which is not interactive by design)?

And what do you mean by not being a state machine?

Back on topic: I don't think that this patch isn't clearly better than what currently exists, nor would require less testing than any other large scale changes to the scheduler behaviour.

So, as Con seems to imply, it is JASW (just another scheduler rewrite). Not that there's anything wrong with that... except it is not really a good fix for a problem with the current scheduler.

Thanks,
Nick

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

I assume that the double negative here is accidental and you mean that this scheduler isn't clearly better than the current one.

Not a rewrite just some major surgery to one small part (at least when compared to nicksched, staircase and the SPA schedulers). This doesn't effect the run queue structure or the load balancing mechanisms. Or, for that matter, even the bonus mechanism itself other than the calculation of the bonus as the way the bonus is applied once calculated is unchanged.

Probably not in its present form but with a little refinement I think that it may provide a solution. As I see it the current strategy of trying to identify interactive tasks and then giving them bonuses is the cause of most of the remaining problems because it's hard to do and if you get it wrong and identify non interactive tasks as interactive tasks it can have long lasting bad effects on the scheduling quality. So I think a strategy that makes bonuses more ephemeral has some chance of success. Only time and testing will tell.

I think that the big advantage of the patch (at the moment) is that it's easy to understand. Which in turn makes it easier to tweak.

Peter

Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce

given the experience, i'm quite reluctant to do that. We should rather concentrate on trying to fix the rare odd case that gets misjudged, than trying to invent totally new mechanism that happen to get _that_ case right. (and most likely get alot of other cases wrong.)

Ingo

Yep.

Well, the runqueue structure is the "easy" part of it. And load balancing should not be changed at all[*] by any of these things because we are talking about a per-CPU runqueue model.

[*] Apart from obvious and really hard to analyse things like which task is
actually running at a point in time, and changing the cache-hotness of things...

OK maybe it isn't as large scale a change as one of the rewrites, however it still is going to probably wildly change behaviour of situations outside the little box you analysed and found it to be an improvement for.

But points to you for experimenting and trying new things. Don't let me put you off because I'm not much of an expert on ingosched so it may not be as large a change as I'm making it out to be.

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

i think we could give this one a workout in -mm, to see the actual effects. Would you mind to merge this to -mm's scheduler queue, to right after sched-add-sched_batch-policy.patch?

Ingo

i have done this for latest -mm, see the patch below (i also merged your patch to the SCHED_BATCH patch's effects), but the resulting kernel has really bad interactivity: e.g. simply starting 4 CPU hogs on a 2-CPU system slows down shell commands like 'ls' noticeably. So NACK for the time being.

Ingo

--------
This patch implements a prototype version of a simplified interactive bonus mechanism. The mechanism does not attempt to identify interactive tasks and give them a bonus (like the current mechanism does) but instead attacks the problem that the bonuses are supposed to fix, unacceptable interactive latency, directly.

It does this by measuring every interactive latency and using a Kalman filter to estimate a running average of each tasks' interactive latency.
This average is then compared to an "unacceptable interactive latency"
value and if it is above this the task's interactive bonus is increased and otherwise it is compared to an "acceptable interactive latency" value and if it is above this value the task's interactive bonus is decreased. This results in the the task's tending to stabilize at a value that keeps its interactive latency between the two limits.

As a first approximation this mechanism assumes that all uninterruptible sleeps are not interactive and that all interruptible sleeps are unless they are tagged with the TASK_NONINTERACTIVE flag.

Advantages:

1. Simple and (arguably) easy to understand mechanism.
2. Tasks only get interactive bonuses when they need them and this should reduce the amount of preemption that occurs which in turn should reduce the context switching rate.
3. It seems to work (at least for me).

Problems addressed:

1. If a task that has acquired an interactive bonus suddenly becomes CPU bound and interactive bonuses are only assessed at wake up they will retain their bonus. This problem is addressed by decrementing all tasks interactive bonuses at the end of their time slice.

Problems not addressed:

1. Like the current mechanism, this mechanism is sub optimal if non interactive sleeps are identified as interactive. This problem be fixed with more widespread (but judicious) use of TASK_INTERACTIVE.

Things that could be better:

1. The mechanism for decreasing interactive bonuses for CPU bound tasks could be better targetted.

Possible Modifications:

1. Increase the maximum available interactive bonus to 19.
2. Do not award interactive bonuses to tasks with nice values greater than zero on the assumption that this is a declaration that interactive latency is not an issue for these tasks.
3. Move the smoothing from the interactive latency to the interactive bonus. I.e. use the raw interactive latency to decide whether the current bonus is increased, decreased or left alone but use a Kalman filter to smooth the bonus value.

 fs/proc/array.c       |    4 
 include/linux/sched.h |   20 +++
 kernel/sched.c        |  273 ++++++++++++++------------------------------------
 3 files changed, 99 insertions(+), 198 deletions(-)

Index: linux/fs/proc/array.c
===================================================================
@@ -165,7 +165,7 @@ static inline char * task_state(struct t
 	read_lock(&tasklist_lock);
 	buffer += sprintf(buffer,
 		"State:\t%s\n"
-		"SleepAVG:\t%lu%%\n"
+		"IALatencyAVG:\t%llu nsec\n"
 		"Tgid:\t%d\n"
 		"Pid:\t%d\n"
 		"PPid:\t%d\n"

@@ -173,7 +173,7 @@ static inline char * task_state(struct t
 		"Uid:\t%d\t%d\t%d\t%d\n"
 		"Gid:\t%d\t%d\t%d\t%d\n",
 		get_task_state(p),
-		(p->sleep_avg/1024)*100/(1020000000/1024),
+		IAL_AVG_RND(p->avg_ia_latency),
 	       	p->tgid,
 		p->pid, pid_alive(p) ? p->group_leader->real_parent->tgid : 0,
 		pid_alive(p) && p->ptrace ? p->parent->pid : 0,

Index: linux/include/linux/sched.h
===================================================================
@@ -688,6 +688,19 @@ static inline void prefetch_stack(struct
 struct audit_context;		/* See audit.c */
 struct mempolicy;
 
+/*
+ * Fixed denominator rational numbers for use estimating task's average
+ * interactive latency
+ */
+#define IAL_AVG_OFFSET 4
+/*
+ * Get the rounded integer value of a scheduling statistic average field
+ * Needs to be public for printing average interactive latency in
+ * fs/proc/array.c
+ */
+#define IAL_AVG_RND(x) \
+	(((x) + (1 << (IAL_AVG_OFFSET - 1))) >> (IAL_AVG_OFFSET))
+
 struct task_struct {
 	volatile long state;	/* -1 unrunnable, 0 runnable, >0 stopped */
 	struct thread_info *thread_info;

@@ -703,7 +716,7 @@ struct task_struct {
 	int oncpu;
 #endif
 #endif
-	int prio, static_prio;
+	int prio, static_prio, ia_bonus;
 #ifdef CONFIG_SMP
 	int bias_prio;
 #endif

@@ -712,10 +725,9 @@ struct task_struct {
 
 	unsigned short ioprio;
 
-	unsigned long sleep_avg;
+	unsigned long long avg_ia_latency;
 	unsigned long long timestamp, last_ran;
 	unsigned long long sched_time; /* sched_clock time spent running */
-	int activated;
 
 	unsigned long policy;
 	cpumask_t cpus_allowed;

@@ -929,6 +941,8 @@ static inline void put_task_struct(struc
 #define PF_BORROWED_MM	0x00400000	/* I am a kthread doing use_mm */
 #define PF_RANDOMIZE	0x00800000	/* randomize virtual address space */
 #define PF_SWAPWRITE	0x01000000	/* Allowed to write to swap */
+#define PF_IA_WAKE_UP	0x02000000	/* just woken from an interactive sleep */
+
 
 /*
  * Only the _current_ task can read/write to tsk->flags, but other

OK. I didn't really think this was ready for the big time yet without some refinement which is why I RFC'd it rather than posting it as a patch.

How good the interactive responsiveness really was one of my concerns as it's hard to evaluate. Just because it seemed to work well on my system doesn't mean that it works well everywhere. I did test it with 16 hard spinners on my SMT workstation but I was mainly looking at things like X responsiveness and the rythmbox music player and not shell commands.

I think that from a theoretical point of view shell commands won't do well with this scheduler (as it stands) as they don't do many interactive sleeps and hence are unlikely to accrue any bonuses. So that means back to the drawing board. It also means that interactive latency isn't the only important latency. Perhaps all latencies need to be considered with interactive latencies being given more weight. (This would be consistent with the current scheduler which only completely discounts sleep that is marked TASK_NONINTERACTIVE and just heavily discounts uninterruptible sleep.)

Thanks for the feed back. You've given me something to think about and I think these issues can be addressed without very little extra complexity. If not I'll just shelve the idea.

Peter

Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce

I've just realized a more serious reason why this scheduler modification needs to be postponed as unsuitable for general use. It essentially relies on sched_clock() having at least microsecond resolution and it has been pointed out to me that on some systems this isn't true and, even though its units are always nanoseconds, the resolution of sched_clock() can be large as 1/HZ. This scheduler would not work very well on these systems so its time has not yet come regardless of successful resolution of the other problems.

Nevertheless, I'll add a scheduler based on ingosched with this modification (and fixes) to PlugSched so that progress can be made on improving it for those systems where it is feasible.

Peter

Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce