博客園 首頁 聯系 管理
隨筆 - 18 文章 - 0 評論 - 0 閱讀 - 1354
3.1 ***享數據帶來的問題
當涉及到***享數據時，問題很可能是因為修改***享數據所導致。如果***享數據是只讀的，那麽只讀操作不會影響到數據，所以所有線程都會獲得同樣的數據。但是，當壹個或多個線程要修改***享數據時，就會產生很多麻煩。
不變量：雙鏈表中每個節點都有壹個指針指向列表中下壹個節點，還有壹個指針指向前壹個節點。其中不變量就是：節點A中指向“下壹個”節點B的指針，還有前向指針。為了從列表中刪除壹個節點，其兩邊節點的指針都需要更新。當其中壹邊更新完成時，不變量就被破壞了，直到另壹邊也完成更新；在兩邊都完成更新後，不變量就又穩定了。
從壹個列表中刪除壹個節點的步驟如下：
找到要刪除的節點N
更新前壹個節點指向N的指針，讓這個指針指向N的下壹個節點
更新後壹個節點指向N的指針，讓這個指正指向N的前壹個節點
刪除節點N
圖3.1 從壹個雙鏈表中刪除壹個節點
圖中b和c在相同的方向上指向和原來已經不壹致了，這就破壞了不變量。破壞不變量的後果是多樣的，當其他線程按從左往右的順序來訪問列表時，它將跳過被刪除的節點；在壹方面，如有第二個線程嘗試刪除圖中右邊的節點，那麽可能會讓數據結構產生永久性的損壞，使程序崩潰。無論結果如何，都是並行代碼常見錯誤：條件競爭。
3.1.1 條件競爭
並發中競爭條件的形成，取決於壹個以上線程的相對執行順序，每個線程都搶著完成自己的任務。
惡性條件競爭：當不變量遭到破壞時，才會產生條件競爭，比如雙向鏈表的例子。並發中對數據的條件競爭通常表示為惡性條件競爭。
3.1.2 避免惡性條件競爭
這裏提供壹些方法來解決惡性條件競爭：
最簡單的辦法就是對數據結構采用某種保護機制，確保只有進行修改的線程才能看到不變量被破壞時的中間狀態；
另壹個選擇是對數據結構和不變量的設計進行修改，修改完的結構必須能完成壹系列不可分割的變化，也就是保證每個不變量保持穩定的狀態，這就是所謂的無鎖編程。
另壹種處理條件競爭的方式是，使用事務的方式去處理數據結構的更新。所需的壹些數據和讀取都存儲在事務日誌中，然後將之前的操作合為壹步，再進行提交。當數據結構被另壹個線程