xu_feng_xu@yahoo.com wrote:
?
>Hello,
>CPU scheduling quantum has remained about the same over the past 2
>decades, despite that the current processors are much much faster. Why
>haven't CPU scheduling quantaum changed much (remained nearly
>~100ms)?

What is the incentive? What is the gain? All it would do is increase the
overhead. The VAST majority of threads give up their quanta by doing I/O
long before the timeout expires.

In other words, "if it ain't broke, don't fix it."
--
Tim Roberts, timr@probo.com
Providenza & Boekelheide, Inc.

Tim Roberts writes:

> xu_feng_xu@yahoo.com wrote:
> ?
>>Hello,
>>CPU scheduling quantum has remained about the same over the past 2
>>decades, despite that the current processors are much much faster. Why
>>haven't CPU scheduling quantaum changed much (remained nearly
>>~100ms)?
>
> What is the incentive? What is the gain? All it would do is increase the
> overhead. The VAST majority of threads give up their quanta by doing I/O
> long before the timeout expires.

People have done experiments running Linux with a timer frequence of
10kHz. Nothing good came out of it.

--
Måns Rullgård
mru@inprovide.com

Tim Roberts wrote:
> xu_feng_xu@yahoo.com wrote:
> ?
> >Hello,
> >CPU scheduling quantum has remained about the same over the past 2
> >decades, despite that the current processors are much much faster. Why
> >haven't CPU scheduling quantaum changed much (remained nearly
> >~100ms)?
>
> What is the incentive? What is the gain? All it would do is increase the
> overhead. The VAST majority of threads give up their quanta by doing I/O
> long before the timeout expires.
>
> In other words, "if it ain't broke, don't fix it."

Are you sure that HZ is still at 100 in modern Linuxes? Anyways it is at 1000
in FreeBSD and similarly in Windows (from what i have heard). Specifically
people have tried measuring the added overhead going from 100 to 1000 in
FreeBSD and have not found anything significant. So the default has been kept
at 1000, which provides more reactivity.

--

Michel TALON

talon@lpthe.jussieu.fr (Michel Talon) writes:

> Tim Roberts wrote:
>> xu_feng_xu@yahoo.com wrote:
>> ?
>> >Hello,
>> >CPU scheduling quantum has remained about the same over the past 2
>> >decades, despite that the current processors are much much faster. Why
>> >haven't CPU scheduling quantaum changed much (remained nearly
>> >~100ms)?
>>
>> What is the incentive? What is the gain? All it would do is increase the
>> overhead. The VAST majority of threads give up their quanta by doing I/O
>> long before the timeout expires.
>>
>> In other words, "if it ain't broke, don't fix it."
>
> Are you sure that HZ is still at 100 in modern Linuxes?

Reasonably recent Linux kernels have compile-time configurable timer
frequency where the platform allows. Common choices on x86 are 100Hz,
250Hz, and 1000Hz. On Alpha the frequency has always been 1024 Hz.

--
Måns Rullgård
mru@inprovide.com

Tim Roberts wrote:
> xu_feng_xu@yahoo.com wrote:
> ?
> >Hello,
> >CPU scheduling quantum has remained about the same over the past 2
> >decades, despite that the current processors are much much faster. Why
> >haven't CPU scheduling quantaum changed much (remained nearly
> >~100ms)?
>
> What is the incentive? What is the gain? All it would do is increase the
> overhead. The VAST majority of threads give up their quanta by doing I/O
> long before the timeout expires.
>
> In other words, "if it ain't broke, don't fix it."
> --
> Tim Roberts, timr@probo.com
> Providenza & Boekelheide, Inc.

Having a short quantum will increase the overhead of context switch. a
longer one, decrease the interactivity. in this link
http://www.cag.lcs.mit.edu/~rinard/osnotes/h6.html

he suggests a heuristic rule that 80% of CPU bursts should be shorter
than the preset quantum. despite this, the quantum value has nearly
remained the same despite the exponential increase in the processor
speed. is it because the applications now include more threads and
capabilities, i.e. requiring more CPU cycles than their ancestors??

xu_feng_xu@yahoo.com wrote:

> Hello,

> CPU scheduling quantum has remained about the same over the past 2
> decades, despite that the current processors are much much faster. Why
> haven't CPU scheduling quantaum changed much (remained nearly
> ~100ms)?

CPU scheduling quantum is largely an interactivity tradeoff. Humans
haven't gotten much faster and network latencies haven't gotten much
lower, so there isn't much reason to reduce the quantum.

