Linux提供了三种定时方法：

  1. socket读写超时选项：SO_RCVTIMEO和SO_SNDTIMEO
  2. IO复用API中的timeout参数
  3. Linux提供的定时函数和计时函数，比如：
    1. 由alarm函数和settimer函数设置的超时闹钟，触发SIGALRM信号
    2. timefd_系列函数处理定时任务

      1 SO_RCVTIMEO和SO_SNDTIMEO

      通过setsockopt函数可以设置socket相关的API函数的收发超时时间。对于不同的API函数，超时返回的errno如下：
系统调用 有效选项 函数超时后的行为
send SO_SNDTIMEO 返回-1，errno为EAGAIN、EWOULDBLOCK
sendmsg SO_SNDTIMEO 返回-1，errno为EAGAIN、EWOULDBLOCK
recv SO_RCVTIMEO 返回-1，errno为EAGAIN、EWOULDBLOCK
recvmsg SO_RCVTIMEO 返回-1，errno为EAGAIN、EWOULDBLOCK
accept SO_RCVTIMEO 返回-1，errno为EAGAIN、EWOULDBLOCK
connect SO_SNDTIMEO 返回-1，errno为EINPROGRESS

在程序中，我们可以根据每个函数的返回值和errno判断是否超时。

connect超时的示例：

  1. //模拟客户端connect超时
  2. #include <sys/types.h>
  3. #include <sys/socket.h>
  4. #include <netinet/in.h>
  5. #include <arpa/inet.h>
  6. #include <assert.h>
  7. #include <stdio.h>
  8. #include <unistd.h>
  9. #include <errno.h>
  10. #include <string.h>
  11. #include <fcntl.h>
  12. #include <stdlib.h>
  13. #include <sys/epoll.h>
  14. #include <stdbool.h>
  15. #include <libgen.h>
  17. int main(int argc, char *argv[])
  18. {
  19.     if (argc <= 2)
  20.     {
  21.         printf("Usage: %s ip_address port_number\n", basename(argv[0]));
  22.         return 1;
  23.     }
  24.     const char *ip = argv[1];
  25.     const int port = atoi(argv[2]);
  26.     int ret = 0;
  28.     struct sockaddr_in address;
  29.     bzero(&address, sizeof(address));
  30.     address.sin_family = AF_INET; //IPv4
  31.     address.sin_addr.s_addr = inet_addr(ip);
  32.     address.sin_port = htons(port);
  34.     int listenfd = socket(PF_INET, SOCK_STREAM, 0);
  35.     assert(listenfd >= 0);
  37.     //设置socket选项，配置可写超时
  38.     struct timeval timeout;
  39.     timeout.tv_sec = 10; //10s
  40.     timeout.tv_usec = 0;
  41.     ret = setsockopt(listenfd, SOL_SOCKET, SO_SNDTIMEO, &timeout, sizeof(timeout));
  42.     assert(ret >= 0);
  44.     ret = connect(listenfd, (struct sockaddr*)&address, sizeof(address));
  45.     if (ret == -1)
  46.     {
  47.         //返回-1，errno为EINPROGRESS，则表示connect超时
  48.         if (errno = EINPROGRESS)
  49.         {
  50.             printf("connecting timeout, process timeout logic\n");
  51.         }
  52.         else
  53.         {
  54.             printf("error occur when connecting to server\n");
  55.         }
  56.     }
  57.     close(listenfd);
  58.     return 0;
  59. }

2 IO复用函数的超时参数

