并行程式設計之多線程共享非volatile變量，會不會可能導緻線程while死循環

大家都知道線程之間共享變量要用volatile關鍵字。但是，如果不用volatile來辨別，會不會導緻線程死循環？比如下面的僞代碼：

線程1,線程2同時運作，線程2退出之後，線程1會不會有可能因為緩存等原因，一直死循環？

直接上代碼：

在main函數裡啟動了一個線程thread1，thread1會等待一段時間後修改vvv = -1，然後當vvv > 0時，主線程會一直while循環等待。

理想的情況下是這樣的：

主線程死循環等待，2秒之後thread1輸出"sss"，thread1退出，主線程退出。

儲存為thread-study.c 檔案，直接用gcc -o3 優化：

再執行 ./a.out，可以發現控制台輸出“sss”之後，會一直等待，再檢視cpu使用率，一個核跑滿了，說明主線程在死循環。

貌似就像上面所的，主線程因為緩存的原因，導緻讀取的 vvv 變量一直是舊的，進而死循環了。

但是否真的如此？

經過測試，除了o0級别（即完全不優化）不死循環外，o1，o2，o3級别，都會死循環。

再檢視下o3級别的彙編代碼（用 gcc -s thread-study.c 生成），main函數部分是這樣的：

為了便于檢視，手動加了注釋。

在l6标号那裡，比較奇怪：

.l6:

jmp .l6

這裡明顯就是死循環，根本沒有去嘗試讀取xxx的值。那麼l4那個标号又是怎麼回事？l4的代碼是讀取 vvv 變量再判斷。但是它為什麼沒有在循環裡？

再用gdb從彙編調試下，發現主線程的确是執行了死循環：

一個jmp指令原地跳轉，自然是一個死循環，正對應上面彙編代碼的l6部分。

相當于生成了這樣的代碼：

可見gcc生成的代碼有問題，它根本就沒有生成正确的彙編代碼。盡管這種優化是符合規範的，但我個人比較反感這種嚴重違反直覺的優化。

那麼我們的問題還沒有解決，接下來修改彙編代碼，讓它真正的像這樣所預期的那樣工作。隻要簡單地把l6的jmp跳轉到l4上：

這個才我們真正預期的代碼。

再測試下這個修改過後的代碼：

執行2秒之後，退出了。

說明，主線程并沒有一直讀取到舊的共享變量的值，符合預期。

給" vvv "變量加上volatile，即：

重新編繹後，再跑下，發現正常了，2秒後程序退出。

檢視下彙編代碼，是這樣的：

這段彙編代碼符合預期。

但是這裡還是有點不對，volatile的特殊性在哪裡？生成的彙編沒有什麼特别的指令，那它是如何“防止”了線程不緩存共享變量的？

網上流傳的一種說法是使用volatile關鍵字之後，讀取資料一定從記憶體中讀取。

這種說法既是對的，也是錯的。volatile關鍵字防止了編繹器優化，是以對于變量不會被放到寄存器裡，或者被優化掉。但是volatile并不能防止cpu從cache中讀取資料。

cpu内部有寄存器，有各級cache，l1，l2，l3。我們來考慮下到底怎樣才會出現線程共享變量被放到cpu的寄存器或者各級cache的情況。

volatile阻止了編繹器把變量放到寄存器裡，那麼對線程共享變量的讀取即直接的記憶體通路。

cpu cache放的正是記憶體的資料，像

movl _zl3vvv(%rip), %eax

這樣的指令，是會先從cpu cache裡查找，如果沒有的話，再通過總線到記憶體裡讀取。

而現代cpu有多核，通常來說每個核的l1, l2 cache是不共享的，l3 cache是共享的。

那麼問題就變成了：線程a修改了cache中的内容，線程b是否會一直讀取到的都是舊資料？

既然cache資料會不一緻，那麼自然要有個機制，讓它們之間重回一緻。經典的cache一緻性協定是mesi協定。

mesi協定是使用的是write back政策，即當一個核内的cache更新了，它隻修改自己核内部的，并不是同步修改到其它核上。

在mesi協定裡，每行cache line可以有4種狀态：

modified     該cache line資料被修改，和記憶體中的不一緻，資料隻存儲在本cache line裡。

exclusive   該cache line資料和記憶體中的一緻，資料隻存在本cache line裡。

shared       該cache line資料和記憶體中的一緻，資料存在多個cache line裡，随時會變成invalid狀态。