Caches and CPU state has gotten larger, and memory speed hasn't kept up
with CPU speed, so the cost of a context switch has remained roughly
constant. Typical modern systems have a scheduling quantum less than
10mS.

DS

xu_feng_xu@yahoo.com wrote:
> Tim Roberts wrote:
> > xu_feng_xu@yahoo.com wrote:
> > ?
> > >Hello,
> > >CPU scheduling quantum has remained about the same over the past 2
> > >decades, despite that the current processors are much much faster. Why
> > >haven't CPU scheduling quantaum changed much (remained nearly
> > >~100ms)?
> >
> > What is the incentive? What is the gain? All it would do is increase the
> > overhead. The VAST majority of threads give up their quanta by doing I/O
> > long before the timeout expires.
> >
> > In other words, "if it ain't broke, don't fix it."
> > --
> > Tim Roberts, timr@probo.com
> > Providenza & Boekelheide, Inc.
>
> Having a short quantum will increase the overhead of context switch. a
> longer one, decrease the interactivity. in this link
> http://www.cag.lcs.mit.edu/~rinard/osnotes/h6.html
>
> he suggests a heuristic rule that 80% of CPU bursts should be shorter
> than the preset quantum.

That point assumes that only the expiration of the time quantum causes
context switches, not any other events.

despite this, the quantum value has nearly
> remained the same despite the exponential increase in the processor
> speed. is it because the applications now include more threads and
> capabilities, i.e. requiring more CPU cycles than their ancestors??

The reason is that the quantum corresponds to human perception of
responsiveness. That is what hasn't changed in twenty years.

Time quanta are not needed for batch computing, and are not essential
for real-time use either. A batch system can use very long quanta. In
fact, it can just run jobs until they hit blocking I/O. A real-time
system can run the highest priority task until it voluntarily
deschedules itself, or some event arrives whose handler makes ahigher
priority task runnable. If such as system has clock hardware for wall
time, and doesn't need software timers, it can do without a clock tick.

Arguably, the concept of the slicing quantum is specifically applicable
in interactive systems where users are sharing time with each other, or
with background tasks.

When a user demands the computer's attention, for instance by pressing
a key, it's possible to dispatch a task in response to that quite
immediately, because an interrupt is generated, regardless of the time
quantum.

However, the response time is measured from that keypress until the
full handling of the event. In order for the system to be perceived as
responsive, the task which handles that keypress has to perform that
response quickly, say within 100 milliseconds. To ensure that the
keypress has that 100 milliseconds, the time quantum has to be at least
that long. If the quantum is shorter than what the task needs, then it
will be preempted to run other tasks. The time taken to slice through
those other tasks will be counted into the response time.

These days, it takes more cycles to respond to a user event. More stuff
happens. Larger, more complex data structures are updated, more complex
screen updates are performed and so on.

You cannot arbitrarily assert that since computers are faster now, all
applications shall only get a ten microsecond slice to produce a
response. It makes sense to just keep the slice the same, based on
human perception of responsiveness, and let software developers stuff
more computation into that slice as computers get faster.

talon@lpthe.jussieu.fr (Michel Talon) wrote:
>
>Are you sure that HZ is still at 100 in modern Linuxes? Anyways it is at 1000
>in FreeBSD and similarly in Windows (from what i have heard).

No, the default quantum in Windows is either 10ms or 16ms depending on the
HAL. The server systems use a longer quantum value.
--
Tim Roberts, timr@probo.com
Providenza & Boekelheide, Inc.

Tim Roberts wrote:
> talon@lpthe.jussieu.fr (Michel Talon) wrote:
> >
> >Are you sure that HZ is still at 100 in modern Linuxes? Anyways it is at 1000
> >in FreeBSD and similarly in Windows (from what i have heard).
>
> No, the default quantum in Windows is either 10ms or 16ms depending on the
> HAL. The server systems use a longer quantum value.

Yes, you are right, my memory is poor.
Since i have googled for this information, i have also found references to the
fact that Linux kernel 2.6 had a default HZ value of 1000 and went down to 250
for kernel 2.6.13, which is the sort of thing i remembered.
In fact the experience of FreeBSD shows that HZ=1000 works perfectly well, and
without noticeable extra overhead.


--

Michel TALON

Michel Talon wrote:

> Yes, you are right, my memory is poor.
> Since i have googled for this information, i have also found references to the
> fact that Linux kernel 2.6 had a default HZ value of 1000 and went down to 250
> for kernel 2.6.13, which is the sort of thing i remembered.
> In fact the experience of FreeBSD shows that HZ=1000 works perfectly well, and
> without noticeable extra overhead.

