當(dāng)涉及到共享數(shù)據(jù)時，問題很可能是因為共享數(shù)據(jù)修改所導(dǎo)致。如果共享數(shù)據(jù)是只讀的，那么只讀操作不會影響到數(shù)據(jù)，更不會涉及對數(shù)據(jù)的修改，所以所有線程都會獲得同樣的數(shù)據(jù)。但是，當(dāng)一個或多個線程要修改共享數(shù)據(jù)時，就會產(chǎn)生很多麻煩。這種情況下，就必須小心謹(jǐn)慎，才能確保一切所有線程都工作正常。
不變量(invariants)的概念對程序員們編寫的程序會有一定的幫助——對于特殊結(jié)構(gòu)體的描述；比如，“變量包含列表中的項數(shù)”。不變量通常會在一次更新中被破壞，特別是比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，或者一次更新就要改動很大的數(shù)據(jù)結(jié)構(gòu)。
雙鏈表中每個節(jié)點都有一個指針指向列表中下一個節(jié)點，還有一個指針指向前一個節(jié)點。其中不變量就是節(jié)點A中指向“下一個”節(jié)點B的指針，還有前向指針。為了從列表中刪除一個節(jié)點，其兩邊節(jié)點的指針都需要更新。當(dāng)其中一邊更新完成時，不變量就被破壞了，直到另一邊也完成更新；在兩邊都完成更新后，不變量就又穩(wěn)定了。
從一個列表中刪除一個節(jié)點的步驟如下(如圖3.1)
http://wiki.jikexueyuan.com/project/cplusplus-concurrency-action/images/chapter3/3-1.png" alt="" />
圖3.1 從一個雙鏈表中刪除一個節(jié)點
圖中b和c在相同的方向上指向和原來已經(jīng)不一致了，這就破壞了不變量。
線程間潛在問題就是修改共享數(shù)據(jù)，致使不變量遭到破壞。當(dāng)不做些事來確保在這個過程中不會有其他線程進(jìn)行訪問的話，可能就有線程訪問到剛剛刪除一邊的節(jié)點；這樣的話，線程就讀取到要刪除節(jié)點的數(shù)據(jù)(因為只有一邊的連接被修改，如圖3.1(b))，所以不變量就被破壞。破壞不變量的后果是多樣，當(dāng)其他線程按從左往右的順序來訪問列表時，它將跳過被刪除的節(jié)點。在一方面，如有第二個線程嘗試刪除圖中右邊的節(jié)點，那么可能會讓數(shù)據(jù)結(jié)構(gòu)產(chǎn)生永久性的損壞，使程序崩潰。無論結(jié)果如何，都是并行代碼常見錯誤：條件競爭。
假設(shè)你去電影院買電影票。如果去的是一家大電影院，有很多收銀臺，很多人就可以在同一時間買電影票。當(dāng)另一個收銀臺也在賣你想看的這場電影的電影票，那么你的座位選擇范圍就取決于在之前已預(yù)定的座位。當(dāng)只有少量的座位剩下，這就意味著，這可能是一場搶票比賽，看誰能搶到最后一張票。這就是一個條件競爭的例子：你的座位(或者你的電影票)都取決于兩種購買方式的相對順序。
并發(fā)中競爭條件的形成，取決于一個以上線程的相對執(zhí)行順序，每個線程都搶著完成自己的任務(wù)。大多數(shù)情況下，即使改變執(zhí)行順序，也是良性競爭，其結(jié)果可以接受。例如，有兩個線程同時向一個處理隊列中添加任務(wù)，因為系統(tǒng)提供的不變量保持不變，所以誰先誰后都不會有什么影響。當(dāng)不變量遭到破壞時，才會產(chǎn)生條件競爭，比如雙向鏈表的例子。并發(fā)中對數(shù)據(jù)的條件競爭通常表示為惡性條件競爭，我們對不產(chǎn)生問題的良性條件競爭不感興趣。C++標(biāo)準(zhǔn)中也定義了數(shù)據(jù)競爭這個術(shù)語，一種特殊的條件競爭：并發(fā)的去修改一個獨立對象(參見5.1.2節(jié))，數(shù)據(jù)競爭是(可怕的)未定義行為的起因。
惡性條件競爭通常發(fā)生于完成對多于一個的數(shù)據(jù)塊的修改時，例如，對兩個連接指針的修改(如圖3.1)。因為操作要訪問兩個獨立的數(shù)據(jù)塊，獨立的指令將會對數(shù)據(jù)塊將進(jìn)行修改，并且其中一個線程可能正在進(jìn)行時，另一個線程就對數(shù)據(jù)塊進(jìn)行了訪問。因為出現(xiàn)的概率太低，條件競爭很難查找，也很難復(fù)現(xiàn)。如CPU指令連續(xù)修改完成后，即使數(shù)據(jù)結(jié)構(gòu)可以讓其他并發(fā)線程訪問，問題再次復(fù)現(xiàn)的幾率也相當(dāng)?shù)?。?dāng)系統(tǒng)負(fù)載增加時，隨著執(zhí)行數(shù)量的增加，執(zhí)行序列的問題復(fù)現(xiàn)的概率也在增加，這樣的問題只可能會出現(xiàn)在負(fù)載比較大的情況下。條件競爭通常是時間敏感的，所以程序以調(diào)試模式運(yùn)行時，它們常會完全消失，因為調(diào)試模式會影響程序的執(zhí)行時間(即使影響不多)。
當(dāng)你以寫多線程程序為生，條件競爭就會成為你的夢魘；編寫軟件時，我們會使用大量復(fù)雜的操作，用來避免惡性條件競爭。
這里提供一些方法來解決惡性條件競爭，最簡單的辦法就是對數(shù)據(jù)結(jié)構(gòu)采用某種保護(hù)機(jī)制，確保只有進(jìn)行修改的線程才能看到不變量被破壞時的中間狀態(tài)。從其他訪問線程的角度來看，修改不是已經(jīng)完成了，就是還沒開始。C++標(biāo)準(zhǔn)庫提供很多類似的機(jī)制，下面會逐一介紹。
另一個選擇是對數(shù)據(jù)結(jié)構(gòu)和不變量的設(shè)計進(jìn)行修改，修改完的結(jié)構(gòu)必須能完成一系列不可分割的變化，也就是保證每個不變量保持穩(wěn)定的狀態(tài)，這就是所謂的無鎖編程。不過，這種方式很難得到正確的結(jié)果。如果到這個級別，無論是內(nèi)存模型上的細(xì)微差異，還是線程訪問數(shù)據(jù)的能力，都會讓工作變的復(fù)雜。內(nèi)存模型將在第5章討論，無鎖編程將在第7章討論。
另一種處理條件競爭的方式是，使用事務(wù)的方式去處理數(shù)據(jù)結(jié)構(gòu)的更新(這里的"處理"就如同對數(shù)據(jù)庫進(jìn)行更新一樣)。所需的一些數(shù)據(jù)和讀取都存儲在事務(wù)日志中，然后將之前的操作合為一步，再進(jìn)行提交。當(dāng)數(shù)據(jù)結(jié)構(gòu)被另一個線程修改后，或處理已經(jīng)重啟的情況下，提交就會無法進(jìn)行，這稱作為“軟件事務(wù)內(nèi)存”。理論研究中，這是一個很熱門的研究領(lǐng)域。這個概念將不會在本書中再進(jìn)行介紹，因為在C++中沒有對STM進(jìn)行直接支持。但是，基本思想會在后面提及。
保護(hù)共享數(shù)據(jù)結(jié)構(gòu)的最基本的方式，是使用C++標(biāo)準(zhǔn)庫提供的互斥量。
掃碼關(guān)注鍍金池微信號
手機(jī)訂課，優(yōu)惠多多
