[lkml]   [2003]   [Mar]   [6]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: [patch] "HT scheduler", sched-2.5.63-B3

On Thu, 6 Mar 2003, Ingo Molnar wrote:
> interesting approach,

Ahh.. After five emails on the subject, you finally took a look at the
patch? Good.

> but it has one problem which so far i tried to
> avoid: it makes it too easy for a process to gain a bonus.

Yes and no. It actually follows your rules:

> Until now
> pretty much the only way to get an interactive bonus was to actually
> sleep.

And that is still true. _Somebody_ has to sleep, and the bonus is still
entirely based on how long that somebody slept.

> Another rule was that interactivity is kept constant, ie. the only
> 'source' of interactivity was passing time, not some artificial activity
> performed by any process.

And this is also still true. Again, the only _source_ of interactivity is
the fact that the woken-up process slept for a noticeable time. There is
no "artificial source" there.

Do the math: the patch uses the exact same source as the current algorithm
does - it only changes the _cutoff_.

The current algorithm just throws away "interactivity bonus" points when
the sleeper has gotten to some maximum value.

The new one doesn't throw them away when it hits the maximum - it gives
them to the person who woke it up.

> Even the timeslice passing across fork()/exit()
> is controlled carefully to maintain the total sum of timeslices.

But my patch DID NOT CHANGE THE TOTAL SUM! Read the patch again.


+ int ticks = p->sleep_avg - MAX_SLEEP_AVG + current->sleep_avg;
p->sleep_avg = MAX_SLEEP_AVG;

Note how this breaks down:

"p->sleep_avg - MAX_SLEEP_AVG"

this is the part we're "throwing away", because the sleeper had already
accumulated enough interactivity points.

" + current->sleep_avg"

this is the part that the waker _already_had_.

if (ticks > MAX_SLEEP_AVG)
ticks = MAX_SLEEP_AVG;

This just says that the waker, too, will be limited by the "maximum
interactivity" thing.

if (!in_interrupt())
current->sleep_avg = ticks;

and this part says "we only give the potential boost to a _synchronous_
waker" (ie a network packet that comes in and wakes somebody up in
bottom half processing will _not_ cause an interactivity boost to a random

See? The patch maintains the rule that "interactivity" only gets created
by sleeping. The only thing it really does is to change how we
_distribute_ the interactivity we get. It gives some of the interactivity
to the waker.

> With the above code it's enough to keep a single helper thread around
> which blocks on a pipe, to create an almost endless source of
> interactivity bonus.

No. You do not get to "create" interactivity. All the CPU cycles you win
from interactivity you must have lost by having one of your processes wait
for it.

Sure - it changes the balance of who gets to be considered interactive.
But that's the whole _point_ of it.

> And does not even have to be 'deliberate' - there's
> tons of code that just waits for a CPU-bound task to finish (eg. 'make'
> waiting for gcc to finish), and which processes/threads have a maximum
> boost already, in which case the interactivity boost is not justified.

And if they already have the maximum boost, they won't get any more. Look
at the five lines of actual code added.

Also, note how your "waiting for gcc to finish" is still not true. Sure,
that "make" will be considered interactive, but it's not going to help the
waker (gcc) any, since it will be interactive waiting for gcc to _die_.

I can come up with better (ie "real") examples of where this changes

- "cc1" (slow) writes to a pipe to "as" (fast)

"as" is fast, so as ends up waiting most of the time. Thus it ends up
being marked interactive.

When cc1 wakes up as, assuming as has been marked "maximally
interactive", cc1 will get an interactivity boost too.

Is this "wrong"? Maybe, if you see it from a pure "interactivity"
standpoint. But another way of seeing it is to say that it automatically
tries to _balance_ this kind of pipeline - since "cc1" is much slower and
actually _wants_ the interactivity that "as" is clearly not ever going to
actually get any real advantage from, it is actually likely to be
perfectly fine give "cc1" a priority.

Also, note that if cc1 is _really_ slow (which it is) and really doesn't
wake up as very often, you won't see this effect, since the
"anti-interactive" code will balance things out.

In short, it's all about balancing. There are things that are
"pro-interactive" (real sleeping), and there are things that are
"anti-interactive" (using up your timeslice). The question is how you
spread out the bonus points (or the negative points).

The current scheduler doesn't spread them out at all. I think that's a
bug, since pipelines of multiple processes are actually perfectly common,
and X is only one example of this.

And my patch may spread it out _too_ much. Maybe we shouldn't give _all_
of the left-over interactivity to the waker. Maybe we should give just
half of it away..



To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

 \ /
  Last update: 2005-03-22 13:33    [W:0.190 / U:3.872 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site