But also without noticeable benefit. The solution to quasi-real-time
problems is *not* a smaller timeslice as this just makes it more likely
that the quasi-real-time application won't finish what it needs to do
when it starts running.

For tasks that need real-time response, pre-emption makes sure they get
started as quickly as possible. Long timeslices make sure they get the
job done before every single other non-interactive process gets the
CPU.

The philosophy used to be to minimize pre-emption because of negative
cache effects and keep the timeslices smallish to minimize latency. The
new philosophy is to keep the timeslices longish to avoid negative
cache effects and pre-empt agressively to maximize interactiveness.

So, in a a sense, timeslices haven't changed much because processors
have gotten faster as scheduling philosophies have changed towards
larger timeslices.

DS

David Schwartz wrote:
>
> Michel Talon wrote:
>
> > Yes, you are right, my memory is poor.
> > Since i have googled for this information, i have also found references to the
> > fact that Linux kernel 2.6 had a default HZ value of 1000 and went down to 250
> > for kernel 2.6.13, which is the sort of thing i remembered.
> > In fact the experience of FreeBSD shows that HZ=1000 works perfectly well, and
> > without noticeable extra overhead.
>
> But also without noticeable benefit.

This is extremely debatable. There are people who think their machine is more
speedy and responsive under FreeBSD, but i shall not enter into a troll
debate. Linux is probably tuned to have a maximal server throughput.

> The solution to quasi-real-time
> problems is *not* a smaller timeslice as this just makes it more likely
> that the quasi-real-time application won't finish what it needs to do
> when it starts running.

It depends on how long the task is. It may be argued that, if the task has to
wait on IO, it will be deferred, but if it can really run, with the present
days fast processors, it can do a *lot* of things in 1 ms. In 1 ms you still
have one million processor cycles available. For many tasks, they will block
on IO well before having run so many processor cycles.

>
>

--

Michel TALON

talon@lpthe.jussieu.fr (Michel Talon) writes:
> David Schwartz wrote:
>> Michel Talon wrote:
>> > Yes, you are right, my memory is poor.
>> > Since i have googled for this information, i have also found references to the
>> > fact that Linux kernel 2.6 had a default HZ value of 1000 and went down to 250
>> > for kernel 2.6.13, which is the sort of thing i remembered.
>> > In fact the experience of FreeBSD shows that HZ=1000 works perfectly well, and
>> > without noticeable extra overhead.
>>
>> But also without noticeable benefit.
>
> This is extremely debatable. There are people who think their machine is more
> speedy and responsive under FreeBSD,

The HZ value is configurable when compiling the kernel. With HZ ==
1000, the kernel spends four times more time 'polling' if there is
anything more important to do than with HZ = 250, so 'the machine is
more speedy' can be dismissed outright, because the overhead is
higher. 'The machine is more responsive' is at least questionable,
because the difference is between 'maximum wait time of 0.004s' and
'maximum wait time of 0.001s', which should hardly be noticable (eg I
am sitting behind a network appliance running a 'content-filtering'
agent that asks a server in NJ [I am in Mainz/ FRG] for a list of
categories for each URL contained in each web page I surf to, which
adds a latency of about 0.1s, ie 25 times more than the larger of the
two times above, to the processing of every request. To me, this is
not generally noticeable).

What people believe about certain things is, of course, an entirely
different type of animal.

Rainer Weikusat wrote:
> talon@lpthe.jussieu.fr (Michel Talon) writes:
> > David Schwartz wrote:
> >> Michel Talon wrote:
> >> > Yes, you are right, my memory is poor.
> >> > Since i have googled for this information, i have also found references to the
> >> > fact that Linux kernel 2.6 had a default HZ value of 1000 and went down to 250
> >> > for kernel 2.6.13, which is the sort of thing i remembered.
> >> > In fact the experience of FreeBSD shows that HZ=1000 works perfectly well, and
> >> > without noticeable extra overhead.
> >>
> >> But also without noticeable benefit.
> >
> > This is extremely debatable. There are people who think their machine is more
> > speedy and responsive under FreeBSD,
>
> The HZ value is configurable when compiling the kernel. With HZ ==
> 1000, the kernel spends four times more time 'polling' if there is
> anything more important to do than with HZ = 250, so 'the machine is
> more speedy' can be dismissed outright, because the overhead is
> higher. 'The machine is more responsive' is at least questionable,

