draveness / blog-comments

面向信仰编程
https://draveness.me
140 stars 6 forks source link

Golang 并发编程与定时器 · /golang-timer #152

Closed draveness closed 2 years ago

draveness commented 5 years ago

https://draveness.me/golang-timer

Devying commented 5 years ago

楼主什么时候开一期 goroutine 原理

draveness commented 5 years ago

楼主什么时候开一期 goroutine 原理

下一节会介绍,还有什么需求么?

Devying commented 5 years ago

@draveness

楼主什么时候开一期 goroutine 原理

下一节会介绍,还有什么需求么?

网络通讯这个可以讲一下,顺带讲下网络协议栈,😊

wyp2013 commented 5 years ago

楼主最近在看你的文章 什么时候讲一下go 内存 最后又图的那种(本人理解能力差) 还有一直在用grpc 但是不知道其原理,能不能顺便也弄一篇讲讲

draveness commented 5 years ago

gRPC 这里不会讲,内存管理之后应该会有 On Jul 17, 2019, 4:01 PM +0800, wyp2013 notifications@github.com, wrote:

楼主最近在看你的文章 什么时候讲一下go 内存 最后又图的那种(本人理解能力差) 还有一直在用grpc 但是不知道其原理,能不能顺便也弄一篇讲讲 — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

wyp2013 commented 5 years ago

@draveness gRPC 这里不会讲,内存管理之后应该会有 On Jul 17, 2019, 4:01 PM +0800, wyp2013 notifications@github.com, wrote:

楼主最近在看你的文章 什么时候讲一下go 内存 最后又图的那种(本人理解能力差) 还有一直在用grpc 但是不知道其原理,能不能顺便也弄一篇讲讲 — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

如果后面讲grpc了 能否发个消息 已关注你微信公众号

jdxj commented 5 years ago

addtimerLocked 会先将最新加入的定时器加到队列的末尾,随后调用 siftupTimer 将当前定时器与四叉树(或者四叉堆)中的父节点进行比较,保证父节点的到期时间一定大于子节点:

这里的到期时间, 是父大于子吗? 前面说是最小堆.

draveness commented 5 years ago

addtimerLocked 会先将最新加入的定时器加到队列的末尾,随后调用 siftupTimer 将当前定时器与四叉树(或者四叉堆)中的父节点进行比较,保证父节点的到期时间一定大于子节点:

这里的到期时间, 是父大于子吗? 前面说是最小堆.

应该是小于,我改一下

Esdeath commented 5 years ago

博客终于改成html静态页面了.之前一直以为灯塔不在意流量呢

draveness commented 5 years ago

博客终于改成html静态页面了.之前一直以为灯塔不在意流量呢

静态页面有什么好处?

Esdeath commented 5 years ago

@draveness

博客终于改成html静态页面了.之前一直以为灯塔不在意流量呢

静态页面有什么好处?

能被搜索引擎抓取.你之前的文章,没有使用静态页面.基本都是别人直接通过博客来看的.并不是通过搜索来的. 我看了一下,你之前的文章现在还没有静态化.

draveness commented 5 years ago

@draveness

博客终于改成html静态页面了.之前一直以为灯塔不在意流量呢

静态页面有什么好处?

能被搜索引擎抓取.你之前的文章,没有使用静态页面.基本都是别人直接通过博客来看的.并不是通过搜索来的. 我看了一下,你之前的文章现在还没有静态化.

没有吧,之前也都是 SEO 过来的

TennyZhuang commented 5 years ago

这里用四叉树有什么讲究吗?不是一般的二叉树也不是像一般 B tree 一样直接用满一个 memory page,有什么考量吗

draveness commented 5 years ago

这里用四叉树有什么讲究吗?不是一般的二叉树也不是像一般 B tree 一样直接用满一个 memory page,有什么考量吗

比二叉树层级低点,没有 B-Tree 实现复杂,B-Tree 的大小是一个 page 的原因是把文件加载到内存是按照页去加载的吧,但是这个树整个都在内存里

bbbbbbbbbbbbba commented 5 years ago

hi,看了你的文章,觉得很不错。 我最近也在学习Go,我有个练手项目,欢迎交流。

bestdpf commented 5 years ago

就是时间轮吧?

