O(1) scheduler gives big boost to tbench 192

Is MQ based on the Davide Libenzi scheduler? (a version of Davide's scheduler is in the -aa tree).

tbench 192 is an anomaly test too. AIM looks like a nice "mixed" bench. Do you have any scripts for it? I'd like to use AIM too.

A side effect of O(1) in ac2 and jam6 on the 4 way box is a decrease in pipe bandwidth and an increase in pipe latency measured by lmbench:

kernel Pipe bandwidth in MB/s - bigger is better

-----------------------  ------
2.4.16                   383.93
2.4.19-pre3aa2           316.88
2.4.19-pre5              385.56
2.4.19-pre5-aa1          345.93
2.4.19-pre5-aa1-2g-hio   371.87
2.4.19-pre5-aa1-3g-hio   355.97
2.4.19-pre7              462.80
2.4.19-pre7-aa1          382.90

2.4.19-pre7-ac2 85.66
2.4.19-pre7-jam6 66.41
2.4.19-pre7-rl 464.60
2.4.19-pre7-rmap13 453.24

kernel                   Pipe latency in microseconds - smaller is better
-----------------------  -----
2.4.16                   12.73
2.4.19-pre3aa2           13.58
2.4.19-pre5              12.98
2.4.19-pre5-aa1          13.46
2.4.19-pre5-aa1-2g-hio   12.83
2.4.19-pre5-aa1-3g-hio   13.08
2.4.19-pre7              10.71
2.4.19-pre7-aa1          13.32
2.4.19-pre7-ac2          31.95
2.4.19-pre7-jam6         29.51
2.4.19-pre7-rl           10.71
2.4.19-pre7-rmap13       10.75

More at:
http://home.earthlink.net/~rwhron/kernel/bigbox.html

Randy Hron

No - Davide's is another variant. All three had similar goals and similar changes. MQ was the "first" public one written by Mike Kravetz and Hubertus Franke with help from a number of others.

The SGI folks may be using more custom scripts. I think there is a reasonable set of options in the released package. OSDL might also be playing with it (Wookie, are you out here?). Sequent used to have a large set of scripts but I don't know where those are at the moment. I may check around.

Not surprised. That seems to be one of our problems with volanomark testing at the moment and we have some hacks to help, one in TCP which allows the receiver to be scheduled on a "close" CPU which seems to help latency. Others are tweaks of the scheduler itself, with nothing conclusively better yet.

gerrit

Davide's patch reduces the complexity of the scheduler from O(N) where N is the number of tasks in the system, to O(N) where N is the number of simultaneous running tasks in the system. It's also a simple optimization and it can make responsiveness even better than the mainline scheduler. I know many people is using 2.4 with some thousand tasks with only a few of them (let's say a dozen of them) running simultaneously, so while the O(1) scheduler would be even better, the dyn-sched patch from Davide looked the most attractive for production usage given its simplicty. I also refined it a little while merging it with Davide's overview.

Soon I will also get into merging the O(1) scheduler, but first I want to inspect the interactivity and pipe bandwith effect, at least to understand why they are getting affected (one first variable could be the removal of the sync-wakeup, O(1) scheduler needs to get the wakeup anyways in order to run the task but still we can teach the O(1) scheduler that it must not try to reschedule the current task after queueing the new one). In theory dyn-sched would be almost optimal for well written applications with only 1 task per-cpu using async-io, but of course in many benchmark (and in some real life environemtn) there are an huge number of tasks running simultaneously and so dyn-sched doesn't help much there compared to mainline.

BTW, Randy, I seen my tree runs slower with tiobench, that's probably because I made the elevator anti-starvation logic more aggressive than mainline and the other kernel trees (to help interactive usage), could you try to run tiobench on -aa after elvtune -r 8192 -w 16384 /dev/hd[abcd] to verify? Thanks for the great benchmarking effort.

And for the reason fork is faster in -aa that's partly thanks to the reschedule-child-first logic, that can be easily merged in mainline, it's just in 2.5.

Andrea

Believe it or not, the increase in pipe latency could be considered a desirable result. I believe that lat_pipe (the latency test) uses two tasks that simply pass a token back and forth. With the 'old' scheduler these two tasks (mostly) got scheduled and ran on the same CPU which produced the 'best results'. With the O(1) scheduler, tasks have some affinity to the CPUs they last ran on. If the tasks end up on different CPUs, then they will have a tendency to stay there. In the case of lat_pipe, IPI latency (used to awaken/schedule a task on another CPU) is added to every 'pipe transfer'. This is bad for the benchmark, but good for most workloads where it is more important to run with warm caches than to be scheduled as fast as possible.

I believe the decrease in pipe bandwidth is a direct result of the removal of the '__wake_up_sync' support. I'm not exactly sure what the arguments were for adding this support to the 'old' scheduler. However, it was only used by the 'pipe_write' code when it had to block after waking up a the reader on the pipe. The 'bw_pipe' test exercised this code path. In the 'old' scheduler '__wake_up_sync' seemed to accomplish the following:
1) Eliminated (possibly) unnecessary schedules on 'remote' CPUs
2) Eliminated IPI latency by having both reader and writer execute on the same CPU
3) ? Took advantage of pipe data being in the CPU cache, by having the reader read data the writer just wrote into the cache. ?
As I said, I'm not sure of the arguments for introducing this functionality in the 'old' scheduler. Hopefully, it was not just a 'benchmark enhancing' patch.

