sched: rsdl improvements

Hi all

As my time at the pc is limited I unfortunately cannot spend it responding to the huge number of emails I got in response to RSDL. Instead, here's a patch. I may be offline for extended periods at a time still so please others feel free to poke at the code and don't take it personally if I don't respond to your emails.

Note no interactive boost idea here.

Patch is for 2.6.21-rc4-mm1. I have not spent the time trying to bring other bases in sync.

---
Further improve the deterministic nature of the RSDL cpu scheduler and make the rr_interval tunable.

By only giving out priority slots to tasks at the current runqueue's prio_level or below we can make the cpu allocation not altered by accounting issues across major_rotation periods. This makes the cpu allocation and latencies more deterministic, and decreases maximum latencies substantially. This change removes the possibility that tasks can get bursts of cpu activity which can favour towards interactive tasks but also favour towards cpu bound tasks which happen to wait on other activity (such as I/O) and is a net gain.

This change also makes negative nice values less harmful to latencies of more niced tasks, and should lead to less preemption which might decrease the context switch rate and subsequently improve throughput.

The rr_interval can be made a tunable such that if an environment exists that is not as latency sensitive, it can be increased for maximum throughput.

A tiny change checking for MAX_PRIO in normal_prio() may prevent oopses on bootup on large SMP due to forking off the idle task.

Other minor cleanups.

---
 Documentation/sysctl/kernel.txt |   12 +++++
 kernel/sched.c                  |   94 ++++++++++++++++++++++------------------
 kernel/sysctl.c                 |   25 ++++++++--
 3 files changed, 83 insertions(+), 48 deletions(-)

Index: linux-2.6.21-rc4-mm1/Documentation/sysctl/kernel.txt
===================================================================
@@ -43,6 +43,7 @@ show up in /proc/sys/kernel:
 - printk
 - real-root-dev               ==> Documentation/initrd.txt
 - reboot-cmd                  [ SPARC only ]
+- rr_interval
 - rtsig-max
 - rtsig-nr
 - sem

@@ -288,6 +289,17 @@ rebooting. ???
 
 ==============================================================
 
+rr_interval:
+
+This is the smallest duration that any cpu process scheduling unit
+will run for. Increasing this value can increase throughput of cpu
+bound tasks substantially but at the expense of increased latencies
+overall. This value is in _ticks_ and the default value chosen depends
+on the number of cpus available at scheduler initialisation. Valid
+values are from 1-100.
+
+==============================================================
+
 rtsig-max & rtsig-nr:
 
 The file rtsig-max can be used to tune the maximum number

Index: linux-2.6.21-rc4-mm1/kernel/sysctl.c
===================================================================
@@ -79,6 +79,7 @@ extern int percpu_pagelist_fraction;
 extern int compat_log;
 extern int maps_protect;
 extern int print_fatal_signals;
+extern int rr_interval;
 
 #if defined(CONFIG_ADAPTIVE_READAHEAD)
 extern int readahead_ratio;

@@ -167,6 +168,13 @@ int sysctl_legacy_va_layout;
 #endif
 
 
