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.