并發資料結構- 1.8 優先隊列&1.9 總結

原文連結，譯文連結，譯者：郭振斌，校對：周可人

并發的優先隊列是一個可線性化到順序優先隊列的資料結構，能夠通過常用的優先隊列語義提供insert和delete-min操作。

<b>基于堆的優先隊列</b>

許多文獻中提到的并發優先隊列結構，其實是本書前面提到的可線性化堆結構。再一次的，這種結構的基本思想是在個别堆節點上使用細粒度鎖，使線程在并行下也能夠盡可能的通路資料結構的不同部分。設計這種并發堆的關鍵問題，在于傳統自底向上的insert和自頂向下的delete-min操作有可能造成死鎖。biswas和brown[17]提出基于鎖的堆算法，通過專門的“清理”線程解決死鎖。rao和kumar[116]建議通過一個将insert和delete-min操作都自頂向下處理的算法[17]來解決問題。ayani[11]在他們算法基礎上做了改善，即通過一種方式在堆兩側進行連續插入。jones[68]提出一種基于類似斜堆的方案[116]。

hunt et al.[61]提出一種基于堆的算法，解決了上述方案的許多局限性，尤其是針對在堆周遊中需要擷取多個鎖的問題。此算法處理上是在一個标記堆大小的變量上加鎖一小段時間和堆的第一個或者最後一個元素上加鎖。為了提升并行性，插入自底向上周遊堆，而删除自頂向下，且不會産生死鎖。插入也采用了自左向右技術，就像[11]允許通路堆兩側，進而最小化沖突。

此外，huang和weihl[60]提出了一種基于斐波那契堆[34]并行版本的并發優先隊列。

herlihy[50], barnes [12], and israeli and rappoport [65]提出了非阻塞可線性化的基于堆的優先隊列算法。sundell 和 tsigas[133]提出了一個基于無鎖版pugh 并發跳表的無鎖優先隊列。

<b>基于樹的隊列池</b>

huang、weihl[60]和johnson[66]這樣描述并發優先池：（并發優先池是）松散語義的優先隊列，不保證delete-min操作的可線性化。他們的設計都是基于修正版的并發b+樹實作。johnson引入了一個集合待删除值的“删除容器”，進而降低在并發執行delete-min操作時的負載。shavit和zemach [130]提出了一個在pugh并發跳表中引入“删除容器”機制的類似（隊列）池。一般情況下，較弱的池語義可以提升并發。在[130]他們還提出，如果允許的鍵容量是有限的（作業系統中通常如此），那麼一個基于結合漏鬥節點的二叉樹的優先池可以擴充到上百個（相比數十個）處理器。

我們概述了在共享記憶體多處理器下設計并發資料結構的相關問題，還調研了此領域的一些重要貢獻。概述中清楚的說明了設計并發資料結構的諸多顯著挑戰，在撰寫本文時，并發資料結構的成熟度還遠遠落後于順序結構。然而，在發現關鍵問題和開發新技術方面已經取得了顯著進展，以促進設計有效的并發資料結構；學術界和工業界重新在通過增強硬體來支援同步上産生興趣，我們感到倍受鼓舞。鑒于新認識，新技術和更強大的硬體支援，我們相信并發資料結構設計會在不久的将來出現重大的進步。