I have experimented with reintroducing '__wake_up_sync' support into the O(1) scheduler. The modifications are limited to the 'try_to_wake_up' routine as they were before. If the 'synchronous' flag is set, then 'try_to_wake_up' trys to put the awakened task on the same runqueue as the caller without forcing a reschedule. If the task is not already on a runqueue, this is easy. If not, we give up. Results, restore previous bandwidth results.

BEFORE
------
Pipe latency: 6.5185 microseconds
Pipe bandwidth: 86.35 MB/sec

AFTER
-----
Pipe latency: 6.5723 microseconds
Pipe bandwidth: 540.13 MB/sec

Comments? If anyone would like to see/test the code (pretty simple really) let me know.

Mike

Are you doing prefetches on the pipe data in your system. Im curious if this is an SMP cross processor pipe issue or simply cache behaviour ?

I'm not doing any prefetches in the code (if that is what you are talking about). The code just moves the pipe reader to the same CPU as the pipe writer (which is about to block). Certainly, the pipe reader could take advantage of any data written by the writer still being in the cache.

The code added to 'try_to_wake_up' looks something like this:

        if (unlikely(synchronous)){
                rq = lock_task_rq(p, &flags);
                if (p->array || p->state == TASK_RUNNING) {
			/* We're too late */
                        unlock_task_rq(rq, &flags);
                        return success;
                }
                p->cpu = smp_processor_id(); /* Change CPU id */
                unlock_task_rq(rq, &flags);
                rq = lock_task_rq(p, &flags);
                p->state = TASK_RUNNING;
                if (!p->array) {
                        activate_task(p, rq);
                }
                unlock_task_rq(rq, &flags);
		return success;
	}

I'm not sure if 'synchronous' is still being passed all the way down to try_to_wake_up in your tree (since it was removed in 2.5). This is based off a back port of O(1) to 2.4.18 that Robert Love did. The rest of try_to_wake_up (the normal/common path) remains the same.

Mike

Hm, interesting. When Ingo removed the sync variants of wake_up he did it believing the load balancer would handle the case. Apparently, at least in this case, that assumption was wrong.

I agree with your earlier statement, though - this benchmark may be a case where it shows up negatively but in general the balancing is preferred. I can think of plenty of workloads where that is the case. I also wonder if over time the load balancer would end up putting the tasks on the same CPU. That is something the quick pipe benchmark would not show.

In 2.5 nor the 2.4 backport I did (what is in -ac) I don't think the sync flag is being passed down since the functionality was removed. The functions were rewritten I believe to not have that parameter at all.

It is just for pipes we previously used sync, no?

Robert Love

That's the only thing I know of that used it.

I'd really like to know if there are any real workloads that benefited from this feature, rather than just some benchmark. I can do some research, but was hoping someone on this list might remember. If there is a valid workload, I'll propose a patch. However, I don't think we should be adding patches/ features just to help some benchmark that is unrelated to real world use.

Mike

So my hypothesis about the sync wakeup in the below email proven to be right:

	http://marc.theaimsgroup.com/?l=linux-kernel&m=102050009725367&w=2

Many thanks for verifying this.

