6.2 Timer Management

Timers are used for a number of purposes in communications systems. There are at least three significant uses for timers, namely:

  1. Protocol tasks and system tasks need to periodically perform certain functions. A protocol like frame relay requires a periodic status request message to be sent to the peer. System tasks can also periodically monitor the status of hardware ports using timers.

  2. Peers may need to time out based on receiving or not receiving messages. If the peer OSPF task has shut down, it will stop sending 'Hello' protocol messages. The local OSPF task will 'time out' the peer since it has not received the message in a specific period of time. This will cause a recalculation of the network topology since the peer router is not a part of the network any more.

  3. The protocol and system tasks may need to use one-shot timers, which 'fire' when the specified time elapses. This can happen when one task contacts another with a specific request. If the second task has not responded within a specified time (as indicated by the timeout), the first task can initiate some error recovery action.

A protocol task may need multiple timers. For example, a task may need to send out a message every 30 seconds and also time out a neighbor if more than 180 seconds has elapsed since it received the last message. As shown in Figure 6.7, the timers may need to be fired at different stages:

click to expand
Figure 6.7: Managing multiple timers.

6.2.1 Timer Management Per Task

The example used in xrefparanum assumed that timers need to be fired every 30 seconds and every 180 seconds. Assume that the lowest granularity of timers that our system requires is in seconds and that the timer tick provided by the system clock is 10 milliseconds. So, the system requires timer processing once every 100 ticks (100 * 10 milliseconds is 1 second).

The RTOS typically offers some timer-related facilities to manipulate timers based on the system clock, which measures time in clock ticks. A board support package (BSP) will hook up to the hardware timer on the board so that it will invoke a timer interrupt on each tick. Most real-time operating systems as well as UNIX systems that support the real-time extensions to POSIX provide facilities for an application to connect to the system clock routine.

The typical sequence of operations for timer ticks in an RTOS environment is shown in Listing 6.3. AppClock () is a routine which is called from the timer interrupt on each tick. Each application can be designed such that it receives a notification after several system ticks. In the example below, App1 requires a notification every 1 second or 100 system ticks. This is realized by incrementing an application tick count (App1Time) and notifying the application App1 when the count reaches 100.

Listing 6.3: RTOS notification routine.

start example
AppClock ( ) {  ………..  ………..  static unsigned long App1Time = 0;  /* Increment the count every tick and reset when 100 ticks i.e. 1 second expires */     App1Time++;     If (App1Time == 100) {          App1Time = 0;          App1TimerTickNotify ( );     } }
end example

The App1TimerTickNotify function is the timer tick routine for the application App1. Figure 6.8 shows how the timers can be organized. A table stores the current timer count and the context. The table is populated based on the timers that are required dynamically, i.e., during runtime. xrefparanum also shows the context, including routines to be called on timeout (also known as timeout routines), such as an update routine or a neighbor timeout routine. The context also includes parameters required by these routines. The timeout occurs when the current timer count reaches 0 for a table entry. If it is a one-shot timer, the entry is removed from the table. If it is a continuous timer, the value is reset to the initial timeout value (30 seconds and 180 seconds).

click to expand
Figure 6.8: Table based timer organization.

The standard disadvantage of a table-based construct applies to timer functions. Tables are cumbersome data structures when the application requires a significant amount of dynamism. The alternative is to use linked lists. The list will consist of entries similar to the table-however, they will be added and removed dynamically based on the application's requirement.

The term timer block refers to each entry in the list. Timer blocks are typically allocated and assigned to a free pool, similar to buffers. To start a timer, a task allocates a timer block from the free pool and links it into a list. The timer block has a count field to indicate the number of timer expirations. As with the table-based approach, a timer tick decrements the timer count in each of the timer blocks until the value reaches zero. At this point, the timeout routine in the timer block is called for each of the entries.

This is a simple approach to address the dynamic requirements for timers during runtime. The only overhead is the need to decrement the timer count in each timer block, a situation compounded by the overhead of pointer dereferencing for linked lists. The solution is to use differential timer counts, as outlined next.

click to expand
Figure 6.9: Differential timers.

6.2.2 Using a Differential Timer Count

