lkml.org 
[lkml]   [2000]   [Jan]   [31]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: Auto-Adaptive scheduler - Final chapter ( the numbers ) ...
Marco Colombo wrote:
> The question "How many switch / sec will do a system with RQ << 1?"
> makes no sense since there's no fixed relationship between the two
> numbers.

That's why the question is asked: what do we actually see when we
measure different applications?

_If_ we see that low RQ applications don't switch much, then we can
assert that low RQ applications aren't adversely affected by the patch.

> > > Let me state this: switch rate has *nothing* to do with load, nor does
> > > the RQ.
> >
> > which you follow by this counter-example:
> >
> > > you can have a server with 5 clients which shows a RQ of 5, if the
> > > backend server is trivially implemented with the basic accept()/fork()
> > > framework, or a RQ of 1 (and NEVER MORE, even with 1000 clients) if
> > > implemented with a clever select() loop (there are clever ways to do
> > > the fork() thing, too). Note that the load on the server is the same,
> > > and (with 5 clients) also the performances will be nearly the same.
> >
> > As you can clearly see,
> >
> > - when the first server is busy, it has a RQ of 5 and switches often
> > - when the second server is busy, it has a RQ of 1 and never switches
>
> [quite unrelated]
> ? never switches ? - i'm not sure of this. I'd like to see real world
> figures. Even the single process may sleep for net I/O, i think.
> So you get some switches. Anyway, that's not the point here.

You don't get switches because an assumption is "when the server is
busy". We're also assuming enough memory for queues etc. and that the
I/O subsystem isn't blocking anything. (A network proxy is the only
example I can think of).

In that case, there is always work to do, and the application always
does it within its single thread. If some network I/O is blocked, its bit
isn't set in select() and some other network I/O is done instead.

So the process never sleeps, and of course never schedules to another
process. (It's single threaded).

( If it does sleep for some reason we assume the time spent scheduling
is then absorbed into the idle period, though it may affect latency. )

> > Therefore in your example, RQ and switching rate are very closely related.
> They are (in my example).

Good. The rest of the article is written around your example, that is
why high RQ is considered synonymous with high switching rate :-)

> The example was made to show that "RQ" is not related to "load". Under
> the same load, you can have very different RQ, depending (in my
> example) on application design. Also it shows that "switch rate" is
> not related to "load". Again, in my example, it's related to
> application design instead.

The article is written around the assumption of constant, i.e., maximum
load. The relationship between "load" and any other parameter is
therefore not relevant.

> The example was not made to show that RQ is not related to switch rate.
> I can provide a easy one, but i don't think it's necessary, since I'm sure
> you know there's no such a fixed relationship.

The question is not "is there a fixed relationship", but "what
relationship do we see?" That depends on the applications that people
run of course. So it's roughly equivalent to "what applications do
people run?".

> > Real servers are not so simple of course. But let us stick with the
> > simple one.
>
> Yes. Counter-examples may be simple and silly... B-)
> Positive examples cannot not.

Oh dear :-)

> > > So please stop stating that:
> > >
> > > long RQ <=> high loads (1)
> >
> > Your own example just demonstrated that long RQ <=> high switching rate
>
> Oh, well, Jamie... below you teach me Logic. I'm pretty sure you know
> that an example does not (positively) "demonstrate" anything.
> You can use examples only to demonstrate something is *false*.

Quite. I used your example to demonstrate that the assertion "the
scheduler should not be patched because the patch adversely affects
single-threaded servers" is false :-)

> Why? You're assuming (like Davide) that small RQ means small switch rate...

That's because I'm assuming the simple server example like I said I was
earlier in the message... And in that example, small RQ <=> small
switch rate.

> Again! Everytime I say "small RQ" you translate into "low switch rate"!!
>
> [ "the scheduler isn't entered at all" - what do you mean?
> I take it for "low switch rate". But I've written "small RQ".
> Why do you keep mixing two unrelated things? ]

Because when considering only the two extreme implementations of a
simple server, "low switch rate" and "small RQ" _are_ related.

The article is a bit mixed up on this point -- I said I'm assuming the
simple server example, but it's easy to read as if I'm talking generalities.

> Yes, the scheduler *is* entered a lot of times under (certain kinds of)
> heavy load, and that's a NORMAL condition. High switch rates MAY be
> caused by real applications, even optimized ones. That's why the scheduler
> should be (and is) optimized to be fast. Please note that under this
> (common, sensible, right, desiderable, what else?) condition Davide's
> patch fails to be effective because the RQ is small.

