self tuning scheduler 0.2

Hi Mike, Everyone,

Mike, I have made a few adjustments which I hope will make you happy. I changed the time_slice code so it gives larger time slices to processes with less than average priorities. This makes my "make -j30" compile times match those of linux-2.5.64.

I have some experimental code to address the irman issues. My first change was to adjust the run_avg value during a synchronous wakeup. The idea is to average the values so that related processes priorities will clump together. I also felt that the circle of processes passing a token are really a disguised compute bound process. To punish this behavoir, I add a small amount to the run_avg of the woken process. You can adjust the amount with /proc/sys/sched/pipe_circle_tax. I default this value to 5. This obviously also punishes the innocent. So the question is if the value is small enough can it fix the irman problem without breaking something else.

I'm attaching the original description and the new patch. It is still against linux-2.5.64-bk4.

Jim Houston - Concurrent Computer Corp.

----

I wish I had been paying attention when the recent "HT scehduler" thread started. I have been playing with some scheduler changes which are relevant to this discussion. The attached patch (against linux-2.5.64-bk4) makes the scheduler's dynamic priority scheme more consistent. The patch should improve the system's interactive feel by not giving long time slices to processes with favorable priorities. Under a heavy load the system should slow down rather than get jerky.

The scheduler currently mixes a priority based approach with a round robin behavior which keeps processes from starving. With my changes, the scheduler always runs in a priority based mode. It measures the cpu time that the process receives and uses this value with the static_prio value to control the process's priority. It uses a feedback approach. The more cpu time a process uses, the lower its priority. A lower priority means that the process competes less effectively with the other processes. It gets less cpu time, and its priority improves.

This scheme also means that comparing priorities between processors is more meaningful. With the current scheduler, you could have two processors both running priority 39 processes. One process might be a "nice -19" process, but you can't tell that from the priority. I have added a rq->prio_avg value which is an average of the priority at which the processor has been running. I believe that this should be useful input for load balancing.

The patch adds a p->run_avg which is a running average of the process's cpu use. Typically these averages are done by multiplying the old value by a fraction and adding in the current value. If you do this at some constant frequency, then the ratio of old vs. new is constant. I only want to deal with this average in the same places that the current sleep_avg is calculated so I need to calculate an appropriate fraction. Here is what I want:

	value *= exp((ln(0.5)/half_life) * delta_time);

This gets ugly when you only have integer math and have to avoid overflows.

To make this pure priority based scheme work, I need occasionally to update the priority of processes which are in the run queue but are not at a priority which allows them to run. I added a linked list of processes in the run queue in least recently run order. I added code to scheduler_tick to examine these forgotten processes re-evaluating their run average value and dynamic priority.

The existing scheduler implements nice(2) by giving processes time slices based on their nice value (static_prio). A normal process would have a 150 millisecond time slice while a "nice -19" process gets 10 milliseconds. There is a trade off here. If you have a shorter time slice, processes will spend more time reloading data into the processor cache, but longer time slices may impact the system's interactive feel.

The patch uses feedback based on the run_avg to implement nice. This allows more creative use for the time slice. If the process is running at a favorable interactive priority, it is given a short time slice. This allows the priority to be re-evaluated if the process decides to go compute bound. Processes which are running at lower priorities are rewarded by giving them longer time slices.

I tried several functions for the effective_prio calculation to make nice(2) work properly. Eventually I realized that log() was the right answer. Consider:

prio = static_prio + C*log(run_avg)

If two processes competing for the cpu with different static_prio values, they will reach equilibrium at some dynamic priority when:

	prio = static_prio1 + C*log(run_avg1) = static_prio2 + C*log(run_avg2)

	static_prio1 - static_prio2 = C*log(run_avg1) - C*log(run_avg2);

	static_prio1 - static_prio2 = C*log(run_avg1/run_avg2)

	run_avg1/run_avg2 = exp((static_prio1-static_prio2)/C)

We can pick the constant C so that nice has the desired effect. If a "nice -19" process competes with a "nice --20" process, it might get 1/50 of the cpu. This would give:

	C = (static_prio1-static_prio2)/log(run_avg1/run_avg2)
	C = (40)/log(50)

Try clipping this into gnuplot

	set xrange [0:1]
	f(x) = nice + C*log(x)
	C=10
	plot nice=30, f(x) title "nice -10", nice=20, f(x) title "normal"

I had to expand the range of dynamic priorities. The range is now from 0-79. Normally interactive processes will have priorities around 30 and compute bound processes will find an equilibrium value which depends on the number of processes sharing the cpu. Is there any reason not to let this new range be user visible? Both ps and top seem happy with the new range.

When I posted a similar patch last fallaa, Albert Cahalan suggested making the run average value available in the /proc/stat for display as %CPU in ps. The patch actually adds both the run_avg and sleep_avg values. I found this useful while debugging.

The patch implements the log() for effective_prio() and the exp() for decay_value() using integer math and only a few multiplies.

