Subject:
|
Implementation of Installable Timers
|
Newsgroups:
|
lugnet.robotics.rcx
|
Date:
|
Thu, 8 Jan 2004 06:31:50 GMT
|
Viewed:
|
3235 times
|
| |
|
|
Hello everybody.
I have an implementation of installable timer handlers, and I’d like to solicit
some feedback. This is definitely a facility that I’d like to see in BrickOS.
The implementation doesn’t have to be my one. But I thought that I’d just start
something, and see what happens. I provide more details below.
One of my first reactions to BrickOS (coming after “This is so cool !”) was “how
does user code install its own interrupt handlers ?” After surfing the code,
and the posts here on LUGNET I discovered there was no provision in BrickOS.
You might say “That stuff should be left to the OS” but the problem with that
sentiment is that the OS does not know what the timeliness demands of the
application are. Some apps may need to read inputs every few tens of
microseconds. Other apps may need to read them only every few hundred
milliseconds.
I see that some others feel the same way:
- Thread 3078 contains a long discussion about how sensor input handling is
taking up to 60 % of the CPU, even if you don’t use the sensors !
Also, in a previous post, Eddie Dost wrote:
> While we are at it, I have two other major changes in mind:
>
> - Implement timers. A timer would install a callback function with a
> private to the caller void * argument. This callback function is called
> at the timers expiration time. This would significantly cleanup systime.c
> as all modules could install their own timers. No more hooks inside
> the timer interrupt with all the #ifdef CONF_XXX around them.
>
> User programs could use timers. This would help a lot I believe.
>
> - Implement event queues. Anyone waiting for an event can add a callback
> to the event in question (this will put the thread to sleep).
> Events are triggered by timers or by the sensor interrupt for example.
> Triggering an event would wake up all threads sleeping on the event queue.
>
> Currently events are implemented by constantly polling the required
> value from the scheduler during each time tick. How wasteful!
> I believe this could reduce power consumption by another 1 or 2 mA
> (see my mail about sensor reading for more reduction).
>
> Both changes can be made with very little code added, and will definitely
> result to reduced code at other places, so overall code size should not
> be a great problem here.
I agree with Eddie. For active object / state machine based applications, these
two facilities are crucial. I have implemented them both. I’ll tell you about
my event queue implementation in another post.
ABOUT THE INSTALLABLE TIMER IMPLEMENTATION
------------------------------------------
The timers are serviced once each ‘tick’ from systime_handler().
The per – tick overhead of servicing the timers is small, and constant,
regardless of how many timers are on the list. I consistently measured 3
microseconds, if no handlers need to be called. I’ll tell you how I achieved
that below.
The timers comprise a struct, with time remaining, a pointer to a client
supplied function, with void * parameter, and a flag indicating whether the
timer should be one-shot, or repeating.
The timers are stored in a linked list by the timer module.
The reason that the per-tick overhead is so low, is that only the timer at the
front of the list is decremented, on each tick. The timers are stored in order:
First one to time out will always be at the front. So we only have to decrement
its counter. Once it expires, it is removed from the list, and its handler
called. In order to preserve the proper time relationships, the timers further
back in the list have the times of the timers in front of them subtracted in
advance, since this much time has already expired once they get to the front.
So every timer on the list other than the first one stores a ‘delta’ time value.
This approach requires some additional work when the timer is started, since the
timer must be inserted in sorted order.
All of this is invisible, of course, to clients.
The current implementation requires client routines to allocate the client
structs. This is intentional, since I feel that low level services such as
these should be independent of memory management policy (such as malloc). The
timers can be made easier to use for those who want it by providing a wrapper
that does the malloc and free operations. I haven’t implemented these.
HOW WELL DO THEY WORK
---------------------
Beautifully. I’ve tested all the obvious cases via a test harness, and using my
own application, and they work great. I haven’t moved any of the system timers
on to this mechanism, yet. I wanted to get some feedback before doing that. If
no-one else is interested, I’ll probably not bother, since my main reason for
implementing the timers was for user code.
If people are interested in this as an ‘official’ facility, then I’d be happy to
clean up the systime_handler () code – it would remove all of the #ifdefs, and
become faster, and smaller.
Reentrancy: The routines that need to be are reentrant. Especially the
timer_start() routine. The routines that manipulate the timer list protect the
list from corruption by disabling interrupts. The timer_tick () routine is not
re-entrant, since it expects that interrupts are already disabled when it is
called.
The implementation is larger than I’d like, at several hundred bytes. Some of
those would be reclaimed by simplifying the existing timers. There are simpler
implementations which would trade code space for run time overhead, which I’d be
happy to do, if people felt that was a better trade off.
WHAT NEXT
---------
Tell me what you think. Do people want this ? As I said, I am prepared to
clean up systime_handler () if ppl are interested. I’d appreciate some advice
on testing those things before I do that, so that I can be sure of not breaking
anything.
I am happy to make my code available for ppl to inspect, and try out. I welcome
feedback on design and implementation correctness, and coding style. I believe
that you will find the code to be easy to read, and I’ve tried hard to make it
bullet proof (I do this kind of stuff for a living).
|
|
Message has 1 Reply:
5 Messages in This Thread:
  
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
