知识卡片
无锁队列用哨兵简化边界
课程Michael–Scott队列以一个不代表有效元素的头部哨兵开始,head和tail初始同指它。入队先CAS链接新节点,再推进tail;出队从head.next取值并CAS推进head。头节点的角色随出队推进,避免为空与首元素设计完全不同的更新路径。
结构图: 类图;关系为组合、引用或隐式实现,不表示Go继承;图中保留所示关键方法,省略无助于当前关系的成员。
classDiagram
class LKQueue {
-head unsafe.Pointer
-tail unsafe.Pointer
+Enqueue(v interface{})
+Dequeue() interface{}
}
class node {
-value interface{}
-next unsafe.Pointer
}
LKQueue o-- node : 头尾指向链表节点
node --> node : next链接
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 12-atomic:要保证原子操作,一定要使用这几种方法 · 查看原书依据
这个lock-free的实现使用了一个辅助头指针(head),头指针不包含有意义的数据,只是一个辅助的节点,这样的话,出队入队中的节点会更简单。
参考来源
- 位置:《Go并发编程实战 (汪明)》第12章《12-atomic:要保证原子操作,一定要使用这几种方法 / 使用atomic实现Lock-Free queue》(来源项目book-sources;源文件:../../../../book-sources/extracted/Go并发编程实战 (汪明)/_epub-src/text/part0014_split_011.html,spine 126)
- 结论依据:原文以“这个lock-free的实现使用了”定位相关定义、实现或具体案例;本卡据此解释无锁队列用哨兵简化边界,对历史实现和示例限制另作明确区分。
- 原始内容:这个lock-free的实现使用了一个辅助头指针(head),头指针不包含有意义的数据,只是一个辅助的节点,这样的话,出队入队中的节点会更简单。