用 proof by contradiction 证明 atomic ops 程序行为是否正确?
这个反证法的核心推理是正确的。在两个线程正常创建并按所示代码执行的前提下,#3 处的循环无法通过读到 true 退出。要使证明严谨,需要明确证明中的 #3 指使循环退出的那一次 load,并补全 sequenced-before、synchronizes-with 和 happens-before 之间的关系。
明确各个操作的含义
将相关操作记为:
Rv:#1 对val的 relaxed load。Wf:#2 对flag的 release store。Rf:假设存在的、使 #3 循环退出的那一次 acquire load。Wv:#4 对val的 relaxed store。
需要区分 #3 的代码位置和具体的 load。循环可能执行多次 load,证明用的是返回 true 的那一次。
从循环退出推导读取来源
假设循环退出,那么 Rf 返回 true。
flag 的初始值为 false,程序中唯一写入 true 的操作是 Wf,所以:
循环退出 ⟾ Rf reads from Wf
因此,假设的执行中必须存在 Wf。Wf 位于 if 分支内,只有 Rv 返回 1 才会执行。
val 的初始值为 0,唯一写入 1 的操作是 Wv,因此:
循环退出 ⟾ Rv reads from Wv
这里是在检查同一个假设执行中的操作是否相容,并未预先假定跨线程操作存在某种全局时间顺序。
补全 happens-before 推导
同一线程中的语句顺序给出:
Rv sequenced-before Wf
Rf sequenced-before Wv
在假设的执行中,Rf 从 Wf 读取。Wf 是 release store,Rf 是对同一个 atomic object 的 acquire load,因此:
Wf synchronizes-with Rf
这一同步关系由 C++ 工作草案的 [atomics.order] 规则规定。
结合 sequenced-before、synchronizes-with 与传递性,可以得到:
Rv happens-before Wf
Wf happens-before Rf
Rf happens-before Wv
因此:Rv happens-before Wv
[intro.races] 对 atomic load 的取值要求是:若读取操作 B 从修改操作 A 取得值,则 B 不得 happens-before A。因此:
Rv happens-before Wv ⟾ ¬( Rv reads from Wv )
这一限制也适用于 relaxed load,memory_order::relaxed 不会取消它。规则见 [intro.races]。
同一个假设由此同时要求:
Rv reads from Wv
¬( Rv reads from Wv )
于是:
循环退出 ⟾ ¬( Rv reads from Wv ) ∧ ( Rv reads from Wv ) ⟾ False
所以,使循环退出的 Rf 不存在。
代码中的哪些顺序不可省略
原程序的相关部分是:
std::jthread t1([&](){
if(val.load(std::memory_order::relaxed) == 1){ // #1
flag.store(true, std::memory_order::release); // #2
}
});
std::jthread t2([&](){
while(!flag.load(std::memory_order::acquire)); // #3
val.store(1,std::memory_order::relaxed); // #4
});
#1 在 #2 之前,退出循环的 #3 在 #4 之前。这两段 sequenced-before 关系,加上假设成立时 #2 与 #3 之间的同步关系,共同推出 #1 happens-before #4。
原推理中的“#3 reads from #2 意味着 #2 happens-before #3”需要注明 release/acquire 前提。一般情况下,单独的 reads from 关系不足以建立 happens-before。也不能因为 #1 reads from #4,就直接声称 #4 happens-before #1。
对程序运行结果的理解
这个证明排除了循环正常退出以及 #4 被执行的可能。#1 若执行,只能读取初始值 0,所以 #2 不会执行。
循环中不断进行 atomic load,不会仅因无限循环而违反 forward progress 要求;atomic 操作属于相关规则认可的执行步骤。见 [intro.progress]。
std::jthread 的析构函数会在对象仍然 joinable 时调用 request_stop(),随后调用 join()。示例中的线程函数没有检查停止请求,因此该请求无法让循环退出;正常析构流程会等待 t2 完成。见 [thread.jthread.cons]。
引用标准条款时,建议同时注明所用标准或草案版本,避免只靠可能随版本变化的段落编号定位规则。
备注:内容仅供参考。