The patch currently adds two blocks of new code and makes several small changes to call the new functions. The patch obsoletes the array switch logic, but I have not removed the obsolete code yet. This makes the patch easier to read and easier to merge with other scheduler work which may be in progress.

Initially I tried replacing the sleep_avg with the run_avg. The run_avg gives a good priority boost to programs that use very little cpu. It does not do a good job of separating processes which sometimes sleep from compute bound processes. The current patch uses the existing 2.5.64-bk4 sleep_avg logic. The variable sleep_avg_nice controls the amount of boost that interactive tasks receive. I default this to 10 which should give an interactive task the equivalent of a nice +10.

Jim Houston - Concurrent Computer Corp.

---

diff -urN -X dontdiff linux-2.5.64-bk4.orig/fs/proc/array.c linux-2.5.64-bk4/fs/proc/array.c
@@ -336,7 +336,7 @@
 	read_unlock(&tasklist_lock);
 	res = sprintf(buffer,"%d (%s) %c %d %d %d %d %d %lu %lu \
 %lu %lu %lu %lu %lu %ld %ld %ld %ld %ld %ld %llu %lu %ld %lu %lu %lu %lu %lu \
-%lu %lu %lu %lu %lu %lu %lu %lu %d %d %lu %lu\n",
+%lu %lu %lu %lu %lu %lu %lu %lu %d %d %lu %lu %lu %lu %u\n",
 		task->pid,
 		task->comm,
 		state,

@@ -382,7 +382,10 @@
 		task->exit_signal,
 		task_cpu(task),
 		task->rt_priority,
-		task->policy);
+		task->policy,
+		task->run_avg,
+		task->sleep_avg,
+		task->time_slice);
 	if(mm)
 		mmput(mm);
 	return res;

diff -urN -X dontdiff linux-2.5.64-bk4.orig/include/asm-i386/bitops.h linux-2.5.64-bk4/include/asm-i386/bitops.h
@@ -426,8 +426,8 @@
 
 /*
  * Every architecture must define this function. It's the fastest
- * way of searching a 140-bit bitmap where the first 100 bits are
- * unlikely to be set. It's guaranteed that at least one of the 140
+ * way of searching a 180-bit bitmap where the first 100 bits are
+ * unlikely to be set. It's guaranteed that at least one of the 180
  * bits is cleared.
  */
 static inline int sched_find_first_bit(unsigned long *b)

@@ -440,7 +440,9 @@
 		return __ffs(b[2]) + 64;
 	if (b[3])
 		return __ffs(b[3]) + 96;
-	return __ffs(b[4]) + 128;
+	if (b[4])
+		return __ffs(b[4]) + 128;
+	return __ffs(b[5]) + 160;
 }
 
 /**

diff -urN -X dontdiff linux-2.5.64-bk4.orig/include/linux/sched.h linux-2.5.64-bk4/include/linux/sched.h
@@ -267,7 +267,7 @@
 #define MAX_USER_RT_PRIO	100
 #define MAX_RT_PRIO		MAX_USER_RT_PRIO
 
-#define MAX_PRIO		(MAX_RT_PRIO + 40)
+#define MAX_PRIO		(MAX_RT_PRIO + 80)
  
 /*
  * Some day this will be a full-fledged user tracking system..

@@ -326,6 +326,10 @@
 	int prio, static_prio;
 	struct list_head run_list;
 	prio_array_t *array;
+  
+	struct list_head run_list_lru;
+	unsigned long run_avg;
+	unsigned long run_avg_timestamp;
 
 	unsigned long sleep_avg;
 	unsigned long last_run;

diff -urN -X dontdiff linux-2.5.64-bk4.orig/include/linux/sysctl.h linux-2.5.64-bk4/include/linux/sysctl.h
@@ -66,7 +66,8 @@
 	CTL_DEV=7,		/* Devices */
 	CTL_BUS=8,		/* Busses */
 	CTL_ABI=9,		/* Binary emulation */
-	CTL_CPU=10		/* CPU stuff (speed scaling, etc) */
+	CTL_CPU=10,		/* CPU stuff (speed scaling, etc) */
+	CTL_SCHED=11,		/* scheduler tunables */
 };
 
 /* CTL_BUS names: */

@@ -157,6 +158,13 @@
 	VM_LOWER_ZONE_PROTECTION=20,/* Amount of protection of lower zones */
 };
 
+/* Tunable scheduler parameters in /proc/sys/sched/ */
+enum {
+	SCHED_MIN_TIMESLICE=1,		/* minimum process timeslice */
+	SCHED_MAX_TIMESLICE=2,		/* maximum process timeslice */
+	SCHED_SLEEP_AVG_NICE=3,		/* sleep_avg priority boost */
+	SCHED_PIPE_CIRCLE_TAX=4,
+};
 
 /* CTL_NET names: */
 enum

diff -urN -X dontdiff linux-2.5.64-bk4.orig/kernel/sysctl.c linux-2.5.64-bk4/kernel/sysctl.c
@@ -56,6 +56,11 @@
 extern int pid_max;
 extern int sysctl_lower_zone_protection;
 
