知识卡片
读者遍历依赖旧链不变
插入先把新节点链向旧表头,再原子发布新表头;读者取得某个表头后可继续沿原链遍历,不受前面新增节点影响。删除则复制目标之前的前缀,把副本接到目标后继,再发布新表头,让早期读者保有旧视图。无锁读取依赖旧结构不被原地破坏,原子换头本身不保护任意节点修改。
结构图:
flowchart LR
O[旧表头A] --> B[旧节点B]
B --> C[旧节点C]
N[新表头A副本] --> C
R[早期读者] --> O
H[发布后的表头] --> N
Note[删除B时复制前缀A
旧链留给既有读者]
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 05 同步
原书出处 · 1 处
- · 查看原书依据
新表头后面的原有单链表中的每个键-元素对,以及它们的链接关系都会原封不动。如此一来,键-元素对获取操作无论何时都可以原子地获取到一个表头,并可以并发安全地向表尾遍历。
参考来源
- 位置:《Go并发编程实战(第2版)》第05章《同步》(来源项目book-sources:extracted/Go并发编程实战(第2版)/_epub-src/OEBPS/text00000_split_009.html;归一字符[46439,46522))
- 结论依据:原文图5-2插入和图5-3删除均已查看,解释发布前构造与旧链保留的不变量。
- 原始内容:新表头后面的原有单链表中的每个键-元素对,以及它们的链接关系都会原封不动。如此一来,键-元素对获取操作无论何时都可以原子地获取到一个表头,并可以并发安全地向表尾遍历。