當(dāng)涉及到共享數(shù)據(jù)時(shí)，問題很可能是因?yàn)楣蚕頂?shù)據(jù)修改所導(dǎo)致。如果共享數(shù)據(jù)是只讀的，那么只讀操作不會(huì)影響到數(shù)據(jù)，更不會(huì)涉及對數(shù)據(jù)的修改，所以所有線程都會(huì)獲得同樣的數(shù)據(jù)。但是，當(dāng)一個(gè)或多個(gè)線程要修改共享數(shù)據(jù)時(shí)，就會(huì)產(chǎn)生很多麻煩。這種情況下，就必須小心謹(jǐn)慎，才能確保一切所有線程都工作正常。

不變量(invariants)的概念對程序員們編寫的程序會(huì)有一定的幫助——對于特殊結(jié)構(gòu)體的描述；比如，“變量包含列表中的項(xiàng)數(shù)”。不變量通常會(huì)在一次更新中被破壞，特別是比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，或者一次更新就要改動(dòng)很大的數(shù)據(jù)結(jié)構(gòu)。

雙鏈表中每個(gè)節(jié)點(diǎn)都有一個(gè)指針指向列表中下一個(gè)節(jié)點(diǎn)，還有一個(gè)指針指向前一個(gè)節(jié)點(diǎn)。其中不變量就是節(jié)點(diǎn)A中指向“下一個(gè)”節(jié)點(diǎn)B的指針，還有前向指針。為了從列表中刪除一個(gè)節(jié)點(diǎn)，其兩邊節(jié)點(diǎn)的指針都需要更新。當(dāng)其中一邊更新完成時(shí)，不變量就被破壞了，直到另一邊也完成更新；在兩邊都完成更新后，不變量就又穩(wěn)定了。

從一個(gè)列表中刪除一個(gè)節(jié)點(diǎn)的步驟如下(如圖3.1)

1. 找到要?jiǎng)h除的節(jié)點(diǎn)N
   
2. 更新前一個(gè)節(jié)點(diǎn)指向N的指針，讓這個(gè)指針指向N的下一個(gè)節(jié)點(diǎn)
   
3. 更新后一個(gè)節(jié)點(diǎn)指向N的指針，讓這個(gè)指正指向N的前一個(gè)節(jié)點(diǎn)
   
4. 刪除節(jié)點(diǎn)N
   

http://wiki.jikexueyuan.com/project/cplusplus-concurrency-action/images/chapter3/3-1.png" alt="" />

圖3.1 從一個(gè)雙鏈表中刪除一個(gè)節(jié)點(diǎn)

圖中b和c在相同的方向上指向和原來已經(jīng)不一致了，這就破壞了不變量。

線程間潛在問題就是修改共享數(shù)據(jù)，致使不變量遭到破壞。當(dāng)不做些事來確保在這個(gè)過程中不會(huì)有其他線程進(jìn)行訪問的話，可能就有線程訪問到剛剛刪除一邊的節(jié)點(diǎn)；這樣的話，線程就讀取到要?jiǎng)h除節(jié)點(diǎn)的數(shù)據(jù)(因?yàn)橹挥幸贿叺倪B接被修改，如圖3.1(b))，所以不變量就被破壞。破壞不變量的后果是多樣，當(dāng)其他線程按從左往右的順序來訪問列表時(shí)，它將跳過被刪除的節(jié)點(diǎn)。在一方面，如有第二個(gè)線程嘗試刪除圖中右邊的節(jié)點(diǎn)，那么可能會(huì)讓數(shù)據(jù)結(jié)構(gòu)產(chǎn)生永久性的損壞，使程序崩潰。無論結(jié)果如何，都是并行代碼常見錯(cuò)誤：條件競爭。

3.1.1 條件競爭

假設(shè)你去電影院買電影票。如果去的是一家大電影院，有很多收銀臺，很多人就可以在同一時(shí)間買電影票。當(dāng)另一個(gè)收銀臺也在賣你想看的這場電影的電影票，那么你的座位選擇范圍就取決于在之前已預(yù)定的座位。當(dāng)只有少量的座位剩下，這就意味著，這可能是一場搶票比賽，看誰能搶到最后一張票。這就是一個(gè)條件競爭的例子：你的座位(或者你的電影票)都取決于兩種購買方式的相對順序。