Personally if the two tasks ends blocking waiting each other, then I prefer them to be in the same cpu. That was the whole point of the optimization. If the pipe buffer is large enough not to require reader or writer to block, then we don't do the sync wakeup just now (there's a detail with the reader that may block simply because the writer is slow at writing, but it probably doesn't matter much). There are many cases where a PAGE_SIZE of buffer gets filled in much less then a timeslice, and for all those cases rescheduling the two tasks one after the other in the same cpu is a win, just like the benchmark shows. Think the normal pipes we do from the shell, like a "| grep something", they are very common and they all wants to be handled as a sync wakeups. In short when loads of data pass through the pipe with max bandwith, the sync-wakeup is a definitive win. If the pipe never gets filled then the writer never sync-wakeup, it just returns the write call asynchronously, but of course the pipe doesn't get filled because it's not a max-bandiwth scenario, and so the producer and the consumer are allowed to scale in multiple cpus by the design of the workload.

Comments?

I would like if you could pass over your changes to the O(1) scheduler to resurrect the sync-wakeup.

Andrea

Maybe this is the reason why O(1) scheduler has big latencies with pthread_cond_*() functions which original scheduler doesn't have? I think I tracked the problem down to try_to_wake_up(), but I was unable to fix it.

- Jussi Laako

PGP key fingerprint: 161D 6FED 6A92 39E2 EB5B  39DD A4DE 63EB C216 1E4B
Available at PGP keyservers

Ah this could be the same case. I just looked into the definition of the conditional variable pthread stuff and it looks like it _could_ be implemented using pipes but I do not see why it would per se. If it does not use pipes, then this sync issue is not at hand (only the pipe code passed 1 for the sync flag).

If it does not use pipes, we could have another problem - but I doubt it. Maybe the benchmark is just another case where it shows worse performance due to some attribute of the scheduler or load balancer?

Robert Love

In some cases, the O(1) scheduler will produce higher latencies than the old scheduler. On 'some' workloads/benchmarks the old scheduler was better because it had a greater tendency to schedule tasks on the same CPU. This is certainly the case with the lat_ctx and lat_pipe components of LMbench. Note that this has nothing to do with the wake_up sync behavior. Rather, it is the difference between scheduling a new task on the current CPU as opposed to a 'remote' CPU. You can schedule the task on the current CPU quicker, but this is not good for optimal cache usage. I believe the O(1) scheduler makes the correct trade off in this area.

Is there anything simple I can do to check the latencies of the pthread_cond_*() functions? I'd like to do some analysis of scheduler behavior, but am unfamiliar with the user level code.

Mike

I just wrote small test program (attached) for testing this. It is similar to my app, but for this test the soundcard is just used more as a timing source.

Adjust the buffer size so that it's on the edge of missing blocks then generate some system load to run it over the edge to see how sensitive it is and how many blocks are lost. I can see clear difference using kernel with original scheduler and with kernel having the O(1) scheduler.

It's quite sensitive when you run it without setuid privileges, but normal situation is to run it at SCHED_FIFO.

Because of famous ReiserFS tailmerging feature lost-and-rewrote part of it after crashing system with it. Found the the binary overwriting top of it after reboot... I was happy to have copied it to another machine over NFS just a few minutes before crash, so not much was lost.

- Jussi Laako

PGP key fingerprint: 161D 6FED 6A92 39E2 EB5B  39DD A4DE 63EB C216 1E4B
Available at PGP keyservers

Here is a patch to reintroduce __wake_up_sync() in 2.5.14. It would be interesting to see if this helps in some of the areas where people have seen a drop in performance. Since, 'full pipes' are the only users of this code, I would only expect to see benefit in workloads expecting high pipe bandwidth.

Let me know what you think.

Mike

diff -Naur linux-2.5.14/fs/pipe.c linux-2.5.14-pipe/fs/pipe.c
--- linux-2.5.14/fs/pipe.c	Mon May  6 03:37:52 2002
+++ linux-2.5.14-pipe/fs/pipe.c	Wed May  8 22:48:39 2002
@@ -116,7 +116,7 @@
 		 * writers synchronously that there is more
 		 * room.
 		 */
-		wake_up_interruptible(PIPE_WAIT(*inode));
+		wake_up_interruptible_sync(PIPE_WAIT(*inode));
 		if (!PIPE_EMPTY(*inode))
 			BUG();
 		goto do_more_read;
diff -Naur linux-2.5.14/include/linux/sched.h linux-2.5.14-pipe/include/linux/sched.h
--- linux-2.5.14/include/linux/sched.h	Mon May  6 03:37:54 2002
+++ linux-2.5.14-pipe/include/linux/sched.h	Thu May  9 20:47:19 2002
@@ -485,6 +485,11 @@
 #define wake_up_interruptible(x)	__wake_up((x),TASK_INTERRUPTIBLE, 1)
 #define wake_up_interruptible_nr(x, nr)	__wake_up((x),TASK_INTERRUPTIBLE, nr)
 #define wake_up_interruptible_all(x)	__wake_up((x),TASK_INTERRUPTIBLE, 0)
