Subject: Callouts
To: None <tech-kern@netbsd.org>
From: Charles M. Hannum <root@ihack.net>
List: tech-kern
Date: 03/27/1999 07:02:39
So, I want to revisit the notion of what to do with callouts. Various
ideas have been suggested; the two that come to mind offhand are:
* the so-called `call wheel'. This changes the insertion time to
O(n/C) (which a careful reader will note is equivalent to O(n)
mathemtically).
* my O(log t) method, which you can think of as a stratified/radix
`call wheel'.
However, I believe that neither of these approaches is actually
desirable in the long run (pun intended).
It occurs to me that the right solution is probably to:
* eliminate the use of tick values, and instead use timespecs, and
* keep the callout structures in a heap.
The reason for this is that it permits high-precision scheduling of
events. Since we always know exactly when the next event will occur,
if the hardware has a high-precision countdown timer, we can always
schedule events with the highest precision available, with very little
overhead. (Note that this actually won't work on PCs; there we would
have to continue to compare against the tick-based clock. But you can
increase HZ to increase precision -- to an extent.)
This would be an important step toward real-time scheduling.