I think it shows up two things. One is the thundering herd problem on accept.
I've got some play patches for that now. They turn out (for that case) fairly
easy to do and to do roughly right.
Accept is only part of the problem though.
> This problem will not go away with small tweaks, such as Richard Gooch's
> seperate real-time queue.
Agreed
> Really, only a few values will change. This is extra work that is a waste
> of CPU time. In an ideal world, we can find the next runnable process in
> O(1), not O(runqueue len) time.
Currently a sleep/wake_one is O(1). That is hard to keep with an O(1)
scheduler.
p->counter has a fixed range. This means we can bucket sort the tasks for
O(1) insert delete.
If as well as the bucket pointers the list is chained then you can handle
the next process as O(1) for uniprocessor. update_process_times
continues to be O(1) but does slightly more work to move the task between
lists.
Why haven't I done this yet ?
Im stumped on how to handle the p->mm == prev->mm bonus without going
walking down the list of that priority and previous. Likewise the SMP
bonuses, although I can see one way to do it which doesnt sound nice
for a large array of CPU's - keep each runnable task array once per cpu
with that CPU's priorities.
> immediately what the next process to run is. I'll present the proposed
> solution at LE, and hopefully, we'll be able to talk about it more then.
Excellent. I look forward to this.
Alan
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/