江苏龙网

  1. 主页 > 生活百科 > >

Linux内核时钟系统和定时器实现( 四 )

Linux内核


flags字段标识到期时间是一个绝对时间还是一个相对时间 。
/* Flag to indicate time is absolute.*/#define TIMER_ABSTIME1如果flags的值为TIMER_ABSTIME，则value的值为一个绝对时间 。否则，value为一个相对时间 。
timer_getoverrun(timer_t timerid)
取得一个定时器的超限运行次数：有可能一个定时器到期了，而同一定时器上一次到期时产生的信号还处于挂起状态 。在这种情况下，其中的一个信号可能会丢失 。这就是定时器超限 。程序可以通过调 用timer_getoverrun来确定一个特定的定时器出现这种超限的次数 。定时器超限只能发生在同一个定时器产生的信号上 。由多个定时器，甚至是那 些使用相同的时钟和信号的定时器，所产生的信号都会排队而不会丢失 。
执行成功时，timer_getoverrun()会返回定时器初次到期与通知进程(例如通过信号)定时器已到期之间额外发生的定时器到期次数 。举例来说，在我们之前的例子中，一个1ms的定时器运行了10ms，则此调用会返回9 。如果超限运行的次数等于或大于DELAYTIMER_MAX，则此调用会返回DELAYTIMER_MAX 。
执行失败时，此函数会返回-1并将errno设定会EINVAL，这个唯一的错误情况代表timerid指定了无效的定时器 。
timer_delete (timer_t timerid)
删除一个定时器：一次成功的timer_delete()调用会销毁关联到timerid的定时器并且返回0 。执行失败时，此调用会返回-1并将errno设定会 EINVAL，这个唯一的错误情况代表timerid不是一个有效的定时器 。
POSIX定时器通过调用内核的posix_timer进行实现，但glibc对POSIX timer进行了一定的封装，例如如果POSIX timer到期通知方式被设置为 SIGEV_THREAD 时，glibc 需要自己完成一些辅助工作，因为内核无法在 Timer 到期时启动一个新的线程 。
inttimer_create (clock_id, evp, timerid)clockid_t clock_id;struct sigevent *evp;timer_t *timerid;{if (evp == NULL || __builtin_expect (evp->sigev_notify != SIGEV_THREAD, 1)){...}else{.../* Create the helper thread.*/pthread_once (&__helper_once, __start_helper_thread);...}...}可以看到 GLibc 发现用户需要启动新线程通知时，会自动调用 pthread_once 启动一个辅助线程（__start_helper_thread），用 sigev_notify_attributes 中指定的属性设置该辅助线程 。
然后 glibc 启动一个普通的 POSIX Timer，将其通知方式设置为：SIGEV_SIGNAL | SIGEV_THREAD_ID 。这样就可以保证内核在 timer 到期时通知辅助线程 。通知的 Signal 号为 SIGTIMER，并且携带一个包含了到期函数指针的数据 。这样，当该辅助 Timer 到期时，内核会通过 SIGTIMER 通知辅助线程，辅助线程可以在信号携带的数据中得到用户设定的到期处理函数指针，利用该指针，辅助线程调用 pthread_create() 创建一个新的线程来调用该处理函数 。这样就实现了 POSIX 的定义 。
3. 自定义定时器实现方案在业务项目中，对于系统提供的定时器API往往很难满足我们的需求：
itimer在进程中每种timer类型(ITIMER_REAL, ITIMER_PROF, ITIMER_VIRT)只能使用一个，另外一点就是他是基于signal进行超时提醒，不仅和alarm，sleep这些api冲突，而且在业务代码中signal是个很不可控的机制，尽量都会减少使用 。
POSIX定时器在itimer基础上进行了很大的改进，解决了itimer的不足，可以说POSIX定时器可以满足了业务很多的需求 。
3.1 基于小根堆的定时器实现
小根堆定时器的实现方式，是最常见的一种实现定时器的方式 。堆顶时钟保存最先到期的定时器，基于事件触发的定时器系统可以根据堆顶定时器到期时间，进行睡眠 。基于周期性睡眠的定时器系统，每次只需遍历堆顶的定时器是否到期，即可 。堆顶定时器超时后，继续调整堆，使其保持为小根堆并同时对堆顶定时器进行超时判断 。
小根堆定时器在插入时的时间复杂度在O(lgn)(n为插入时定时器堆的定时器数量)，定时器超时处理时调整堆的复杂度在所有定时器都超时情况下为：O(nlgn) 。在一般情况下，小根堆的实现方式可满足业务的基本需求 。
3.2 基于时间轮的定时器实现
定时器的实现方式有两种：一级时间轮和多级时间轮 。
一级时间轮
一级时间轮如下图所示：一个轮子(数组实现)，轮子的每个槽(spoke)后面会挂一个timer列表，表示当命中该spoke时，timer列表的所有定时器全部超时 。
如果定时器轮的精度是1ms，那么spoke个数为2^10时，仅仅能够表示1s，2^20表示17.476min.
如果精度为1s，那么spoke个数为2^10时，能够表示17min，2^20表示12day.
所有这种一级时间轮的实现方式所带来的空间复杂度还是不小的 。特别是在需要跨度比较长的定时器时 。基于此，就出现了多级时间轮，也就是linux2.6.16之前内核所采用的定时器的实现方式 。


推荐阅读


上一篇：PHP 二维数组根据某个键值 给二位数组分类

下一篇：新人头条创作介绍四大领域，容易上手，建议收藏