We are clearly entering a troll debate. If the time spent in the scheduler
is small enough, it is totally irrelevant that the scheduler runs each ms or
each 10 ms. So this boils down to the efficiency of the scheduler, and
the Linux scheduler is very efficient, the Linux task switching is very fast.
We are here speaking of times of the order of the microsecond, that is 1000
times smaller at least than the quantum, whatever it is.

Anyways, Linux developers were of the opinion that HZ=1000 was a good thing
since this is the default value at the beginning of kernel 2.6. It happens that
Linus T. who is very opinionated on some subjects, reduced HZ to 250 for
the 2.6.13 kernel, and not to 100 HZ, as you can note. He was also a strong
opponent of preemption, still kernel 2.6 is preemptive. Not to mention he was
opposed to freebsd-style VM management, still kernel 2.6 has it.

> two times above, to the processing of every request. To me, this is
> not generally noticeable).

What about servers systems which run thousands of threads, like big
JBoss or Tomcat installations. With HZ=100, how many *seconds* does it
take to cycle between the threads?

>
> What people believe about certain things is, of course, an entirely
> different type of animal.

Yes, of course, amen.


--

Michel TALON

talon@lpthe.jussieu.fr (Michel Talon) writes:
> Rainer Weikusat wrote:
>> talon@lpthe.jussieu.fr (Michel Talon) writes:
>> > David Schwartz wrote:
>> >> Michel Talon wrote:
>> >> > Yes, you are right, my memory is poor.
>> >> > Since i have googled for this information, i have also found references to the
>> >> > fact that Linux kernel 2.6 had a default HZ value of 1000 and went down to 250
>> >> > for kernel 2.6.13, which is the sort of thing i remembered.
>> >> > In fact the experience of FreeBSD shows that HZ=1000 works perfectly well, and
>> >> > without noticeable extra overhead.
>> >>
>> >> But also without noticeable benefit.
>> >
>> > This is extremely debatable. There are people who think their machine is more
>> > speedy and responsive under FreeBSD,
>>
>> The HZ value is configurable when compiling the kernel. With HZ ==
>> 1000, the kernel spends four times more time 'polling' if there is
>> anything more important to do than with HZ = 250, so 'the machine is
>> more speedy' can be dismissed outright, because the overhead is
>> higher. 'The machine is more responsive' is at least questionable,
>
> We are clearly entering a troll debate.

I take this is promise on your behalf that you will try to avoid
technical discussion in favor of personal insults as far as possible ...

> If the time spent in the scheduler is small enough, it is totally
> irrelevant that the scheduler runs each ms or each 10 ms.

If the scheduler runs each ms, it spends ten times the time it would
spend if it runs each 10 ms. This is a plain and simple fact, no use
to argue about it. So a machine where the scheduler runs each ms will
have less CPU time available to spend on useful work than a machine
where the scheduler runs each 10ms. Therefore, processing of useful
work is going to be slower on the first machine and faster on the
second. The question was not if you consider the additional overhead
to be negligent, but if the machine actually can become faster this
way ('more speedy') and the answer to that question is no.

[diatribe deleted]

> Anyways, Linux developers were of the opinion that HZ=1000 was a good thing
> since this is the default value at the beginning of kernel 2.6.

This is a tradeoff, and, depending on what you are trying to
accomplish, different things may make sense.

> It happens that Linus T. who is very opinionated on some subjects,
> reduced HZ to 250 for the 2.6.13 kernel, and not to 100 HZ, as you
> can note.

I do note that you are talking about 100 Hz without an apparent
motivation.

> He was also a strong opponent of preemption, still kernel 2.6 is
> preemptive. Not to mention he was opposed to freebsd-style VM
> management, still kernel 2.6 has it.

How does this relate to my text? And what are you up to, anyway?

>> two times above, to the processing of every request. To me, this is
>> not generally noticeable).
>
> What about servers systems which run thousands of threads, like big
> JBoss or Tomcat installations. With HZ=100, how many *seconds* does it
> take to cycle between the threads?

It is unclear to me how this should relate to the issue I was talking
about (namely, that 0.001s and 0.004s are hardly noticeable
differences for humans). Additionally, you fail to tell what you are
up to.

>> What people believe about certain things is, of course, an entirely
>> different type of animal.
>
> Yes, of course, amen.

Trottel.

