Messages in this thread Patch in this message |  | | Date | Mon, 6 Nov 2000 17:03:41 +0100 | From | Andrea Arcangeli <> | Subject | Re: [PATCH] Re: Negative scalability by removal of |
| |
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/
|  |