+/* Constants for minimum and maximum testing in vm_table.
+   We use these as one-element integer vectors. */
+static int  __read_mostly zero;
+static int  __read_mostly one = 1;
+static int  __read_mostly one_hundred = 100;
+
+
 /* The default sysctl tables: */
 
 static ctl_table root_table[] = {

@@ -515,6 +523,17 @@ static ctl_table kern_table[] = {
 		.mode		= 0444,
 		.proc_handler	= &proc_dointvec,
 	},
+	{
+		.ctl_name	= CTL_UNNUMBERED,
+		.procname	= "rr_interval",
+		.data		= &rr_interval,
+		.maxlen		= sizeof (int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec_minmax,
+		.strategy	= &sysctl_intvec,
+		.extra1		= &one,
+		.extra2		= &one_hundred,
+	},
 #if defined(CONFIG_X86_LOCAL_APIC) && defined(CONFIG_X86)
 	{
 		.ctl_name       = KERN_UNKNOWN_NMI_PANIC,

@@ -631,12 +650,6 @@ static ctl_table kern_table[] = {
 	{ .ctl_name = 0 }
 };
 
-/* Constants for minimum and maximum testing in vm_table.
-   We use these as one-element integer vectors. */
-static int zero;
-static int one_hundred = 100;
-
-
 static ctl_table vm_table[] = {
 	{
 		.ctl_name	= VM_OVERCOMMIT_MEMORY,

-ck

I might actually need to drop RSDL from next -mm, see if those sched oopses whcih several people have reported go away.

I've tried RSDLv.31+this on 2.6.20.3 as i'm not tracking -mm.

I'm not sure this is going in the right direction... I'm writing this while compiling a kernel w/ "nice -20 make -j2" and X is almost unusable -- even the x pointer jumps instead of moving smoothly like it always did; I had to stop the build to be able to quickly finish this as the latency is making it hard to properly position the cursor... Hmm, this is weird; I've tried various nice values for the build and 19 is the only one triggering this, w/ 18 and less the cursor moves smoothly, but there are short sub-second stalls. nice=0 isn't much different.
RSDL 0.31 was behaving properly, and only exhibited problems when the box was overloaded w/ non-niced tasks; Right now even a properly niced background job kills interactivity completely.

artur

Did you mean "nice -20"? If so, that should have slowed X quite a bit. Try "nice 19" instead.

nice(1):
Run COMMAND with an adjusted niceness, which affects process
scheduling. With no COMMAND, print the current niceness. Nicenesses range from -20 (most favorable scheduling) to 19 (least favorable).

i did try "nice --20" too :) Resulted in long X stalls, but i don't think that's a reasonable load so I did not mention it. "nice -20 cmd" runs cmd at nice==19.

Usage: nice [OPTION] [COMMAND [ARG]...]
Run COMMAND with an adjusted niceness, which affects process scheduling. With no COMMAND, print the current niceness. Nicenesses range from -20 (most favorable scheduling) to 19 (least favorable).

-n, --adjustment=N add integer N to the niceness (default 10)

No he's right. Something scrambled my brain and I've completely left out the part where I offer the old bursts as a tunable option as well, which unintentionally killed off SCHED_BATCH as an entity. I'll have to put that as an additional patch sorry as this by itself is not always a win. Hang in there.

-ck

Actually, reworking the priority matrix to always have a slot at position 1 should fix this without needing a tunable. That is a better approach so I'll do that.

-ck

Here is the best fix for the bug pointed out. Thanks.

I'll try and find pc time to wrap these two patches together and make a v0.32 available.

---
Ensure niced tasks are not inappropriately limiting sleeping unniced tasks by explicitly checking what the best static priority that has run this major rotation was.

Reimplement SCHED_BATCH using this check.

---
 kernel/sched.c |   33 ++++++++++++++++++++++++---------
 1 file changed, 24 insertions(+), 9 deletions(-)

Index: linux-2.6.21-rc4-mm1/kernel/sched.c
===================================================================
@@ -201,8 +201,11 @@ struct rq {
 	struct prio_array *active, *expired, arrays[2];
 	unsigned long *dyn_bitmap, *exp_bitmap;
 
-	int prio_level;
-	/* The current dynamic priority level this runqueue is at */
+	int prio_level, best_static_prio;
+	/*
+	 * The current dynamic priority level this runqueue is at, and the
+	 * best static priority queued this major rotation.
+	 */
 
 	unsigned long prio_rotation;
 	/* How many times we have rotated the priority queue */

@@ -704,16 +707,24 @@ static inline int entitled_slot(int stat
 
 /*
  * Find the first unused slot by this task that is also in its prio_matrix
- * level.
+ * level. Ensure that the prio_level is not unnecessarily low by checking
+ * that best_static_prio this major rotation was not a niced task.
+ * SCHED_BATCH tasks do not perform this check so they do not induce
+ * latencies in tasks of any nice level.
  */
 static inline int next_entitled_slot(struct task_struct *p, struct rq *rq)
 {
-	DECLARE_BITMAP(tmp, PRIO_RANGE);
+	if (p->static_prio < rq->best_static_prio && p->policy != SCHED_BATCH)
+		return SCHED_PRIO(find_first_zero_bit(p->bitmap, PRIO_RANGE));
+	else {
+		DECLARE_BITMAP(tmp, PRIO_RANGE);
 
-	bitmap_or(tmp, p->bitmap, prio_matrix[USER_PRIO(p->static_prio)],
-		  PRIO_RANGE);
-	return SCHED_PRIO(find_next_zero_bit(tmp, PRIO_RANGE,
-		USER_PRIO(rq->prio_level)));
+		bitmap_or(tmp, p->bitmap,
+			  prio_matrix[USER_PRIO(p->static_prio)],
+			  PRIO_RANGE);
+		return SCHED_PRIO(find_next_zero_bit(tmp, PRIO_RANGE,
+			USER_PRIO(rq->prio_level)));
+	}
 }
 
 static void queue_expired(struct task_struct *p, struct rq *rq)

@@ -3315,6 +3326,7 @@ static inline void major_prio_rotation(s
 	rq->active = new_array;
 	rq->exp_bitmap = rq->expired->prio_bitmap;
 	rq->dyn_bitmap = rq->active->prio_bitmap;
+	rq->best_static_prio = MAX_PRIO;
 	rq->prio_rotation++;
 }
 

@@ -3640,10 +3652,12 @@ need_resched_nonpreemptible:
 	}
 switch_tasks:
 	if (next == rq->idle) {
+		rq->best_static_prio = MAX_PRIO;
 		rq->prio_level = MAX_RT_PRIO;
 		rq->prio_rotation++;
 		schedstat_inc(rq, sched_goidle);
-	}
+	} else if (next->static_prio < rq->best_static_prio)
+		rq->best_static_prio = next->static_prio;
 	prefetch(next);
 	prefetch_stack(next);
 	clear_tsk_need_resched(prev);

@@ -7093,6 +7107,7 @@ void __init sched_init(void)
 		lockdep_set_class(&rq->lock, &rq->rq_lock_key);
 		rq->nr_running = 0;
 		rq->prio_rotation = 0;
+		rq->best_static_prio = MAX_PRIO;
 		rq->prio_level = MAX_RT_PRIO;
 		rq->active = rq->arrays;
 		rq->expired = rq->arrays + 1;

-ck

I did mention them in the changelog further down. While it may not be immediately apparent from the minimal emails I'm sending, I am trying hard to address every known regression in the time alloted. Without access to the hardware though I'm reliant on others testing it so I can't know for certain if I've fixed them.

-ck

yes, this made the machine usable again.

After noticing that the context switch rate during a "nice -19 make -j2" has now been halved vs stock 2.6.20, compiled a kernel under both and RSDL w/these two patches was 2% faster; so this may be the right direction after all :)

artur

Hello List!

I'm using the new scheduler since a few days and I have to say that this is an amazing improvement for gaming loads. When playing enemy-territory the animations are completly smooth and fluid, without any hiccups. Et runs now clearly better on Linux than on my Win XP partition (same HW). I have never seen such smooth animations on any OS before.
(I have LD_PRELOADED a libnoyield ripped from a post here on lkml)

I can play et and have a 'nice make -j4' in the background and the only thing you notice is longer load-times/more latency on disk access. I can't tell if the compilation is finished or not while gaming ;-)

On everyday dektop usage there is a slight improvement too. But for me the current mainline scheduler has no problems. I couldn't tell which scheduler is in use by only doing desktop related things. Mainline scheduler is good and has no probs there.

I didn't find any severe regressions on my dual core system. No problems with sound or video even with make -j8 kernel compile in the background.

When I start a single cpu-hog it tends to jump around cores every second or so. I think that this is a regression to the current scheduler which tends to have a better affinity management on multicore.

Really nice work Con! ;-)

-Christian