Rainer Weikusat wrote:
>
> If the scheduler runs each ms, it spends ten times the time it would
> spend if it runs each 10 ms. This is a plain and simple fact, no use
> to argue about it. So a machine where the scheduler runs each ms will
> have less CPU time available to spend on useful work than a machine
> where the scheduler runs each 10ms. Therefore, processing of useful
> work is going to be slower on the first machine and faster on the
> second. The question was not if you consider the additional overhead
> to be negligent, but if the machine actually can become faster this
> way ('more speedy') and the answer to that question is no.

You seem to be a mathematician, i am a physicist, and so for me a number which
is irrelevant, i don't consider it. That is if the scheduler overhead is
1/1000 or 1/10000 i could not care less. Other operating system overheads
are far more considerable anyways. And by the way a "fast" machine is not and
has never been a machine with maximal throughput. Maximal throughput was
obtained on old big iron machines by purely batch systems where computations
were not interrupted. Since the advent of time sharing systems, the speed
is the apparent speed you see as a time sharing user.

> >
> > What about servers systems which run thousands of threads, like big
> > JBoss or Tomcat installations. With HZ=100, how many *seconds* does it
> > take to cycle between the threads?
>
> It is unclear to me how this should relate to the issue I was talking
> about (namely, that 0.001s and 0.004s are hardly noticeable
> differences for humans). Additionally, you fail to tell what you are
> up to.
>

It is very relevant, because the scheduler will cycle between a lot of
programs before returning to the one with which you are interacting.
Typically 100 programs on a desktop and thousands on a server. So
the 1 ms or 10 ms duration of the quantum may have to be multiplied by some
big N number before you see the effective latency you observe on your machine.
And i am not in any ways up to proving any theory. Someone asked why, since
the machines run 100 times faster than ten years ago people still use the same
quantum. Another person said that today programs are much bigger than old
programs so that they need a relative bigger quantum to proceed. This at least
is reasonable. It may be that indeed HZ=1000 is a reasonable compromise.
Perhaps HZ=250 is also a reasonable compromise. Definitely HZ=10000 is bad.
And it may be that HZ=100 is bad except for certain types of servers who don't
run heavily threaded programs.

> >> What people believe about certain things is, of course, an entirely
> >> different type of animal.
> >
> > Yes, of course, amen.
>
> Trottel.

--

Michel TALON

Michel Talon wrote:
> Tim Roberts wrote:
> > talon@lpthe.jussieu.fr (Michel Talon) wrote:
> > >
> > >Are you sure that HZ is still at 100 in modern Linuxes? Anyways it is at 1000
> > >in FreeBSD and similarly in Windows (from what i have heard).
> >
> > No, the default quantum in Windows is either 10ms or 16ms depending on the
> > HAL. The server systems use a longer quantum value.
>
> Yes, you are right, my memory is poor.
> Since i have googled for this information, i have also found references to the
> fact that Linux kernel 2.6 had a default HZ value of 1000 and went down to 250
> for kernel 2.6.13, which is the sort of thing i remembered.
> In fact the experience of FreeBSD shows that HZ=1000 works perfectly well, and
> without noticeable extra overhead.

However, note that HZ isn't the time quantum. The time quantum consists
of an independently configurable number of clock ticks.

There are reasons for wanting a finer granularity HZ, not related to
time slicing. The interrupt timer drives software timers, which means
that with a larger HZ, you can have finer-grained timing. On systems
without clock hardware, you also get a more precise clock with a larger
HZ.

Take a look at the header linux/init_task.h, the macro INIT_TASK(), how
the .time_slice member is set up.

Also, look at the DEF_TIMESLICE macro in kernel/sched.c. It's defined
as 100*HZ/1000, which means one tenth of a second, regardless of what
HZ is set to.

Michel Talon wrote:

> David Schwartz wrote:

> > Michel Talon wrote:

> > > Yes, you are right, my memory is poor.
> > > Since i have googled for this information, i have also found references to the
> > > fact that Linux kernel 2.6 had a default HZ value of 1000 and went down to 250
> > > for kernel 2.6.13, which is the sort of thing i remembered.
> > > In fact the experience of FreeBSD shows that HZ=1000 works perfectly well, and
> > > without noticeable extra overhead.

> > But also without noticeable benefit.

> This is extremely debatable. There are people who think their machine is more
> speedy and responsive under FreeBSD, but i shall not enter into a troll
> debate. Linux is probably tuned to have a maximal server throughput.

I'm specifically talking about FreeBSD with HZ=250 compared to FreeBSD
with HZ=1000. I'm not comparing Linux to FreeBSD as a way to make an
argument about time quantum size, that wouldn't make any sense because
so many other things are different.

DS