invalid         該cache line資料無效（即不會再使用）

mesi協定裡，狀态的轉換比較複雜，但是都和人的直覺一緻。對于我們研究的問題而言，隻需要知道：

當是shared狀态的時，修改cache line的内容前，要先通過request for ownership (rfo)的方式廣播通知其它核，把cache line置為invalid。

當是modified狀态時，cache控制器會(snoop)攔截其它核對該cache line對應的記憶體位址的通路，在回應回插入目前cache line的資料。并把本cache line的内容回寫到記憶體裡，狀态改為shared。

是以，并不會存在一個核内的cache資料修改了，另一個核沒有感覺的情況。

即不會出現線程a修改了cache中的内容，線程b一直讀取到的都是舊資料的情況。考慮到cpu内部通迅都是很快的，本人估計線程a修改了共享變量，線程b讀取到新值的時間應該是納秒級之内。

現代很多cpu都有亂序執行能力，從上面加了volatile之後生成的彙編代碼來看，沒有什麼特别的地方。那麼它對于cpu亂序執行也是無能為力的。比如：

對于這兩個線程，jobb()有可能比joba()先執行！

因為thread1裡，可能會因為cpu亂序執行，先執行了flag = 1，再執行joba()。

那麼如何防止這種情況？這個麻煩是cpu搞出來的，自然也是cpu提供的解決辦法。

gcc内置了一些原子記憶體通路的函數，如：

http://gcc.gnu.org/onlinedocs/gcc-4.6.2/gcc/atomic-builtins.html

type __sync_fetch_and_add (type *ptr, type value, ...)

type __sync_fetch_and_sub (type *ptr, type value, ...)

type __sync_fetch_and_or (type *ptr, type value, ...)

type __sync_fetch_and_and (type *ptr, type value, ...)

type __sync_fetch_and_xor (type *ptr, type value, ...)

type __sync_fetch_and_nand (type *ptr, type value, ...)

這些函數實際即隐含了memory barrier。

比如為之前讨論的代碼加上memory barrier：

再檢視下生成的彙編代碼：

可以看到，加多了一條 lock addl 的指令。

這個lock，實際上是一個指令字首，它保證了目前操作的cache line是處于exclusive狀态，而且保證了指令的順序性。這個指令有可能是通過鎖總線來實作的，但是如果總線已經被鎖住了，那麼隻會消耗字尾指令的時間。

實際上java裡的volatile就是在前面加了一個lock add指令實作的。這個有空再寫。

抛開上面的讨論，其實有些場景可以不使用volatile，比如這種随機擷取資源的代碼：

這樣的代碼pos是非volatile，但多線程調用getresource()函數完全沒有問題。

為什麼c11和c++11不把volatile更新為java/c#那樣的語義？我猜可能是所謂的“相容性”問題。。蛋疼

c++11提供了atomic相關的操作，語義和java裡的volatile差不多。但是c11仍然沒有什麼好的辦法，貌似隻能用gcc内置函數，或者寫一些類似的彙編的宏了。

http://en.cppreference.com/w/cpp/atomic

gcc優化的一些東東

其實在讨論的代碼裡，如果while循環裡多一些代碼，gcc可能就分辨不出是否能優化了

比如，在大部分語言裡（特别是動态語言），第一份代碼要比第二份代碼要高效得多。

回到最初的問題：多線程共享非volatile變量，會不會可能導緻線程while死循環？

其實這事要看很多别的東西的臉色。。編繹器的，cpu的，語言規範的。。

對于沒有被編繹器優化掉的代碼，cpu的cache一緻性協定（典型mesi）保證了，不會出現死循環的情況。這個不是volatile的功勞，這個隻是cpu内部的正常機制而已。

對于多線程同步程式，要小心地在合适的地方加上記憶體屏障(memory barrier)。

http://en.wikipedia.org/wiki/volatile_variable  

http://en.wikipedia.org/wiki/mesi

http://en.wikipedia.org/wiki/write-back#write-back

http://en.wikipedia.org/wiki/bus_snooping

http://en.wikipedia.org/wiki/cpu_cache#multi-level_caches

http://blog.jobbole.com/36263/     每個程式員都應該了解的 cpu 高速緩存

http://stackoverflow.com/questions/4232660/which-is-a-better-write-barrier-on-x86-lockaddl-or-xchgl

http://stackoverflow.com/questions/8891067/what-does-the-lock-instruction-mean-in-x86-assembly