Periodic clock tick considered harmful (was: Re: HZ, preferably as small as possible)

Periodic clock tick considered harmful (was: Re: HZ, preferably as small as possible)

[dank]

Mark Mielke <mark@mark.mielke.cc> wrote:
> 
> On Wed, Jul 10, 2002 at 04:09:21PM -0600, Cort Dougan wrote:
> > Yes, please do make it a config option.  10x interrupt overhead makes me
> > worry.  It lets users tailor the kernel to their expected load.
> 
> All this talk is getting to me.
> 
> I thought we recently (1 month ago? 2 months ago?) concluded that
> increases in interrupt frequency only affects performance by a very
> small amount, but generates an increase in responsiveness. The only
> real argument against that I have seen, is the 'power conservation'
> argument. The idea was, that the scheduler itself did not execute
> on most interrupts. The clock is updated, and that is about all.

On UML and mainframe Linux, *any* periodic clock tick 
is heavy overhead when you have a large number of 
(mostly idle) instances of Linux running, isn't it?   
I think I once heard those architectures went to great lengths 
to avoid periodic clock ticks.  (My memory is rusty, though.)

How about this: let's apply the high-resolution timer patch,
which adds explicit timer events inbetween the normal 100 Hz
events when needed to satisfy precise sleep requests.  Then
let's increase the interval between the normal periodic clock
events from 10ms to infinity.  Everything will keep working,
as the high-resolution timer patch code will schedule timer
events as needed -- but suddenly we'll have power consumption 
as low as possible, snappier performance, and the thousands-of-instances
case will no longer have this huge drain on performance from
periodic timer events that do nothing but update jiffiers.

OK, so I'm just an ignorant member of the peanut gallery, but
I'd like to hear a real kernel hacker explain why this isn't
the way to go.

- Dan

Re: Periodic clock tick considered harmful (was: Re: HZ, preferably as small as possible)

[Thunder from the hill]

Hi,

On Thu, 11 Jul 2002 dank@kegel.com wrote:

> Then let's increase the interval between the normal periodic clock
> events from 10ms to infinity.  Everything will keep working, as the
> high-resolution timer patch code will schedule timer events as needed --
> but suddenly we'll have power consumption as low as possible, snappier
> performance, and the thousands-of-instances case will no longer have
> this huge drain on performance from periodic timer events that do
> nothing but update jiffiers.

Well, that's the aim.

> OK, so I'm just an ignorant member of the peanut gallery, but
> I'd like to hear a real kernel hacker explain why this isn't
> the way to go.

The only thing that was mentioned yet was the amount of stuff that depends 
on periodic ticks. If we just tick unperiodically, we'd fail for sure, but 
if we make these instances depend on another timer - we won.

I think a good scheduler can handle this and should also be able to 
determine a halfaway optimal tick rate for the current load.

That's a _real_ challenge, guys!

							Regards,
							Thunder
