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++內存模型提供了一些特性用以實現不同的內存模型。