~
The issue is not its length, but can we interrupt at its end. The key to high
res is being on time. If we want a 100usec resolution timer, we need to have
the low res timer hit its mark with something real close to this.
Indeed.
As an aside, one nice thing with Nish's code is that the maximum soft-
timer latency is only the maximum interval between ticks. This avoids
accumulating error caused by lost ticks.
I think you are confusing the x86 problems with lost ticks with the wider world.
Most archs have reasonable time resources and, while they may suffer from late
ticks, do not, therefor loose time. In as much as you can find a way to
eliminate time loss in the x86 due to lost ticks of the time base, you can also
do so with the current time keeping system. The current code is just to
dependant on catching every timer tick. It should use the other resources
available to it to cover any missing ticks. (We do this rather nicely in the
HRT patch, by the way.)
Now when the new code expires timers it does so against the timeofday
subsystem's notion of time instead of jiffies. It simply goes through
all the timer bucket entries between now and the last time we expired
timers.
This is not unlike what happens now. I would hope that the number of buckets
visited averages to to something real close to 1 per run_timers entery.
Well, as long as the HZ period is close to the timer-interval unit
length, this is true. However if the timer-interval unit is smaller,
multiple bucket entries would be expired. The performance considerations
here are being looked at and this may be an area where the concepts in
HRT might help (having a HRT specific sub-bucket).
This is where we get in trouble with HR timers. For a HR timer, we need to know
how to get a timer to expire (i.e. appear in the call back) at a well defined
and presise time (leaving aside latency issues). The above discription allows
timers to be put in buckets without (as near as I can tell) making transparent
exactly when the bucket will be emptied, only saying that it will be after the
latest timer in the bucket is due.
Now an interesting point you bring up above is when to schedule timer
interrupts. One could just have a fine-grained timer-interval unit and
crank up HZ, but clearly we don't want to schedule interrupts to go off
too frequently or the overhead won't be worth it. Instead to get high-
res timers, the idea is to look at the timer list and schedule
interrupts appropriately. Then we only take an interrupt when there is
work to do, rather then at regular periodic intervals when there may or
may not be anything to expire.
This would suggest that all timers are high res. I don't think this makes sense:
1) because most users just don't care that much about resolution and high-res
carries some overhead.
2) Not all platform hardware is able to handle high res.
Indeed, in our system all timers could be high res, but don't
necessarily need to be by default. It ends up being a function of how
finely-grained the timer-interval units are set to be and how
efficiently the hardware can be scheduled.
We currently ship HRT with a resolution of 1usec. Lets agree that you don't
want to even try to do this by adjusting the timer-interval.
I think high res timers should only be used when the user asks for them. This
keeps the overhead under control.
Abstractly that makes sense, but I'm not sure how you mean "when the
user asks for them". Is this a runtime consideration, or is it compile
time?
Run time, he uses the POSIX clocks and timers interface and uses a seperate high
res clock. Only timers on high res clocks are high res.
~
A small, measureable latency is ok and need not be backed out by the software.
If you go this route you risk expiring a timer early and the standard says bad
things about this.
Since we expire based upon time instead of ticks, we can never expire
early.
Think of it this way. Decompose a HR timer into corse and fine units (you
choose, but here let say jiffies and nanoseconds). Now we want the normal timer
system to handle the jiffies part of the time and to turn the timer over to the
HR timer code to take care of the nanosecond remainder. If the jiffie part is
late, depending on the nanosecond part, it could make the timer late (i.e for
low values of the nanosecond part). For high values of the nanosecond part, we
can compenstate...
This decomposition makes a lot of sense, by the way, for, at least, the
following reasons:
1) it keeps the most of the HR issues out of the normal timer code,
2) it keeps high res and low res timer in the correct time order, i.e. a low res
timer for jiffie X will expire prior to a high res timer for jiffie X + Y
nanoseconds.
3) handling the high res timer list is made vastly easier as it will only need
to have a rather small number of timers in it at any given time (i.e. those that
are to expire prior to the next corse timer tick).
What is missing in this is that the flag ship arch (x86) has piss poor
capability to schedule timer interrupts. I.e. there really is no commonly
available timer to generate interrupts at some arbitrary time. There is,
however, the PIT, which, if you don't mess with it, is very low overhead but
periodic.
Then there is the issue of what the time standard is. In the x86, the PIT is
it. The pm_timer is close, but the read problem adds so much overhead as to
make it hard to justify. Possibly the HPET does a better job, but it is still
an I/O access (read SLOW) and is not commonly available as yet.
With my rework, the time standard issue is separate problem domain from
HRT. If the timeofday code cannot give correct time, its a bug in that
subsystem. While you're point is a fair critique of my timeofday work
(which I am trying to address), the clear interface between soft-timers
and timeofday allows for the soft-timer subsystem to not worry about
that.
Leaving aside timers, one issue I am trying to get you to address is that on
most X86 machines the "clock" rock is only expressed via PIT interrupts. While
we must express time with more resolution than this, we must also "use" that
rock (i.e. PIT) to keep decent long term time.
You also have to do something reasonable for the accounting subsystems.
Currently this is done by sampling the system at a periodic rate. What ever is
running gets charged with the last period. If you go non-periodic, either you
have to charge a variable period when the sample is taken or you have to set up
timers as part of context switching. This ladder is not wise as the context
switch overhead then gets larger. It is rather easy to show that the accounting
overhead in such a system with a modest load is higher than in a periodic
sampled system. This system is also charged with doing the time slicing. With
out a periodic tick, a timer needs to be set up each context switch.
I've not looked at the accounting subsystem yet, but I'll try to dig in
and see what we can do here. Thanks for the heads up.
This is the main reason a tick less system is unwise. It is overload prone.
In addition to all of this, there is the issue of how to organize the timer list
so that you can find the next timer. With the current organization this is
something you just don't want to do. On the other hand, I am convinced that,
for periodic timers, it is about as good as it gets.
You might have to go a bit more into detail on this last point.
First, lets agree that we need not be in love with any given timer list structure.
The issues to be addressed are:
1) Fast insert.
2) Fast removal prior to expire, (almost all timers never expire).
3) Fast look up and removal of timers to expire NOW
If you want to find the next timer to expire at some time in the furture:
4) Fast look up of the next timer.
The current cascade timer list does a very good job of 1, 2, and 3 but is not
set up to make 4 easy or fast.
One thing I'd like to emphasize is that while Nish and my work do change
a large amount of code that collides with your code, we want to make
sure that what the HRT patch achieves is still possible. As I get more
familiar with the HRT code needs and you get more familiar with what
we're providing I hope things will work smoothly.
As do I.
--
George Anzinger [email protected]
High-res-timers: http://sourceforge.net/projects/high-res-timers/
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
