self tuning scheduler

Hi Everyone,

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\n",
 		task->pid,
 		task->comm,
 		state,

@@ -382,7 +382,9 @@
 		task->exit_signal,
 		task_cpu(task),
 		task->rt_priority,
-		task->policy);
+		task->policy,
+		task->run_avg,
+		task->sleep_avg);
 	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;

Greetings,

I took your patch out for a test-drive, and it appears to have starvation problems with irman's process load (dang thing seems to be HELL on schedulers).

Irman starts a load (defaults to 9 tasks passing data in a pipe ring), and forks a child which pingpongs one character back and forth to the parent for 1000000 iterations, measuring response time for each iteration and computing statistics. With an iteration % 1000 printf() in the evaluation routine, I see it start off nice and fast, then begins to get starved for up to 30 seconds. It jerks around for a bit, then slows down to a ~stable 1 sec/iteration after approximately 300000 iterations. The whole test takes ~2minutes with 2.5.64-virgin. (I'm not patient enough to wait for the rest of the .5million iterations left on this burn before reporting:)

It also shows a serious throughput loss with make -j30 bzImage on this box (I think you expect that though from what I read). With stock, it takes ~8m30s... this scheduler adds a full minute.

The window wave test with a make -j5 bzImage running (fits easily in ram) is pretty ragged.

Ending on a more positive note, vmstat output from the parallel build looks quite nice.

-Mike

Hi Mike,

Thanks for taking the time to test my changes.

I found an irman rpm which is 2001 vintage and a broken link at:
http://people.redhat.com/bmatthews/irman/
So I'm not sure if I'm duplicating your test. If you could send me a tar ball with the source for the irman you are running, it would help.

When I run the version of irman I have, it runs to completion, maybe a bit slower than it should. I have some ideas why my scheduler does badly on this test.

When I start a new process, I pick an initial priority for the new process based on the average priority at which the system has been running. From this I back calculate a run_avg value. If this guess is bad, the new process may have an unfair advantage with respect to its parent. I have been thinking of ways to fix this. One idea is to use a shorter half-life value for processes which are recently started.

This test is an example where basing the child priority on the parent makes sense. Perhaps I should use the parent priority if it is lower than the rq->prio_avg value.

I guess it was wishful thinking when I titled this self tuning. If your interested you could adjust the run_avg_halflife and/or prio_avg_halflife to a smaller values.

It may also be a sampling problem where the period of the ping-pong exchange is a fraction of the HZ tick, and one process is charged more than its share of the cpu.

On the make -j30 kernel make, I intentionally reduce the timeslice as the process priority increases. This should reduce jitter for interactive processes. As more processes try to share the cpu they all get higher priority and the smaller time slice. If there are only 1-2 compute bound processes they would get 0.5 second time slices.

I'm also curious about the hardware you are testing on.

Jim Houston - Concurrent Computer Corp.

(dang, wouldn't ya know I'd get a reply _after_ grumbling for ~wasting 6 hrs thinking;)

You're quite welcome.

Con put up a 0.5 tarball, and I grabbed that... likely the same.

It runs to completion here too, but takes a _really_ long time. I also have some ideas why it runs so badly with your scheduler and Ingo's. It's basically a BAD test case IMHO. It is however a very effective DOS as things stand. (nothing more)

That's not what I _think_ I see. What I see is a steady degradation (same with Ingo scheduler, but Ingo's degrades to livelock). IMVHO, the 100000:1 work ratio (same work, data is 100000:1... that's the only difference) just skews the priority calculations in favor of the background load.

(hmmMMM. will ruminate)

(interested!... hard problem)

(hmm. I saw 1 sec/1000 iterations or a long while, then it degraded to 5 secs/1000 iterations)

This hurts that kind of load badly. ;) this load is kind of a religious issue with me. This load is very generic... it just divides a known volume of work into 30 sub-units such that the VM has something to deal with... in a known-to-be-doable size... it does _not_ saturate my box. Ingo's scheduler throttles it in such a way that total system throughput remains constant. I've thought long and hard about this, and can't assert that anything bad is being done to the load by the scheduling decisions made by Ingo. OTOH, shortening timeslice simply because there are N consumers is guaranteed to damage throughput for compute bound loads like this.

Cheezy little UP P3/500/128Mb box.

-Mike

<crickets chirping>
For the record, let me say that I understand that this proggy approx=DOS attack (100000:1).