why the time quantum has not changed much - Linux

This is a discussion on why the time quantum has not changed much - Linux ; 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)? Regards...

+ Reply to Thread
Results 1 to 18 of 18

Thread: why the time quantum has not changed much

  1. why the time quantum has not changed much

    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)?

    Regards


  2. Re: why the time quantum has not changed much

    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.

  3. Re: why the time quantum has not changed much

    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

  4. Re: why the time quantum has not changed much

    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


  5. Re: why the time quantum has not changed much

    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

  6. Re: why the time quantum has not changed much


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


  7. Re: why the time quantum has not changed much


    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


  8. Re: why the time quantum has not changed much

    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.


  9. Re: why the time quantum has not changed much

    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.

  10. Re: why the time quantum has not changed much

    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


  11. Re: why the time quantum has not changed much


    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


  12. Re: why the time quantum has not changed much

    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


  13. Re: why the time quantum has not changed much

    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.

  14. Re: why the time quantum has not changed much

    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


  15. Re: why the time quantum has not changed much

    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.

  16. Re: why the time quantum has not changed much

    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


  17. Re: why the time quantum has not changed much

    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.


  18. Re: why the time quantum has not changed much


    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


+ Reply to Thread