Why HZ on i386 is 100 ?
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 8 lines · Alan Cox
Quoted 4 lines
The problem is in accounting (or time slicing if you prefer) where we need to start a timer each time a task is context switched to, and stop it when the task is switched away. The overhead is purely in the set up and tear down. MOST of these never expire.
Done properly on many platforms a variable tick is very very easy and also very efficient to handle. X86 is a paticular problem case because the timer is so expensive to fiddle with
Depends. On modern x86 you can either use the local APIC timer or the mmtimers (ftp://download.intel.com/ial/home/sp/mmts097.pdf - should be in newer x86 chipsets). Both should be better than the 8254 timer and are also not expensive to work with.
-Andi
Quoted 8 lines · Andi Kleen
Quoted 5 lines · Alan Cox
Quoted 4 lines
The problem is in accounting (or time slicing if you prefer) where we need to start a timer each time a task is context switched to, and stop it when the task is switched away. The overhead is purely in the set up and tear down. MOST of these never expire.
Quoted 8 lines
Quoted 3 lines
Done properly on many platforms a variable tick is very very easy and also very efficient to handle. X86 is a paticular problem case because the timer is so expensive to fiddle with
Depends. On modern x86 you can either use the local APIC timer or the mmtimers (ftp://download.intel.com/ial/home/sp/mmts097.pdf - should be in newer x86 chipsets). Both should be better than the 8254 timer and are also not expensive to work with.
I must not be making my self clear :) The overhead has nothing to do with hardware. It is all timer list insertion and deletion. The problem is that we need to do this at context switch rates, which are MUCH higher that tick rates and, even with the O(1) insertion code, cause the overhead to increase above the ticked overhead.
-g
Quoted 7 lines
(quoted diff) +0
-2-Andi -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/
Signature · 4 lines
George Anzinger [email protected] 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
Quoted 5 lines
I must not be making my self clear :) The overhead has nothing to do with hardware. It is all timer list insertion and deletion. The problem is that we need to do this at context switch rates, which are MUCH higher that tick rates and, even with the O(1) insertion code, cause the overhead to increase above the ticked overhead.
I remain unconvinced. Firstly the timer changes do not have to occur at schedule rate unless your implementaiton is incredibly naiive. Secondly for the specfic schedule case done that way, it would be even more naiive to use the standard timer api over a single compare to getthe timer list versus schedule clock.
Quoted 9 lines · Alan Cox
Quoted 6 lines
I must not be making my self clear :) The overhead has nothing to do with hardware. It is all timer list insertion and deletion. The problem is that we need to do this at context switch rates, which are MUCH higher that tick rates and, even with the O(1) insertion code, cause the overhead to increase above the ticked overhead.
I remain unconvinced. Firstly the timer changes do not have to occur at schedule rate unless your implementaiton is incredibly naiive.
OK, I'll bite, how do you stop a task at the end of its slice if you don't set up a timer event for that time?
Quoted 3 lines
Secondly for the specfic schedule case done that way, it would be even more naiive to use the standard timer api over a single compare to getthe timer list versus schedule clock.
I guess it is my day to be naive :) What are you suggesting here?
Signature · 4 lines
George Anzinger [email protected] 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
Quoted 5 lines
Quoted 2 lines
I remain unconvinced. Firstly the timer changes do not have to occur at schedule rate unless your implementaiton is incredibly naiive.
OK, I'll bite, how do you stop a task at the end of its slice if you don't set up a timer event for that time?
At high scheduling rate you task switch more often than you hit the timer, so you want to handle it in a lazy manner most of the time. Ie so long as the timer goes off before the time slice expire why frob it
Quoted 5 lines
Quoted 3 lines
Secondly for the specfic schedule case done that way, it would be even more naiive to use the standard timer api over a single compare to getthe timer list versus schedule clock.
I guess it is my day to be naive :) What are you suggesting here?
At the point you think about setting the timer register you do
next_clock = first_of(timers->head, next_timeslice);
if(before(next_clock, current_clock)
{
current_clock = next_clock;
set_timeout(next_clock);
}Quoted 10 lines · Alan Cox
Quoted 6 lines
Quoted 3 lines
I remain unconvinced. Firstly the timer changes do not have to occur at schedule rate unless your implementaiton is incredibly naiive.
OK, I'll bite, how do you stop a task at the end of its slice if you don't set up a timer event for that time?
At high scheduling rate you task switch more often than you hit the timer, so you want to handle it in a lazy manner most of the time. Ie so long as the timer goes off before the time slice expire why frob it
So then we test for this condition (avoiding races, of course) and if so, what? We will have a timer interrupt prior to the slice end, and will have to make this decision all over again. However, the real rub is that we have to keep track of elapsed time and account for that (i.e. shorten the remaining slice) not only in the timer interrupt, but each context switch. We are still doing more work each schedule and making it "smaller" just puts off the inevitable, i.e. at some level of scheduling activity we will accumulate more time in this accounting code than in the current "flat" or constant overhead way of doing things.
Quoted 1 line
Signature · 4 lines
George Anzinger [email protected] 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
Quoted 2 lines
so, what? We will have a timer interrupt prior to the slice end, and will have to make this decision all over again. However, the real rub
Only on unusual occasions.
Quoted 2 lines
is that we have to keep track of elapsed time and account for that (i.e. shorten the remaining slice) not only in the timer interrupt, but each
We do anyway
Alan
Quoted 10 lines · Alan Cox
Quoted 3 lines
so, what? We will have a timer interrupt prior to the slice end, and will have to make this decision all over again. However, the real rub
Only on unusual occasions.
Quoted 2 lines
is that we have to keep track of elapsed time and account for that (i.e. shorten the remaining slice) not only in the timer interrupt, but each
We do anyway
Yes, but now we do all this in the timer tick, not in schedule(). This occures much less often.
Quoted 2 lines
Alan
Signature · 4 lines
George Anzinger [email protected] 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
Quoted 4 lines
Quoted 1 line
We do anyway
Yes, but now we do all this in the timer tick, not in
schedule(). This occures much less often.
Well in the timer tick code we already hold the locks needed to check the front of the timer queue safely, we already have current and the top timer needing to touch cache (current for accounting stats at the least). So thats what an extra compare and cmov - 1 clock maybe 2 ?
Quoted 10 lines · Alan Cox
Quoted 5 lines
Quoted 2 lines
We do anyway
Yes, but now we do all this in the timer tick, not in
schedule(). This occures much less often.Well in the timer tick code we already hold the locks needed to check the front of the timer queue safely, we already have current and the top timer needing to touch cache (current for accounting stats at the least). So thats what an extra compare and cmov - 1 clock maybe 2 ?
The problem is the extra code in the schedule() path, not in the timer tick path. It is traversed FAR more often.
The current tick at 1/HZ is really quite relaxed. Given the PIT (ugh!) the longest we can put off a tick is about 50 ms. This means that any time greater than this will require more than one interrupt, i.e. the best case improvement by going tick less (again given the PIT) is about 5 times. Other platforms/ hardware, of course, change this.
Signature · 4 lines
George Anzinger [email protected] 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
Quoted 2 lines
The problem is the extra code in the
schedule()path, not in the timer tick path. It is traversed FAR more often.
Thats still in most cases a single compare. The tick timer will mostly be going off before our time slice completes. Also importantly the more we context switch the less timers go off - so it scales correctly.
Quoted 5 lines
The current tick at 1/HZ is really quite relaxed. Given the PIT (ugh!) the longest we can put off a tick is about 50 ms. This means that any time greater than this will require more than one interrupt, i.e. the best case improvement by going tick less (again given the PIT) is about 5 times. Other platforms/ hardware, of course, change this.
If you are arguing that the PIT makes it impractical on basic x86 then we are in violent agreement. I don't propose this kind of stuff for the PIT but for real computers where a timer reload is a couple of clocks
Quoted 8 lines · Andi Kleen
Quoted 5 lines · Alan Cox
Quoted 4 lines
The problem is in accounting (or time slicing if you prefer) where we need to start a timer each time a task is context switched to, and stop it when the task is switched away. The overhead is purely in the set up and tear down. MOST of these never expire.
Quoted 8 lines
Quoted 3 lines
Done properly on many platforms a variable tick is very very easy and also very efficient to handle. X86 is a paticular problem case because the timer is so expensive to fiddle with
Depends. On modern x86 you can either use the local APIC timer or the mmtimers (ftp://download.intel.com/ial/home/sp/mmts097.pdf - should be in newer x86 chipsets). Both should be better than the 8254 timer and are also not expensive to work with.
I just looked at the mmtimers. Looks like the right idea but a bit overblown. I would prefer an interrupt generated by a compare to the TSC all on board the cpu chip. This would eliminate the I/O overhead. Still the 8-bit PIT is the pits.
When can we expect to see this in a real cpu?
-g
Quoted 7 lines
(quoted diff) +0
-2-Andi -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/
Signature · 4 lines
George Anzinger [email protected] 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
Quoted 13 lines · george anzinger
Quoted 12 lines · Andi Kleen
Quoted 8 lines · Alan Cox
Quoted 4 lines
The problem is in accounting (or time slicing if you prefer) where we need to start a timer each time a task is context switched to, and stop it when the task is switched away. The overhead is purely in the set up and tear down. MOST of these never expire.
Done properly on many platforms a variable tick is very very easy and also very efficient to handle. X86 is a paticular problem case because the timer is so expensive to fiddle with
Quoted 8 lines
Quoted 4 lines
Depends. On modern x86 you can either use the local APIC timer or the mmtimers (ftp://download.intel.com/ial/home/sp/mmts097.pdf - should be in newer x86 chipsets). Both should be better than the 8254 timer and are also not expensive to work with.
I just looked at the mmtimers. Looks like the right idea but a bit overblown. I would prefer an interrupt generated by a compare to the TSC all on board the cpu chip. This would eliminate the I/O overhead.
That's the local APIC timer. Pretty much all modern x86 have it. But at least microsoft warns from using them for high precision tim ekeeping on their mmtimer page "due to inaccuracy and frequent silicon bugs" (and I guess they have the data for that)
For scheduling and time accounting it seems to work reasonably though, even though I've had some problems with inaccuracies (e.g. when you instrument both 8254 and apic timer and log the TSCs there are sometimes drifts)
The linux local APIC timer setup could be probably also improved, for example the 16 multiplier is a bit dubious and the calibration does not look very robust.
Quoted 1 line
When can we expect to see this in a real cpu?
mmtimers? They are in the chipset, not in the CPU.
They are in some modern Intel and AMD chipsets already for example and Microsoft is pushing them too so I guess they will be soon in all new chipsets.
-Andi
Quoted 4 lines · Andi Kleen
That's the local APIC timer. Pretty much all modern x86 have it. But at least microsoft warns from using them for high precision tim ekeeping on their mmtimer page "due to inaccuracy and frequent silicon bugs" (and I guess they have the data for that)
That's nothing new -- I recall a problem of missing half a tick each
time when hardware reloads the timer after reaching zero with certain revisions of Pentium CPUs. It is documented in the specification update.
Quoted 3 lines
The linux local APIC timer setup could be probably also improved, for example the 16 multiplier is a bit dubious and the calibration does not look very robust.
When fiddling with the predivider, please keep in mind the i82489DX only
supports 2, 4, 8 and 16 as dividers and you may set up 1 (i.e. no division) but in a different way -- by setting LVTT appropriately (use SET_APIC_TIMER_BASE(APIC_TIMER_BASE_CLKIN)).
Signature · 3 lines
+ Maciej W. Rozycki, Technical University of Gdansk, Poland + +--------------------------------------------------------------+ + e-mail: [email protected], PGP key available +