Nick's scheduler policy

Hi,
Patch against 2.6.0-test4. It fixes a lot of problems here vs previous versions. There aren't really any open issues for me, so testers would be welcome.

The big change is more dynamic timeslices, which allows "interactive" tasks to get very small timeslices while more compute intensive loads can be given bigger timeslices than usual. This works properly with nice (niced processes will tend to get bigger timeslices).

I think I have cured test-starve too.

Worst case scheduling latency for a very nice (19) process I have observed is about 210ms during a niced make -j3 and frantic window moving in X, on a UP... I did see one of Con's recent kernels have a worst case of >7s.

On the other hand, I expect the best cases and maybe most usual cases would be better on Con's... and Con might have since done some work in the latency area.

@@ -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);

@@ -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.

I haven't still found any starvation cases, but forking time when the system is under heavy load has increased considerable with respect to vanilla or Con's O18.1int:

1. On a Konsole session, run "while true; do a=2; done"
2. Now, try forming a new Konsole session and you'll see it takes approximately twice the time it takes when the system is under no load.

Also, renicing X to -20 helps X interactivity, while with Con's patches, renicing X to -20 makes it feel worse.

Yeah, it probably penalises parents and children too much on fork, and doesn't penalise parents of exiting cpu hogs enough. I have noticed this too.

renicing IMO is a lot more sane in my patches, although others might disagree. In Con's patches, when you make X -20, it gets huge timeslices. In my version, it will get lots of smaller timeslices.

Thanks again for testing.

Nick

Not having starvation cases may be worth a little overhead. I am more concerned about avoiding "jackpot cases" than throughput, at least on a desktop.

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

Seems to do badly with CPU intensive tasks:

Kernbench: (make -j vmlinux, maximal tasks)

                              Elapsed      System        User         CPU
              2.6.0-test3       46.00      115.49      571.94     1494.25
         2.6.0-test4-nick       49.37      131.31      611.15     1500.75

Oddly, schedule itself is significantly cheaper, but you seem to end up with much more expense elsewhere. Thrashing tasks between CPUs, maybe (esp given the increased user time)? I'll do a proper baseline against test4, but I don't expect it to be any different, really.

diffprofile {2.6.0-test3,2.6.0-test4-nick}/kernbench/0/profile

     12314     7.4% total
      3843    16.3% page_remove_rmap
      1657    20.8% __d_lookup
      1322     9.4% do_anonymous_page
      1143    21.5% __copy_to_user_ll
      1034    55.3% atomic_dec_and_lock
       683    48.4% free_hot_cold_page
       669   393.5% filp_close
       553   147.5% .text.lock.file_table
       484   479.2% file_ra_state_init
       409    24.3% buffered_rmqueue
       391    24.9% kmem_cache_free
       362    11.3% zap_pte_range
       304    16.5% path_lookup
       247    31.5% pte_alloc_one
       237    68.3% pgd_ctor
       229    19.0% file_move
       224    16.7% link_path_walk
       220    57.7% file_kill
       188     7.9% do_no_page
       164    24.6% __wake_up
       162     4.4% find_get_page
       146    24.4% generic_file_open
       141    87.6% .text.lock.dcache
       139    11.5% release_pages
       131    51.4% vfs_read
       127    40.2% dnotify_parent
...
      -144    -4.2% __copy_from_user_ll
      -149    -2.3% page_add_rmap
      -352   -25.1% schedule
     -3469    -6.8% default_idle

Thanks Martin.

Yeah I'd say most if not all would be my fault though. What happens is that a lowest priority process will get a 1ms timeslice if there is a highest priority process on the same runqueue, though it will get I think 275ms if there are only other low priority processes there.

A kernbench probably has enough IO to keep priorities up a bit and keep timeslices short. The timeslice stuff could probably still use a bit of tuning. On the other hand, nice -20 processes should get big timeslices, while other schedulers give them small timeslices.

Hi,
I didn't miss 5 revisions, I'll just stick to using my internal numbering for releases.

This one has a few changes. Children now get a priority boost on fork, and parents retain more priority after forking a child, however exiting CPU hogs will now penalise parents a bit.

Timeslice scaling was tweaked a bit. Oh and remember raising X's priority should _help_ interactivity with this patch, and IMO is not an unreasonable thing to be doing.

Please test. I'm not getting enough feedback!

@@ -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);

@@ -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.

On Mon, 2003-08-25 at 12:41, Nick Piggin wrote:

[...]

I'm testing, I'm testing ;-)
Just let me a few hours to play with it...

OK, if you test my software.

Seriously, though, it seems OK at first glance. I can't reproduce the XEmacs problems I had with Con's recent versions. I'll have to run it for a while and see what it seems like.

Måns Rullgård
[email protected]

Well, it's actually a bit faster than either mainline or your previous rev whilst running SDET:

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%

But kernbench is significantly slower. The increase in sys time has dropped from last time, but user time is up.

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

diffprofile {2.6.0-test4,2.6.0-test4-nick7a}/kernbench/0/profile

     13989     8.6% total
      4402     9.6% default_idle
      3385    14.4% page_remove_rmap
      1093    13.8% __d_lookup
       702     5.0% do_anonymous_page
       613    11.5% __copy_to_user_ll
       613    32.9% atomic_dec_and_lock
       565    40.9% free_hot_cold_page
       322    18.7% buffered_rmqueue
       296     9.4% zap_pte_range
       282    75.6% .text.lock.file_table
       185    11.4% kmem_cache_free
       183     9.8% path_lookup
       164    12.2% link_path_walk
       154    12.7% release_pages
       152    43.1% pgd_ctor
       127    33.0% file_kill
       126    15.8% pte_alloc_one
       123    10.4% file_move
       107    75.4% .text.lock.dcache
