如何用“非顺序”语义证明MT程序正确?

这可能是一个与语言无关的问题,但是在实践中我对C ++案例很感兴趣:用支持MT编程的C ++版本(即带有内存模型的现代C ++)编写的多线程程序如何被证明是正确的? / p>

在旧的C ++中,MT程序只是根据pthread语义编写的,并根据pthread规则进行了验证,从概念上讲,这很容易:正确使用基元并避免数据争用。

现在,C ++语言的语义是根据内存模型定义的,而不是根据原始步骤的顺序执行定义的。 (该标准还提到了“抽象机器”,但我再也听不懂它的意思了。)

如何用非顺序语义证明C ++程序正确?谁会想到一个没有依次执行原始步骤的程序

szv123_rier 回答:如何用“非顺序”语义证明MT程序正确?

与C ++内存模型之前的pthreads相比,C ++内存模型“在概念上更容易”。内存模型与pthread交互之前的C ++宽松地指定,并且对该规范的合理解释允许编译器“引入”数据竞争,因此很难(如果可能的话)很难推理或证明MT算法的正确性。带有pthread的旧C ++的上下文。

这个问题似乎有一个基本的误解,因为C ++从未定义为原始步骤的顺序执行。表达式评估之间总是存在部分排序的情况。除非有限制,否则允许编译器来回移动这些表达式。内存模型的引入并没有改变。内存模型为执行的单独线程之间的评估引入了部分顺序。

“正确使用原语并避免数据争用”的建议仍然适用,但是C ++内存模型更严格,更精确地限制了原语与语言其余部分之间的交互,从而可以进行更精确的推理。

在实践中,要证明两种情况的正确性都不容易。大多数程序都没有证明没有数据争用。人们试图尽可能多地封装任何同步,以便对较小的组件进行推理,其中一些可以证明是正确的。人们使用诸如地址清除器和线程清除器之类的工具来捕获数据争用。

在数据竞赛中,POSIX says

  

应用程序应确保限制一个以上控制线程(线程或进程)对任何内存位置的访问,以使任何控制线程都无法读取或修改一个内存位置,而另一个控制线程可以对其进行修改。使用同步线程执行并与其他线程同步内存的函数来限制这种访问。...应用程序可能允许多个控制线程同时读取内存位置。

在数据竞赛中,C++ says

  

如果程序包含两个潜在并发 冲突动作,则该程序的执行包含数据争用,其中至少有一个不是原子动作,除了以下所述的信号处理程序的特殊情况外,都没有先发生。任何此类数据争用都会导致不确定的行为。

C ++定义了更多术语,并尝试更加精确。其要点是,两种禁止数据竞争,两者都被定义为冲突访问,而没有使用同步原语。

POSIX说pthread函数相对于其他线程同步内存。这是未指定的。可以合理地解释为:(1)编译器无法在此类函数调用之间移动内存访问,并且(2)在一个线程中调用此类函数之后,从该线程到内存的先前操作将在该线程之后对另一个线程可见。调用这样的函数。这是一种常见的解释,可以通过将函数视为不透明并可能破坏所有内存来轻松实现。

作为此宽松规范存在的问题的一个示例,仍然允许编译器引入或删除内存访问(例如通过寄存器提升和溢出),并进行必要的更大访问(例如,触摸结构中的相邻字段)。因此,编译器可以完全正确地“引入”未直接在源代码中编写的数据竞争。 C ++ 11内存模型阻止了这样做。

C++ says,with regard to mutex lock

  

同步:对同一对象的先前的unlock()操作应与此操作同步。

因此C ++更加具体。您必须锁定和解锁同一个互斥锁才能进行同步。但是,鉴于此,C++ says可以在新储物柜看到解锁之前的操作:

  

如果...存在评估B和C,使得A在B之前进行排序,B仅在C之前进行,而C在D之前进行排序,则A在评估D之前强烈发生。 [注意:非正式地,如果A强烈地发生在B之前,那么在所有情况下A似乎都在B之前被评估。强烈发生在排除消耗操作之前。 —尾注]

(使用B =解锁,C =锁定,因为B与C同步,所以B仅仅发生在C之前。在先序列是在单个执行线程中的概念,因此,例如,一个完整表达式在下一个序列之前进行排序。)

因此,如果您将自己限制在pthread中存在的原语(锁,条件变量等)种类以及pthread提供的保证类型(顺序一致性)下,C ++应该不会给您带来任何惊喜。实际上,它消除了一些意外,增加了精度,并且更适合于正确性证明。

对于任何对此主题感兴趣的人,这篇文章Foundations of the C++ Concurrency Memory Model是一篇很棒的说明性文章,内容涉及当时的现状问题以及在C ++ 11内存模型中进行修复的选择。


为了清楚地说明问题的前提存在缺陷,使用记忆模型进行推理更容易,并添加了对Boehm论文的引用,这也构成了一些论述。

本文链接:https://www.f2er.com/3155070.html

大家都在问