select、poll和epoll函数都带有超时参数，所以它们也能统一处理定时事件。
由于函数可能在超时之前就返回，所以需要不断的更新定时参数以反映剩余的时间，如下：

  1. #define TIMEOUT 5000
  2. int timeout = TIMEOUT;
  3. time_t start = time(NULL);
  4. time_t end = time(NULL);
  6. while(1)
  7. {
  8.     printf("the timeout is now %d ml-seconds\n", timeout);
  9.     start = time(NULL);
  10.     //指定timeout参数
  11.     int number = epoll_wait(epollfd, events, MAX_EVENT_NUMBER, timeout);
  12.     if (number < 0 && errno != EINTR)
  13.     {
  14.         printf("epoll failed\n");
  15.         break;
  16.     }
  17.     if (number = 0)//返回0，说明超时时间到了，没有监听的事件发生
  18.     {
  19.         timeout = TIMEOUT;//重置定时时间
  20.         continue;
  21.     }
  22.     end = time(NULL);
  23.     //如果number>0，说明监听的事件发生，没有超时，需要计算剩余时间
  24.     timeout -= (end - start) / 1000;
  25.     if (timeout <= 0)//剩余时间不够，重置时间
  26.     {
  27.         timeout = TIMEOUT;
  28.     }
  29.     //do somethings
  30. }

3 Linux定时函数

3.1 SIGALRM信号

一般而言，SIGALRM信号按照固定的频率生成，即有alarm或setitimer函数设置的定时周期T保持不变。如果某个定时任务的超时时间不是T的整数倍，那么它实际被执行的时间和预期的时间将略有偏差，因此定时周期T反映了定时的精度。
在多线程中处理信号是很麻烦的事，所以应该尽量避免使用触发信号的方式。

  1. int setitimer(int which, const struct itimerval *new_value, struct itimerval *old_value);
  2. //结构体定义如下：
  3. struct itimerval {
  4.     struct timeval it_interval; /* Interval for periodic timer */
  5.     struct timeval it_value;    /* Time until next expiration */
  6. };
  8. unsigned int alarm(unsigned int seconds);

3.2 timefd_系列函数

陈硕在muduo的书中提到，对于定时任务，应该采取如下原则：

  • 计时：只使用gettimeofday来获取当前时间
  • 定时：只使用timerfd_*系列函数来处理定时任务
    • timerfd_create把时间变成了一个文件描述符，该“文件”在定时器超时的那一刻变得可读，这样就能很方便地融入select(2)/poll(2)框架中，用统一的方式来处理IO事件和超时事件。
    • IO复用函数自带的timeout参数精度是毫秒，而timerfd_setime的精度可以达到纳秒。

函数定义如下：

  1. int gettimeofday(struct timeval *tv, struct timezone *tz);
  3. int timerfd_create(int clockid, int flags);
  4. int timerfd_settime(int fd, int flags,
  5.                     const struct itimerspec *new_value,
  6.                     struct itimerspec *old_value);
  7. int timerfd_gettime(int fd, struct itimerspec *curr_value);

4 两种高性能定时器设计

4.1 时间轮

image.png
在时间轮中：

  • 实线指针指向轮子上的一个槽（slot）。它以恒定的速度顺时针转动，每转动一步就指向下一个槽（slot）。每次转动称为一个滴答（tick），一个tick时间间隔为时间轮的si（slot interval）。该时间轮共有N个槽，因此它转动一周的时间是N*si
  • 每个槽指向一条定时器链表，每条链表上的定时器具有相同的特征：它们的定时时间相差N*si的整数倍。时间轮正是利用这个关系将定时器散列到不同的链表中
  • 假如现在指针指向槽cs，我们要添加一个定时时间为ti的定时器，则该定时器将被插入槽ts（timer slot）对应的链表中：ts=(cs + (ti / si)) % N。

