Skip to contentSkip to conversation

Nick's scheduler policy v10

PATCH In review Nick Piggin 5 participants 13 messages Aug 30, 2003 – Sep 5, 2003

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Nick's scheduler policy v10

Hi,
This is quite a big change from v8. Fixes a few bugs in child priority, and adds a small lower bound on the amount of history that is kept. This should improve "fork something" times hopefully, and stops new children being able to fluctuate priority so wildly.

Eliminates "timeslice backboost" and only uses "priority backboost". This decreases scheduling latency quite nicely - I can only measure 130ms for a very low priority task, with a make -j3 and wildly moving an xterm around in front of a mozilla window.

Makes a fairly fundamental change to how sleeping/running is accounted. It now takes into account time on the runqueue. This hopefully will keep priorities more stable under varying loads.

Includes an upper bound on the amount of priority a task can get in one sleep. Hopefully this catches freak long sleeps like a SIGSTOP or unexpected swaps. This change breaks the priority calculation a little bit. I'm thinking about how to fix it.

Feedback welcome! Its against 0-test4, as usual.

include/linux/sched.h renamed from linux-2.6/include/linux/sched.h +9 -2
@@ -281,7 +281,9 @@ struct signal_struct {
 #define MAX_RT_PRIO		MAX_USER_RT_PRIO
 
 #define MAX_PRIO		(MAX_RT_PRIO + 40)
- 
+
+#define rt_task(p)		((p)->prio < MAX_RT_PRIO)
+
 /*
  * Some day this will be a full-fledged user tracking system..
  */
@@ -339,12 +341,16 @@ struct task_struct {
 	struct list_head run_list;
 	prio_array_t *array;
 
+	unsigned long array_sequence;
+	unsigned long timestamp;
+
+	unsigned long total_time, sleep_time;
 	unsigned long sleep_avg;
-	unsigned long last_run;
 
 	unsigned long policy;
 	cpumask_t cpus_allowed;
 	unsigned int time_slice, first_time_slice;
+	unsigned int used_slice;
 
 	struct list_head tasks;
 	struct list_head ptrace_children;
@@ -552,6 +558,7 @@ extern int FASTCALL(wake_up_state(struct
 extern int FASTCALL(wake_up_process(struct task_struct * tsk));
 extern int FASTCALL(wake_up_process_kick(struct task_struct * tsk));
 extern void FASTCALL(wake_up_forked_process(struct task_struct * tsk));
+extern void FASTCALL(sched_fork(task_t * p));
 extern void FASTCALL(sched_exit(task_t * p));
 
 asmlinkage long sys_wait4(pid_t pid,unsigned int * stat_addr, int options, struct rusage * ru);
kernel/fork.c renamed from linux-2.6/kernel/fork.c +3 -27
@@ -911,33 +911,9 @@ struct task_struct *copy_process(unsigne
 	p->exit_signal = (clone_flags & CLONE_THREAD) ? -1 : (clone_flags & CSIGNAL);
 	p->pdeath_signal = 0;
 
-	/*
-	 * Share the timeslice between parent and child, thus the
-	 * total amount of pending timeslices in the system doesn't change,
-	 * resulting in more scheduling fairness.
-	 */
-	local_irq_disable();
-        p->time_slice = (current->time_slice + 1) >> 1;
-	/*
-	 * The remainder of the first timeslice might be recovered by
-	 * the parent if the child exits early enough.
-	 */
-	p->first_time_slice = 1;
-	current->time_slice >>= 1;
-	p->last_run = jiffies;
-	if (!current->time_slice) {
-		/*
-	 	 * This case is rare, it happens when the parent has only
-	 	 * a single jiffy left from its timeslice. Taking the
-		 * runqueue lock is not a problem.
-		 */
-		current->time_slice = 1;
-		preempt_disable();
-		scheduler_tick(0, 0);
-		local_irq_enable();
-		preempt_enable();
-	} else
-		local_irq_enable();
+	/* Perform scheduler related accounting */
+	sched_fork(p);
+
 	/*
 	 * Ok, add it to the run-queues and make it
 	 * visible to the rest of the system.
kernel/sched.c renamed from linux-2.6/kernel/sched.c +250 -208

670 lines not on this page · raw message

#1 lore raw
Quoted 14 lines

This is quite a big change from v8. Fixes a few bugs in child priority, and adds a small lower bound on the amount of history that is kept. This should improve "fork something" times hopefully, and stops new children being able to fluctuate priority so wildly.

Eliminates "timeslice backboost" and only uses "priority backboost". This decreases scheduling latency quite nicely - I can only measure 130ms for a very low priority task, with a make -j3 and wildly moving an xterm around in front of a mozilla window.

Makes a fairly fundamental change to how sleeping/running is accounted. It now takes into account time on the runqueue. This hopefully will keep priorities more stable under varying loads.

Quoted 6 lines

Includes an upper bound on the amount of priority a task can get in one sleep. Hopefully this catches freak long sleeps like a SIGSTOP or unexpected swaps. This change breaks the priority calculation a little bit. I'm thinking about how to fix it.

Feedback welcome! Its against 0-test4, as usual.

Oooh - much better.

Kernbench: (make -j vmlinux, maximal tasks)

                              Elapsed      System        User         CPU
              2.6.0-test4       45.87      116.92      571.10     1499.00
         2.6.0-test4-nick       49.37      131.31      611.15     1500.75
       2.6.0-test4-nick7a       49.48      125.95      617.71     1502.00
       2.6.0-test4-nick10       46.91      114.03      584.16     1489.25

SDET 128 (see disclaimer)

                           Throughput    Std. Dev
              2.6.0-test4       100.0%         0.3%
         2.6.0-test4-nick       102.9%         0.3%
       2.6.0-test4-nick7a       105.1%         0.5%
       2.6.0-test4-nick10       107.7%         0.2%

System time of kernbench is back to what it would be with virgin, or actually a little less. Elapsed time is still up a little bit, along with user time, but it's getting pretty close.

Have you looked at Rick Lindsley's schedstat patches? I don't have a totally up-to-date version, but that might give us a better idea of what's going on wrt migrations, balancing, etc.

I'll try to get together a broader set of benchmarks and hammer on this some more ...

M.

#2 lore raw
Quoted 4 lines

Kernbench: (make -j vmlinux, maximal tasks)

                              Elapsed      System        User         CPU
              2.6.0-test4       45.87      116.92      571.10     1499.00
       2.6.0-test4-nick10       46.91      114.03      584.16     1489.25

Actually, now looks like you have significantly more idle time, so perhaps the cross-cpu (or cross-node) balancing isn't agressive enough:

      4583    10.0% default_idle
      2246     1.4% total
       377    12.0% zap_pte_range
       210    15.2% free_hot_cold_page
       161     9.3% buffered_rmqueue
       138    47.4% __set_page_dirty_buffers
       102     0.7% do_anonymous_page
        54     4.9% clear_page_tables
...
       -51    -4.3% file_move
       -63    -7.9% pte_alloc_one
       -63    -3.4% path_lookup
       -69   -18.5% .text.lock.file_table
       -70    -8.2% strnlen_user
       -76    -1.0% __d_lookup
       -96    -1.5% page_add_rmap
      -104   -16.8% copy_process
      -109    -2.9% find_get_page
      -118   -28.2% release_task
      -267   -18.8% schedule
      -357    -6.7% __copy_to_user_ll
      -531   -15.2% __copy_from_user_ll
      -809    -3.4% page_remove_rmap
#3 lore raw
Quoted 9 lines · Martin J. Bligh
Quoted 5 lines

Kernbench: (make -j vmlinux, maximal tasks)

                             Elapsed      System        User         CPU
             2.6.0-test4       45.87      116.92      571.10     1499.00
      2.6.0-test4-nick10       46.91      114.03      584.16     1489.25

Actually, now looks like you have significantly more idle time, so perhaps the cross-cpu (or cross-node) balancing isn't agressive enough:

Yeah, there is a patch for this in mm that is not in mine. It should help both mine and mainline though...

Looks like mine is still context switching a bit more by the increased user time but its probably nearly acceptable now.

#4 lore raw
Quoted 6 lines
Quoted 6 lines
Quoted 5 lines

Kernbench: (make -j vmlinux, maximal tasks)

                             Elapsed      System        User         CPU
             2.6.0-test4       45.87      116.92      571.10     1499.00
      2.6.0-test4-nick10       46.91      114.03      584.16     1489.25
Quoted 6 lines
Quoted 3 lines

Actually, now looks like you have significantly more idle time, so perhaps the cross-cpu (or cross-node) balancing isn't agressive enough:

Yeah, there is a patch for this in mm that is not in mine. It should help both mine and mainline though...

Not convinced of that - mm performs worse than mainline for me.

Quoted 2 lines

Looks like mine is still context switching a bit more by the increased user time but its probably nearly acceptable now.

Yeah, is odd, you have more user time, but also more idle time. schedstats should measure context switch rates, balances, etc.

M.

#5 lore raw
Quoted 10 lines · Martin J. Bligh
Quoted 10 lines
Quoted 10 lines
Quoted 6 lines

Kernbench: (make -j vmlinux, maximal tasks)

                            Elapsed      System        User         CPU
            2.6.0-test4       45.87      116.92      571.10     1499.00
     2.6.0-test4-nick10       46.91      114.03      584.16     1489.25

Actually, now looks like you have significantly more idle time, so perhaps the cross-cpu (or cross-node) balancing isn't agressive enough:

Quoted 6 lines
Quoted 3 lines

Yeah, there is a patch for this in mm that is not in mine. It should help both mine and mainline though...

Not convinced of that - mm performs worse than mainline for me.

Well, one of Con's patches caused a lot of idle time on volanomark. The reason for the change was unclear. I guess either a fairness or wakeup latency change (yes, it was a very scientific process, ahem).

Anyway, in the process of looking at the load balancing, we found and fixed a problem (although it might now possibly over balance). This did cure most of the idle problems.

So it could just be small changes causing things to go out of whack. I will try to get better data after (if ever) the thing is working nicely on the desktop.

#6 lore raw
Quoted 6 lines
Quoted 1 line

Not convinced of that - mm performs worse than mainline for me.

Well, one of Con's patches caused a lot of idle time on volanomark. The reason for the change was unclear. I guess either a fairness or wakeup latency change (yes, it was a very scientific process, ahem).

Quoted 7 lines

Anyway, in the process of looking at the load balancing, we found and fixed a problem (although it might now possibly over balance). This did cure most of the idle problems.

So it could just be small changes causing things to go out of whack. I will try to get better data after (if ever) the thing is working nicely on the desktop.

I think Con and I worked out that the degredations I was seeing (on kernbench and SDET) were due to (in his words) "my hacks throwing the cc cpu hogs onto the expired array more frequently".

M.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 6 lines
Quoted 1 line

Not convinced of that - mm performs worse than mainline for me.

Well, one of Con's patches caused a lot of idle time on volanomark. The reason for the change was unclear. I guess either a fairness or wakeup latency change (yes, it was a very scientific process, ahem).

Quoted 7 lines

Anyway, in the process of looking at the load balancing, we found and fixed a problem (although it might now possibly over balance). This did cure most of the idle problems.

So it could just be small changes causing things to go out of whack. I will try to get better data after (if ever) the thing is working nicely on the desktop.

I think Con and I worked out that the degredations I was seeing (on kernbench and SDET) were due to (in his words) "my hacks throwing the cc cpu hogs onto the expired array more frequently".

M.

#7 lore raw
Quoted 10 lines · Martin J. Bligh
Quoted 10 lines
Quoted 2 lines

Not convinced of that - mm performs worse than mainline for me.

Well, one of Con's patches caused a lot of idle time on volanomark. The reason for the change was unclear. I guess either a fairness or wakeup latency change (yes, it was a very scientific process, ahem).

Anyway, in the process of looking at the load balancing, we found and fixed a problem (although it might now possibly over balance). This did cure most of the idle problems.

Quoted 8 lines
Quoted 4 lines

So it could just be small changes causing things to go out of whack. I will try to get better data after (if ever) the thing is working nicely on the desktop.

I think Con and I worked out that the degredations I was seeing (on kernbench and SDET) were due to (in his words) "my hacks throwing the cc cpu hogs onto the expired array more frequently".

This didn't explain the huge idle time increases on volanomark and SPECjbb I think.

#8 lore raw
Quoted 15 lines · Nick Piggin
Quoted 14 lines · Martin J. Bligh
Quoted 13 lines
Quoted 1 line

Not convinced of that - mm performs worse than mainline for me.

Well, one of Con's patches caused a lot of idle time on volanomark. The reason for the change was unclear. I guess either a fairness or wakeup latency change (yes, it was a very scientific process, ahem).

Anyway, in the process of looking at the load balancing, we found and fixed a problem (although it might now possibly over balance). This did cure most of the idle problems.

So it could just be small changes causing things to go out of whack. I will try to get better data after (if ever) the thing is working nicely on the desktop.

Quoted 6 lines
Quoted 3 lines

I think Con and I worked out that the degredations I was seeing (on kernbench and SDET) were due to (in his words) "my hacks throwing the cc cpu hogs onto the expired array more frequently".

This didn't explain the huge idle time increases on volanomark and SPECjbb I think.

Yeah this was before the profile showed it to be idle time, and before I isolated it to Ingo's A3 patch.

Con

#9 lore raw
In reply to Martin J. Bligh
Quoted 31 lines · Martin J. Bligh
Quoted 14 lines

This is quite a big change from v8. Fixes a few bugs in child priority, and adds a small lower bound on the amount of history that is kept. This should improve "fork something" times hopefully, and stops new children being able to fluctuate priority so wildly.

Eliminates "timeslice backboost" and only uses "priority backboost". This decreases scheduling latency quite nicely - I can only measure 130ms for a very low priority task, with a make -j3 and wildly moving an xterm around in front of a mozilla window.

Makes a fairly fundamental change to how sleeping/running is accounted. It now takes into account time on the runqueue. This hopefully will keep priorities more stable under varying loads.

Quoted 7 lines

Includes an upper bound on the amount of priority a task can get in one sleep. Hopefully this catches freak long sleeps like a SIGSTOP or unexpected swaps. This change breaks the priority calculation a little bit. I'm thinking about how to fix it.

Feedback welcome! Its against 0-test4, as usual.

Oooh - much better.

Kernbench: (make -j vmlinux, maximal tasks)

                             Elapsed      System        User         CPU
             2.6.0-test4       45.87      116.92      571.10     1499.00
        2.6.0-test4-nick       49.37      131.31      611.15     1500.75
      2.6.0-test4-nick7a       49.48      125.95      617.71     1502.00
      2.6.0-test4-nick10       46.91      114.03      584.16     1489.25
Quoted 7 lines

SDET 128 (see disclaimer)

                          Throughput    Std. Dev
             2.6.0-test4       100.0%         0.3%
        2.6.0-test4-nick       102.9%         0.3%
      2.6.0-test4-nick7a       105.1%         0.5%
      2.6.0-test4-nick10       107.7%         0.2%

Nice.

Quoted 9 lines

System time of kernbench is back to what it would be with virgin, or actually a little less. Elapsed time is still up a little bit, along with user time, but it's getting pretty close.

Have you looked at Rick Lindsley's schedstat patches? I don't have a totally up-to-date version, but that might give us a better idea of what's going on wrt migrations, balancing, etc.

I haven't had a look, no. I will see.

Quoted 5 lines

I'll try to get together a broader set of benchmarks and hammer on this some more ...

That would be cool. It seems to be rapidly becoming "acceptable" to desktop users, so high end tuning needs to be next. But hopefully I might not have to do much.

#10 lore raw
In reply to Nick Piggin

In article <[email protected]>,
Nick Piggin <[email protected]> wrote:

| This is quite a big change from v8. Fixes a few bugs in child priority,
| and adds a small lower bound on the amount of history that is kept. This
| should improve "fork something" times hopefully, and stops new children
| being able to fluctuate priority so wildly.
| 
| Eliminates "timeslice backboost" and only uses "priority backboost". This
| decreases scheduling latency quite nicely - I can only measure 130ms for
| a very low priority task, with a make -j3 and wildly moving an xterm around
| in front of a mozilla window.
| 
| Makes a fairly fundamental change to how sleeping/running is accounted.
| It now takes into account time on the runqueue. This hopefully will keep
| priorities more stable under varying loads.
| 
| Includes an upper bound on the amount of priority a task can get in one
| sleep. Hopefully this catches freak long sleeps like a SIGSTOP or unexpected
| swaps. This change breaks the priority calculation a little bit. I'm 
| thinking
| about how to fix it.
| 
| Feedback welcome! Its against 0-test4, as usual.

I've been running it for a while on a dog-slow machine, 350MHz Pentium-II with 96MB RAM, I was running V7, and I'm not sure it's an improvement, at least on this system. while I'm doing things like a kernel build (no -j on this box!) it feels perhaps a bit less smooth than v7, and I do see some occasional artifact on the screen which I didn't see with v7.

I'll be switching back and forth for a bit, and I have no working sound, 2.6.0-test4 just doesn't like the old Soundblaster, which works with Redhat 2.4.18 whatever from RH 7.3 install. I'm trying to get a clean oops to report when loading the aha152x module, and I want to generate it without *any* patches, in case someone ever cares. Other than that I do my security stuff on it, since the crypto loopback is working for me.

The v10 is better than stock test4, but I do think v7 was better. I'll tune a few things (suggestions?) but memory isn't a big problem under my light usage.

Signature · 3 lines
bill davidsen <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.
#11 lore raw
Quoted 5 lines · Bill Davidsen

I'll be switching back and forth for a bit, and I have no working sound, 2.6.0-test4 just doesn't like the old Soundblaster, which works with Redhat 2.4.18 whatever from RH 7.3 install. I'm trying to get a clean oops to report when loading the aha152x module, and I want to generate it without *any* patches, in case someone ever cares. Other than that I

I was able to generate the oops on one of my systems, and Andrew already included a patch that works for me in test4-mm4.

#12 lore raw
Quoted 9 lines · Mike Fedyk
Quoted 5 lines · Bill Davidsen

I'll be switching back and forth for a bit, and I have no working sound, 2.6.0-test4 just doesn't like the old Soundblaster, which works with Redhat 2.4.18 whatever from RH 7.3 install. I'm trying to get a clean oops to report when loading the aha152x module, and I want to generate it without *any* patches, in case someone ever cares. Other than that I

I was able to generate the oops on one of my systems, and Andrew already included a patch that works for me in test4-mm4.

Thanks for the pointer! Tomorrow I will get to test test4-mmX vs. plain test-+NickV10. There is an aweful lot of scheduler development going on...

Signature · 3 lines
bill davidsen <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.