+#ifdef CONFIG_SMP
+#define wake_up_interruptible_sync(x)   __wake_up_sync((x),TASK_INTERRUPTIBLE, 1)
+#else
+#define wake_up_interruptible_sync(x)   __wake_up((x),TASK_INTERRUPTIBLE, 1)
+#endif
 asmlinkage long sys_wait4(pid_t pid,unsigned int * stat_addr, int options, struct rusage * ru);
 
 extern int in_group_p(gid_t);
diff -Naur linux-2.5.14/kernel/sched.c linux-2.5.14-pipe/kernel/sched.c
--- linux-2.5.14/kernel/sched.c	Mon May  6 03:37:57 2002
+++ linux-2.5.14-pipe/kernel/sched.c	Thu May  9 21:04:13 2002
@@ -329,27 +329,38 @@
  * "current->state = TASK_RUNNING" to mark yourself runnable
  * without the overhead of this.
  */
-static int try_to_wake_up(task_t * p)
+static int try_to_wake_up(task_t * p, int sync)
 {
 	unsigned long flags;
 	int success = 0;
 	runqueue_t *rq;
 
+repeat_lock_task:
 	rq = task_rq_lock(p, &flags);
-	p->state = TASK_RUNNING;
 	if (!p->array) {
+		if (unlikely(sync)) {
+			if (p->thread_info->cpu != smp_processor_id()) {
+				p->thread_info->cpu = smp_processor_id();
+				task_rq_unlock(rq, &flags);
+				goto repeat_lock_task;
+			}
+		}
 		activate_task(p, rq);
+		/*
+		 * If sync is set, a resched_task() is a NOOP
+		 */
 		if (p->prio < rq->curr->prio)
 			resched_task(rq->curr);
 		success = 1;
 	}
+	p->state = TASK_RUNNING;
 	task_rq_unlock(rq, &flags);
 	return success;
 }
 
 int wake_up_process(task_t * p)
 {
-	return try_to_wake_up(p);
+	return try_to_wake_up(p, 0);
 }
 
 void wake_up_forked_process(task_t * p)
@@ -872,7 +883,7 @@
  * started to run but is not in state TASK_RUNNING.  try_to_wake_up() returns
  * zero in this (rare) case, and we handle it by continuing to scan the queue.
  */
-static inline void __wake_up_common(wait_queue_head_t *q, unsigned int mode, int nr_exclusive)
+static inline void __wake_up_common(wait_queue_head_t *q, unsigned int mode, int nr_exclusive, int sync)
 {
 	struct list_head *tmp;
 	unsigned int state;
@@ -883,7 +894,7 @@
 		curr = list_entry(tmp, wait_queue_t, task_list);
 		p = curr->task;
 		state = p->state;
-		if ((state & mode) && try_to_wake_up(p) &&
+		if ((state & mode) && try_to_wake_up(p, sync) &&
 			((curr->flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive))
 				break;
 	}
@@ -897,7 +908,22 @@
 		return;
 
 	wq_read_lock_irqsave(&q->lock, flags);
-	__wake_up_common(q, mode, nr_exclusive);
+	__wake_up_common(q, mode, nr_exclusive, 0);
+	wq_read_unlock_irqrestore(&q->lock, flags);
+}
+
+void __wake_up_sync(wait_queue_head_t *q, unsigned int mode, int nr_exclusive)
+{
+	unsigned long flags;
+
+	if (unlikely(!q))
+		return;
+
+	wq_read_lock_irqsave(&q->lock, flags);
+	if (likely(nr_exclusive))
+		__wake_up_common(q, mode, nr_exclusive, 1);
+	else
+		__wake_up_common(q, mode, nr_exclusive, 0);
 	wq_read_unlock_irqrestore(&q->lock, flags);
 }
 
@@ -907,7 +933,7 @@
 
 	spin_lock_irqsave(&x->wait.lock, flags);
 	x->done++;
-	__wake_up_common(&x->wait, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, 1);
+	__wake_up_common(&x->wait, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, 1, 0);
 	spin_unlock_irqrestore(&x->wait.lock, flags);
 }