知识卡片
矢量时钟判断先后
有 n 个协程,就有 n 个逻辑时钟。矢量时钟是把这些时钟合成的数组,记下每个协程自己知道的事件进度。若 A 的每一维都不大于 B,并且至少有一维更小,可以判断 A 先于 B。若两边都有一维比对方大,就没有可证实的先后。
示例:A 解锁时自己的向量是 (1, 0)。B 加锁后看见 A 已经放开锁,把自己对 A 的记录更新上去,变成 (1, 1)。比较这两个向量:1≤1,并且 0,所以 (1, 0) 先于 (1, 1),这次解锁先于这次加锁。争用检测用这个关系判断两次冲突访问之间有没有 happens-before。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 并发控制 · 查看原书依据
矢量时钟(Vector Clock)技术[6]用来观察事件之间happened-before的顺序,该技术在分布式系统中使用广泛,用于检测和确定分布式系统中事件的因果关系,也可以用于数据争用的探测。在Go程序中,有n个协程就会有对应的n个逻辑时钟,而矢量时钟是
参考来源
- 位置:《Go语言底层原理剖析》第17章《并发控制》17.3.3节《race工具原理》;`_epub-src/OEBPS/Text/0021.xhtml`
- 结论依据:原文把每个协程的逻辑时钟合成向量,并以加锁后观察到另一协程的进度解释 happens-before;卡片抽取偏序判断原则,避免照搬原文末尾未给定 X 的含糊推论。正文里的 (1, 0) 与 (1, 1) 是按这个“加锁后看见对方已释放”做的补充示例,不是原书给出的向量数值。
- 原始内容:矢量时钟(Vector Clock)技术 [6] 用来观察事件之间happened-before的顺序……在Go程序中,有 n 个协程就会有对应的 n 个逻辑时钟,而矢量时钟是所有这些逻辑时钟组成的数组……当加锁后,协程B能够观察到协程A已经释放了锁,其会更新内部对于协程A的逻辑时钟。