Trying to understand how FreeRTOS implements timers. Looks to me timers are arranged in a linked list I suppose based on the timeout? As soon as the timer expires, the node is deleted off the list and if it’s periodic, it’s added back?
So if you have timers due to expire in 10, 30, and 100 seconds, would we have a list looking something like this?
10 → 20 → 70
Every timer tick, the timeout value decrements in the node where the head points to.
And the expiry is determined by adding up the timeout in the nodes till the node whichever head pointer points to?
Lastly, how is the situation dealt with when multiple timers have the same timeout value but of different priorities? I have looked through timer.c but haven’t grasped everything.
I need to implement a timer based app to fire certain events of different priorities and seeing whether I could take some wisdom from FreeRTOS implementation
Time linked lists work exactly as the per the kernel - the list item is the time at which the timer expires. That means the time at the head of the list is compared to the current tick count - if it matches the timer has expired and executes.
but the tick count continues to run and doesn’t reset, right? if the expiry time is 5 seconds periodic, and once the timer count is beyond 5, how does the comparison work to determine whether the timer has expired?
If the tick frequency is 1KHz, and the timer is started when the tick count is 0, then the first expire time will be 5000, so that is the value used in the linked list. When the tick count is 5000 the timer expires, executes, and is reinserted at the time it next expires, which will be when the tick count is 10,000, so that is the time used in the linked list. When the tick count reaches 10,000 the timer expires and executes and is re-inserted using an expiry time of 15,000, etc.
If the tick frequency is 1KHz, and the timer is started when the tick count is 0, then the first expire time will be 5000, so that is the value used in the linked list
The expiry time set by the application no?
When the tick count is 5000 the timer expires, executes, and is reinserted at the time it next expires, which will be when the tick count is 10,000, so that is the time used in the linked list
prvProcessExpiredTimer() is invoked to process the expiry of a timer, yes? If so, I see it removes the timer from the active list, and appends it rightaway with the next expiry time stored? I think you meant the same but your words sounded a bit confusing…
Is the following condition in prvProcessTimerOrBlockTask used to determine whether expiry happened? So you’re comparing (current tick count + expiry time) with the current ticket count and if it’s lesser, timer expired?
Yes, the response assumes your previous example of 5 seconds periodic timer.
The doc comments of the function explains it:
/*
* An active timer has reached its expire time. Reload the timer if it is an
* auto-reload timer, then call its callback.
*/
static void prvProcessExpiredTimer( const TickType_t xNextExpireTime,
const TickType_t xTimeNow ) PRIVILEGED_FUNCTION;
The following line compares the next expiry time to the current time: xNextExpireTime <= xTimeNow. I’d encourage you to read the code comments/docs if you are trying to understand the internal workings.
I think I get the gist of it. One thing that’s bothering me is determining the position of the node that would contain the next expiry time.
This snippet is where the processing takes place of the expired timer. It first removes the node, and it’s a periodic timer, it adds the node with an updated expiry time (current time + expiry time) in prvReloadTimer()/prvInsertTimerInActiveList() .
Can you please brief on where/how the new location of the node that’s to be added determined?
static void prvProcessExpiredTimer( const TickType_t xNextExpireTime,
const TickType_t xTimeNow )
{
Timer_t * const pxTimer = ( Timer_t * ) listGET_OWNER_OF_HEAD_ENTRY( pxCurrentTimerList ); /*lint !e9087 !e9079 void * is used as this macro is used with tasks and co-routines too. Alignment is known to be fine as the type of the pointer stored and retrieved is the same. */
/* Remove the timer from the list of active timers. A check has already
* been performed to ensure the list is not empty. */
( void ) uxListRemove( &( pxTimer->xTimerListItem ) );
/* If the timer is an auto-reload timer then calculate the next
* expiry time and re-insert the timer in the list of active timers. */
if( ( pxTimer->ucStatus & tmrSTATUS_IS_AUTORELOAD ) != 0 )
{
prvReloadTimer( pxTimer, xNextExpireTime, xTimeNow );
}
else
{
pxTimer->ucStatus &= ( ( uint8_t ) ~tmrSTATUS_IS_ACTIVE );
}
static BaseType_t prvInsertTimerInActiveList( Timer_t * const pxTimer,
const TickType_t xNextExpiryTime,
const TickType_t xTimeNow,
const TickType_t xCommandTime )
{
BaseType_t xProcessTimerNow = pdFALSE;
listSET_LIST_ITEM_VALUE( &( pxTimer->xTimerListItem ), xNextExpiryTime );
listSET_LIST_ITEM_OWNER( &( pxTimer->xTimerListItem ), pxTimer );
if( xNextExpiryTime <= xTimeNow )
{
/* Has the expiry time elapsed between the command to start/reset a
* timer was issued, and the time the command was processed? */
if( ( ( TickType_t ) ( xTimeNow - xCommandTime ) ) >= pxTimer->xTimerPeriodInTicks ) /*lint !e961 MISRA exception as the casts are only redundant for some ports. */
{
/* The time between a command being issued and the command being
* processed actually exceeds the timers period. */
xProcessTimerNow = pdTRUE;
}
else
{
vListInsert( pxOverflowTimerList, &( pxTimer->xTimerListItem ) );
}
}
else
{
if( ( xTimeNow < xCommandTime ) && ( xNextExpiryTime >= xCommandTime ) )
{
/* If, since the command was issued, the tick count has overflowed
* but the expiry time has not, then the timer must have already passed
* its expiry time and should be processed immediately. */
xProcessTimerNow = pdTRUE;
}
else
{
vListInsert( pxCurrentTimerList, &( pxTimer->xTimerListItem ) );
}
}
return xProcessTimerNow;
}
The timer with the next expiry time is always at the front of the list so you only ever have to look in one place to know if a timer has expired. I.e. the list is sorted. If you add something to the list you add it in the correct sort order.
I recommend stepping through the code in the debugger as you will see how it operates.
Times do not have a “priority” - they are fired in the order they expire. Therefore, as Richard mentioned before, the list maintains timers in the order of expiry time.