+extern int min_timeslice;
+extern int max_timeslice;
+extern int sleep_avg_nice;
+extern int pipe_circle_tax;
+
 /* this is needed for the proc_dointvec_minmax for [fs_]overflow UID and GID */
 static int maxolduid = 65535;
 static int minolduid;

@@ -112,6 +117,7 @@
 
 static ctl_table kern_table[];
 static ctl_table vm_table[];
+static ctl_table sched_table[];
 #ifdef CONFIG_NET
 extern ctl_table net_table[];
 #endif

@@ -156,6 +162,7 @@
 	{CTL_FS, "fs", NULL, 0, 0555, fs_table},
 	{CTL_DEBUG, "debug", NULL, 0, 0555, debug_table},
         {CTL_DEV, "dev", NULL, 0, 0555, dev_table},
+	{CTL_SCHED, "sched", NULL, 0, 0555, sched_table},
 	{0}
 };
 

@@ -359,6 +366,23 @@
 static ctl_table dev_table[] = {
 	{0}
 };  
+
+
+static ctl_table sched_table[] = {
+	{SCHED_MAX_TIMESLICE, "max_timeslice", &max_timeslice,
+	 sizeof(int), 0644, NULL, &proc_dointvec_minmax,
+	 &sysctl_intvec, NULL, &one, NULL},
+	{SCHED_MIN_TIMESLICE, "min_timeslice", &min_timeslice,
+	 sizeof(int), 0644, NULL, &proc_dointvec_minmax,
+	 &sysctl_intvec, NULL, &one, NULL},
+	{SCHED_SLEEP_AVG_NICE, "sleep_avg_nice", &sleep_avg_nice,
+	 sizeof(int), 0644, NULL, &proc_dointvec_minmax,
+	 &sysctl_intvec, NULL, &zero, NULL},
+	{SCHED_PIPE_CIRCLE_TAX, "pipe_circle_tax", &pipe_circle_tax,
+	 sizeof(int), 0644, NULL, &proc_dointvec_minmax,
+	 &sysctl_intvec, NULL, &zero, NULL},
+	{0}
+};
 
 extern void init_irq_proc (void);
 

Greetings,

I only did one run, but yep, it's pretty close on my box too.

A value of 5 doesn't seem to be enough. I fixed irman's parse problem so it can run the memory test properly and ran it with pipe_circle_tax set to 5, 25 and 50. The results are attached along with results from 2.5.64.virgin and 2.5.64.bk5 for comparison.

There isn't any detectable change wrt the window wiggle test... still pretty choppy.

-Mike

pipe_circle_tax = 5
aborted after 20 minutes

pipe_circle_tax = 25
[mikeg]:> time ./irman
Response time measurements (milliseconds) for: 2.5.64bk5sts

      Load       Max       Min       Avg Std. Dev.
      NULL     0.362     0.009     0.010     0.002
    MEMORY   250.048     0.009     0.019     1.075
   FILE_IO   749.965     0.010     0.027     2.199
   PROCESS   824.305     0.010     0.080     2.821

real    3m20.733s
user    0m52.662s
sys     0m20.981s

pipe_circle_tax = 50
[mikeg]:> time ./irman
Response time measurements (milliseconds) for: 2.5.64bk5sts

      Load       Max       Min       Avg Std. Dev.
      NULL     0.247     0.010     0.011     0.002
    MEMORY   375.001     0.009     0.020     1.244
   FILE_IO   499.987     0.009     0.032     2.483
   PROCESS   525.932     0.010     0.051     2.306

real    3m5.857s
user    0m54.828s
sys     0m21.571s

[mikeg]:> time ./irman
Response time measurements (milliseconds) for: 2.5.64.virgin

      Load       Max       Min       Avg Std. Dev.
      NULL     0.733     0.010     0.011     0.002
    MEMORY   151.308     0.010     0.017     0.969
   FILE_IO   454.016     0.010     0.027     2.718
   PROCESS  1216.848     0.010     0.049     6.411

real    2m46.591s
user    0m20.270s
sys     0m21.622s

[mikeg]:> time ./irman
Response time measurements (milliseconds) for: 2.5.64bk5

      Load       Max       Min       Avg Std. Dev.
      NULL     3.373     0.010     0.012     0.004
    MEMORY   106.042     0.011     0.023     1.090
   FILE_IO   312.046     0.011     0.047     3.297
   PROCESS   223.482     0.010     0.037     0.488

real    2m51.265s
user    0m29.902s
sys     0m23.920s

Hi Mike, Everyone,

I'm still working on the window wiggle problem. The problem is that I'm expecting too much from the running average. I wanted it to provide long term history about the process's cpu use. I also wanted the process priority to change fairly quickly when the process is given some cpu time. These are contradictory goals.

I'm working on a change which would use a short time constant for the run_avg. Rather than directly calculating the p->prio value from the run_avg, I will treat the p->prio as another filtered value.

I'm still working on the irman issue. I'm thinking about counting the number of levels of synchronous wakeup. This would be used to decide if the process should benefit from the sleep time.

Jim Houston - Concurrent Computer Corp.