Blog
网站首页
CAS和Pure load的可观测集合对比
CAS和Pure load的可观测集合对比
2026-03-18 14:52
2026-03-19 13:11
作者:
xmh0511
提交
给定程序 ````rust static A:AtomicI32 = AtomicI32::new(0); // thread 1: A.store(1,Relaxed); // #0 // #1 if A.load(Relaxed)==1 { // 对比 A.compare_exchange(1,1,Relaxed,Relaxed).is_ok() //balabla } // thread 2: A.swap(2,Relaxed); // #2 ```` ### #1为Pure load: 由于Pure load不产生对原子变量的修改，因此不会导致`A`的modification order发生变化，对于任意情况，`A`的modification order总是$$W_{0} < W_{swap}$$. 记`#1`处的Load操作为`L`。 1.`L`时间上先于$$W_{swap}$$ $$ L \ {<}_{\text{\scriptsize{timing}}} \ W_{swap}$$ `L`读 $$W_\text{0}$$ 则符合时序结果（按时序）。 `L`读$$W_{swap}$$ 则读取未来值 2.$$W_{swap}$$时间上先于`L` $$ W_{swap} \ {<}_{\text{\scriptsize{timing}}} \ L$$ `L`读$$W_\text{0}$$ 则读取到旧值 `L`读$$W_\text{swap}$$ 则符合时序结果（按时序）。 ### #1为CAS操作时： 由于CAS比较成功则为RMW操作，即对`A`有修改操作，会导致`A`的modification order变化，而如果CAS比较失败则为pure load操作，与上面pure load相同，不会修改`A`. 因此程序对应的`A`的modification order是不同的。而又由于RMW的读必须读取在modification order中它写入元素之前最后的modification, 并且比较的值是`1`此处只能是$$W_{0}$$。 记`#1`处的CAS操作为 $$W_{cas}$$ 因此讨论的情况为： MO: $$W_{0} \ {<} \ W_{cas} < W{swap}$$ （限定了`Wcas`只能读`W0`） 1.`W_cas` 时间上先于 `W_swap` $$ W_{cas} \ {<}_{\text{\scriptsize{timing}}} \ W_{swap}$$ `Wcas`读`W0`则符合时序结果（按时序）。 2.`W_swap`时间上先于`W_cas` $$ W_{swap} \ {<}_{\text{\scriptsize{timing}}} \ W_{cas}$$ `Wcas`读`W0`则读取到旧值 MO: $$W_{0} \ {<} \ W{swap}$$ （限定了`Wcas`只能读`Wswap`,因为比较失败） 1.`W_cas` 时间上先于 `W_swap` $$ W_{cas} \ {<}_{\text{\scriptsize{timing}}} \ W_{swap}$$ `Wcas`读`Wswap` 则读取未来值 2.`W_swap`时间上先于`W_cas` $$ W_{swap} \ {<}_{\text{\scriptsize{timing}}} \ W_{cas}$$ `Wcas`读`Wswap` 则符合时序结果（按时序）。 **** ### 统计 | | `#1`时间上先于`#2` | `#2`时间上先于`#1` | | ------------ | ------------ | ------------ | | `L` | 读`W0`(按时序) MO:`W0 < Wswap`| 读`W0`(旧值) MO:`W0 < Wswap` | |`L`|读`Wswap`(未来值) MO:`W0 < Wswap`| 读`Wswap`(按时序) MO:`W0 < Wswap` | | `WCAS` | 读`W0`(按时序) MO:`W0 < WCAS < Wswap` | 读`W0`(旧值) MO:`W0 < WCAS < Wswap` | |`WCAS`|读`Wswap`(未来值) MO:`W0 < Wswap`|读`Wswap`(按时序) MO:`W0 < Wswap` | 从统计的表格可知，如果能够通过某种实现手段观测到`#1`和`#2`在时序上的发生顺序，以及对应的`#1`操作读取值的情况，可观测集合是完全等价的。 *** 这里有个[stackoverflow](https://stackoverflow.com/questions/79838504/should-we-judge-whether-programs-are-functionally-equivalent-based-on-identical)引申问题, 问题是在相同的modification order下，CAS操作是不是比pure load更能读到最新值？ 其实，在这个问题中，通过限定相同的MO来对比可观测行为是不公平的比较，因为如上所述，对于pure load来说，其操作本身不参与MO, 而CAS作为RMW操作一定会导致MO发生变化。如果说前提假设是在pure load的操作所对应的MO下，讨论CAS操作的可观测行为，这个前提本身就限定了CAS必须是Pure load操作，而根据CAS定义，只有当CAS发生比较值不相等时，才会导致它是Pure load。这就暗含了，CAS比较一定不相等。具体来说，给定pure load下的MO: $$W_0 \ {<} W_{swap}$$ 对于CAS操作，这个MO对应的CAS操作一定是比较失败的，只有失败的情况下CAS才不会产生modification。即蕴含，CAS失败和这个MO互为充分必要，即CAS必然读`Wswap`，否则CAS读取`W0`, 比较必然成功并且立即在W0后有modification，因为CAS不是weak compare，所以不存在spurious failure。非weak的CAS，如果比较失败那么值一定是不等的，在这个程序中，结果不等就蕴含读到的是`Wswap`。而weak的CAS,可以在即使值相等的情况下，依然返回比较结果失败，因此weak版的读允许返回`W0`的值。 举个例子，A和B两个比赛猜硬币正反面，A无论是赢还是输，都会在每次的计分卡片上标记`输`或`赢`，而B赢会标记`赢`输会标记`输*`。当比赛结束时，裁判说我只看双方卡片中标记了`输`或`赢`的卡片（这就排除了B输的情况），然后统计谁100%赢，然后声称B100%赢因为没标记`输`的卡片。 这种比较是一种幸存者偏差，因为前置的条件已经对B的部分结果进行过滤了，然后用过滤后的结果去解释B所有的可能性，这就是不公平比较的来源。