a quest for a better scheduler

Hello,

I sent a message a few days ago about some limitations I found in the linux scheduler.

In servers like Apache where a large (> 1000) number of processes can be running at the same time and where many of them are runnable at the same time, the default Linux scheduler just starts trashing and the machine becomes very rapidly unusable.

Performance degradations are quite noticeable on a two-way SMP machine (20-30% of the CPU gets lost) and are even more glaring on a multi-cpu machine. As an example, an 8-way Compaq Proliant just crawls with linux.

possible solutions to the problem:

http://lse.sourceforge.net/scheduling/

http://resourcemanagement.unixsolutions.hp.com/WaRM/schedpolicy.html

Indeed I've tried the patches available on the sites for the multi-queue scheduler and I was amazed by the performance improvement that I got. Both patches allow me to get to a 100% real CPU utilization on a two way machine running ~1500 processes.

What those patches do is quite simple, instead of having the single global process queue present in the normal Linux scheduler, they add multiple queues (one per CPU). In this way the scheduling decision can be greatly simplified and almost made local to each CPU. No hotspots, no global locks (well, almost).

Although some scalability problems are still there (there still is a global decision to make), the performance improvement obtained and the simplicity of the solution are remarkable.

The HP patch is probably the most interesting, since it consists of really a few lines of code and it gets (for what I could measure) the same kind of performance improvement of the more elaborate (but still quite simple) sourceforge patch.

Is there any special reason why any of those patches didn't make it to the mainstream kernel code?

TIA, ciao,

- Fabio

it is *not* a scheduler problem. This is an application design problem. Do not expect > 1000 runnable processes to perform well. Apache's one-process-per-parallel-client-connection application model is especially bad for such kind of loads. The scheduler has more important priorities to worry about than to fix application design problems.

There were many promises along the years, and none as of now met all the requirements the scheduler has to fulfill. 'many runnable processes' is not on the top of the list - if we are scheduling like mad then we have lost lots of performance already.

even with such 'improvements', the many-parallel-clients performance of one-process-per-request HTTP server designs is an order slower than what is possible.

having said that, improving this workload is still a useful task and we added improvements to the scheduler to improve this case. But those patches sacrifice other functionality just to get better many-runnable-processes performance, which is unacceptable.

the problem is that the *real* scheduling complexity (and needed functionality) shows when the number of runnable processes is in the neighborhood of the number of processors. Running many processes just masks eg. load-balancing deficiencies in schedulers, so obviously the simplest and most localized scheduler 'wins'. So comparing schedulers based on many-runnable-processes load is like comparing cars solely based on the size of their fuel tanks.

you can easily make the scheduler fast in the many-processes case by sacrificing functionality in the much more realistic, few-processes case. None of the patch i've seen so far maintained the current scheduler's few-processes logic. But i invite you to improve the current scheduler's many-processes behavior, without hurting its behavior in the few-processes case.

Ingo

All of them are worse for the normal case. Also 1500 running apache's isnt a remotely useful situation, you are thrashing the cache even if you are now not thrashing the scheduler. Use an httpd designed for that situation. Then you can also downgrade to a cheap pentium class box for the task ;)

Alan,

for the "normal case" performance see my other message.

I agree that a better threading model would surely help in a web server, but to me this is not an excuse to live up with a broken scheduler.

The X15 server I'm working on now is a sort of user-space TUX, it uses only 8 threads per CPU and it achieves the same level of performance of the kernel space TUX. Even in this case the performance advantage of the multiqueue scheduler is remarkable, especially on a multi-CPU (> 2) architecture.

To achieve some decent disk/CPU/network overlapping with the current linux blocking disk IO limitations there is no way to avoid a "bunch of server threads". I've (experimentally) figured out that 8-16 threads per CPU can assure some reasonable overlapping, depending on the memory size and disk subsystem speed. On a 8-way machine this means 64-128 active tasks, a total disaster with the current scheduler.

Unless we want to maintain the position tha the only way to achieve good performance is to embed server applications in the kernel, some minimal help should be provided to goodwilling user applications :)

TIA, ciao,

- Fabio

I did - and with a lot of interest

The problem has always been - alternative scheduler, crappier performance for 2 tasks running (which is most boxes). If your numbers are right then the HP patch is working as well for 1 or 2 tasks too