yanjinbin commented 5 years ago

@TennyZhuang 这里用四叉树有什么讲究吗?不是一般的二叉树也不是像一般 B tree 一样直接用满一个 memory page,有什么考量吗

这里楼主说的是四叉树 准确的说应该是个数组实现的四叉堆吧

yanjinbin commented 5 years ago

https://blog.gopheracademy.com/advent-2016/go-timers/ 这篇讲的也不错哦,配合饮用风味更佳

draveness commented 5 years ago

这里楼主说的是四叉树 准确的说应该是个数组实现的四叉堆吧

没有找到四叉堆这个概念,文中也只是简单带过了,因为当时只找到了 四叉树,有可靠的信息来源么?

yanjinbin commented 5 years ago

@draveness

这里楼主说的是四叉树 准确的说应该是个数组实现的四叉堆吧

没有找到四叉堆这个概念,文中也只是简单带过了,因为当时只找到了 四叉树,有可靠的信息来源么?

的确没有四叉堆的叫法, 我了解过的叫法 二叉堆 多叉树 , 但是你看他源码 不是用树的结构,而是数组来通过上浮shiftup 下沉shiftdown来处理存储index 所以我认为 叫堆更妥当点吧 ,虽然查询复杂度都是log4(N)左右 另外,请教下楼主,你是怎么看出这些源码调用的关联尤其是入口 以及遇到反射 , 常规IDE debug玩不转 是不是从汇编和GDB调式工具入手的 这方面,能请教下吗?

draveness commented 5 years ago

但是你看他源码 不是用树的结构,而是数组来通过上浮shiftup 下沉shiftdown来处理存储index 所以我认为 叫堆更妥当点吧 ,虽然查询复杂度都是log4(N)左右

我还是不想使用没有准确定义的概念,不过你自己可以这么用

另外,请教下楼主,你是怎么看出这些源码调用的关联尤其是入口 以及遇到反射 , 常规IDE debug玩不转

没有用过调试器,一般用两种方式:

  1. 直接看的汇编,翻源码;
  2. 比较复杂搞不太清楚的,就改一下 Go 的源码,然后重新编译用编译的 Go 二进制执行一些代码看看行为;
yanjinbin commented 5 years ago

@draveness

但是你看他源码 不是用树的结构,而是数组来通过上浮shiftup 下沉shiftdown来处理存储index 所以我认为 叫堆更妥当点吧 ,虽然查询复杂度都是log4(N)左右

我还是不想使用没有准确定义的概念,不过你自己可以这么用

另外,请教下楼主,你是怎么看出这些源码调用的关联尤其是入口 以及遇到反射 , 常规IDE debug玩不转

没有用过调试器,一般用两种方式:

  1. 直接看的汇编,翻源码;
  2. 比较复杂搞不太清楚的,就改一下 Go 的源码,然后重新编译用编译的 Go 二进制执行一些代码看看行为;

哈哈 好 蟹蟹你 , 四叉树 那个 wiki定义 应该遵循的还是 类似二叉树 Tree{ up,down,left,right }, 既然数据查询是数组索引 杠一下,主体还是堆 1父4子的堆 更贴切点

wwlwwww commented 4 years ago

该函数会先获取当前的 Goroutine 并在当前的『CPU 上』创建一个信号量,随后在 entersyscallblock 和 exitsyscall 之间执行系统调用让当前的 Goroutine 陷入休眠并在 ns 纳秒后返回。

这个系统调用是什么呢,如何实现“陷入休眠并在ns纳秒后返回”?

GavinXu520 commented 4 years ago

楼主干货满满,大赞一个

ahjdzx commented 4 years ago

这个四叉树只能保证父节点的到期时间大于子节点,这对于我们来说其实也足够了

应该是小于吧? @draveness

draveness commented 4 years ago

这个四叉树只能保证父节点的到期时间大于子节点,这对于我们来说其实也足够了

应该是小于吧? @draveness

修复了

draveness commented 4 years ago

@Devying 楼主什么时候开一期 goroutine 原理

Goroutine 原理可以看这个了 https://draveness.me/golang/docs/part3-runtime/ch06-concurrency/golang-goroutine/