The inefficiency of the multiple decrements is addressed by a differential timeout scheme, which is common in communications software systems. With a differential timeout, the lowest timer count entry is stored at the head of the list. xrefparanum illustrates three timer blocks with 10-, 15-, and 20-second timeouts. Instead of storing them in the same sequence, there are three entries, with the first entry's initial timer count set to 10, the second to 5 (since this entry needs a timeout 5 seconds after the first entry's timeout) and the third entry to 5 (i.e., 5 seconds after the second entry's timeout). When timers have the same value, the differential count is 0, and the timeout happens at the same time as the previous entry's timeout. The advantage of this approach is that the current timer count is decremented only in the first entry of the list. When it reaches 0, that entry is processed along with all subsequent entries in which the current timer count is 0. These entries can now be removed from the list.

A typical application using the timer tick notification and the addition and deletion of timer block entries in the timer list is shown below:

  • Application calls StartTimer (10, Parameter List);

  • Application calls StartTimer (15, Parameter List)

  • Application calls StartTimer (20, Parameter List)

These three calls create three separate timer blocks and store the parameter list (context) along with the differential count-which will resemble the organization of timers in Figure 6.9. Each timer block is as in Listing 6.4.

Listing 6.4: Timer block.

start example
Struct  {          unsigned long Count;           ……..           Param1           Param 2           ……..           Param n;   } TimerBlockType;
end example

TimerTickAppNotify sends a timer event to the application task that schedules it.

From the main loop of the task, we check the event type. If it is a timer event, the application calls ProcessTimers (Listing 6.5).

Listing 6.5: Process the timer event.

start example
ProcessTimers () {    Decrement the current timer count in the first entry    of the timer list;    If the count is 0 {        For all the entries in the timer list whose current timer            count is zero {             Process timer expiry by calling the timeout routine with               context provided in the timer block;         }    }
end example

We note that processing the timers in the main loop is preferred to processing the timers in the notification routine. The timeout routine in the timer block could involve a significant amount of processing, including constructing and transmitting packets, processing lists, and calculations. Since it possible that the notification routine can be called from the interrupt context, it is preferable that time-consuming activities be kept out of its execution path.

6.2.3 Timer Management Task

In the previous example, each task maintains its own set of timers by using a set of timer blocks in a timer list. Each of these tasks needs to be notified of a timer tick. This solution uses a large number of context switches to decrement a count in a timer block, since each application to be notified can be a separate task. Also, for each of the applications notified for a tick, we need a separate counter. In the example, AppClock maintains a counter AppxTime for each of the applications requiring a timer. This could be necessary if the granularity of a tick varies. One application may require a one-millisecond tick while another requires a one-second tick. While this is more flexible, it gets complicated if a large number of tasks need timers.

One way to address this is to use a single timer management task. Figure 6.10 illustrates a timer management task, with a tick equal to the lowest of all the ticks required for the various tasks. There is only one change to AppClock, that is, to provide a tick to the timer management task (TMT). The TMT, represented in Figure 6.10, separates the timer tick types by granularity. Assume the need for a 1-millisecond tick, a 10-millisecond tick, and a 1-second tick. The TMT will be notified of a 1-millisecond tick only. It will maintain counters for simulating a 10-millisecond and 1-second timer. For each of these tick types, there are separate timer lists.

click to expand
Figure 6.10: Timer management task.

The context in each timer block is now expanded to include the application task which requested the timer. When the timer expires, the TMT sends an event to the specified task in the timer block and passes along information such as the callback routine and parameter list. The TMT sends this as a message to the specified task.

Note that in Figure 6.10, the TMT receives one event, a timer tick expiration for 1 millisecond. The data structures for timer blocks are as specified earlier. An array is used for entries for each of the granularities-1 millisecond, 10 milliseconds, 1 second, and 10 seconds. The initial timer counts for each of the entries are 1, 10, 100, and 1000, respectively. For each tick, each of the timer counts is decremented. When an entry in the array reaches zero, the first timer block for this array entry has its count decremented. If it reaches zero, the timer processing event is called. The logic can be summarized as in Listing 6.6.

Listing 6.6: Create a new timer.

start example
AddTimer (TimeoutValue,  ApplicationModuleId, Param1, Param2….) {    Allocate a timer block and fill in the fields with       the  task id, and parameters;    Determine the granularity of the timer from the timeout value    specified and access the array entry corresponding to the    granularity (1 ms, 10 ms, 1 sec and 10 secs);    Add the timer block to the list in the array entry      using the differential timeout approach; } ProcessTick ( ) {     Decrement the counts in all the array entries;     If count reaches zero, decrement the count field in the        first timer block of the list for the array entry;     If  the decremented timer count reaches zero {          Delete the block(s) from the timer list and            indicate the timeout with the parameters            from the timer block to the task which started the timer;           Return the timer block to the timer block free list;     } }
end example

Comparing the Approaches

The first approach, which called for having timer management done in the individual tasks, is quite flexible. A library can be developed that will be used by tasks to allocate and free timer blocks and for maintaining timer lists. The disadvantage is that each task needs to be notified of a timer tick and do its own timer list processing.

The TMT centralizes management but has its own drawbacks. The TMT needs to send events/messages to the applications on timer expiration, requiring additional resources from the system. In addition, the task can itself become a bottleneck if it needs to handle a large number of timers.

Third-party stacks that are licensed and included in the software subsystem usually employ the first approach. All that the new protocol stack requires is a timer tick. The timer processing is handled internally within the stack, usually with a differential timer scheme.

System Issues in Timer Management

The timer management schemes discussed above are quite powerful because of the stored context in the timer block. When the timeout occurs, the application can just use the context from the timer block and perform the timeout action(s).

When the TMT is employed, as shown in xrefparanum, this task constructs a message with the context provided when the timer was started. It then queues the message to the application task which started the timer and requested notification. The notification is queued to the application task as a message. When the application task processes this message in its main loop, it looks into the context information and determines the timeout routine that should be called.

This flexibility comes at a price. Each of the timer management schemes can allocate and free a large number of timer blocks with each timer block requiring space for application context. This can create a significant memory requirement, especially when there is a large number of timers to be maintained, as with connection-oriented protocols such as TCP. The developer should identify the memory requirements for timers up front and determine the impact on system resources.

If the timer block uses a pointer to reference the context instead of storing it inside the block, it can save some space. This approach is preferred in situations where no context is required-say, when a task just needs to be woken up on a timer event without any additional processing. In this situation, the task does not need to start a timer with a set of parameters or a context.

Checklist for Timer Management

The following can be used as a checklist for the timer management strategy:

  1. Use timer management per task if each task has a complex set of requirements for timers-otherwise, use a common timer management task.

  2. Choose the minimum number of application timer ticks for the applications, so that you can have a small number of timer lists (see xrefparanum). Optimize this using the calculated memory requirements for a timer block.

  3. Implement a differential timer scheme for each of the timer lists.

  4. Connect up to the RTOS timer ISR to obtain the application tick for the timer list.



Designing Embedded Communications Software
Designing Embedded Communications Software
ISBN: 157820125X
EAN: 2147483647
Year: 2003
Pages: 126
Authors: T. Sridhar

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net