Article source: Click the open link
Finished reading “Linux high performance server programming” on the inside of the timer is very interested. There are three kinds of timers mentioned in the book, which are: timer based on ascending linked list, timer based on time wheel, timer based on time heap. The realization of three kinds of timer books are given C++ code, but I am not too interested in C++, although I am doing C++ development, so I wrote the C version. In the book, timers are only given to the encapsulated timer class, not to the call layer code, I guess I wrote the call layer code. Here’s a summary for later reference:
Timers based on ascending lists are not too difficult to summarize.
Talk about the time wheel. Here’s a screenshot from the book
Time wheel, like a wheel rolling timing, every roll a scale, the pointer will go a tick, roll a circle, into the next circle. Hence the structure of the time wheel: 1. Gear (slot), which identifies a tick; 2. 2. Slot interval: How long it takes for the current slot to move to the next slot. 3. Number of slots in a circle (N); 4. For the current pointer, go one tick plus one, and return to the initial position after completing a circle.
To dig a little deeper, in what way is the timer added to the slot? You can see the figure, each slot is actually a linked list head node, timer is added to the slot after the linked list. In this way, we can analyze the performance of the time wheel. The smaller SI is, the higher the timing accuracy is. If SI=10s, the timer can only be a multiple of 10s. If the larger N is, the more efficient the timer is, which makes sense, and the smaller N is, the fewer slots in a circle, then we also add 100 timers, and the more timers assigned to each header, the more time it takes to traverse the current slot with each tick.
How to determine the timer position? It can be calculated according to the timer time, for example: The current interval SI=2s, the number of slots in a circle N=70, and the current pointer cur_slot points to the 5th slot. We can calculate the position of the timer. Here we need two variables. Slot = (cur_slot + timeout/SI) % N = 15, rotation = timeout/SI/N = 0 If the rotation is 0, the current rotation timer will trigger. If the rotation is greater than 0, the current rotation timer will trigger the current rotation timer. If the rotation is greater than 0, the rotation timer will trigger the current rotation timer. Don’t deal with the next round, just decrease its rotation and skip it. Wait until the cur_slot rotates to the next round to judge the timer. If other parameters remain unchanged and we have a timer with timeout=161s and cur_slot=5, we can calculate that the timer has slot=15 and rotation=1, which happens to be in slot 15, but is triggered by the next rotation.
In other words, if we add a 15s timer and a 161s timer according to the above parameters, both of them will be fired over time, except that when the pointer first wants to think about slot 15, the rotation of the 15s timer is 0, then the timer will be fired, and then the timer will be deleted. When traversing to the 161s timer, Rotation =1, perform decrement (1), skip the rotation, and continue the rotation. When the rotation has passed 65*2=130s (cur_slot=0), continue the rotation for the next time. After 14*2=28s, the rotation reaches 15. Rotation =0, trigger the timer.
With this analysis in mind, here’s the code:
\
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <signal.h>
#include <stdlib.h>typedef struct client_data { int fd; time_t tt; char buf[512]; void* data; }client_data; Typedef struct tw_timer {// Struct tw_timer (struct tw_timer, struct tw_timer, struct tw_timer, struct tw_timer, struct tw_timer; // The number of slots in the current rotation int slot; Void * (*cb_func)(void* param); Struct client_data c_data; //struct tw_timer* prev; struct tw_timer* next; }tw_timer; Typedef struct timer_manager {// int cur_slot; // int cur_slot; // int cur_slot; Int slot_num_r; int slot_num_r; int slot_num_r; The shorter the interval, the higher the precision. For example, 10s indicates that the timer can be added 10s // The minimum interval is 1s int slot_interval. Struct tw_timer* slots_head[512] struct tw_timer* slots_head[512]; }timer_manager; timer_manager tmanager; void* ontime_func( void* param ) { client_data* data = (client_data*)param; time_t tt = time(NULL); printf("\n----------------------------------------------------\n"); printf("\tontime,interval:%d\n", (int)(tt - data->tt)); printf("\told time:%s", ctime(&data->tt)); printf("\t%s", data->buf); printf("\tcur time:%s", ctime(&tt)); //getchar(); printf("----------------------------------------------------\n"); return NULL; } int add_timer( timer_manager* tmanager, int timeout, client_data* c_data ) { if ( timeout < 0 || ! tmanager ) return -1; int tick = 0; // Rotate several slots to trigger int rotation = 0; Int slot = 0; If (timeout < tManager ->slot_interval) tick = 0; else tick = timeout / tmanager->slot_interval; rotation = tick / tmanager->slot_num_r; slot = ( tmanager->cur_slot + tick % tmanager->slot_num_r ) % tmanager->slot_num_r - 1; printf("addtimer-->timeout:%d, rotation:%d,slot:%d\n", timeout, rotation, slot); tw_timer* tmp_t = (tw_timer*)malloc(sizeof(tw_timer)); tmp_t->rotation = rotation; char buf[100] = {0}; time_t tt = time(NULL) + timeout; sprintf( buf, "set time:%s", ctime(&tt)); memset( tmp_t->c_data.buf, 0, sizeof(tmp_t->c_data.buf)); strcpy( tmp_t->c_data.buf, buf ); tmp_t->slot = slot; tmp_t->c_data.tt = time(NULL); tmp_t->cb_func = ontime_func; if ( ! tmanager->slots_head[slot] ) { tmanager->slots_head[slot] = tmp_t; tmp_t->next = NULL; //printf("[line]:%d\n", __LINE__); return 0; } //printf("[line]:%d\n", __LINE__); tmp_t->next = tmanager->slots_head[slot]->next; tmanager->slots_head[slot]->next = tmp_t; return 0; } int tick(timer_manager* tmanager) {if (! tmanager ) return -1; tw_timer* tmp = tmanager->slots_head[tmanager->cur_slot]; tw_timer* p_tmp; While (TMP) {rotation=1, rotation=1, rotation=1, rotation=1 TMP cannot point to the timer in the current turn because cur_slot is constantly moving. The timer can be determined in the next turn when cur_slot is 0. If (TMP ->rotation > 0) {TMP ->rotation--; p_tmp = tmp; tmp = tmp->next; } else {// otherwise, trigger the callback TMP ->cb_func(& TMP ->c_data); // Delete this timer node Write so low if (TMP = = tmanager - > slots_head [tmanager - > cur_slot]) {/ / printf (" [the line] : % d \ n ", __LINE__); tmanager->slots_head[tmanager->cur_slot] = tmp->next; p_tmp = tmp; tmp = tmp->next; free( p_tmp ); p_tmp = NULL; p_tmp = tmp; //printf("[line]:%d\n", __LINE__); } else { p_tmp->next = p_tmp->next->next; free( tmp ); tmp = NULL; tmp = p_tmp->next; Tmanager ->cur_slot = ++ tManager ->cur_slot % tmanager->slot_num_r; return 0; } int init_t_manager( timer_manager* tmanager, int slot_num_r, int slot_interval ) { tmanager->cur_slot = 0; tmanager->slot_num_r = slot_num_r; tmanager->slot_interval = slot_interval; return 0; } void alarm_handler(int sig) {time_t t = time(NULL); //printf("timer tick:%s", ctime(&tt)); int ret = tick( &tmanager ); if ( ret < 0 ) printf("tick error\n"); alarm( tmanager.slot_interval ); } int main() { time_t tt = time(NULL); signal( SIGALRM, alarm_handler ); //init_t_manager( &tmanager, 60, 10 ); init_t_manager( &tmanager, 60, 1 ); add_timer( &tmanager, 6, NULL ); add_timer( &tmanager, 11, NULL ); add_timer( &tmanager, 22, NULL ); add_timer( &tmanager, 33, NULL ); add_timer( &tmanager, 44, NULL ); add_timer( &tmanager, 55, NULL ); add_timer( &tmanager, 66, NULL ); add_timer( &tmanager, 77, NULL ); add_timer( &tmanager, 88, NULL ); add_timer( &tmanager, 99, NULL ); add_timer( &tmanager, 111, NULL ); add_timer( &tmanager, 122, NULL ); add_timer( &tmanager, 133, NULL ); add_timer( &tmanager, 144, NULL ); printf("start time:%s\n", ctime(&tt)); alarm( tmanager.slot_interval ); while ( 1 ) sleep( 5 ); return 0; }Copy the code\
The main function starts with SI=1s, N=60, and adds a number of timers. Then it starts to execute the timer in SI, firing the tick() function each time, so that the timer is rotated.
Code considerations: Here with a SIGALRM signal, each time, then the main thread to suspend, to execute the signal function, if a SIGALRM signal processing function is too large, affect the task of the main thread caton, although the above code execution amount is not big, but in order to expand, I think you can change the timer trigger actions performed to task node is added to the task chain, This is a little more efficient with thread pools, which themselves take task nodes from the task chain to execute, and it would be much better if our timed handlers simply put tasks to the task chain instead of executing specific business logic into CB_func.
Next time heap.
\