tidyoux commented 4 years ago
  1. 6.3.3 状态机 部分有一处笔误:
  • timerModifiedEarliertimerModifiedLater — 计时器虽然在堆上,但是可能位于错误的处理器上;

根据原代码:

// The timer is in some P's heap, possibly in the wrong place.
timerModifiedEarlier

cleantimers:

case timerModifiedEarlier, timerModifiedLater:
    ...

    // Move t to the right position.
    if !dodeltimer0(pp) {
        return false
    }
    if !doaddtimer(pp, t) {
        return false
    }

    ...

可见这里的意思应该是说 在堆的错误的位置上(需要排序)

  1. 删除计时器 部分有两处笔误:

runtime.deltimer 函数会标记需要删除的计时器,它会根据以下的规则处理计时器:

  • timerNoStatus -> timerDeleted
  • timerModifiedEarlier -> timerModifying -> timerDeleted
  • timerModifiedLater -> timerDeleted
  • timerWaiting -> 崩溃:不合法的状态
  • timerRunning、timerMoving -> 等待状态改变
  • timerModifying -> 崩溃:并发删除或者修改计时器

根据原代码应为,

  1. 调整计时器 部分有一处表述不清:

runtime.cleantimers 不同的是,上述函数会遍历处理器堆中的全部计时器,而不是只修改四叉堆顶部。

这会让人误以为 adjusttimers 在正常情况下总会遍历堆中的全部计时器,这和下面 调度器 部分的说法矛盾:

runtime.clearDeletedTimers 能够避免堆中出现大量长时间运行的计时器,该函数和 runtime.moveTimers 也是唯二会遍历计时器堆的函数。

实际上根据原代码,有退出遍历的条件:

if n := atomic.Xadd(&pp.adjustTimers, -1); int32(n) <= 0 {
    break loop
}
  1. 调度器 部分有一处表述不清:

runtime.checkTimers 函数的最后,如果当前 Goroutine 的处理器和传入的处理器相同,并且处理器中删除的计时器是堆中计时器的 1/4 以上,就会调用 runtime.clearDeletedTimers 删除处理器堆中的全部计时器。

runtime.clearDeletedTimers 能够避免堆中出现大量长时间运行的计时器

这里应该是 删除全部被标记为 timerDeleted 的计时器 ,因为 cleantimersadjusttimers 可能处理不到那些非常靠后的计时器,这些计时器的 timerDeleted 状态需要通过 clearDeletedTimers 来处理。

draveness commented 4 years ago
  1. 6.3.3 状态机 部分有一处笔误:
  • timerModifiedEarliertimerModifiedLater — 计时器虽然在堆上,但是可能位于错误的处理器上;

根据原代码:

// The timer is in some P's heap, possibly in the wrong place.
timerModifiedEarlier

cleantimers:

case timerModifiedEarlier, timerModifiedLater:
    ...

    // Move t to the right position.
    if !dodeltimer0(pp) {
      return false
    }
    if !doaddtimer(pp, t) {
      return false
    }

    ...

可见这里的意思应该是说 在堆的错误的位置上(需要排序)

  1. 删除计时器 部分有两处笔误:

runtime.deltimer 函数会标记需要删除的计时器,它会根据以下的规则处理计时器:

  • timerNoStatus -> timerDeleted
  • timerModifiedEarlier -> timerModifying -> timerDeleted
  • timerModifiedLater -> timerDeleted
  • timerWaiting -> 崩溃:不合法的状态
  • timerRunning、timerMoving -> 等待状态改变
  • timerModifying -> 崩溃:并发删除或者修改计时器

根据原代码应为,

  • timerNoStatus -> 状态保持不变
  • timerWaiting -> timerDeleted
  1. 调整计时器 部分有一处表述不清:

runtime.cleantimers 不同的是,上述函数会遍历处理器堆中的全部计时器,而不是只修改四叉堆顶部。

这会让人误以为 adjusttimers 在正常情况下总会遍历堆中的全部计时器,这和下面 调度器 部分的说法矛盾:

runtime.clearDeletedTimers 能够避免堆中出现大量长时间运行的计时器,该函数和 runtime.moveTimers 也是唯二会遍历计时器堆的函数。

实际上根据原代码,有退出遍历的条件:

