skynet的定时器

kindf 收录于类别 skynet相关

2023-11-14 约 1877 字

简析

skyent 用 5 个链表数组来存储定时事件，分别是 near[256] 和 t[4]，其中 near 数组用来存放即将到期的定时事件，t[0] ~ t[3] 数组分别存放不同时间段的定时事件
插入时，定时器根据过期时间 expire 和当前时间 now 的相对时间，将事件放到对应的链表当中
tick的时候，定时器直接取 near 中的到期事件触发
每过一定时间，定时器将 t[0] ~ t[3] 中的事件重新分配到合适的位置

主要结构

   39 >   struct timer {
   40 >   struct link_list near[TIME_NEAR];   //到期时间较近定时器事件链表
   41 >   struct link_list t[4][TIME_LEVEL];  //定时器事件链表
   42 >   struct spinlock lock;               //自旋锁
   43 >   uint32_t time;                      //启动后tick的时间
   44 >   uint32_t starttime;                 //启动时的系统时间
   45 >   uint64_t current;                   //skynet自己计算出的实际时间
   46 >   uint64_t current_point;             //系统启动后的绝对时间
   47 };

skynet定时器的基本思想就是把到期时间较近的事件放到near数组中，其余的放到t数值中，每次tick后就从near数组中找到到期的事件触发

tick函数

  165 static void-
  166 timer_update(struct timer *T) {
  167 >   SPIN_LOCK(T);
  168
  169 >   // try to dispatch timeout 0 (rare condition)
  170 >   timer_execute(T);
  171
  172 >   // shift time first, and then dispatch timer message
  173 >   timer_shift(T);
  174
  175 >   timer_execute(T);
  176
  177 >   SPIN_UNLOCK(T);
  178 }

  245 void
  246 skynet_updatetime(void) {
  247 >   uint64_t cp = gettime();
  248 >   if(cp < TI->current_point) {
  249 >   >   skynet_error(NULL, "time diff error: change from %lld to %lld", cp, TI->current_point);
  250 >   >   TI->current_point = cp;
  251 >   } else if (cp != TI->current_point) {
  252 >   >   uint32_t diff = (uint32_t)(cp - TI->current_point);
  253 >   >   TI->current_point = cp;
  254 >   >   TI->current += diff;
  255 >   >   int i;
  256 >   >   for (i=0;i<diff;i++) {
  257 >   >   >   timer_update(TI);
  258 >   >   }
  259 >   }
  260 }

skynet的timer线程每2500微秒（即2.5毫秒）执行一次skynet_updatetime

主要流程

  165 static void-
  166 timer_update(struct timer *T) {
  167 >   SPIN_LOCK(T);
  168
  169 >   // try to dispatch timeout 0 (rare condition)
  170 >   timer_execute(T);     // 触发定时器
  171
  172 >   // shift time first, and then dispatch timer message
  173 >   timer_shift(T);       // 过期时间再分配
  174
  175 >   timer_execute(T);     // 触发定时器
  176
  177 >   SPIN_UNLOCK(T);
  178 }

这里执行了两次timer_execute，按理来说，第一次timer_execute并不是必须的，因为注册过期时间为现在的事件是直接分发事件而不进入到定时器中。对于为啥执行两次的解释，作者希望timer 不需要关注 skynet 的用法实现，即不管skynet有没有处理time==0的情况，timer都不会因此出现bug

定时器的插入

   67 static void
   68 add_node(struct timer *T,struct timer_node *node) {
   69 >   uint32_t time=node->expire;       // 过期时间
   70 >   uint32_t current_time=T->time;    // 当前时间
   71 >
   72 >   if ((time|TIME_NEAR_MASK)==(current_time|TIME_NEAR_MASK)) {   // 将较近的放到near数组中
   73 >   >   link(&T->near[time&TIME_NEAR_MASK],node);
   74 >   } else {
   75 >   >   int i;
   76 >   >   uint32_t mask=TIME_NEAR << TIME_LEVEL_SHIFT;
   77 >   >   for (i=0;i<3;i++) {
   78 >   >   >   if ((time|(mask-1))==(current_time|(mask-1))) {
   79 >   >   >   >   break;
   80 >   >   >   }
   81 >   >   >   mask <<= TIME_LEVEL_SHIFT;
   82 >   >   }
   83
   84 >   >   link(&T->t[i][((time>>(TIME_NEAR_SHIFT + i*TIME_LEVEL_SHIFT)) & TIME_LEVEL_MASK)],node);>     // 根据过期时间的长短放到 t 中
   85 >   }
   86 }

