Precision periodic timer using virtual timers

This forum is dedicated to feedback, discussions about ongoing or future developments, ideas and suggestions regarding the ChibiOS projects are welcome. This forum is NOT for support.
faisal
Posts: 260
Joined: Wed Jul 19, 2017 12:44 am
Has thanked: 35 times
Been thanked: 34 times

Precision periodic timer using virtual timers

Postby faisal » Sat Apr 25, 2020 1:34 am

I took at a look at ChibiOS/os/various/evtimer.c, and it implements the last idea presented here using virtual timers:
http://www.chibios.org/dokuwiki/doku.ph ... :kb:timing

The issue is that the timing will always be off due to the execution time it takes to get to the place where the one shot timer is reprogrammed, and also if you get preempted with a higher priority interrupt before you can set the next one shot timer. Is there a way to essentially have the accuracy of a hardware periodic timer using the virtual timer subsystem?

For example, when a virtual timer interrupt fires perhaps the output compare value of the timer is provided as part of the context for the virtual timer callback. If that value could be used, then one could simply add the next interval to that value. Thereby, the timing accuracy of a periodic timer using the virtual timer would be as good as the hardware timer. The output compare value (for use in the context of next virtual timer event) could be stored when the timer is configured for the first time. Then, when starting the virtual timer again, the object would contain the last output compare value - to be optionally used as the starting time of the requested duration.

User avatar
Giovanni
Site Admin
Posts: 12944
Joined: Wed May 27, 2009 8:48 am
Location: Salerno, Italy
Has thanked: 731 times
Been thanked: 609 times
Contact:

Re: Precision periodic timer using virtual timers

Postby Giovanni » Sat Apr 25, 2020 5:57 am

Hi,

This is a good point, VTs have been designed as one-shot timers only and, when using high resolution time, there could be an accumulating error.

Perhaps VTs should have a periodic mode built-in, without having to reload the timer from the callback. The drawback would be that the timer object would become larger.

I need to look into details, the implementation would not be straightforward in tick-less mode.

Giovanni

steved
Posts: 719
Joined: Fri Nov 09, 2012 2:22 pm
Has thanked: 10 times
Been thanked: 102 times

Re: Precision periodic timer using virtual timers

Postby steved » Sat Apr 25, 2020 1:08 pm

I find I've always got a spare timer to use as the base for things like this; adding a virtual timer to the list takes an indeterminate (and possibly significant, if you have lots of VTs) time to add to the list, so I prefer to avoid the overhead, especially for short times. (Plus doesn't rescheduling VTs require the system to be locked, increasing interrupt jitter?).
Depends a bit on the time period required.
I've also been conscious that a need for a regular 'tick' can rather negate the point of tickless mode.

User avatar
Giovanni
Site Admin
Posts: 12944
Joined: Wed May 27, 2009 8:48 am
Location: Salerno, Italy
Has thanked: 731 times
Been thanked: 609 times
Contact:

Re: Precision periodic timer using virtual timers

Postby Giovanni » Sat Apr 25, 2020 1:47 pm

Of course processing a virtual timer takes longer that just serving an HW timer.

About jitter, VTs use a delta list structure, only the first element on the list processed but the algorithm is not executed in constant time. If it happens that multiple timers elapse around the same tick ("around" because the delta parameter) then complexity is N, it is that loop where callbacks are called. It is not frequent but the jitter upper limit increases linearly with the number of active timers.

The problem is not much jitter but the accumulation of errors if you re-arm the timer from its own callback. This is only an issue when the system time frequency is very high, you could spend some ticks executing the callback and the error accumulates over time, and this is the issue Faisal was concerned about I think. This could be solved with a "periodic mode" where timers rearm automatically based on the latest deadline and not "current time".

Giovanni

faisal
Posts: 260
Joined: Wed Jul 19, 2017 12:44 am
Has thanked: 35 times
Been thanked: 34 times

Re: Precision periodic timer using virtual timers

Postby faisal » Sat Apr 25, 2020 7:58 pm

Giovanni wrote:Hi,

This is a good point, VTs have been designed as one-shot timers only and, when using high resolution time, there could be an accumulating error.

Perhaps VTs should have a periodic mode built-in, without having to reload the timer from the callback. The drawback would be that the timer object would become larger.

I need to look into details, the implementation would not be straightforward in tick-less mode.

Giovanni


I agree, having a built in periodic mode for a virtual timer is good idea. Other RTOS's have this feature, and when the built in feature is not available, we typically have to roll-our-own implementation or use a dedicated hardware timer. It's not an uncommon pattern to have periodic timers which send events to various tasks in the system running at different rates. If the existing virtual timers can be used which guarantee the same accuracy as the system tick timer - that would be great.

It''s important that this feature work in tickless mode too.

Thanks for considering this and looking into it Giovanni!

faisal
Posts: 260
Joined: Wed Jul 19, 2017 12:44 am
Has thanked: 35 times
Been thanked: 34 times

Re: Precision periodic timer using virtual timers

Postby faisal » Sat Apr 25, 2020 8:07 pm

Giovanni wrote:The drawback would be that the timer object would become larger.


This could be mitigated with a compile time kernel option to enable virtual timers to be optionally configured as periodic timers.

steved
Posts: 719
Joined: Fri Nov 09, 2012 2:22 pm
Has thanked: 10 times
Been thanked: 102 times

Re: Precision periodic timer using virtual timers

Postby steved » Sat Apr 25, 2020 8:53 pm

Giovanni wrote:About jitter, VTs use a delta list structure, only the first element on the list processed but the algorithm is not executed in constant time. If it happens that multiple timers elapse around the same tick ("around" because the delta parameter) then complexity is N, it is that loop where callbacks are called. It is not frequent but the jitter upper limit increases linearly with the number of active timers.

I was thinking more about the time involved in adding a VT to the list - especially if the delay of the VT is long compared to those already on the list, it can take a relatively long time to find the right place to insert the new timer.

User avatar
Giovanni
Site Admin
Posts: 12944
Joined: Wed May 27, 2009 8:48 am
Location: Salerno, Italy
Has thanked: 731 times
Been thanked: 609 times
Contact:

Re: Precision periodic timer using virtual timers

Postby Giovanni » Sun Apr 26, 2020 6:45 am

Correct, that has complexity N as well.

Giovanni


Return to “Development and Feedback”

Who is online

Users browsing this forum: No registered users and 3 guests