并發資料結構-1.4 池

實作高效并發棧和隊列的大部分挑戰來自于一個被插入的元素可以被删除這一需求。并發池是一種支援插入和删除操作的資料結構，它允許删除操作移除任何一個已經被插入的，并且沒有在随後被删除的元素。這樣的弱需求提供了提高并發性能的機會。

一個高效的并發池可以使用任意靜态一緻的計數器來建構。在這樣的并發池中，元素被置于數組當中，fetch-and-inc操作決定插入操作在哪個位置存儲元素，同樣的，fetch-and-inc操作決定删除操作在哪個位置獲得元素。每一個數組元素都包含了一個表示滿/空的比特位或者等效的機制，來表明在相應的位置，将要删除的元素已經存在。在這種政策下，使用combining tree，combining funnel，counting network，diffracting tree中的任何一個技術都可以并行化共享技術器，解決這一主要的瓶頸來建立出一個高吞吐量的共享并發池。此外，一個類似棧的池可以使用一個允許增加和減少操作的計數器來實作，然後利用以上技術中的一種來并行化.

最後，在前文中說讨論的消除技術（elimination technique）可以使用在利用combining tree，combining funnel，counting network，diffracting tree等技術實作的并發池中：假如在樹中插入和删除操作相遇，那麼删除操作可以擷取插入操作插入的值，之後兩個操作就不用繼續周遊這個結構樹。這項技術在高負載下能表現出良好的高性能.

上述的這些實作的缺點是，它們在低複雜的情況下性能糟糕。而且，在做負載分布工作的時候，這些實作并不允許我們如同那些專門為負載分布設計的池一樣，得到具體的位置資訊。

負載均衡算法涉及到一個任務池集合，每個任務池中有一些工作單元，其中每一個任務池都被本地化到一個處理器上。當線程建立了工作項之後就把它們置于本地化的任務池中，依靠負載均衡算法確定任務池中的工作數量都是均衡的。這樣就避免了其他處理器仍然忙碌于自己工作的時候，有些處理器卻處于空閑狀态。大體上有兩種解決這類問題的算法：工作共享（work sharing ）和工作竊取（work stealing ）。在工作共享方案中，每一個處理器嘗試不斷地将自身任務池中的工作卸下，放到其他任務池中。在工作竊取模式下，一個線程已經完成了自己的工作後就會去竊取其他任務池中的工作去執行。兩種方案通過随機選擇任務池來平衡工作或竊取工作。

傳統工作竊取技術是arara等人提出的，它基于一個無鎖結構的雙向隊列。該雙向隊列隻允許一個線程（該任務池的本地線程）在隊列的一端進行操作，在另一端隻允許彈出操作，并且允許在這一端的并發彈出操作線上程互相幹擾的情況下中止。在這樣的限制下，雙向隊列适合于任務竊取，并且這種限制允許一種簡單的實作方式，即本地線程用低開銷的load and store操作來進行插入和删除，隻有當它和其他非本地删除線程競争隊列裡的最後一個任務的時候，才會依賴昂貴的cas操作。

在一些案例中已經清晰表明一次竊取多個任務的效果是令人滿意的。一個非阻塞的多任務竊取算法由hendler與shavit在podc(2002)上提出。在一些案例中同樣表明通過使用 同類工作項資訊來決定竊取那些工作是可取的。另外在spaa(2000)上，acar等人提出了一種位置引導（locality-guided）的竊取算法.