if n := atomic.Xadd(&pp.adjustTimers, -1); int32(n) <= 0 {
  break loop
}
  1. 调度器 部分有一处表述不清:

runtime.checkTimers 函数的最后,如果当前 Goroutine 的处理器和传入的处理器相同,并且处理器中删除的计时器是堆中计时器的 1/4 以上,就会调用 runtime.clearDeletedTimers 删除处理器堆中的全部计时器。 runtime.clearDeletedTimers 能够避免堆中出现大量长时间运行的计时器

这里应该是 删除全部被标记为 timerDeleted 的计时器 ,因为 cleantimersadjusttimers 可能处理不到那些非常靠后的计时器,这些计时器的 timerDeleted 状态需要通过 clearDeletedTimers 来处理。

已修复,感谢

yanjinbin commented 4 years ago

如果超过 10ms 的时间没有轮询,调用 runtime.netpoll 轮询网络

笔误?看代码应该是不超过吧。

PS 真的看到这个就觉得头疼,让我想起Java的线程池实现,简直就是折磨,太绕了。 为什么这么设计(这么多种状态),没看懂!

draveness commented 4 years ago

如果超过 10ms 的时间没有轮询,调用 runtime.netpoll 轮询网络

笔误?看代码应该是不超过吧。

就是超过 10ms,你再看看

PS 真的看到这个就觉得头疼,让我想起Java的线程池实现,简直就是折磨,太绕了。 为什么这么设计(这么多种状态),没看懂!

每个状态都有存在的理由,再想想,哪个状态没看懂可以说一下

yanjinbin commented 4 years ago

@draveness

如果超过 10ms 的时间没有轮询,调用 runtime.netpoll 轮询网络

笔误?看代码应该是不超过吧。

就是超过 10ms,你再看看

PS 真的看到这个就觉得头疼,让我想起Java的线程池实现,简直就是折磨,太绕了。 为什么这么设计(这么多种状态),没看懂!

每个状态都有存在的理由,再想想,哪个状态没看懂可以说一下

嗯 我看错轮询时间10ms这个条件了。 对于计时器的状态机,主要是那些状态 有2个疑问 1为什么需要这些?2以及状态之间为什么要这么转换? 这是我纳闷的点

zzhzero commented 4 years ago

想知道这些图是用什么工具做的

draveness commented 4 years ago

想知道这些图是用什么工具做的

https://draveness.me/sketch-and-sketch/

qiluge commented 4 years ago

大佬,请教下:添加计时器的时候,addTimer() -> wakeNetPoller() -> 如果when小于轮询器的下次唤醒时间,则提前唤醒netpoller。 这个时候netpoller被唤醒了,是不是还得等到系统监控sysmon在循环里面检查netpoller才运行到期的计时器,而不会立即运行到期的计时器?

draveness commented 4 years ago

@qiluge 大佬,请教下:添加计时器的时候,addTimer() -> wakeNetPoller() -> 如果when小于轮询器的下次唤醒时间,则提前唤醒netpoller。 这个时候netpoller被唤醒了,是不是还得等到系统监控sysmon在循环里面检查netpoller才运行到期的计时器,而不会立即运行到期的计时器?

添加计时器的时候其实调用了文件描述符的 write,这时还没有唤醒计时器,但是不止是 sysmon 会运行计时器,所有调用 netpoll 的都会触发计时器。

qiluge commented 4 years ago

@qiluge 大佬,请教下:添加计时器的时候,addTimer() -> wakeNetPoller() -> 如果when小于轮询器的下次唤醒时间,则提前唤醒netpoller。 这个时候netpoller被唤醒了,是不是还得等到系统监控sysmon在循环里面检查netpoller才运行到期的计时器,而不会立即运行到期的计时器?

添加计时器的时候其实调用了文件描述符的 write,这时还没有唤醒计时器,但是不止是 sysmon 会运行计时器,所有调用 netpoll 的都会触发计时器。

也就是说netpoller会维持timer的状态,如果timer到期了,会在netpoll被调用时返回给调用方,由调用方去run timer。这里面有两个问题我不是很懂:1. netpoller怎么保存timer的状态,看addTimer调用的wakeNetPoller函数并没有将timer的信息放到netpoller里,那么是怎么通过大佬你所说的write实现这种机制的;2. 在timer到期和netpoll被调用之间有时间gap,这种gap是不是被允许的,就比如说是sysmon每隔10ms的一次循环。

