Книга: Real-Time Concepts for Embedded Systems
11.5.2 Implementation Considerations
11.5.2 Implementation Considerations
A soft-timer facility should allow for efficient timer insertion, timer deletion and cancellation, and timer update. These requirements, however, can conflict with each other in practice. For example, imagine the linked list-timer implementation shown in Figure 11.8. The fastest way to start a timer is to insert it either at the head of the timer list or at the tail of the timer list if the timer entry data structure contains a double-linked list.
Figure 11.8: Maintaining soft timers.
Because the timer list is not sorted in any particular order, maintaining timer ticks can prove costly. Updating the timer list at each tick requires the worker task to traverse the entire linked list and update each timer entry. When the counter reaches zero, the callout function is invoked. A timer handle is returned to the application in a successful timer installation. The cancellation of a timer also requires the worker task to traverse the entire list. Each timer entry is compared to the timer handle, and, when a match is found, that particular timer entry is removed from the timer list.
As shown in Figure 11.9, while timer installation can be performed in constant time, timer cancellation and timer update might require O(N) in the worst case.
Figure 11.9: Unsorted soft timers.
Sorting expiration times in ascending order results in efficient timer bookkeeping. In the example, only the first timer-entry update is necessary, because all the other timers are decremented implicitly. In other words, when inserting new timers, the timeout value is modified according to the first entry before inserting the timer into the list.
As shown in Figure 11.10, while timer bookkeeping is performed in constant time, timer installation requires search and insertion. The cost is O(log(N)), where N is the number of entries in the timer list. The cost of timer cancellation is also O(log(N)).
Figure 11.10: Sorted soft timers.
Оглавление книги
- System Considerations
- 9.6.5. Implementation of COOL
- Implementation Inheritance
- Chapter 13. Platform-Specific Considerations
- Implementation ID
- Speed considerations
- UNIX Security Considerations
- DNS Security Considerations
- Appendix D. SDRAM Interface Considerations
- 3.4.3. Implementation
- Business Considerations
- User Considerations