并發(fā)中競爭條件的形成，取決于一個(gè)以上線程的相對執(zhí)行順序，每個(gè)線程都搶著完成自己的任務(wù)。大多數(shù)情況下，即使改變執(zhí)行順序，也是良性競爭，其結(jié)果可以接受。例如，有兩個(gè)線程同時(shí)向一個(gè)處理隊(duì)列中添加任務(wù)，因?yàn)橄到y(tǒng)提供的不變量保持不變，所以誰先誰后都不會(huì)有什么影響。當(dāng)不變量遭到破壞時(shí)，才會(huì)產(chǎn)生條件競爭，比如雙向鏈表的例子。并發(fā)中對數(shù)據(jù)的條件競爭通常表示為惡性條件競爭，我們對不產(chǎn)生問題的良性條件競爭不感興趣。C++標(biāo)準(zhǔn)中也定義了數(shù)據(jù)競爭這個(gè)術(shù)語，一種特殊的條件競爭：并發(fā)的去修改一個(gè)獨(dú)立對象(參見5.1.2節(jié))，數(shù)據(jù)競爭是(可怕的)未定義行為的起因。

惡性條件競爭通常發(fā)生于完成對多于一個(gè)的數(shù)據(jù)塊的修改時(shí)，例如，對兩個(gè)連接指針的修改(如圖3.1)。因?yàn)椴僮饕L問兩個(gè)獨(dú)立的數(shù)據(jù)塊，獨(dú)立的指令將會(huì)對數(shù)據(jù)塊將進(jìn)行修改，并且其中一個(gè)線程可能正在進(jìn)行時(shí)，另一個(gè)線程就對數(shù)據(jù)塊進(jìn)行了訪問。因?yàn)槌霈F(xiàn)的概率太低，條件競爭很難查找，也很難復(fù)現(xiàn)。如CPU指令連續(xù)修改完成后，即使數(shù)據(jù)結(jié)構(gòu)可以讓其他并發(fā)線程訪問，問題再次復(fù)現(xiàn)的幾率也相當(dāng)?shù)?。?dāng)系統(tǒng)負(fù)載增加時(shí)，隨著執(zhí)行數(shù)量的增加，執(zhí)行序列的問題復(fù)現(xiàn)的概率也在增加，這樣的問題只可能會(huì)出現(xiàn)在負(fù)載比較大的情況下。條件競爭通常是時(shí)間敏感的，所以程序以調(diào)試模式運(yùn)行時(shí)，它們常會(huì)完全消失，因?yàn)檎{(diào)試模式會(huì)影響程序的執(zhí)行時(shí)間(即使影響不多)。

當(dāng)你以寫多線程程序?yàn)樯?，條件競爭就會(huì)成為你的夢魘；編寫軟件時(shí)，我們會(huì)使用大量復(fù)雜的操作，用來避免惡性條件競爭。

3.1.2 避免惡性條件競爭

這里提供一些方法來解決惡性條件競爭，最簡單的辦法就是對數(shù)據(jù)結(jié)構(gòu)采用某種保護(hù)機(jī)制，確保只有進(jìn)行修改的線程才能看到不變量被破壞時(shí)的中間狀態(tài)。從其他訪問線程的角度來看，修改不是已經(jīng)完成了，就是還沒開始。C++標(biāo)準(zhǔn)庫提供很多類似的機(jī)制，下面會(huì)逐一介紹。

另一個(gè)選擇是對數(shù)據(jù)結(jié)構(gòu)和不變量的設(shè)計(jì)進(jìn)行修改，修改完的結(jié)構(gòu)必須能完成一系列不可分割的變化，也就是保證每個(gè)不變量保持穩(wěn)定的狀態(tài)，這就是所謂的無鎖編程。不過，這種方式很難得到正確的結(jié)果。如果到這個(gè)級別，無論是內(nèi)存模型上的細(xì)微差異，還是線程訪問數(shù)據(jù)的能力，都會(huì)讓工作變的復(fù)雜。內(nèi)存模型將在第5章討論，無鎖編程將在第7章討論。

另一種處理?xiàng)l件競爭的方式是，使用事務(wù)的方式去處理數(shù)據(jù)結(jié)構(gòu)的更新(這里的"處理"就如同對數(shù)據(jù)庫進(jìn)行更新一樣)。所需的一些數(shù)據(jù)和讀取都存儲在事務(wù)日志中，然后將之前的操作合為一步，再進(jìn)行提交。當(dāng)數(shù)據(jù)結(jié)構(gòu)被另一個(gè)線程修改后，或處理已經(jīng)重啟的情況下，提交就會(huì)無法進(jìn)行，這稱作為“軟件事務(wù)內(nèi)存”。理論研究中，這是一個(gè)很熱門的研究領(lǐng)域。這個(gè)概念將不會(huì)在本書中再進(jìn)行介紹，因?yàn)樵?code>C++中沒有對STM進(jìn)行直接支持。但是，基本思想會(huì)在后面提及。

保護(hù)共享數(shù)據(jù)結(jié)構(gòu)的最基本的方式，是使用C++標(biāo)準(zhǔn)庫提供的互斥量。