Java 理論與實踐 ：關于非阻塞算法簡介
發布: 2008-10-07 11:38 | 作者: 不詳 | 來源: 領測軟件測試網采編 | 查看: 23次 | 進入軟件測試論壇討論
性能考慮
在輕度到中度的爭用情況下，非阻塞算法的性能會超越阻塞算法，因為 CAS 的多數時間都在第一次嘗試時就成功，而發生爭用時的開銷也不涉及線程掛起和上下文切換，只多了幾個循環迭代。沒有爭用的 CAS 要比沒有爭用的鎖便宜得多（這句話肯定是真的，因為沒有爭用的鎖涉及 CAS 加上額外的處理），而爭用的 CAS 比爭用的鎖獲取涉及更短的延遲。
在高度爭用的情況下（即有多個線程不斷爭用一個內存位置的時候），基于鎖的算法開始提供比非阻塞算法更好的吞吐率，因為當線程阻塞時，它就會停止爭用，耐心地等候輪到自己，從而避免了進一步爭用。但是，這么高的爭用程度并不常見，因為多數時候，線程會把線程本地的計算與爭用共享數據的操作分開，從而給其他線程使用共享數據的機會。（這么高的爭用程度也表明需要重新檢查算法，朝著更少共享數據的方向努力。）“流行的原子” 中的圖在這方面就有點兒讓人困惑，因為被測量的程序中發生的爭用極其密集，看起來即使對數量很少的線程，鎖定也是更好的解決方案。
非阻塞的鏈表
目前為止的示例（計數器和堆棧）都是非常簡單的非阻塞算法，一旦掌握了在循環中使用 CAS，就可以容易地模仿它們。對于更復雜的數據結構，非阻塞算法要比這些簡單示例復雜得多，因為修改鏈表、樹或哈希表可能涉及對多個指針的更新。CAS 支持對單一指針的原子性條件更新，但是不支持兩個以上的指針。所以，要構建一個非阻塞的鏈表、樹或哈希表，需要找到一種方式，可以用 CAS 更新多個指針，同時不會讓數據結構處于不一致的狀態。
在鏈表的尾部插入元素，通常涉及對兩個指針的更新：“尾” 指針總是指向列表中的最后一個元素，“下一個” 指針從過去的最后一個元素指向新插入的元素。因為需要更新兩個指針，所以需要兩個 CAS。在獨立的 CAS 中更新兩個指針帶來了兩個需要考慮的潛在問題：如果第一個 CAS 成功，而第二個 CAS 失敗，會發生什么？如果其他線程在第一個和第二個 CAS 之間企圖訪問鏈表，會發生什么？
對于非復雜數據結構，構建非阻塞算法的 “技巧” 是確保數據結構總處于一致的狀態（甚至包括在線程開始修改數據結構和它完成修改之間），還要確保其他線程不僅能夠判斷出第一個線程已經完成了更新還是處在更新的中途，還能夠判斷出如果第一個線程走向 AWOL，完成更新還需要什么操作。如果線程發現了處在更新中途的數據結構，它就可以 “幫助” 正在執行更新的線程完成更新，然后再進行自己的操作。當第一個線程回來試圖完成自己的更新時，會發現不再需要了，返回即可，因為 CAS 會檢測到幫助線程的干預（在這種情況下，是建設性的干預）。
這種 “幫助鄰居” 的要求，對于讓數據結構免受單個線程失敗的影響，是必需的。如果線程發現數據結構正處在被其他線程更新的中途，然后就等候其他線程完成更新，那么如果其他線程在操作中途失敗，這個線程就可能永遠等候下去。即使不出現故障，這種方式也會提供糟糕的性能，因為新到達的線程必須放棄處理器，導致上下文切換，或者等到自己的時間片過期（而這更糟）。