PAYATHON 2026

用 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]。

引用标准条款时,建议同时注明所用标准或草案版本,避免只靠可能随版本变化的段落编号定位规则。

备注:内容仅供参考。