Right, but can we have an example of such a "real application" please?

> Also the select() server may switch somethimes...
> but yes, I *agree* than in real world cases you can have high switch rates...

I agree too, but I'd like an example.

> > Now now, that isn't true if all the processes are scheduling around the
> > same memory image. At that point we might even find that it's kernel
> > stack cache conflicts that are most significant, in which case we might
> > want to colour the stack entry position a little...
>
> OK. The whole matter is for real world cases. I thought it was clear...
> Do you think the case you illustraded is common in real world
> applications?

Consider the canonical static HTTP server which has most of its files
mmapped. You receive a URL, look up the file in your hash table, and
write() the file. Really, very little happens in the application in
that case. The code is shared between all threads, including the kernel
TCP/IP part. Very little data is copied -- no bulk data, once zero-copy
TCP sending is implemented. And the hash lookup is optimised for
minimal cache impact.

Of course you could write that with select(), but then your write()
calls will block the server for the few pages that aren't in memory.
Better to use a few threads. I think that could schedule through a few
threads without too much cache churn.

> And BTW, if "the processes are scheduling around the same memory image",
> i think you are referring to the i-cache. They are doing the same
> "computation". Are they also processing the same data? If yes, can you
> even imagine a real, useful application that comes close to that behavior
> (all the CPUs doing the same thing on the same data)?

Sending files via zero-copy DMA to the network card. The bulk data
is never seen by the CPU.

> And if not, it seems clear to me that if you have N threads doing the
> same job, it's useless to have N bigger than the number of the CPUs,
> in the general case, unless they sleep for I/O every since and
> then. So the RQ is small anyway, unless we're on a > 16 CPUs SMP...

Indeed, the optimal number of threads would seem to be where there tends
to be 1 per CPU plus "a bit" where "a bit" is enough to cover the slack
due to blocking. And as blocking removes threads from the run queue,
that keeps the run queue size around, oh, .... <ta da> 1.

You get a more than one in fact because you can't perfectly predict when
you'll be blocking. You need more RQ load to keep working despite the
variation in blocking -- and even that isn't perfect. (So perfect might
be a way to keep that RQ level at 1 at all times, in other words kernel
assisted thread managament).

But as far as I know, you don't get a lot more than one simply to
optimise around I/O blocking.

So we can assume the applications the scheduler patch is targetted at
aren't these applications either. They're not simply "performance tuned
multi-threaded servers". They're "non-performance tuned multi-threaded
servers".

> Server design has an impact on switch rate, though. It can be high or low.
> Anyway, it says *nothing* on the RQ size. Let's assume the server is
> overloaded, and thus the RQ is long.

You got that from where? The single threaded server will have a maximum
RQ of 1.

> I think you can shorten the RQ even it this case, optimizing the
> application... and if you can't, either the hardware is overloaded
> (and there's little you can do, software-side), or some other kernel
> parts need to be optimized (assuming the application is not at fault).
> It's not a scheduler problem anyway. So please don't change it. Give
> us a better poll() , a clone_httpd_thread(), a do_apache_all(), or
> whatever. But don't change the scheduler, which is not at fault.

The point is that the scheduler patch is not targetted at the kinds of
applications you're thinking about.

As far as I can see, for all "performance tuned server applications",
that really are tweaked for performance at the application level, then
the scheduler we've got is pretty good. And the only remaining
optimisation is to do with blocking I/O, not run queue length at all.

The scheduler patch is targetted at what's left _after_ you've
considered all the performance-tuned applications. I.e. Java business
objects, which aren't performance-tuned by definition: they're written
using Java threads so performance is not the top priority.

> Ok, I'll dive into it... B-)
> But the matter is that operating a system with a large RQ it's usally
> a mistake. So no need to optimize the scheduler for that... fix the problem
> instead.

The only two known fixes are (a) don't write that kind of program in
Java; (b) something possibly complicated involving user space threads.

(a) isn't going to happen because, when you get right down to it,
performance is not actually the top priority. It's important, but it
takes second place or lower to other stuff.

> So, what's the purpose of the patch? To support broken application designs?
> If it comes at no costs, I agree. Davide's "no cost" argument is simply
> based on the wrong assumpion that "short RQ" means "low switch rate".

Correct, that is the purpose of the patch! :-)

The patch is to improve the performance of applications that _aren't_
written in the best way for performance. Because changing the
applications is too difficult -- changing the kernel is not.

have a nice day,
-- Jamie

-
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/

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