draveness commented 4 years ago
  1. netpoller怎么保存timer的状态,看addTimer调用的wakeNetPoller函数并没有将timer的信息放到netpoller里,那么是怎么通过大佬你所说的write实现这种机制的;

看下 网络轮询器 一节

  1. 在timer到期和netpoll被调用之间有时间gap,这种gap是不是被允许的,就比如说是sysmon每隔10ms的一次循环。

是的,timer 没法做到精准

qiluge commented 4 years ago

@qiluge 大佬,请教下:添加计时器的时候,addTimer() -> wakeNetPoller() -> 如果when小于轮询器的下次唤醒时间,则提前唤醒netpoller。 这个时候netpoller被唤醒了,是不是还得等到系统监控sysmon在循环里面检查netpoller才运行到期的计时器,而不会立即运行到期的计时器?

添加计时器的时候其实调用了文件描述符的 write,这时还没有唤醒计时器,但是不止是 sysmon 会运行计时器,所有调用 netpoll 的都会触发计时器。

还是有几个问题:

  1. 添加计时器的时候是怎么调用文件描述符的write的?在addTimer和doaddTimer函数里没找着这部分逻辑,只有addtimer的wakenetpoller里会调用netpollBreak函数,才会向管道里面write数据;
  2. 当新添加的计时器小于netpoll的等待时间,则会立即激活netpoll,如果新的计时器不满足这个条件,请问这个计时器是怎么触发的?如果是被动的依赖调度器、findRunnable去调用netpoll监听文件描述符的事件,那么netpoller又是怎么监听计时器到期的呢?
draveness commented 4 years ago

还是有几个问题:

  1. 添加计时器的时候是怎么调用文件描述符的write的?在addTimer和doaddTimer函数里没找着这部分逻辑,只有addtimer的wakenetpoller里会调用netpollBreak函数,才会向管道里面write数据;

就是这里

  1. 当新添加的计时器小于netpoll的等待时间,则会立即激活netpoll,如果新的计时器不满足这个条件,请问这个计时器是怎么触发的?

被动依赖调度器、系统监控等组件

如果是被动的依赖调度器、findRunnable去调用netpoll监听文件描述符的事件,那么netpoller又是怎么监听计时器到期的呢?

netpoller 在上面这些组件主动调用时判断是不是到期

qiluge commented 4 years ago
  1. 调度的时候调用checkTimers()检查并运行到期的计时器;
  2. 系统监控也会调用checkTimers();
  3. 添加计时器的时候,会调用wakenetpoller(),如果计时器的触发时间小于netpoller的下一次轮询时间,则通过向netpollBreakWr里面写入数据,立即中断netpoll,形成事件,这样在netpoll()被调用的时候,这个事件会被返回,即timer对应的goroutine会被返回,调度器会运行这个timer;但是这种情况下,计时器的执行还是有延迟,因为必须等到netpoll()被调用的时候才会去runtimer()。

不知道我这么理解对不对?

draveness commented 4 years ago
  1. 调度的时候调用checkTimers()检查并运行到期的计时器;
  2. 系统监控也会调用checkTimers();
  3. 添加计时器的时候,会调用wakenetpoller(),如果计时器的触发时间小于netpoller的下一次轮询时间,则通过向netpollBreakWr里面写入数据,立即中断netpoll,形成事件,这样在netpoll()被调用的时候,这个事件会被返回,即timer对应的goroutine会被返回,调度器会运行这个timer;但是这种情况下,计时器的执行还是有延迟,因为必须等到netpoll()被调用的时候才会去runtimer()。

不知道我这么理解对不对?

没啥大问题,不过 Timer 的延迟是没有办法避免的,哪种触发的方法都会有延迟

yanjinbin commented 4 years ago

这篇 我看更新过好多次了 想看以前的版本文章 还能看的到么?

yanjinbin commented 4 years ago

