Not really. When an interactive task becomes runnable, you calculate the new
priority and insert it into the run-queue at the right place. Chances are that
the run-queue is empty and there's no work. Even if its not empty, its
probably pretty short, and your newly runnable processes has been asleep for a
while, so it has a higher priority than other runnable processes, so you find
its slot quickly, near the head of the list.
> - the priorities change quite often (the running
> process' priority is decreased every jiffie)
Yes, but more importantly, does each running process change position with
respect to other runnable processes every jiffie? The absolute value of the
priority matters less than the relative priority to other processes. For
example, if there's no contention (runnable processes <= number of CPUs) you
could defer calculating priority altogether.
> - with Richard's RT_queue patch, goodness() has
> become a little more efficient
Yes, but if you're inserting into the run queue based on priority, you'd always
put RT tasks first (ie, you sort on policy, then priority). This means that
even if there's lots of interactive runnable processes, your effective run
queue is the same as the number of runnable RT processes.
> - the run queue is very short most of the time,
> walking it is about as expensive as sorting
> each time
Not if you use insertion sort to put each process into its place as you insert,
rather than resorting the whole thing every time.
The main problem of doing ordered inserts into the run queue is that the
current scheduler code assumes that inserts can only happen at the head and so
it leaves the queue unlocked while traversing the list. This only affects SMP
performance though, and could be solved by having per-processor run queues.
Its debatable whether its worth the extra complexity though.
J
-
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/