Data Race Free 的前世今生

Published: 07 Mar 2014 Category:

Data Race Free 的前世今生

Data Race Free 是多线程程序是非常重要的概念,因为Java 和 C++的内存模型都是基于 Data Race Free 的,这篇文章将介绍这个概念的由来,另一篇文章《Data Race Free的理解》介绍它的主要思想。

事情要追溯到遥远的1979年, Lamport 在他的著名论文 How to make a multiprocessor computer that correctly executes multiprocess programs 中提出了今后在内存模型领域被广泛使用的概念 :sequential consistency,即顺序一致性。这篇文章告诉我们,你要做一台多处理器的计算机,需要满足什么条件,才能保证程序的正确性。当然,这里的程序跑在不同处理器上,共享同一块内存。虽然现在不说多处理器了,都说多核,多线程,但是问题的本质是没有变的。就是多个执行单元一起完成一个任务,并且通过共享存储单元的方式通信,在这种情况下,底层的系统需要提供什么样的支持,才能保证计算的结果和程序员的预期是一样的。

7年后的1986年,Dubois, Scheurich , Briggs 三人在论文 Memory access buffering in multiprocessors 中对 Lamport 的工作进行了扩展,他们提出了一种框架,用于分析共享内存的多处理器系统中的一致性问题。文中引入了三个 states,以此为基础提出了strong ordering的概念,并说明了他与Lamport提出的sequential consistency是一致的。但是,strong ordering对内存操作的限制太强了,对系统性能是一个阻碍,所以,他们又提出了 weak ordering的概念,以此提高系统性能。 满足weak ordering的系统并不是 sequential consistency的,程序员们需要自己去声明同步变量,以保证程序的正确性。

又过了4年,到了1990年,Adve大妈出手了,大妈现在是内存模型这个领域的权威,Java和C++内存模型的确立都有大妈的功劳,而Java和C++内存模型中相当重要的Data Race Free 概念就是Adve大妈在这一年提出的。

在这篇名为 Weak ordering—a new definition的文章中,Adve对Dubois等人提出的Weak Ordering进行了新的定义,并做出了一些修改以便进一步提高系统的性能。 新的定义出于这样一种想法,程序员习惯使用 sequential consistency来推断程序的运行结果,而底层的系统要想取得更高的性能,又不能使用sequential consistency内存模型来运行程序。那么

如何使得程序员可以使用sequential consistency推断程序结果,底层的实现又可以进行种种优化呢?

解决方案是:对程序本身进行足够的同步。

这种内存模型保证:如果你的程序进行了足够的同步,那么在我的weak oerding内存模型上运行,我可以保证结果和你在sequential consistency模型下运行的结果一样。

这样一来,程序员保证程序正确同步,就可以使用sequential consistency推断程序结果,而底层又可以灵活地进行各种优化,提高系统性能。

这里有一个关键问题:

什么叫“足够的同步”

Adve提出了Data Race Free的概念,也就是说,你的程序要是满足Data Race Free的条件了,你的同步就足够了,“足够”的意思就是说,这程序在weak ordering上跑和在sequential consistency上跑,结果是一样一样的~

Adve对weak ordering给出的新定义是:

Hardware is weakly ordered with respect to a synchronization model if and only if it appears sequentially consistent to all software that obey the synchronization model.

这里的synchronization model的一种实现方式,就是 Data Race Free。

Data Race Free 后来成为了 Java 和 C++ 内存模型的基础。

Java 的内存模型最早出现在1995年,但是自1997年起,这一内存模型被发现了许多严重的错误和缺陷,它阻碍了很多优化措施,对程序的安全性也没有足够的保证。2001年JSR 133被确立下来,由William Pugh领导,专家组的成员包括了Adve,Doug Lea, William Pugh等。2004年,JSR 133最终版本发布。2005年,Manson Jeremy, William Pugh, 和 Sarita V. Adve 一同发表了论文 The Java memory model,描述了最新的Java内存模型,这一内存模型在Java 5.0中引入,一直沿用至今。

Java 内存模型的关键是:如果多线程程序满足Data Race Free,那么内存模型保证程序执行结果和sequentially consistent模型下一样。另外,Java 内存模型的复杂之处还在于,为了保证程序的安全性,即使多线程程序不满足Data Race Free,我们也要对它进行一定程度的限制,这种限制必须恰到好处,太强会阻碍合理的优化,太弱保证不了程序的安全性。

三年后的2008年,Hans-J. Boehm 和 Sarita V. Adve 一同发表了文章 Foundations of the C++ concurrency memory model,描述了C++内存模型的基础,这一内存模型为C++ 11标准中的线程提供了明确的语义。

C++内存模型与的关键在于:如果多线程程序满足Data Race Free,那么内存模型保证程序执行结果和sequentially consistent模型下一样。与Java内存模型不同,对于那些不满足 Data Race Free的多线程程序,C++内存模型不对其结果提供任何保证。另外,C++内存模型提供了一些特性用以实现不同的内存模型。

comments powered by Disqus