Article source: Click the open link
An introduction to
Timer is the basis of the basic components, whether the user space program development, or the development of the kernel space application, most of the time all needs to have a timer as basic components of support, but the different usage scenarios, to consider the realization of the timer is different, this paper discusses on the Linux environment, the application layer and the kernel layer of various implementation methods of the timer, The advantages and disadvantages of various implementation methods as well as suitable application environment are analyzed.
First of all, a basic model is given. The realization of timer needs to have the following behaviors, which is also a basic model for judging the realization of various timers [1] :
StartTimer(Interval, TimerId, ExpiryAction)
Register a timer instance that executes a ExpiryAction after an Interval, in which the TimerId is returned to distinguish other timer instances in the timer system.
StopTimer(TimerId)
Locate the registered timer instance by TimerId and execute Stop.
PerTickBookkeeping()
In a Tick, the timer system performs an action. The main action is to check whether any timer instance in the timer system has expired. Notice that a concept of time granularity is implied in the word Tick here.
ExpiryProcessing()
After the timer instance expires, a preregistered ExpiryAction behavior is executed.
The basic timer model is described above, but for practical use, there are two basic behavior timers:
Single-Shot Timer
This timer is executed only once, from registration to termination.
Repeating Timer
The timer automatically restarts after each termination. In essence, Repeating Timer can be considered as a Single Shot Timer that is re-registered into the Timer system after the Single Shot Timer expires. Therefore, Supporting a Repeating Timer on top of supporting a single-shot Timer isn’t particularly complicated.
Timers based on linked lists and signals (2.4 kernel)
POSIX Timer [2] is not supported in the 2.4 kernel. To support multiple timers in the process environment, you have to implement your own, but Linux provides a SetiTimer (2) interface. It is an interval timer with an interval function, but if you want to support multiple timers in a process environment, you have to manage all of them yourself. Setitimer (2) is defined as follows:
Listing 1. Prototype of setiTimer
| 123 | #include < sys /time.h> int setitimer(int which, const struct itimerval *new_value,struct itimerval *old_value); |
|---|
Setitimer can automatically restart itself after the Timer expires, so it’s easy to solve the problems of single-shot Timer and Repeating Timer. This function can work in three modes:
ITIMER_REAL decrement in real time, sending SIGALRM after expiration
ITIMER_VIRTUAL decrements only when the process is executing in user space and sends SIGVTALRM after expiration
The ITIMER_PROF process is decrement when it is executed in user space and when the kernel serves the process (typically completing a system call). When shared with ITIMER_VIRTUAL, the time consumption of the application in kernel space and user space can be measured, and SIGPROF signal can be sent after expiration
Timer values are defined by the following structure:
Listing 2. Setitimer value definition
| 123456789 | struct itimerval {`` struct timeval it_interval; /* next value */`` struct timeval it_value; /* current value */`` }; struct timeval {`` long tv_sec; /* seconds */`` long tv_usec; /* microseconds */`` }; |
|---|
Setitimer () sets a specific timer with new_value, and if old_value is not empty, it returns the previous value of the which interval timer. The timer is decayed from IT_value to zero, then a signal is generated and reset to IT_interval. If it_interval is zero, the timer stops. The timer stops at any time it_value is set to zero.
Since setitimer() cannot be used more than once in the same process to support multiple timers, it is up to the implementer to manage all of them if multiple timing instances need to be supported simultaneously. Using setiTimer () and linked lists, you can construct a Timer that supports multiple Timer instances in a process environment, incrementing the elapse value of each Timer in a general implementation of PerTickBookkeeping, If the value increases to the initial interval, the timer expires.
Timers based on linked list implementation can be defined as:
Listing 3. Linked list-based timer definition
| 123456789101112131415161718192021222324252627 | typedef int timer_id; / * * ` ` * The type of callback function to be called by timer scheduler when a timer`` * has expired.`` * ` ` * @param id The timer id.`` * @param user_data The user data.`` * $param len The length of user data.`` * / ` ` typedef int timer_expiry(timer_id id, void *user_data, int len); / * * ` ` * The type of the timer`` * / ` ` struct timer {`` LIST_ENTRY(timer) entries; /**< ``list entry */ timer_id id; /**< timer id */ int interval; /**< timer interval(second) */`` int elapse; /**< 0 -> interval */ timer_expiry *cb; /**< call if expiry */`` void *user_data; /**< callback arg */`` int len; /**< user_data length */`` }; |
|---|
The timer interval is expressed as interval, while Elapse incremented at PerTickBookkeeping() until interval indicates that the timer was terminated, at which point the callback function cb was called to perform the relevant behavior, User_data and len are parameters that the user can pass to the callback function.
All timer instances are managed in linked lists:
Listing 4. Timer linked list
| 1234567891011121314 | / * * ` ` * The timer list`` * / ` ` struct timer_list {`` LIST_HEAD(listheader, timer) header; /**< list header */`` int num; /**< timer entry number */`` int max_num; /**< max entry number */ void (*old_sigfunc)(int); /**< save previous signal handler */`` void (*new_sigfunc)(int); /**< our signal handler */ struct itimerval ovalue; /**< old timer value */`` struct itimerval value; /**< our internal timer value */`` }; |
|---|
The implementation of linked lists here uses a BSD-style set of macros for linked lists, avoiding reinventing the wheel; In this structure, old_sigFUNc is used to save the system’s SIGALRM handler function when init_timer initial timer chain, and is used to restore the previous handler function when timer system destory. Ovalue serves a similar purpose.
Listing 5. Timer list creation and Destroy
| 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667 | / * * ` ` * Create a timer list.`` * ` ` * @param count The maximum number of timer entries to be supported initially.`` * ` ` * @return 0 means ok, the other means fail.`` * / ` ` int init_timer(int count)`` {` ` int ret = 0; if(count <=0 || count > MAX_TIMER_NUM) {`` printf("the timer max number MUST less than %d.\n", MAX_TIMER_NUM); ` ` return -1; ` ` } memset(&timer_list, 0, sizeof(struct timer_list)); ` ` LIST_INIT(&timer_list.header); ` ` timer_list.max_num = count; /* Register our internal signal handler and store old signal handler */`` if ((timer_list.old_sigfunc = signal(SIGALRM, sig_func)) == SIG_ERR) {`` return -1; ` ` } ` ` timer_list.new_sigfunc = sig_func; /*Setting our interval timer for driver our mutil-timer and store old timer value*/`` timer_list.value.it_value.tv_sec = TIMER_START; ` ` timer_list.value.it_value.tv_usec = 0; ` ` timer_list.value.it_interval.tv_sec = TIMER_TICK; ` ` timer_list.value.it_interval.tv_usec = 0; ` ` ret = setitimer(ITIMER_REAL, &timer_list.value, &timer_list.ovalue); return ret; ` ` } / * * ` ` * Destroy the timer list.`` * ` ` * @return 0 means ok, the other means fail.`` * / ` ` int destroy_timer(void)`` {` ` struct timer *node = NULL; if ((signal(SIGALRM, timer_list.old_sigfunc)) == SIG_ERR) {`` return -1; ` ` } if((setitimer(ITIMER_REAL, &timer_list.ovalue, &timer_list.value)) < ``0 ) {` ` return -1; ` ` } while (! LIST_EMPTY(&timer_list.header)) { /* Delete. */`` node = ``LIST_FIRST (&timer_list.header); ` ` LIST_REMOVE(node, entries); ` ` /* Free node */`` printf("Remove id %d\n", node->id); ` ` free(node->user_data); ` ` free(node); ` ` } memset(&timer_list, 0, sizeof(struct timer_list)); return 0; ` ` } |
|---|
Adding a timer is very simple, essentially just a linked list insertion:
Listing 6. Adding a timer to the timer chain
| 123456789101112131415161718192021222324252627282930313233343536373839404142 | / * * ` ` * Add a timer to timer list.`` * ` ` * @param interval The timer interval(second).`` * @param cb When cb! = NULL and timer expiry, call it.`` * @param user_data Callback's param.`` * @param len The length of the user_data.`` * ` ` * @return The timer ID, if == INVALID_TIMER_ID, add timer fail.`` * / ` ` timer_id add_timer(int interval, timer_expiry *cb, void *user_data, int len)`` {` ` struct timer *node = NULL; if (cb == NULL || interval <= 0) {`` return INVALID_TIMER_ID; ` ` } if(timer_list.num < ``timer_list.max_num ) {` ` timer_list.num++; ` ` } else {`` return INVALID_TIMER_ID; ` ` } if(( node = ``malloc (sizeof(struct timer))) == NULL) {`` return INVALID_TIMER_ID; ` ` } ` ` if(user_data ! = NULL || len ! = 0) {` ` node->user_data = malloc(len); ` ` memcpy(node->user_data, user_data, len); ` ` node->len = len; ` ` } node->cb = cb; ` ` node->interval = interval; ` ` node->elapse = 0; ` ` node->id = timer_list.num; LIST_INSERT_HEAD(&timer_list.header, node, entries); return node->id; ` ` } |
|---|
The registered signal handler is used to drive the timer system:
Listing 7. The signal handler function drives the timer
| 123456789101112 | /* Tick Bookkeeping */`` static void sig_func(int signo)`` {` ` struct timer *node = timer_list.header.lh_first; ` ` for ( ; node ! = NULL; node = node->entries.le_next) {`` node->elapse++; ` ` if(node->elapse >= node->interval) {`` node->elapse = 0; ` ` node->cb(node->id, node->user_data, node->len); ` ` } ` ` } ` ` } |
|---|
It performs the increment operation of each timer ELAPSE in the timer chain every time a SIGALRM signal is received, and is compared with interval. If it is equal, it means that the registered timer has timed out, and then the registered callback function is called.
The above implementation has a number of optimizations: Another way to think about it is to convert the maintained relative interval into absolute time within the timer system, so that on every PerTickBookkeeping, you can know whether the timer expires by comparing the current time with the absolute time of the timer. In this way, the increment operation becomes the comparison operation. In StartTimer, StopTimer and PerTickBookkeeping, the algorithm complexity is O(1), O(n) and O(n), respectively. A simple improvement can be made to the above implementation. In StartTimer, That is, the linked list is sorted when the Timer instance is added. Such improvement can make the algorithm complexity of StartTimer, StopTimer and PerTickBookkeeping to be O(n), O(1) and O(1) respectively. The improved timer system is shown in Figure 1:
Figure 1. Timer based on sorted linked list
Implementation of Kernel Timer Based on version 2.6 (Posix Real-time Timer)
Linux has supported POSIX Timer [2] since 2.6, which consists of the following interfaces:
Listing 8. POSIX Timer interface
| 1234567891011 | #include < signal.h > ` ` #include < time.h > int timer_create(clockid_t clockid, struct sigevent *evp,`` timer_t *timerid); ` ` int timer_settime(timer_t timerid, int flags,`` const struct itimerspec *new_value,`` struct itimerspec * old_value); ` ` int timer_gettime(timer_t timerid, struct itimerspec *curr_value); ` ` int timer_getoverrun(timer_t timerid); ` ` int timer_delete(timer_t timerid); |
|---|
This interface is intended to provide better real-time support for the operating system. -LRT needs to be specified when linking.
Timer_create (2): A timer is created.
Timer_settime (2): starts or stops a timer.
Timer_gettime (2): Returns the value of the remaining time to the next expiration and the interval defined by the timer. The reason for this interface is that if a user defines a 1ms timer, the system may be overloaded and the timer may time out after 10ms. In this case, overrun=9ms.
Timer_getoverrun (2): Returns the upper limit when the last timer expired.
Timer_delete (2): Stops and deletes a timer.
The most important interface above is timer_Create (2), where clockid indicates the clock type to be used, and POSIX requires that a clock of type CLOCK_REALTIME be implemented. The EVP parameter specifies how the caller is notified after the timing expires. The structure is defined as follows:
Listing 9. Signal and event definitions in the POSIX Timer interface
| 12345678910111213141516171819 | union sigval {`` int sival_int; ` ` void *sival_ptr; ` ` }; struct sigevent {`` int sigev_notify; /* Notification method */`` int sigev_signo; /* Timer expiration signal */`` union sigval sigev_value; /* Value accompanying signal or`` passed to thread function */`` void (*sigev_notify_function) (union sigval); ` ` /* Function used for thread`` notifications (SIGEV_THREAD) */`` void *sigev_notify_attributes; ` ` /* Attributes for notification thread`` (SIGEV_THREAD) */`` pid_t sigev_notify_thread_id; ` ` /* ID of thread to signal (SIGEV_THREAD_ID) */`` }; |
|---|
Sigev_notify specifies the notification mode:
SIGEV_NONE
When the timer expires, no asynchronous notification is sent, but the progress of the timer can be monitored using timer_getTime (2).
SIGEV_SIGNAL
When the timer expires, the sigEV_SIGNO signal is sent.
SIGEV_THREAD
When the timer expires, a new thread is started with sigev_notify_function. This function takes sigev_value as its argument, and when sigEV_notify_Attributes is not empty, attributes for the thread are specified. Note that due to the particularities of threading on Linux, this functionality is actually implemented by glibc in conjunction with the kernel.
SIGEV_THREAD_ID (Linux-specific)
It is recommended only when implementing thread libraries.
If EVP is empty, the behavior of this function is equivalent to sigEV_notify = SIGEV_SIGNAL, SIGEV_SIGNO = SIGVTALRM, sigEV_value.siVAL_int = timer ID.
Because the POSIX Timer [2] interface supports multiple timer instances in a process, the setiTimer () and linked list based PerTickBookkeeping actions above are maintained by the Linux kernel, which greatly reduces the burden of implementing timers. Since the POSIX timer [2] interface has more control when the timer expires, real-time signals can be used to avoid signal loss and the sigEV_value.sival_INT value is specified as the timer ID, so that multiple timers can be managed together. Note that the POSIX Timer [2] interface only makes sense in a process environment (fork(2) and exec(2) also require special treatment) and is not suitable for multithreaded environments. Similarly, Linux provides an interface for related timers based on file descriptors:
Listing 10. A file descriptor-based timer interface provided by Linux
| 1234567 | #include < sys /timerfd.h> int timerfd_create(int clockid, int flags); ` ` int timerfd_settime(int fd, int flags,`` const struct itimerspec *new_value,`` struct itimerspec *old_value); ` ` int timerfd_gettime(int fd, struct itimerspec *curr_value); |
|---|
In this way, based on file descriptor, the interface can support select(2), poll(2) and other asynchronous interfaces, making the implementation and use of timer more convenient, more importantly, support fork(2), exec(2) semantics, so it can be used in multithreaded environment. Their use is more flexible than POSIX Timer [2], and the fundamental reason is that timer management is unified under one of the basic Unix/Linux philosophies —- “Everything is a file”.
Minimum heap implementation timer
The minimum heap refers to a heap where every node except the root node is no smaller than its parent. In this way, the minimum value in the heap is stored in the root node, and in a subtree rooted at a node, the value of each node is not less than that of the child root node. An example of a minimal heap is shown in Figure 2 below:
Figure 2. Minimum heap
A minimum heap generally supports the following operations:
Insert(TimerHeap, Timer): To Insert a value into the heap, keeping the minimum heap nature, corresponding to the implementation of Timer, Timer is inserted into the Timer heap. According to the analysis of the minimum heap insertion algorithm, we know that the time complexity of this operation is O(LGN).
Minimum(TimerHeap): Retrieves the Minimum value of the Minimum heap; In a timer system, it returns the first timer in the timer stack that is likely to terminate. Since it is the smallest heap, you simply return the root of the heap. In this case, the algorithm complexity is O(1).
ExtractMin(TimerHeap): Performs related actions after the timer expires. Its algorithm complexity is O(1).
The minimum heap is essentially a min-priority queue. Timing can be used as an application of the minimum priority queue, which converts the interval value of timer into an absolute time to deal with. ExtractMin operation is to find out the timer that times out first among all waiting timers. At any time, a new timer instance can be added to the timer queue by an Insert operation.
In pjSIP project’s base library, Pjlib, there is a timer based on the minimal heap implementation, which mainly provides the following interfaces:
Listing 10. The minimal heap-based timer interface provided by pjlib
| 1234567891011121314151617181920212223242526272829303132333435363738394041 | / * * ` ` * Create a timer heap.`` * / ` ` PJ_DECL(pj_status_t) pj_timer_heap_create( pj_pool_t *pool,`` pj_size_t count,`` pj_timer_heap_t **ht); / * * ` ` * Destroy the timer heap.`` * / ` ` PJ_DECL(void) pj_timer_heap_destroy( pj_timer_heap_t *ht ); / * * ` ` * Initialize a timer entry. Application should call this function at least`` * once before scheduling the entry to the timer heap, to properly initialize`` * the timer entry.`` * / ` ` PJ_DECL(pj_timer_entry*) pj_timer_entry_init( pj_timer_entry *entry,`` int id,`` void *user_data,`` pj_timer_heap_callback *cb ); / * * ` ` * Schedule a timer entry which will expire AFTER the specified delay.`` * / ` ` PJ_DECL(pj_status_t) pj_timer_heap_schedule( pj_timer_heap_t *ht,`` pj_timer_entry *entry,`` const pj_time_val *delay); / * * ` ` * Cancel a previously registered timer.`` * / ` ` PJ_DECL(int) pj_timer_heap_cancel( pj_timer_heap_t *ht,`` pj_timer_entry *entry); / * * ` ` * Poll the timer heap, check for expired timers and call the callback for`` * each of the expired timers.`` * / ` ` PJ_DECL(unsigned) pj_timer_heap_poll( pj_timer_heap_t *ht,`` pj_time_val *next_delay); |
|---|
The timer in Pjlib implements the heap internally using arrays, which makes memory space more compact; Its implementation also increases the maximum number of timers itself when the number of timers exceeds a preset maximum. The file pjlib/ SRC /pjlib-test/timer.c is one of its unit tests. Compared to the list-based implementation, it obviously has a lower time complexity and can support more timer instances.
Timer based on Timing-Wheel
The Timing Wheel algorithm is similar to a revolver spinning at a constant speed. The firing pin of the gun strikes the chamber of the gun. If there is a bullet in the chamber, it will be fired. For PerTickBookkeeping, the essence of the job is to add clocks by Tick, and if any timer expires, you would call ExpiryProcessing. Set a cycle as N Tick units, the Current Time is pointing to the element I after S cycles (I >=0 and I <= n-1), then the Current Time Tc can be expressed as: Tc = S*N + I; If a timer with Ti Interval is inserted, it will be placed in element N (Next). Then n = (Tc + Ti) mod n = (S* n + I + Ti) mod n = (I + Ti) mod n. If our N is large enough, it is clear that StartTimer, StopTimer, and PerTickBookkeeping will be O(1), O(1), and O(1), respectively. In [5], the timing of a simple timer wheel is given. Figure 3 shows a simple time wheel timer:
Figure 3. Simple time wheel
If the range of timers to be supported is very large, the above implementation method cannot meet such requirements. Since this would consume a considerable amount of memory, assuming that the range of timers needed to be represented was 0 — 2^ 3-1Ticks, the simple time wheel would require 2^32 element space, which would be a very large use of memory space. It may be possible to reduce the accuracy of the timer so that each Tick represents a longer time, but at the cost of this, the accuracy of the timer will be greatly reduced. The question now is, can only one granularity be used to measure the granularity of timers? Consider a water meter in your daily life, as shown in Figure 4 below:
Figure 4. Water meter
In the water meter above, in order to represent the measurement range, it is divided into different units, such as 1000,100,10, etc. Similarly, to represent a 32bits range, there is no need for an array of 2^32 elements. In fact, the Linux kernel divides timers into five groups, with the granularity of each group expressed as: 1 jiffies, 256 jiffies, 256*64 jiffies, 256*64*64 jiffies, 256*64*64 jiffies, 256*64*64 256, 64, 64, 64, 64, thus, in 256+64+64+64+64 = 512 buckets, the range of representations is 2^32. With such implementation, drive the kernel timer mechanism can also through the example to understand the water meter, like a water meter, each granularity has a pointer to the current time, at a fixed time tick increment, the pointer to the current time is also increasing in turn, if it is found that the current cursor position can be identified as a registered timer, Triggers its registered callback function. The Linux kernel Timer is essentially a single-shot Timer. If you want to become a Repeating Timer, you can register yourself again in the registered callback function. The kernel timer is shown in Figure 5:
Figure 5. Linux time wheel
conclusion
From the above analysis, we can see the complexity of various timer implementation algorithms:
Table 1. Timer implementation algorithm complexity
| implementation | StartTimer | StopTimer | PerTickBookkeeping |
|---|---|---|---|
| Based on the list | O(1) | O(n) | O(n) |
| Based on sorted linked lists | O(n) | O(1) | O(1) |
| Minimum heap based | O(lgn) | O(1) | O(1) |
| Based on time wheel | O(1) | O(1) | O(1) |
If you need timers that can be used in a threaded environment, you may need to be very careful about handling signals for linked list-based timers; The POSIX timer [2] interface has only the semantics of the process. If you want to use it in a multi-threaded environment, you can use the Timerfd_create (2) interface provided by Linux. If you need to support a very large number of timers, consider using a minimal heap and time wheel approach.
Download resources
- The sample code (test – signal. C | 7 KB)
On the topic
- George Varghese , Tony Lauck. Hashed and Hierarchical Timing Wheels: Efficient Data Structures for Implementing a Timer Facility are analyzed in this paper, and the concept of time wheel is proposed. If you want to be a good timer, you need to read this paper over and over again.
- Open Group’s description of POSIX Timer. If you are interested in UNIX standards, I recommend you to post the latest description on this website. Moreover, the description of POSIX Timer is quite easy to read. It was my first choice after Steven’s book.
- www.pjsip.org/ is an Open Source VoIP project, and if you don’t care about VoIP, the pjlib library provided in the project is also worth looking at, as it is an example of a common base library implementation in an embedded environment.
- www.monkey.org/~provos/lib… One of the best known event notification libraries, it internally uses a priority queue based minimal heap implementation to handle all kinds of events including time, signals, etc.
- In his article “An Embedded Single Timer Wheel”, Bo Berry described a Timer implemented by a simple time Wheel algorithm.
- Linux 2.6.31-RC6 source code.
- Lwn.net/Articles/15… Ingo Molnar has the best explanation for the implementation of time wheels in Linux.
- By Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein. Introduction to algorithms (2nd Ed.). Beijing: China Machine Press, 2006:73-82.
\