Re: [PATCH] Re: Negative scalability by removal of

From: Andrea Arcangeli (andrea@suse.de)
Date: Mon Nov 06 2000 - 11:03:41 EST


On Tue, Nov 07, 2000 at 01:27:07AM +1100, Andrew Morton wrote:
> context. For networking, where it is called from softirq context
> it is O(N).

Yes, the heuristic that runs from irqs has an O(N) worst case in wakeup.
But the current implementation is silly because the best case could run
without browsing the whole queue. This is an untested fix for such heuristic
implementation complexity problem:

--- 2.4.0-test10/kernel/sched.c.~1~ Thu Nov 2 20:59:05 2000
+++ 2.4.0-test10/kernel/sched.c Mon Nov 6 16:44:07 2000
@@ -742,9 +742,10 @@
                         if (irq && (state & mode & TASK_EXCLUSIVE)) {
                                 if (!best_exclusive)
                                         best_exclusive = p;
- else if ((p->processor == best_cpu) &&
- (best_exclusive->processor != best_cpu))
- best_exclusive = p;
+ if (p->processor == best_cpu) {
+ best_exclusive = p;
+ break;
+ }
                         } else {
                                 if (sync)
                                         wake_up_process_synchronous(p);

This also ensure a FIFO order between the threads that are affine to the
current CPU (while previously it was first LIFO for the affine threads and then
FIFO if there was none affine thread and that doesn't make sense, since for
seldom cases like accept we want LIFO in both cases and for everything else
like semaphores we need FIFO and just allowing affine tasks to pass the other
threads can generate starvation in theory... (and that heuristic in infact
not fair at all with tasks running in other CPUs while using irq affinity, and
on alpha we are likley to use it most of the time to avoid interrupting all the
CPUs).

> hmm.. Has this been changed in 2.4? The performance is the same.

It is fixed in 2.4.x. Anyways it probably worth to do the wake-one in 2.2.x
too even if it's a wake-three in the first stage.

Andrea
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/



This archive was generated by hypermail 2b29 : Tue Nov 07 2000 - 21:00:19 EST