-- 
(Use http://www.ebb.org/ungeek if you can't decode)
------BEGIN GEEK CODE BLOCK------
Version: 3.12
GCS/E/G/S/AT d- s++:-- a? C++$ ULAVHI++++$ P++$ L++++(+++++)$ E W-$
N--- o?  K? w-- O- M V$ PS+ PE- Y- PGP+ t+ 5+ X+ R- !tv b++ DI? !D G
e++++ h* r--- y- 
------END GEEK CODE BLOCK------

Re: Periodic clock tick considered harmful (was: Re: HZ, preferably as small as possible)

[Hubertus Franke]

On Thursday 11 July 2002 03:45 pm, Arnd Bergmann wrote:
> Thunder from the hill wrote:
> > On Thu, 11 Jul 2002 dank@kegel.com wrote:
> >> OK, so I'm just an ignorant member of the peanut gallery, but
> >> I'd like to hear a real kernel hacker explain why this isn't
> >> the way to go.
> >
> > The only thing that was mentioned yet was the amount of stuff that
> > depends on periodic ticks. If we just tick unperiodically, we'd fail for
> > sure, but if we make these instances depend on another timer - we won.
> >
> > I think a good scheduler can handle this and should also be able to
> > determine a halfaway optimal tick rate for the current load.
>
> The current approach on s390 is stop the timer tick only for idle cpus,
> because that's where it hurts. A busy system can just keep on using 100
> (or 1000) Hz timers.
> The jiffies value then gets updated from the time stamp counter when an
> interrupt happens on an idle CPU.
>
> See Martin Schwidefsky's recent post for code:
>
> http://marc.theaimsgroup.com/?l=linux-kernel&m=102578746520177&w=2
> http://marc.theaimsgroup.com/?l=linux-kernel&m=102578746420174&w=2
>
>         Arnd <><
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/


There has also been some work done by Michael Olsen (cmolsen@us.ibm.com)
regarding noperiodic jiffie updates. This was in the context of embedded 
handheld devices, in particular IBM's LinuxWatch. Similar problem
arise in such devices where the timer tick can be a significant source of 
battery drainage.
There are/were some settled differences between Michael and Martin approach, 
which I won't be able to adequately describe. 
I believe Michael has a publication on this, I let him respond.

-- 
-- Hubertus Franke  (frankeh@watson.ibm.com)

Re: Periodic clock tick considered harmful (was: Re: HZ, preferably as small as possible)

[george anzinger]

dank@kegel.com wrote:
> 
> Mark Mielke <mark@mark.mielke.cc> wrote:
> >
> > On Wed, Jul 10, 2002 at 04:09:21PM -0600, Cort Dougan wrote:
> > > Yes, please do make it a config option.  10x interrupt overhead makes me
> > > worry.  It lets users tailor the kernel to their expected load.
> >
> > All this talk is getting to me.
> >
> > I thought we recently (1 month ago? 2 months ago?) concluded that
> > increases in interrupt frequency only affects performance by a very
> > small amount, but generates an increase in responsiveness. The only
> > real argument against that I have seen, is the 'power conservation'
> > argument. The idea was, that the scheduler itself did not execute
> > on most interrupts. The clock is updated, and that is about all.
> 
> On UML and mainframe Linux, *any* periodic clock tick
> is heavy overhead when you have a large number of
> (mostly idle) instances of Linux running, isn't it?
> I think I once heard those architectures went to great lengths
> to avoid periodic clock ticks.  (My memory is rusty, though.)
> 
> How about this: let's apply the high-resolution timer patch,
> which adds explicit timer events inbetween the normal 100 Hz
> events when needed to satisfy precise sleep requests.  Then
> let's increase the interval between the normal periodic clock
> events from 10ms to infinity.  Everything will keep working,
> as the high-resolution timer patch code will schedule timer
> events as needed -- but suddenly we'll have power consumption
> as low as possible, snappier performance, and the thousands-of-instances
> case will no longer have this huge drain on performance from
> periodic timer events that do nothing but update jiffiers.

Ah, but you haven't looked at all that happens on a 1/HZ
tick.  The high-res-timers patch does NOT eliminate the 1/HZ
tick.  That tick is used to do a LOT of accounting activity
which IMHO is best done by a periodic tick.  In particular,
the time slice and execution time management depend on the
periodic tick.  As a test we put together a tickless system,
much as suggested above, and put enough stuff in it to see
what the overhead was and how it changed.  The conclusion
was that the timer over head increased far beyond the
current overhead as soon as the system load (actually the
number of context switches per second) increased beyond what
a moderately busy system experiences.  In other words, the
system was overload prone.  The current accounting activity
is flat WRT to context switching which is IMHO just what it
should be.  For those who want to know, a patch to put that
test system together is still on the HRT sourceforge site.

-g
> 
> OK, so I'm just an ignorant member of the peanut gallery, but
> I'd like to hear a real kernel hacker explain why this isn't
> the way to go.
> 
> - Dan

-- 
George Anzinger   george@mvista.com
High-res-timers: 
http://sourceforge.net/projects/high-res-timers/
Real time sched:  http://sourceforge.net/projects/rtsched/
Preemption patch:
http://www.kernel.org/pub/linux/kernel/people/rml

Re: Periodic clock tick considered harmful (was: Re: HZ, preferably as small as possible)

[mbs]

george, 

	with the HRT is there any reason to have 10 timer interrupts per process 
quantum anymore? (10 ms ticks, 100 ms proc quantum)



On Thursday 11 July 2002 15:06, george anzinger wrote:
> Ah, but you haven't looked at all that happens on a 1/HZ
> tick.  The high-res-timers patch does NOT eliminate the 1/HZ
> tick.  That tick is used to do a LOT of accounting activity
> which IMHO is best done by a periodic tick.  In particular,
> the time slice and execution time management depend on the
> periodic tick.  As a test we put together a tickless system,
> much as suggested above, and put enough stuff in it to see
> what the overhead was and how it changed.  The conclusion
> was that the timer over head increased far beyond the
> current overhead as soon as the system load (actually the
> number of context switches per second) increased beyond what
> a moderately busy system experiences.  In other words, the
> system was overload prone.  The current accounting activity
> is flat WRT to context switching which is IMHO just what it
> should be.  For those who want to know, a patch to put that
> test system together is still on the HRT sourceforge site.
>
> -g
>
> > OK, so I'm just an ignorant member of the peanut gallery, but
> > I'd like to hear a real kernel hacker explain why this isn't
> > the way to go.
> >
> > - Dan

-- 
/**************************************************
**   Mark Salisbury       ||      mbs@mc.com     **
** If you would like to sponsor me for the       **
** Mass Getaway, a 150 mile bicycle ride to for  **
** MS, contact me to donate by cash or check or  **
** click the link below to donate by credit card **
**************************************************/
https://www.nationalmssociety.org/pledge/pledge.asp?participantid=86736

Re: Periodic clock tick considered harmful (was: Re: HZ, preferably as small as possible)

[Arnd Bergmann]

Thunder from the hill wrote:
> On Thu, 11 Jul 2002 dank@kegel.com wrote:
>> OK, so I'm just an ignorant member of the peanut gallery, but
>> I'd like to hear a real kernel hacker explain why this isn't
>> the way to go.
> 
> The only thing that was mentioned yet was the amount of stuff that depends
> on periodic ticks. If we just tick unperiodically, we'd fail for sure, but
> if we make these instances depend on another timer - we won.
> 
> I think a good scheduler can handle this and should also be able to
> determine a halfaway optimal tick rate for the current load.

The current approach on s390 is stop the timer tick only for idle cpus,
because that's where it hurts. A busy system can just keep on using 100
(or 1000) Hz timers.
The jiffies value then gets updated from the time stamp counter when an 
interrupt happens on an idle CPU.

See Martin Schwidefsky's recent post for code:

http://marc.theaimsgroup.com/?l=linux-kernel&m=102578746520177&w=2
http://marc.theaimsgroup.com/?l=linux-kernel&m=102578746420174&w=2

        Arnd <><

Re: Periodic clock tick considered harmful (was: Re: HZ, preferably as small as possible)

[george anzinger]

mbs wrote:
> 
> george,
> 
>         with the HRT is there any reason to have 10 timer interrupts per process
> quantum anymore? (10 ms ticks, 100 ms proc quantum)

First blush is HELL YES!  The issue is accounting.  When you
ask how long a program ran, you are looking at the
accounting that happens on a tick.  This is where one of two
counters gets bumped (one for system, the other for user,
depending on what was interrupted).  This information could,
of course, be gathered every system call/ exit and every
context switch, BUT, there are FAR more system calls and
context switches than 1/HZ ticks.  Thus collecting
accounting info this way adds overhead as the system load
increases, a VERY BAD thing IMHO.

A second point is that tasks only run for a quantum IF they
never block or get preempted.  Most tasks will have some
fraction of a quantum remaining when they are scheduled.

-g
> 
> On Thursday 11 July 2002 15:06, george anzinger wrote:
> > Ah, but you haven't looked at all that happens on a 1/HZ
> > tick.  The high-res-timers patch does NOT eliminate the 1/HZ
> > tick.  That tick is used to do a LOT of accounting activity
> > which IMHO is best done by a periodic tick.  In particular,
> > the time slice and execution time management depend on the
> > periodic tick.  As a test we put together a tickless system,
> > much as suggested above, and put enough stuff in it to see
> > what the overhead was and how it changed.  The conclusion
> > was that the timer over head increased far beyond the
> > current overhead as soon as the system load (actually the
> > number of context switches per second) increased beyond what
> > a moderately busy system experiences.  In other words, the
> > system was overload prone.  The current accounting activity
> > is flat WRT to context switching which is IMHO just what it
> > should be.  For those who want to know, a patch to put that
> > test system together is still on the HRT sourceforge site.
> >
> > -g
> >
> > > OK, so I'm just an ignorant member of the peanut gallery, but
> > > I'd like to hear a real kernel hacker explain why this isn't
> > > the way to go.
> > >
> > > - Dan
> 
> --
> /**************************************************
> **   Mark Salisbury       ||      mbs@mc.com     **
> ** If you would like to sponsor me for the       **
> ** Mass Getaway, a 150 mile bicycle ride to for  **
> ** MS, contact me to donate by cash or check or  **
> ** click the link below to donate by credit card **
> **************************************************/
> https://www.nationalmssociety.org/pledge/pledge.asp?participantid=86736

-- 
George Anzinger   george@mvista.com
High-res-timers: 
http://sourceforge.net/projects/high-res-timers/
Real time sched:  http://sourceforge.net/projects/rtsched/
Preemption patch:
http://www.kernel.org/pub/linux/kernel/people/rml

Re: Periodic clock tick considered harmful (was: Re: HZ, preferably as small as possible)

[Per Jessen]

On Thu, 11 Jul 2002 09:44:35 -0700, dank@kegel.com wrote:

>Mark Mielke <mark@mark.mielke.cc> wrote:
>> 
>> On Wed, Jul 10, 2002 at 04:09:21PM -0600, Cort Dougan wrote:
>> > Yes, please do make it a config option.  10x interrupt overhead makes me
>> > worry.  It lets users tailor the kernel to their expected load.
>> 
>> All this talk is getting to me.
>> 
>> I thought we recently (1 month ago? 2 months ago?) concluded that
>> increases in interrupt frequency only affects performance by a very
>> small amount, but generates an increase in responsiveness. The only
>> real argument against that I have seen, is the 'power conservation'
>> argument. The idea was, that the scheduler itself did not execute
>> on most interrupts. The clock is updated, and that is about all.
>
>On UML and mainframe Linux, *any* periodic clock tick 
>is heavy overhead when you have a large number of 
>(mostly idle) instances of Linux running, isn't it?   

Without knowing what UML is in this context, but assuming that mainframe
means IBM s390 mainframes, I can confirm that any periodic clock tick
is heavy overhead. With or without (mostly) idle instances. 

/Per



regards,
Per Jessen, Zurich
http://www.enidan.com - home of the J1 serial console.

Windows 2001: "I'm sorry Dave ...  I'm afraid I can't do that."

Re: Periodic clock tick considered harmful (was: Re: HZ, preferably as

[Alan Cox]

> First blush is HELL YES!  The issue is accounting.  When you
> ask how long a program ran, you are looking at the
> accounting that happens on a tick.  This is where one of two

Thats also an implementation issue. Note that the current code is also
wildly inaccurate. Mr Shannon says we are good to at best 50 run/sleep
changes a second.  I've got "100% busy" workloads that are 99% asleep.

Tracking cpu usage at task switch works a lot better for newer processors
which as well as having rdtsc also have performance counters. In fact you
can do much more interesting things on modern PC class platforms like
scheduling using pre-emption interrupts based on instructions executed,
memory accesses and more.

Alan

Re: Periodic clock tick considered harmful (was: Re: HZ, preferably as

[george anzinger]

Alan Cox wrote:
> 
> > First blush is HELL YES!  The issue is accounting.  When you
> > ask how long a program ran, you are looking at the
> > accounting that happens on a tick.  This is where one of two
> 
> Thats also an implementation issue. Note that the current code is also
> wildly inaccurate. Mr Shannon says we are good to at best 50 run/sleep
> changes a second.  I've got "100% busy" workloads that are 99% asleep.
> 
> Tracking cpu usage at task switch works a lot better for newer processors
> which as well as having rdtsc also have performance counters. In fact you
> can do much more interesting things on modern PC class platforms like
> scheduling using pre-emption interrupts based on instructions executed,
> memory accesses and more.
> 
Oh, I agree.  Hardware could make all this a lot easier.  
-- 
George Anzinger   george@mvista.com
High-res-timers: 
http://sourceforge.net/projects/high-res-timers/
Real time sched:  http://sourceforge.net/projects/rtsched/
Preemption patch:
http://www.kernel.org/pub/linux/kernel/people/rml

Re: Periodic clock tick considered harmful (was: Re: HZ, preferably as small as possible)

[Karim Yaghmour]

george anzinger wrote:
> First blush is HELL YES!  The issue is accounting.  When you
> ask how long a program ran, you are looking at the
> accounting that happens on a tick.  This is where one of two
> counters gets bumped (one for system, the other for user,
> depending on what was interrupted).  This information could,
> of course, be gathered every system call/ exit and every
> context switch, BUT, there are FAR more system calls and
> context switches than 1/HZ ticks.  Thus collecting
> accounting info this way adds overhead as the system load
> increases, a VERY BAD thing IMHO.

In addition to syscall entries/exits and sched changes, you then
also need to keep track of interrupt and trap entries/exits in
order to have the complete picture. Even then, determining exactly
when you're going to return to user-space can be tricky. Your
statement is indeed accurate, exact accounting's cost increases
linearly with the number of events that occur.

Having exact accounting all the time is certainly not necessary,
but it is indeed sometimes useful. *shameless self-promotion*,
That's yet another reason why I think LTT's inclusion in the
mailing kernel would be helpful. In addition to the rest of
the capabilities it provides, it provides exact accounting for
whoever really needs it on the spot.

If you are looking for better accounting using clock ticks, then
have a look at McCanne and Torek's paper "A Randomized Sampling
Clock for CPU Utilization Estimation and Code Profiling"
presented at Usenix in '93. As the title implies, they vary
the clock to obtain random samples and therefore obtain very
accurate results about system accounting. The use of hardware
counters to obtain samples is also viable, although it's much
more arch dependent than random clock ticks.

Cheers,

Karim

===================================================
                 Karim Yaghmour
               karim@opersys.com
      Embedded and Real-Time Linux Expert
===================================================

Re: Periodic clock tick considered harmful (was: Re: HZ, preferably as small as possible)

[Linus Torvalds]

In article <3D2DB5F3.3C0EF4A2@kegel.com>,  <dank@kegel.com> wrote:
>
>How about this: let's apply the high-resolution timer patch,
>which adds explicit timer events inbetween the normal 100 Hz
>events when needed to satisfy precise sleep requests.

The thing is, I think that's the wrong way around.

What we should have is a notion of a reasonably high frequency timer,
and then _slow_it_down_ to something else if not needed.

Speeding the timer up is bad, because:
 - you do need to limit the speedup to _something_ anyway (and it might
   as well be HZ)
 - you get "partial jiffies", which means that only stuff that knows
   about the finer granularity gets it.

In contrast, if you slow things down in integer increments of "n", the
only thing you need to do is to add in "n" instead of "1" in the timer
tick handler.  Nobody else needs to really care - there is no such thing
as a "fractional jiffy". 

		Linus

Re: Periodic clock tick considered harmful (was: Re: HZ, preferably as small as possible)

[Linus Torvalds]

In article <agtm4f$iic$1@penguin.transmeta.com>,
Linus Torvalds <torvalds@transmeta.com> wrote:
>
>In contrast, if you slow things down in integer increments of "n", the
>only thing you need to do is to add in "n" instead of "1" in the timer
>tick handler.  Nobody else needs to really care - there is no such thing
>as a "fractional jiffy". 

An added issue: if you slow the tick down, you can easily do it in _one_
place: the idle loop. When you exit the idle loop you speed it up again,
and nobody is ever any wiser (sure, you need to know enough about timers
in idle to know when you can do it, but that's still fairly localized).

In constrast, if you speed the timer up, you have to make this quite
fundamental in timer handling, and have architecture-specific issues on
how to speed the timer up and down etc. Big ugh, compared to just havin
git in one place inside code that is already architecture-specific for
other reasons.

		Linus

Re: Periodic clock tick considered harmful (was: Re: HZ, preferably as small as possible)

[Martin Schwidefsky]

>We have a Linux kernel (2.4.18-rmk2) running on the IBM Linux Watch which
>skips timer ticks, but only when there's no work to be done. We have dubbed
>this timing scheme the Work Dependent Timing scheme.  Briefly, on every
>return to the "Linux idle loop", the kernel checks if there's more work to
>be done by parsing relevant lists and queues. If there's no current work to
>be done, nor any work to be done in the next timer tick, the software timer
>with the nearest timeout is retrieved and a hardware timer is programmed
>accordingly with the nearest timeout to wake up the system in time to service
>the associated software timer.

In principle that is what the version 2 of the s/390 timer patch does. My
timer patch is a bit more complicated since it has to cope with an SMP system
but that are just details in the backend code that deal with the question
which cpu is doing the calls to do_timer(). The idea is to stop the hz timer
for every cpu going idle. The last cpu going idle has to check if something is
on tq_timer. If there is work on tq_timer then the clock is not reprogrammed
and the next hz tick comes in normally. If there is nothing on tq_timer
then the next timer event is calculated from the tv1-tv5 arrays and the
clock comparator is reprogrammed. With that all cpus are truly doing nothing
until either the clock comparator or another hardware interrupt comes in.
That is where the monitor call instruction on s/390 comes into play. This neat
instruction either causes a program check or does nothing (a nop). This is
controlled by a bit in control register 8. So the additional cost on the
system entry path is just one cycle for the nop if a cpu is running normally.
The amount of additional work on the system entry path was the main backdraw
of version 1 of the timer patch.

Version 1 of the s/390 timer patch is even more radical. It eliminates the hz
timer completly. Timer events are done with the clock comparator and process
related timer (time slice, itimer and profiling timer) are done with the cpu
timer. Since there isn't a periodic check anymore every change related to
timers has to be notified to the architecture backend. That makes it necessary
to introduce two hooks timer_notify and itimer_notify that are called from
common code. Not really nice but necessary for this approach. A second, more
severe backdraw is the need to check on every system entry if a jiffy update
needs to be done and to do the calculations for proper process time accounting
(in fact the jiffy variable is replaced by a macro and is not a problem but
the wall_time and other internal timing stuff have to get updated).
This makes up for about 60 cycles in the system entry path. This shows up on
some micro benchmarks and was the reason to do version 2.

blue skies,
   Martin

P.S. the two timer patches are available on developer works:
http://www10.software.ibm.com/developerworks/opensource/linux390/current2_4_17.shtml#jun132002-timer
http://www10.software.ibm.com/developerworks/opensource/linux390/current2_4_17-may2002.shtml#timer20020531

Linux/390 Design & Development, IBM Deutschland Entwicklung GmbH
Schönaicherstr. 220, D-71032 Böblingen, Telefon: 49 - (0)7031 - 16-2247
E-Mail: schwidefsky@de.ibm.com