Indeed. I'd love to see you beat tux entirely in userspace. It proves the rest of the API for the kernel is right

thanks! :)

Please verify them if you have a couple of spare hours.

BTW: I measured similar results for the "scalability" patches on a 2.4.1 kernel, it would be worth the effort to seriously compare them from an architectural point of view, but I don't have the time right now...

Indeed, I'm using RT sigio/sigwait event scheduling, bare clone threads and zero-copy io.

If only I had a really asynchronous sendfile, or a smarter madvise that wouldn't require to map files :)

My server cannot execute dynamic stuff yet, it relies on Apache for that.

Running X15 and TUX in the same conditions (i.e. dynamic code in Apache) I get exactly the same score in both cases.

I'm adding a TUX-like dynamic interface, I hope to get it to work by next week, then I'll make a real confrontation.

Regards, ciao,

- Fabio

Fabio, I'm working on a similar solution, although I'm experimenting with SGI's KAIO patch to see what it can do. I've had to patch the kernel to implement POSIX style signal dispatch symantics (so that the thread which posted an I/O request doesn't have to be the one which catches the signal). Are you taking a similar approach, or is the lack of this behavior the reason you are using so many threads?

--Chris

it's not only the 2-task case, but also less flexibility or lost semantics.

well, until the cost of entry into the kernel is eliminated, this is not possible - unless there are performance bugs in TUX :-)

but yes, getting a userspace solution that gets 'close enough' in eg. SPECweb99 benchmarks (which is complex enough to be trusted as a generic performance metric) would be a nice thing to have. There are existing SIGIO based, multithreaded solutions (eg. phttpd), with varying success.

Ingo

believe me, there are many other parts of the kernel that are not optimized for the nutcase. In this case it's the scheduler that punishes you first. Do not shoot the messenger.

then your design is still bad. TUX has no problems with the scheduler, and TUX doesnt have many runnable processes at once. And this has nothing to do with TUX being within the kernel.

false.

