【2-6 Golang】Go并发编程—定时器timer

tomato01 · · 1303 次点击 · · 开始浏览    

&emsp;&emsp;定时器使得我们可以延迟若干时间执行某项任务,或者以某一时间周期性执行某项任务,Linux系统本身也具备定时器能力,Go语言是定时器是基于系统调用实现的吗?另外,Go语言不是多协程吗,定时器触发时,是在哪个协程执行任务的呢?创建任务的协程吗? ## 基本操作 &emsp;&emsp;Go语言time包提供了时间/定时器相关的API,如获取当前系统时间(可以到达纳秒级别),协程休眠指定时间,延迟指定时间执行某项任务,以某一时间周期性执行某项任务等等,操作如下: ``` package main import ( "fmt" "time" ) func main() { //纳秒时间戳 t := time.Now().UnixNano() fmt.Println(t) //1652510180050345000 //秒时间戳 t = time.Now().Unix() fmt.Println(t) //1652510180 //格式化显示时间 fmt.Println(time.Now().Format("2006-01-02 15:04:05")) //2022-05-14 14:36:20 // 一秒后执行函数 time.AfterFunc(time.Second, func() { fmt.Println(time.Now().Format("2006-01-02 15:04:05")) }) // 以一秒为周期,定时触发 ticker := time.NewTicker(time.Second) go func() { for { <- ticker.C //时间触发时,管道可读 fmt.Println(time.Now().Format("2006-01-02 15:04:05")) } }() //协程休眠3秒 time.Sleep(10 * time.Second) } ``` &emsp;&emsp;注意格式化时间显示时间年月日时分秒,用的是"2006-01-02 15:04:05",Format方法使用其他格式如"2022-05-14 14:36:20"可以吗?按理说这两个时间字符串格式是一样的,只是值不一样罢了,结果应该没区别。写个小程序测试下,你会发现,结果有点奇怪: ``` package main import ( "fmt" "time" ) func main() { //格式化显示时间 fmt.Println(time.Now().Format("2022-05-14 14:36:20")) //输出:141414-02-540 540:26:140 } ``` &emsp;&emsp;这是什么?为什么不是正常的年月日时分秒显示呢?这就需要研究下Go语言Format方法,支持的格式标识,比如其他一些语言使用Y表示年,M表示月等。Go语言定义的年月日等标识如下: ``` const ( stdZeroMonth // "01" stdZeroDay // "02" stdHour = iota + stdNeedClock // "15" stdZeroMinute // "04" stdZeroSecond // "05" stdLongYear = iota + stdNeedDate // "2006" //省略了其他标识定义 ) ``` &emsp;&emsp;看到了吧,"2006"、"01"等才是Go语言定义的时间格式标识,所以"2006-01-02 15:04:05"才能正常显示年月日时分秒,而其他如"2022-05-14 14:36:20"的结果就有些不符合预期了。当然,这里还省略了很多其他时间格式标识,就定义在time/format.go文件,有兴趣的读者可以自己研究。 &emsp;&emsp;再回顾上面的程序,time.AfterFunc可以在指定时间执行函数,time.NewTicker可以以一定时间周期触发时间,time.Sleep可以使协程休眠一定时间(过期后再恢复协程的调度),这如何实现呢?要知道项目中可能大量使用定时器,Go语言如何能在精确的时间触发定时事件呢?另外time.AfterFunc,执行函数时,是在哪个协程执行呢?添加定时器的协程吗? ## 实现原理-堆 &emsp;&emsp;Go语言如何能在精确的时间触发定时事件呢?这意味着定时器的增删改查效率必须要高,不然难道每次都遍历所有定时器,判断哪些该触发吗?如果维护所有定时器有序呢?只需要查找第一个定时器,如果到期了则触发,并且继续查找;如果未到期也就不用继续查找了,因为后面的到期时间肯定大于第一个定时器的到期时间。但是为了维护有序,添加定时器、修改定时器以及删除定时器的效率又太低。 &emsp;&emsp;需要具备一定的有序性,增删改查性能还要高,什么数据结构合适呢?有一种数据结构叫堆(最大堆,最小堆),以最小堆为例,它本质上是一棵完全二叉树,只是要求任何一个节点的值,都小于左右两个子节点的值,所以根节点的值一定是最小的。这样如果定时器使用了最小堆,只需要判断根节点是否到期,如果到期则触发并删除根节点,而删除的过程中还需要保证剩下的节点依然满足最小堆的条件;这样一来,获取下一个最近到期的定时器,时间复杂度依然是O(1)。那么,最小堆,节点的删除以及添加的时间复杂度是多少呢?也是比较低的,O(logn)。 &emsp;&emsp;普通二叉树节点通常需要左右left、right指针,而堆是完全二叉树,可以基于数组实现的,为什么呢?因为父子节点的索引是有关系的,如下图: ![2.6-1.png](https://static.golangjob.cn/220929/8d55ce7ed855b3cf8cc6d39de5b71da8.png) &emsp;&emsp;堆在插入节点时,通常先添加到数组的最后,再与父节点比较,如果满足堆的定义,则结束;否则,与父节点交换。持续比较交换到根节点为止,这一过程称之为上浮。一棵节点数为N的完全二叉树,高度为logn,也就是说比较交换最多需要执行logn次,即堆的插入时间复杂度为O(logn)。 &emsp;&emsp;堆在删除根节点时,通常先交换根节点与最后一个节点,再直接删除最后一个节点(也就是根节点);此时根节点可能不满足堆的定义,所以,还需要与左右两个子节点比较。持续比较交换到最后一个节点为止,这一过程称之为下沉。删除的时间复杂度同样为O(logn)。删除过程逻辑如下: &emsp;&emsp;普通堆是完全二叉树,而Go语言使用的是四叉树,为什么呢?树更低,时间复杂度更低呗。结合我们介绍的堆的插入与删除逻辑,我们看看Go语言四叉堆的插入与上浮逻辑: ``` func siftupTimer(t []*timer, i int) int { tmp := t[i] for i > 0 { //四叉树,父节点索引是(i - 1) / 4 p := (i - 1) / 4 // parent if when >= t[p].when { //父节点小于当前节点,break break } t[i] = t[p] //交换 i = p } if tmp != t[i] { //交换 t[i] = tmp } return i } //添加定时器 func doaddtimer(pp *p, t *timer) { i := len(pp.timers) pp.timers = append(pp.timers, t) siftupTimer(pp.timers, i) //如果是根节点,记录过期时间(最小) if t == pp.timers[0] { atomic.Store64(&pp.timer0When, uint64(t.when)) } } ``` &emsp;&emsp;Go语言四叉堆的删除与下沉逻辑非常类似,这里就不再赘述,可以参考runtime/time.go文件,dodeltimer0与siftdownTimer这两个函数。 &emsp;&emsp;另外可以看到,结构timer就代表了一个定时器,包含了定时器的过期时间,执行周期,执行方法等等,定义如下: ``` type timer struct { // Timer wakes up at when, and then at when+period, ... (period > 0 only) when int64 period int64 //执行方法+参数 f func(any, uintptr) arg any seq uintptr } ``` &emsp;&emsp;思考一下,Go语言是多线程+多协程程序,如果多个协程并发添加定时器呢?如果全局只有一个定时器堆,是不是每次操作都需要加锁呢?Go语言低版本就是这么实现的。现在是每一个P都维护了一个定时器堆,从doaddtimer函数就能看出来,传入了当前线程M绑定的P,而定时器也是添加到该P的定时器堆。看看P结构定义的定时器相关字段: ``` type p struct { //定时器堆 timers []*timer // The when field of the first entry on the timer heap. // This is updated using atomic functions. // This is 0 if the timer heap is empty. //定时器堆根节点的过期时间(最小) timer0When uint64 } ``` &emsp;&emsp;最后读者要注意的是,time包定义了很多定时器相关的函数,但是这些函数的具体实现往往是在runtime包,比如 ``` func Sleep(d Duration) //实现函数为 timeSleep func startTimer(*runtimeTimer) //time.NewTicker、time.After等都是基于startTimer函数添加的定时器 func stopTimer(*runtimeTimer) bool func resetTimer(*runtimeTimer, int64) bool //timeSleep基于resetTimer实现 ``` &emsp;&emsp;可以简单看看time.AfterFunc函数的实现: ``` func AfterFunc(d Duration, f func()) *Timer { t := &Timer{ r: runtimeTimer{ when: when(d), f: goFunc, //启动一个协程执行函数f arg: f, }, } startTimer(&t.r) return t } ``` ## 定时器与调度器schedule &emsp;&emsp;每一个P都维护一个定时器四叉堆,那么Go语言是在什么时候检测是否要定时器过期呢?这肯定与调度器schedule有关了: ``` func schedule() { //检测定时器并执行 checkTimers(pp, 0) //查找可执行协程 } func checkTimers(pp *p, now int64) (rnow, pollUntil int64, ran bool) { //最近过期的定时器 next := int64(atomic.Load64(&pp.timer0When)) if next == 0 { // No timers to run or adjust. return now, 0, false } if now == 0 { now = nanotime() } //第一个定时器没有过期,返回 if now < next { return now, next, false } if len(pp.timers) > 0 { adjusttimers(pp, now) for len(pp.timers) > 0 { //运行定时器(获取第一个定时器,如果过期则执行,否则返回时间差) if tw := runtimer(pp, now); tw != 0 { //第一个定时器没有过期,结束循环 break } ran = true } } } ``` &emsp;&emsp;这下都明白了,调度器schedule在查找可运行协程时,先通过checkTimers检测定时器是否过期,并执行。也就是说,定时器函数f是在调度调度栈执行的;而且,如果某一个协程长时间运行(假设也没有被抢占),也有可能导致定时器的延后触发。 ## 系统时间 &emsp;&emsp;最后再思考一个问题,Go语言获取时间戳甚至可以精确到纳秒级别,按理来说,获取时间通常需要通过系统调用完成,而系统调用又会导致程序的低性能。那么Go语言是如何高性能的实现系统时间的获取呢? &emsp;&emsp;这里需要了解一个概念,Linux VDSO(virtual dynamic shared object),他是为了优化用户程序频繁的系统调用,把系统调用改成用户态的函数调用,gettimeofday就是其中一个。 &emsp;&emsp;VDSO的介绍可以参考文章:https://zhuanlan.zhihu.com/p/436454953 ## 总结 &emsp;&emsp;本篇文章主要介绍了Go语言定时器的基本使用以及实现原理,堆(最大堆/最小堆)有很多应用场景,如定时器,优先级队列等等。用户程序可能添加很多定时任务,而调度器schedule在调度协程之前,会检测是否有定时任务到期,如果有则执行该定时任务。

有疑问加站长微信联系(非本文作者))

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1303 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传