...
       -59    -9.5% copy_process
       -94   -22.5% release_task
      -146    -2.3% page_add_rmap
      -352   -24.7% schedule
     -1026   -29.4% __copy_from_user_ll

Not sure why you're beating up on rmap so much more from a scheduler change.

diffprofile {2.6.0-test4,2.6.0-test4-nick7a}/sdetbench/128/profile

       513    19.1% .text.lock.filemap
       246     2.6% find_get_page
       150     4.4% copy_mm
        86    46.0% try_to_wake_up
        82    24.1% kunmap_high
        76     0.0% sched_fork
        74     0.5% copy_page_range
        67     1.1% do_no_page
        54    17.3% __pagevec_lru_add_active
        53    10.2% radix_tree_lookup
        51     7.4% __wake_up
...
      -101    -8.6% __block_prepare_write
      -105   -65.2% release_blocks
      -108    -4.7% link_path_walk
      -112   -15.2% mmgrab
      -116    -5.5% buffered_rmqueue
      -118    -5.9% path_release
      -119    -2.9% do_wp_page
      -125    -3.9% pte_alloc_one
      -125   -15.6% proc_pid_status
      -127    -5.5% free_hot_cold_page
      -132   -10.2% exit_notify
      -138   -11.7% __read_lock_failed
      -146    -9.7% number
      -154   -28.5% proc_check_root
      -155   -20.9% proc_root_link
      -176   -10.3% d_alloc
      -179   -13.6% task_mem
      -186    -9.8% .text.lock.dcache
      -186    -7.6% proc_pid_stat
      -193   -11.1% ext2_new_inode
      -230    -4.0% kmem_cache_free
      -239    -8.2% .text.lock.dec_and_lock
      -244   -11.5% schedule
      -250   -38.3% __blk_queue_bounce
      -257   -15.0% current_kernel_time
      -307   -17.6% release_task
      -327    -1.8% zap_pte_range
      -338    -7.7% clear_page_tables
      -384   -20.7% lookup_mnt
      -406   -26.5% __find_get_block
      -412   -18.5% follow_mount
      -565    -9.7% path_lookup
      -729   -11.6% atomic_dec_and_lock
      -865   -46.1% grab_block
     -1185   -10.5% __d_lookup
     -2145    -0.5% default_idle
     -2786    -7.0% page_add_rmap
    -12702   -14.2% page_remove_rmap
    -29467    -3.8% total

Again, rmap and dlookup. Very odd. Some sort of locality thing, I guess.

M.

Thanks Martin. OK, so the drop in kernbench is quite likely to be what I thought - elevated priorities (caused by eg. make waiting for children) causing timeslices to shrink. As long as its not a fundamental problem, this should be able to be tweaked back.

Yeah, I guess the random kernel and user times are probably due to cache.

Hi !

And here's my report (almost no numbers, everything is purely subjective). I haven't tested Con's O18.1 yet, so my comparision is against -test4 vanilla. First (and most subjective opinion) - great. Under casual load (Opera rendering page and using its motifwrapper to handle flash (it's a CPU hog alone) + ocassional compilation + XMMS using ALSA ) everything feels very smooth _and_ responsive, no XMMS jerks, windows are moving nicely - X is definitely not starved, ps ax in xterm displays its output almost instantly, apps startup time is also very pleasantly low - all in all great. Unusual load (make -j 4 bzImage + aforementioned activity ) - I was able to notice 1 jerk in XMMS (wasn't able to reproduce, so this is acceptable), application startup time is slightly worse, but nonetheless useable and once started, all apps are quite smooth, but X is definitely starved, and it has great impact on WM - window movement is jerky and feels bad. However, renice -20 <X pid> cures this behavior completely, without any noticeable penalty on another apps - music is playing nicely, page rendering is still clean and nice.

Overall - very nice.
I'll stick to your scheduling policy for a while .

System specs:

IBM ThinkPad T21, PIII-800Mhz , 256Mb.
Linux 2.6.0-test4, APM, ALSA, anticipatory IO scheduling XFree 4.3.99.9

P.S. make clean && make -j 4 bzImage completed while I was writing this letter, so I'm assuming throughput is also OK for me.

With all the best, yarick at relex dot ru.

Greetings,

Heavy parallel make throughput is still down a little over 10%, but X choppiness is markedly improved. Test-starve is now working. One thing that I noticed is that irman takes quite a bit longer to complete than with stock. I've attached the results of that, plus some contest numbers. My local variant of contest has a couple of differences to stock: dbench doesn't run so many instances, and list_load is just a small tree being md5summed. There are two additional loads as well. ab_load is an ancient apache bench jabbering with an also ancient apache (boring static page via localhost)... you can guess what irman2_load is :)

-Mike

...

Has anyone developed a (run-time) scheduler [policy] selector, via sysctl or sysfs, so that different kernel builds aren't required?

I know that I have heard discussions of this previously.

~Randy

Not that I know of. This would probably require an extra layer of indirection in the standard form of Linux's struct of pointers to functions, with your standard schedule functions as wrappers. I think it would be highly unlikely that this would get into a standard kernel, but might make a nice testing tool...

In fact this might end up being incompatible with architectures like SPARC... but I'm sure someone could make it work if they really wanted to.

I think the present boot-time selector (selecting different kernels at boot) will have to suffice for now :P

...

Why wouldn't it work on sparc?