时间轮使用了哈希表处理冲突的思想，将定时器散列到不同的链表上。这样每条链表上的定时器数目都将明显少于原来的排序链表上的定时器数目，插入操作的效率基本不受定时器数目的影响。对于时间轮而言，要提高精度，就要使si的值足够小; 要提高执行效率，则要求N值足够大，使定时器尽可能的分布在不同的槽。
对于时间轮，添加、删除和执行一个定时器的时间复杂度都是O(1)。
**
简单的一层时间轮设计示例：

  1. #ifndef TIME_WHEEL_TIMER
  2. #define TIME_WHEEL_TIMER
  4. #include <time.h>
  5. #include <netinet/in.h>
  6. #include <stdio.h>
  8. #define BUFFER_SIZE 64
  9. class tw_timer;
  10. struct client_data //绑定socket和定时器
  11. {
  12.     sockaddr_in address;
  13.     int sockfd;
  14.     char buf[BUFFER_SIZE];
  15.     tw_timer *timer;
  16. };
  18. class tw_timer //定时器类
  19. {
  20. public:
  21.     tw_timer(int rot, int ts)
  22.         : next(NULL), prev(NULL), rotation(rot), time_slot(ts) {}
  23. public:
  24.     int rotation;                   //记录该定时器在时间轮转多少圈后生效
  25.     int time_slot;                  //记录定时器属于那个槽
  26.     void (*cb_func)(client_data *); //定时器回调函数
  27.     client_data *user_data;         //用户数据
  28.     tw_timer *next;                 //指向上一个定时器
  29.     tw_timer *prev;                 //指向下一个定时器
  30. };
  32. class time_wheel //事件轮管理定时器
  33. {
  34. public:
  35.     time_wheel() : cur_slot(0)
  36.     {
  37.         for (int i = 0; i < N; ++i)
  38.         {
  39.             slots[i] = NULL; //每个槽的头节点初始化为空
  40.         }
  41.     }
  42.     ~time_wheel()
  43.     {
  44.         for (int i = 0; i < N; ++i)
  45.         {
  46.             tw_timer *tmp = slots[i];
  47.             while (tmp)
  48.             {
  49.                 slots[i] = tmp->next;
  50.                 delete tmp; //遍历每个槽，销毁new分配在堆中的定时器
  51.                 tmp = slots[i];
  52.             }
  53.         }
  54.     }
  55.     tw_timer *add_timer(int timeout) //添加新的定时器，插入到合适的槽中
  56.     {
  57.         if (timeout < 0) //时间错误
  58.         {
  59.             return NULL;
  60.         }
  61.         int ticks = 0;
  62.         if (timeout < TI) //小于每个槽的interval，则为1
  63.         {
  64.             ticks = 1;
  65.         }
  66.         else
  67.         {
  68.             ticks = timeout / TI; //相对当前位置的槽数
  69.         }
  70.         int rotation = ticks / N;                     //记录多少圈后生效
  71.         int ts = (cur_slot + (ticks % N)) % N;        //确定插入槽的位置
  72.         tw_timer *timer = new tw_timer(rotation, ts); //根据位置和圈数，插入对应的槽中
  73.         if (!slots[ts])                               //所在槽头节点为空，直接插入
  74.         {
  75.             printf("add timer, rotation is %d, ts is %d, cur_slot is %d\n", rotation, ts, cur_slot);
  76.             slots[ts] = timer;
  77.         }
  78.         else //头插法
  79.         {
  80.             timer->next = slots[ts];
  81.             slots[ts]->prev = timer;
  82.             slots[ts] = timer;
  83.         }
  84.         return timer; //返回含有时间信息和所在槽位置的定时器
  85.     }
  86.     void del_timer(tw_timer *timer) //从时间轮上删除定时器
  87.     {
  88.         if (!timer)
  89.         {
  90.             return;
  91.         }
  92.         int ts = timer->time_slot; //找到所在槽
  93.         if (timer == slots[ts])
  94.         {
  95.             slots[ts] = slots[ts]->next;
  96.             if (slots[ts])
  97.             {
  98.                 slots[ts]->prev = NULL;
  99.             }
  100.             delete timer;
  101.         }
  102.         else
  103.         {
  104.             timer->prev->next = timer->next;
  105.             if (timer->next)
  106.             {
  107.                 timer->next->prev = timer->prev;
  108.             }
  109.             delete timer;
  110.         }
  111.     }
  112.     void tick()
  113.     {
  114.         tw_timer *tmp = slots[cur_slot]; //取出当前槽的头节点
  115.         printf("current slot is %d\n", cur_slot);
  116.         while (tmp) //遍历
  117.         {
  118.             printf("tick the timer once\n");
  119.             if (tmp->rotation > 0)
  120.             {
  121.                 tmp->rotation--;
  122.                 tmp = tmp->next;
  123.             }
  124.             else
  125.             {
  126.                 tmp->cb_func(tmp->user_data); //符合条件，调用回调函数
  127.                 if (tmp == slots[cur_slot])
  128.                 {
  129.                     printf("delete header in cur_slot\n");
  130.                     slots[cur_slot] = tmp->next;
  131.                     delete tmp;
  132.                     if (slots[cur_slot])
  133.                     {
  134.                         slots[cur_slot]->prev = NULL;
  135.                     }
  136.                     tmp = slots[cur_slot];
  137.                 }
  138.                 else
  139.                 {
  140.                     tmp->prev->next = tmp->next;
  141.                     if (tmp->next)
  142.                     {
  143.                         tmp->next->prev = tmp->prev;
  144.                     }
  145.                     tw_timer *tmp2 = tmp->next;
  146.                     delete tmp;
  147.                     tmp = tmp2;
  148.                 }
  149.             }
  150.         }
  151.         cur_slot = ++cur_slot % N;
  152.     }
  153. private:
  154.     static const int N = 60;
  155.     static const int TI = 1;
  156.     tw_timer *slots[N];
  157.     int cur_slot;
  158. };
  159. #endif