if they are doing IO *only* then there wont be 64-128 active tasks. This is how TUX does async IO: helper threads do the IO and *only* the IO. This way cache locality is maximized. (the scheduler is irrelevant in this case.) Again you are blaming the scheduler - the poor scheduler is simply the first kernel subsystem that tells you: your design still sucks. (if you have 64-128 active tasks then you already pay a very big cache footprint price as well.) [I'm wondering how your solution was just as fast as TUX, although you claim that the scheduler was already killing things. Perhaps your test was done over localhost or was saturating network bandwidth?]

FYI, TUX related functionality is constantly being pushed out and made accessible to userspace as well. Witness zerocopy, IRQ-affinity, and tons of generic patches such as pagecache-scalability and timer-scalability. (and soon the remaining, TUX-private improvements too.) TUX is intended to be a testbed for kernel subsystems, where performance optimizations and APIs can be tested without having to export them to userspace. (exporting to userspace cannot be done lightly and makes things less flexible.)

Ingo

Maintaining the current scheduler's logic is exactly what we are trying to do in the projects at:

http://lse.sourceforge.net/scheduling/

A common design goal for the the two alternative scheduler implementations at this site is to maintain the current scheduler's behavior/scheduling decisions. In the case of the priority queue scheduler, we have actually used a copy of the existing scheduler running in parallel (in the same kernel) to determine if we are making the same scheduling decisions. Currently, in this implementation we only deviate from the current scheduler in a small number of cases where tasks get a boost due to having the same memory map.

The multi-queue implementation is more interesting. It is also designed to maintain the behavior of the current scheduler. However, as the runqueues get longer (and we start getting contention on the runqueue locks) it starts to deviate from existing scheduler behavior and make more local scheduling decisions. Ideally, this implementation will exhibit the behavior of the current scheduler at low thread counts and make more localized decisions as pressure on the scheduler is increased.

Neither of these implementations are at a point where I would advocate their adoption; yet.

Can someone tell me what a good workload/benchmark would be to examine 'low thread count' performance? In the past people have used the 'spinning on sched_yield' benchmark. However, this now makes little sense with the sched_yield optimizations introduced in 2.4. In addition, such a benchmark mostly ignores the 'reschedule_idle' component of the scheduler. We have developed a 'token passing' benchmark which attempts to address these issues (called reflex at the above site). However, I would really like to get a pointer to a community acceptable workload/benchmark for these low thread cases.

Mike Kravetz                                 [email protected]
IBM Linux Technology Center

thread-thread-affinity pretty much makes it impossible to use a priority queue. This 'small number of cases' is actually a fundamental issue: can the 'goodness()' function be an arbitrary function of:

goodness(process_prev,process_next) := f(process_prev,process_next)

, or is the queue design restricting the choice of goodness() functions? Priority queues for example restrict the choice of the goodness() function to subset of functions:

	goodness(process_prev,process_next) := f(process_next);

this restriction (independence of the priority from the previous process) is a fundamentally bad property, scheduling is nonlinear and affinity decisions depend on the previous context. [i had a priority-queue SMP scheduler running 2-3 years ago but dropped the idea due to this issue.] IMO it's more important to have a generic and flexible scheduler, and arbitrary, nonnatural restrictions tend to bite us later on.

one issue regarding multiqueues is the ability of interactive processes to preempt other, lower priority processes on other CPUs. These sort of things tend to happen while using X. In a system where process priorities are different, scheduling decisions cannot be localized per-CPU (unfortunately), and 'the right to run' as such is a global thing.

lmbench's lat_ctx for example, and other tools in lmbench trigger various scheduler workloads as well.

Ingo

It seems like we may be talking about two different things.

Our 'priority queue' implementation uses almost the same goodness function as the current scheduler. The main difference between our 'priority queue' scheduler and the current scheduler is the structure of the runqueue. We break up the single runqueue into a set of priority based runqueues. The 'goodness' of a task determines what sub-queue a task is placed in. Tasks with higher goodness values are placed in higher priority queues than tasks with lower goodness values. This allows us to limit the scan of runnable tasks to the highest priority sub-queue, as opposed to the entire runquue. When scanning the highest priority sub-queue we use almost the same goodness function as that which is used today (it does take CPU affinity into account). In fact, if we used the same goodness function I'm pretty sure we would exactly match the behavior of the existing scheduler.

Hopefully, Hubertus Franke will speak up and provide more details, as he is much more familiar with this implementation than I am.

In any case, I think we have almost reached the conclusion that our priority queue implementation may not be acceptable due to the extra overhead in low thread counts.

Agreed. This is why our multi-queue scheduler always attempts to make global decisions. It will preempt lower priority tasks on other CPUs. This implementation tends to make 'more localized' scheduling decisions as contention on the runqueue locks increase. However, at this point one could argue that we have moved away from a 'realistic' low task count system load.

Thanks, I'll add these to our list.

Mike Kravetz                                 [email protected]
IBM Linux Technology Center

we are talking about the same thing, re-read my mail. this design assumes that 'goodness' is constant in the sense that it does not depend on the previous process.

and no, your are not using the same goodness() function, you omitted the prev->mm == next->mm component to goodness(), due to this design limitation.

Ingo

Dear all,

I've spent my afternoon running some benchmarks to see if MQ patches would degrade performance in the "normal case".

To measure performance I've used the latest lmbench and I have mesured the kernel compile times on a dual pentium III box runing at 1GHz with an 133MHz bus.

Results (attached) show that there is no measurable difference in performace between a vanilla scheduler and a multiqueue scheduler when running only few processes (the compilation benchmark runs essentially two processes, one per CPU).

I have measured the HP and not the "scalability" patch because the two do more or less the same thing and give me the same performance advantages, but the former is a lot simpler and I could port it with no effort on any recent kernel. It is indeed interesting to see that this patch was originally designed for a 2.4.0-test10 kernel, and still works fine on the latest kernels, only a minor change (one line) was required. A version of the patch for the 2.4.2-ac26 kernel is attached to this message.

Given the zero impact on "normal case" performance and the huge positive impact (> 20%) in the heavy load case (70-80 runnable processess on a load of about 1400 total) I don't see why such a thing shouldn't be accepted in the mainstream scheduler.

- Fabio

@@ -34,6 +34,7 @@
 extern void timer_bh(void);
 extern void tqueue_bh(void);
 extern void immediate_bh(void);
+static inline void hop_queues(struct task_struct *, int);
 
 /*
  * scheduler variables

@@ -90,7 +91,8 @@
 spinlock_t runqueue_lock __cacheline_aligned = SPIN_LOCK_UNLOCKED;  /* inner */
 rwlock_t tasklist_lock __cacheline_aligned = RW_LOCK_UNLOCKED;	/* outer */
 
-static LIST_HEAD(runqueue_head);
+static struct list_head runqueue_head[NR_CPUS] = { LIST_HEAD_INIT((runqueue_head[0]))};
+static LIST_HEAD(rt_queue_head);
 
 /*
  * We align per-CPU scheduling data on cacheline boundaries,

@@ -100,12 +102,15 @@
 	struct schedule_data {
 		struct task_struct * curr;
 		cycles_t last_schedule;
+		struct list_head runqueue_head;
 	} schedule_data;
 	char __pad [SMP_CACHE_BYTES];
-} aligned_data [NR_CPUS] __cacheline_aligned = { {{&init_task,0}}};
+} aligned_data [NR_CPUS] __cacheline_aligned = { {{&init_task,0,
+	LIST_HEAD_INIT((aligned_data[0].schedule_data.runqueue_head))}}};
 
 #define cpu_curr(cpu) aligned_data[(cpu)].schedule_data.curr
 #define last_schedule(cpu) aligned_data[(cpu)].schedule_data.last_schedule
+#define cpu_rq(cpu) (aligned_data[(cpu)].schedule_data.runqueue_head)
 
 struct kernel_stat kstat;
 

@@ -199,6 +204,33 @@
 	return goodness(p, cpu, prev->active_mm) - goodness(prev, cpu, prev->active_mm);
 }
 
+
+static inline int other_goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm)
+{
+	int weight;
+
+	/*
+	 * select the current process after every other
+	 * runnable process, but before the idle thread.
+	 * Also, dont trigger a counter recalculation.
+	 * 
+	 * Give the process a first-approximation goodness value
+	 * according to the number of clock-ticks it has left.
+	 *
+	 * Don't do any other calculations if the time slice is
+	 * over..
+	 */
+	weight = p->counter;
+	if (!weight)
+		goto out2;
+			
+	/* .. and a slight advantage to the current MM */
+	if (p->mm == this_mm || !p->mm)
+		weight += 1;
+	weight += 20 - p->nice;
+out2:
+	return weight;
+}
 /*
  * This is ugly, but reschedule_idle() is very timing-critical.
  * We are called with the runqueue spinlock held and we must

@@ -266,6 +298,10 @@
 		} else {
 			if (oldest_idle == -1ULL) {
 				int prio = preemption_goodness(tsk, p, cpu);
+				/* 
+				 * this will never be true for < 400 HZ non
+				 * realtime. optimize this?  SAR
+				 */
 
 				if (prio > max_prio) {
 					max_prio = prio;

@@ -277,6 +313,10 @@
 	tsk = target_tsk;
 	if (tsk) {
 		if (oldest_idle != -1ULL) {
+			/* push onto best queue */
+			if (p->policy == SCHED_OTHER){
+				hop_queues(p, tsk->processor);
+			}
 			best_cpu = tsk->processor;
 			goto send_now_idle;
 		}

@@ -306,20 +346,28 @@
  */
 static inline void add_to_runqueue(struct task_struct * p)
 {
-	list_add(&p->run_list, &runqueue_head);
+	if (p->policy == SCHED_OTHER){
+		list_add(&p->run_list, &cpu_rq(p->processor));
+	} else  list_add(&p->run_list, &rt_queue_head);
 	nr_running++;
 }
 
-static inline void move_last_runqueue(struct task_struct * p)
+static inline void move_last_rt_queue(struct task_struct * p)
+{
+	list_del(&p->run_list);
+	list_add_tail(&p->run_list, &rt_queue_head);
+}
+
+static inline void move_first_rt_queue(struct task_struct * p)
 {
 	list_del(&p->run_list);
-	list_add_tail(&p->run_list, &runqueue_head);
+	list_add(&p->run_list, &rt_queue_head);
 }
 
-static inline void move_first_runqueue(struct task_struct * p)
+static inline void hop_queues(struct task_struct * p, int this_cpu)
 {
 	list_del(&p->run_list);
-	list_add(&p->run_list, &runqueue_head);
+	list_add(&p->run_list, &cpu_rq(this_cpu));
 }
 
 /*

@@ -343,6 +391,7 @@
 	if (task_on_runqueue(p))
 		goto out;
 	add_to_runqueue(p);
+ 	/* LATER : make an effort to choose rq before add ? */
 	if (!synchronous || !(p->cpus_allowed & (1 << smp_processor_id())))
 		reschedule_idle(p);
 	success = 1;

@@ -531,9 +580,9 @@
 asmlinkage void schedule(void)
 {
 	struct schedule_data * sched_data;
-	struct task_struct *prev, *next, *p;
+	struct task_struct *prev, *next, *p = NULL; /* LATER fix this */
 	struct list_head *tmp;
-	int this_cpu, c;
+	int this_cpu, c, i;
 
 
 	spin_lock_prefetch(&runqueue_lock);

@@ -592,18 +641,63 @@
 		goto still_running;
 
 still_running_back:
-	list_for_each(tmp, &runqueue_head) {
+	/* 
+	 * we unrolled the original combined runqueue in to two separate
+	 * checks, first the real time and then then policy OTHER for own
+	 * cpu, and finally theft from another cpu.
+	 */
+	list_for_each(tmp, &rt_queue_head) {
 		p = list_entry(tmp, struct task_struct, run_list);
-		if (can_schedule(p, this_cpu)) {
-			int weight = goodness(p, this_cpu, prev->active_mm);
+		if (can_schedule(p, this_cpu) && !(p->policy & SCHED_YIELD)) {
+			int weight = 1000 + p->rt_priority;
 			if (weight > c)
 				c = weight, next = p;
 		}
 	}
 
+	if (c >= 1000)
+		goto choice_made;
+
+	list_for_each(tmp, &cpu_rq(this_cpu)) {
+		p = list_entry(tmp, struct task_struct, run_list);
+		if (can_schedule(p, this_cpu) && !(p->policy & SCHED_YIELD)) {
+			int weight = other_goodness(p, this_cpu, prev->active_mm);
+			if (weight > c)
+				c = weight, next = p;
+		}
+	}
+
+#ifdef CONFIG_SMP
+	if (c > 0)
+		goto choice_made;
+
+	/* 
+	 * try to steal from another CPU's queue.  since we don't have to 
+	 * worry about real time or CPU preference, pick anything available.
+	 * this is an area for detailed policy.
+	 */
+	for (i = 0; i < smp_num_cpus; i++) {
+		int cpu = cpu_logical_map(i);
+		if (cpu == this_cpu) 
+			continue;
+
+		list_for_each(tmp, &cpu_rq(cpu)) {
+                	p = list_entry(tmp, struct task_struct, run_list);
+                	if (can_schedule(p, this_cpu) && !(p->policy & SCHED_YIELD)) {
+                        	int weight = other_goodness(p, cpu, prev->active_mm);
+                        	if (weight > c)
+                                	c = weight, next = p;
+                	}
+        	}
+	}
+
+	if (c > 0)
+		hop_queues(next, this_cpu); /* pull onto mine */
+#endif
 	/* Do we need to re-calculate counters? */
 	if (!c)
 		goto recalculate;
+choice_made:
 	/*
 	 * from this point on nothing can prevent us from
 	 * switching to the next task, save this fact in

@@ -705,7 +799,7 @@
 move_rr_last:
 	if (!prev->counter) {
 		prev->counter = NICE_TO_TICKS(prev->nice);
-		move_last_runqueue(prev);
+		move_last_rt_queue(prev);
 	}
 	goto move_rr_back;
 

@@ -938,8 +1032,14 @@
 	retval = 0;
 	p->policy = policy;
 	p->rt_priority = lp.sched_priority;
-	if (task_on_runqueue(p))
-		move_first_runqueue(p);
+	if (task_on_runqueue(p)){
+		if (policy != SCHED_OTHER)
+			move_first_rt_queue(p);
+		else {
+			/* push onto appropriate non-rt queue */
+			hop_queues(p, p->processor);
+		}
+	}
 
 	current->need_resched = 1;
 

@@ -1251,9 +1351,12 @@
 	 * process right in SMP mode.
 	 */
 	int cpu = smp_processor_id();
-	int nr;
+	int nr, i;
 
 	init_task.processor = cpu;
+	for (i=1; i<NR_CPUS; i++){
+		INIT_LIST_HEAD(&cpu_rq(i));
+	}
 
 	for(nr = 0; nr < PIDHASH_SZ; nr++)
 		pidhash[nr] = NULL;

Kernel compilation times
========================

three runs of "time make -j2"

--

Linux 2.4.2-ac26 + HP Multiqueue patch

216.34user 14.36system 2:00.03elapsed 192%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (482269major+691020minor)pagefaults 0swaps

216.53user 14.23system 1:57.91elapsed 195%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (482269major+691020minor)pagefaults 0swaps

217.65user 13.46system 1:58.05elapsed 195%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (482269major+691020minor)pagefaults 0swaps

--

Linux 2.4.2-ac26

220.07user 14.88system 2:02.67elapsed 191%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (482269major+691019minor)pagefaults 0swaps

220.31user 14.90system 2:00.64elapsed 194%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (482269major+691018minor)pagefaults 0swaps

220.58user 14.84system 2:00.57elapsed 195%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (482269major+691018minor)pagefaults 0swaps

LMBENCH-2BETA1
==============

First two: Linux 2.4.2-ac26 + HP Multiqueue patch

Second Two: Linux 2.4.2-ac26

Processor, Processes - times in microseconds - smaller is better
----------------------------------------------------------------
Host OS Mhz null null open selct sig sig fork exec sh
call I/O stat clos TCP inst hndl proc proc proc
--------- ------------- ---- ---- ---- ---- ---- ----- ---- ---- ---- ---- ----

skinny    Linux 2.4.2-a  997 0.34 0.56 3.96 5.04    27 0.89 2.72  245 1128 4044
skinny    Linux 2.4.2-a  997 0.34 0.57 4.19 5.32    25 0.89 2.71  247 1150 4067
skinny    Linux 2.4.2-a  997 0.34 0.58 3.90 5.00    25 0.89 2.69  249 1121 3968
skinny    Linux 2.4.2-a  997 0.34 0.57 3.90 5.01    25 0.87 2.70  246 1126 4018

Context switching - times in microseconds - smaller is better
-------------------------------------------------------------
Host OS 2p/0K 2p/16K 2p/64K 8p/16K 8p/64K 16p/16K 16p/64K
ctxsw ctxsw ctxsw ctxsw ctxsw ctxsw ctxsw
--------- ------------- ----- ------ ------ ------ ------ ------- -------

skinny    Linux 2.4.2-a 1.820 4.7700     12 8.0800    109      27     110
skinny    Linux 2.4.2-a 1.890 4.7300     20 6.6500    109      27     110
skinny    Linux 2.4.2-a 1.620 4.5900     12 6.7000    109      24     109
skinny    Linux 2.4.2-a 1.700 4.6400     12 7.0600    109      26     109

*Local* Communication latencies in microseconds - smaller is better
-------------------------------------------------------------------
Host OS 2p/0K Pipe AF UDP RPC/ TCP RPC/ TCP
ctxsw UNIX UDP TCP conn
--------- ------------- ----- ----- ---- ----- ----- ----- ----- ----

skinny    Linux 2.4.2-a 1.820 7.390   15    16    52    23    91   55
skinny    Linux 2.4.2-a 1.890 7.185   14    16    41    23    56   54
skinny    Linux 2.4.2-a 1.620 6.793   15    16    40    21    56   54
skinny    Linux 2.4.2-a 1.700 6.801   15    16    40    21    55   54

File & VM system latencies in microseconds - smaller is better
--------------------------------------------------------------

Host                 OS   0K File      10K File      Mmap    Prot    Page	
                        Create Delete Create Delete  Latency Fault   Fault 
--------- ------------- ------ ------ ------ ------  ------- -----   ----- 
skinny    Linux 2.4.2-a 6.2054 0.7192     12 1.6973      451 0.672 2.00000
skinny    Linux 2.4.2-a 6.2469 0.7360     12 1.7142      465 0.668 2.00000
skinny    Linux 2.4.2-a 3.1992 0.7182     12 1.5857      449 0.680 2.00000
skinny    Linux 2.4.2-a 6.1576 0.7119     12 1.5817      448 0.669 2.00000

*Local* Communication bandwidths in MB/s - bigger is better
-----------------------------------------------------------
Host OS Pipe AF TCP File Mmap Bcopy Bcopy Mem Mem
UNIX reread reread (libc) (hand) read write
--------- ------------- ---- ---- ---- ------ ------ ------ ------ ---- -----

skinny    Linux 2.4.2-a  823  233  162    434    558    271    218  558   282
skinny    Linux 2.4.2-a  828  289  243    408    558    269    216  558   281
skinny    Linux 2.4.2-a  839  285  249    445    558    222    147  558   219
skinny    Linux 2.4.2-a  811  284  242    445    558    222    147  558   219

Memory latencies in nanoseconds - smaller is better
(WARNING - may not be correct, check graphs)
---------------------------------------------------

Host                 OS   Mhz  L1 $   L2 $    Main mem    Guesses
--------- -------------  ---- ----- ------    --------    -------
skinny    Linux 2.4.2-a   997 3.009 7.0230    101
skinny    Linux 2.4.2-a   997 3.010 7.0220    101
skinny    Linux 2.4.2-a   997 3.010 7.0280    101
skinny    Linux 2.4.2-a   997 3.009 7.0290    101

no doubt priority-queue can run almost as fast as the current scheduler. What i'm worried about is the restriction of the 'priority' of processes, it cannot depend on previous processes (and other 'current state') anymore.

to so we have two separate issues:

#1: priority-queue: has the fundamental goodness() design limitation.

#2: per-CPU-runqueues: changes semantics, makes scheduler less
effective due to nonglobal decisions.

about #1: while right now the prev->mm rule appears to be a tiny issue (it might not affect performance significantly), but forbidding it by hardcoding the assumption into data structures is a limitation of *future* goodness() functions. Eg. with the possible emergence of CPU-level threading and other, new multiprocessing technologies, this could be a *big* mistake.

the Linux scheduler is not designed for the case of 1000 runnable processes.

Ingo

This is not correct Ingo. I haven't seen the HP code but if You store processes in slots S :

S = FS( goodness(p, p->processor, p->mm) )

and You start scanning from the higher slots, as soon as you find a task with a goodness G' that is equal to the max goodness in slot You can choose that process to run.
Again, if You haven't found such a goodness during the slot scan but You've found a task with a goodness G' :

G' >= SG - DD

where :

SG = max slot goodness
DD = SG(i) - SG(i - 1)

You can select that task as the next to spin.
This was the behaviour that was implemented in my scheduler patch about 2 years ago.
Beside this, I this that with such loads We've more serious problem to face with inside the kernel.

- Davide

Actually, there is a significant difference between the HP patch and the one I developed. In the HP patch, if there is a schedulable task on the 'local' (current CPU) runqueue it will ignore runnable tasks on other (remote) runqueues. In the multi-queue patch I developed, the scheduler always attempts to make the same global scheduling decisions as the current scheduler.

Mike Kravetz                                 [email protected]
IBM Linux Technology Center

I was actually suspecting that the extra lines in your patch were there for a reason :)

A few questions:

What is the real impact of a (slight) change in scheduling semantics?

Under which situation one should notice a difference?

As you state in your papers the global decision comes with a cost, is it worth it?

Could you make a port of your thing on recent kernels?
I tried and I failed and I don't have enough time to figure out why, that should be trivial for you though.

TIA, ciao,

- Fabio

I assume your questions are directed at the difference between local and global scheduling decisions. As with most things the impact of these differences depends on workload. Most multi-queue scheduler implementations make local scheduling decisions and depend on load balancing for system wide fairness. Schedulers which make global decisions handle load balancing via their global policy.

The HP multi-queue implementation you are using performs no load balancing. Therefore, in a worst case situation you could have low priority tasks sharing one CPU while high priority tasks are sharing another. To be fair, I have talked to the HP people and this scheduler was never intended to be a general purpose solution. Therefore, it makes little sense to comment its merits as such.

My primary motivation for attempting to perform the same global decisions as the current scheduler was so that meaningful comparisons could be made. Also, by using the same global decision policy I was able to avoid the issue of load balancing. In most multi-queue implementations, load balancing algorithms take considerable effort to get working in a reasonable well performing manner.

There is a 2.4.2 patch on the web page. I'll put out a 2.4.3 patch as soon as I get some time.

Mike Kravetz                                 [email protected]
IBM Linux Technology Center