分析：
- 将和 current_time 高 24 位相同的 time 放到 near[x] 中，x 为 time 的第 0 ~ 7 位表示的十进制值（如 time 的第 0 ~ 7 位为 00000010时，放到 near[2] 中）
- 将和 current_time 高 18 位相同的 time 放到 t[0][x]中，x 为 time 的第 8 ~ 14 位表示的十进制值（如 time 的第 8 ~ 14 位为 000010时，放到 t[0][2] 中）
- 将和 current_time 高 12 位相同的 time 放到 t[1][x]中，x 为 time 的第 15 ~ 21 位表示的十进制值（如 time 的第 15 ~ 21 位为 000010时，放到 t[1][2] 中）
- 将和 current_time 高 6 位相同的 time 放到 t[2][x]中，x 为 time 的第 22 ~ 27 位表示的十进制值（如 time 的第 22 ~ 27 位为 000010时，放到 t[2][2] 中）
- 将其余的 time 放到 t[3][x] 中，x 为 time 的第 28 ~ 32 位表示的十进制值（如 time 的第 28 ~ 32 位为 000010时，放到 t[3][2] 中）

定时器的执行

  152 static inline void
  153 timer_execute(struct timer *T) {
  154 >   int idx = T->time & TIME_NEAR_MASK;
  155 >
  156 >   while (T->near[idx].head.next) {
  157 >   >   struct timer_node *current = link_clear(&T->near[idx]);
  158 >   >   SPIN_UNLOCK(T);
  159 >   >   // dispatch_list don't need lock T
  160 >   >   dispatch_list(current);
  161 >   >   SPIN_LOCK(T);
  162 >   }
  163 }

因为最近的事件都在near上，只需要根据idx就能找到到期的事件

过期事件的再分配

  101 static void
  102 move_list(struct timer *T, int level, int idx) {
  103 >   struct timer_node *current = link_clear(&T->t[level][idx]);
  104 >   while (current) {
  105 >   >   struct timer_node *temp=current->next;
  106 >   >   add_node(T,current);
  107 >   >   current=temp;
  108 >   }
  109 }

  111 static void
  112 timer_shift(struct timer *T) {
  113 >   int mask = TIME_NEAR;
  114 >   uint32_t ct = ++T->time;
  115 >   if (ct == 0) {
  116 >   >   move_list(T, 3, 0);
  117 >   } else {
  118 >   >   uint32_t time = ct >> TIME_NEAR_SHIFT;
  119 >   >   int i=0;
  120
  121 >   >   while ((ct & (mask-1))==0) {
  122 >   >   >   int idx=time & TIME_LEVEL_MASK;
  123 >   >   >   if (idx!=0) {
  124 >   >   >   >   move_list(T, i, idx);
  125 >   >   >   >   break;> >   >   >
  126 >   >   >   }
  127 >   >   >   mask <<= TIME_LEVEL_SHIFT;
  128 >   >   >   time >>= TIME_LEVEL_SHIFT;
  129 >   >   >   ++i;
  130 >   >   }
  131 >   }
  132 }

由于要保证快到期的事件都要在 near 中，随着 current_time 增加，t 中某些事件与 current_time 的相对位置就会发生改变，time_shift 函数就是处理这种情况
重新分配的时机：
- 当 current_time 为低 8 位为 0 时，将 t[0][x] 中的事件重新分配，x 为第 8 ~ 13 位所表示的十进制值（如 current_time 为 111111 | 111111 | 111111 | 100010 | 00000000 时，x 则为 000000 | 000000 | 000000 | 000000 | 00100010，即放到 t[0][34] 中）
- 当 current_time 为低 14 位为 0 时，将 t[1][x] 中的事件重新分配，x 为第 14 ~ 19 位所表示的十进制值（如 current_time 为 111111 | 111111 | 000010 | 000000 | 00000000 时，x = 2）
- 当 current_time 为低 20 位为 0 时，将 t[2][x] 中的事件重新分配，x 为第 20 ~ 25 位所表示的十进制值（如 current_time 为 111111 | 000010 | 000000 | 000000 | 00000000 时，x = 2）
- 当 current_time 为低 26 位为 0 时，将 t[3][x] 中的事件重新分配，x 为第 14 ~ 19 位所表示的十进制值（如 current_time 为 000010 | 000000 | 000000 | 000000 | 00000000 时，x = 2）
可以看出来，每隔 256（ 2 的 8 次方）单位时间重新分配 t[0]，每隔 2 的 14 次方单位时间重新分配 t[1]，每隔 2 的 20 次方单位时间重新分配 t[2]，每隔 2 的 26 次方单位时间重新分配 t[3]