4.2 时间堆

时间轮方案都是以固定的频率调用心搏函数tick，并在其中依次检测到期的定时器，然后执行到期定时器上的回调函数。
设计定时器的另外一种思路是：将所有定时器中超时时间最小的一个定时器的超时值作为心搏间隔。这样，一旦心搏函数tick被调用，超时时间最小的定时器必然到期，我们就可以在tick函数中处理该定时器。然后，再次从剩余的定时器中找出超时时间最小的一个，并将这段最小时间设置为下一次心搏间隔。如此反复， 就可以使用最小堆（每个节点都小于等于其子节点）实现了较为精确的定时。

对于时间堆，添加一个定时器的时间复杂度为O(lgn)，删除和执行一个定时器的时间复杂度为O(1)。

实现示例：

  1. #ifndef intIME_HEAP
  2. #define intIME_HEAP
  4. #include <iostream>
  5. #include <netinet/in.h>
  6. #include <time.h>
  7. using std::exception;
  9. #define BUFFER_SIZE 64
  11. class heap_timer;
  12. struct client_data
  13. {
  14.     sockaddr_in address;
  15.     int sockfd;
  16.     char buf[BUFFER_SIZE];
  17.     heap_timer *timer;
  18. };
  20. class heap_timer
  21. {
  22. public:
  23.     heap_timer(int delay)
  24.     {
  25.         expire = time(NULL) + delay;
  26.     }
  28. public:
  29.     time_t expire; //定时器生效的绝对时间
  30.     void (*cb_func)(client_data *); //定时器回调函数
  31.     client_data *user_data; //用户数据
  32. };
  34. class time_heap //时间堆类
  35. {
  36. public:
  37.     time_heap(int cap) throw(std::exception)
  38.         : capacity(cap), cur_size(0)//构造函数，初始化空堆
  39.     {
  40.         array = new heap_timer *[capacity];
  41.         if (!array)
  42.         {
  43.             throw std::exception();
  44.         }
  45.         for (int i = 0; i < capacity; ++i)
  46.         {
  47.             array[i] = NULL;
  48.         }
  49.     }
  50.     time_heap(heap_timer **init_array, int size, int capacity) throw(std::exception)
  51.         : cur_size(size), capacity(capacity)//构造函数，有init_array初始化堆
  52.     {
  53.         if (capacity < size)
  54.         {
  55.             throw std::exception();
  56.         }
  57.         array = new heap_timer *[capacity];
  58.         if (!array)
  59.         {
  60.             throw std::exception();
  61.         }
  62.         for (int i = 0; i < capacity; ++i)
  63.         {
  64.             array[i] = NULL;
  65.         }
  66.         if (size != 0)
  67.         {
  68.             for (int i = 0; i < size; ++i)
  69.             {
  70.                 array[i] = init_array[i];
  71.             }
  72.             for (int i = (cur_size - 1) / 2; i >= 0; --i)
  73.             {
  74.                 percolate_down(i);
  75.             }
  76.         }
  77.     }
  78.     ~time_heap()
  79.     {
  80.         for (int i = 0; i < cur_size; ++i)
  81.         {
  82.             delete array[i];
  83.         }
  84.         delete[] array;
  85.     }
  86. public:
  87.     void add_timer(heap_timer *timer) throw(std::exception)
  88.     {
  89.         if (!timer)
  90.         {
  91.             return;
  92.         }
  93.         if (cur_size >= capacity)
  94.         {
  95.             resize();//当前堆容量不够，扩大一倍容量
  96.         }
  97.         int hole = cur_size++;
  98.         int parent = 0;
  99.         for (; hole > 0; hole = parent)
  100.         {
  101.             parent = (hole - 1) / 2;
  102.             if (array[parent]->expire <= timer->expire)
  103.             {
  104.                 break;
  105.             }
  106.             array[hole] = array[parent];
  107.         }
  108.         array[hole] = timer;
  109.     }
  110.     void del_timer(heap_timer *timer)
  111.     {
  112.         if (!timer)
  113.         {
  114.             return;
  115.         }
  116.         //设置回调函数为空，节省了真正删除定时器构成的开销，但缺点是容易使堆数组膨胀
  117.         timer->cb_func = NULL;
  118.     }
  119.     heap_timer *top() const
  120.     {
  121.         if (empty())
  122.         {
  123.             return NULL;
  124.         }
  125.         return array[0];
  126.     }
  127.     void pop_timer()
  128.     {
  129.         if (empty())
  130.         {
  131.             return;
  132.         }
  133.         if (array[0])
  134.         {
  135.             delete array[0];
  136.             array[0] = array[--cur_size];
  137.             percolate_down(0);
  138.         }
  139.     }
  140.     void tick()
  141.     {
  142.         heap_timer *tmp = array[0];
  143.         time_t cur = time(NULL);
  144.         while (!empty())
  145.         {
  146.             if (!tmp)
  147.             {
  148.                 break;
  149.             }
  150.             if (tmp->expire > cur)
  151.             {
  152.                 break;
  153.             }
  154.             if (array[0]->cb_func)//array[0]使最小的超时时间，执行其回调函数
  155.             {
  156.                 array[0]->cb_func(array[0]->user_data);
  157.             }
  158.             pop_timer();//删除堆顶节点，生成新的顶节点
  159.             tmp = array[0];
  160.         }
  161.     }
  162.     bool empty() const { return cur_size == 0; }
  164. private:
  165.     void percolate_down(int hole)
  166.     {
  167.         heap_timer *temp = array[hole];
  168.         int child = 0;
  169.         for (; ((hole * 2 + 1) <= (cur_size - 1)); hole = child)
  170.         {
  171.             child = hole * 2 + 1;
  172.             if ((child < (cur_size - 1)) && (array[child + 1]->expire < array[child]->expire))
  173.             {
  174.                 ++child;
  175.             }
  176.             if (array[child]->expire < temp->expire)
  177.             {
  178.                 array[hole] = array[child];
  179.             }
  180.             else
  181.             {
  182.                 break;
  183.             }
  184.         }
  185.         array[hole] = temp;
  186.     }
  187.     void resize() throw(std::exception)
  188.     {
  189.         heap_timer **temp = new heap_timer *[2 * capacity];
  190.         for (int i = 0; i < 2 * capacity; ++i)
  191.         {
  192.             temp[i] = NULL;
  193.         }
  194.         if (!temp)
  195.         {
  196.             throw std::exception();
  197.         }
  198.         capacity = 2 * capacity;
  199.         for (int i = 0; i < cur_size; ++i)
  200.         {
  201.             temp[i] = array[i];
  202.         }
  203.         delete[] array;
  204.         array = temp;
  205.     }
  207. private:
  208.     heap_timer **array; //堆数组
  209.     int capacity; //堆容量
  210.     int cur_size; //当前元素个数
  211. };
  212. #endif