@draveness

  1. 调度的时候调用checkTimers()检查并运行到期的计时器;
  2. 系统监控也会调用checkTimers();
  3. 添加计时器的时候,会调用wakenetpoller(),如果计时器的触发时间小于netpoller的下一次轮询时间,则通过向netpollBreakWr里面写入数据,立即中断netpoll,形成事件,这样在netpoll()被调用的时候,这个事件会被返回,即timer对应的goroutine会被返回,调度器会运行这个timer;但是这种情况下,计时器的执行还是有延迟,因为必须等到netpoll()被调用的时候才会去runtimer()。

不知道我这么理解对不对?

没啥大问题,不过 Timer 的延迟是没有办法避免的,哪种触发的方法都会有延迟

为什么这么说呢?好奇

draveness commented 4 years ago

这篇 我看更新过好多次了 想看以前的版本文章 还能看的到么?

看不到历史,只能看到最新的

@draveness

  1. 调度的时候调用checkTimers()检查并运行到期的计时器;
  2. 系统监控也会调用checkTimers();
  3. 添加计时器的时候,会调用wakenetpoller(),如果计时器的触发时间小于netpoller的下一次轮询时间,则通过向netpollBreakWr里面写入数据,立即中断netpoll,形成事件,这样在netpoll()被调用的时候,这个事件会被返回,即timer对应的goroutine会被返回,调度器会运行这个timer;但是这种情况下,计时器的执行还是有延迟,因为必须等到netpoll()被调用的时候才会去runtimer()。

不知道我这么理解对不对?

没啥大问题,不过 Timer 的延迟是没有办法避免的,哪种触发的方法都会有延迟

为什么这么说呢?好奇

因为 Timer 一定会在到时间之后触发,触发后经过一段代码才 ticker.C 才会收到通知,这时一定会晚于期望的通知时间

ningmonguo commented 3 years ago

https://draveness.me/golang/docs/part3-runtime/ch06-concurrency/golang-timer/#632-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84

这里有个疑问想请教一下,timer结构体里面没有带有timer的指针,是怎么实现堆的数据结构的呢? 之前的桶方式里边儿,timer 里面有 一个 []*timer 就很好理解。

draveness commented 3 years ago

https://draveness.me/golang/docs/part3-runtime/ch06-concurrency/golang-timer/#632-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84

这里有个疑问想请教一下,timer结构体里面没有带有timer的指针,是怎么实现堆的数据结构的呢? 之前的桶方式里边儿,timer 里面有 一个 []*timer 就很好理解。

数组也可以实现四叉堆,只要遵循特定的规则存储就可以了,例如 index=0 是堆顶 index=1-4 是第二层,依次类推

imzhongqi commented 3 years ago

如果当前有应该运行的计时器没有执行,可能因为存在无法被抢占的处理器,这时我们应该系统(启动?)新的线程计时器;


2021-01-02 UPDATES: 已修复

lun-zhang commented 3 years ago

请教一下大佬, 为啥不用一个OS计时器(准确来说每个P一个OS计时器)

  1. 然后用heap.top.when - now作为OS计时器的超时duration,
  2. 然后将OS计时器放到epoll中
  3. OS计时器fd到期会变成可读, 就能被epoll收集了
  4. 若新add的timer.when < heap.top.when, 就break epoll, 堆顶更换成这个更小的timer, 然后回到1, reset duration

我没看过linux源码不清楚OS提供的计时器是如何实现的(作者这方面应该熟悉些吧, 望赐教), 似乎像个管道, 超时后管道变的可读

这样时间精度就取决于OS计时器的精度了, (操作系统是否提供了更高的精度)

draveness commented 3 years ago

请教一下大佬, 为啥不用一个OS计时器(准确来说每个P一个OS计时器)

  1. 然后用heap.top.when - now作为OS计时器的超时duration,
  2. 然后将OS计时器放到epoll中
  3. OS计时器fd到期会变成可读, 就能被epoll收集了
  4. 若新add的timer.when < heap.top.when, 就break epoll, 堆顶更换成这个更小的timer, 然后回到1, reset duration

我没看过linux源码不清楚OS提供的计时器是如何实现的(作者这方面应该熟悉些吧, 望赐教), 似乎像个管道, 超时后管道变的可读

这样时间精度就取决于OS计时器的精度了, (操作系统是否提供了更高的精度)

这个定时器的精度主要还是因为系统的负载太高了,定时器处理不过来,想要在 ns 或者 us 级别处理上万的计时器是很困难的