併發可變優先級隊列

是否存在併發可變優先級隊列？理想情況下，我正在尋找C++實現，但對於初學者來說，指向算法的指針會非常有幫助。併發可變優先級隊列

要清楚，我正在尋找一個優先級隊列，我可以調整元素的優先級。特別是，TBB的concurrent_priority_queue不提供必要的功能。（就此而言，即使我們忽略了併發性，STL的priority_queue也不是。）Boost.Heap庫提供了我想要的串行功能，但沒有併發性。當然，我正在尋找更細粒度的東西，而不僅僅是在每個操作上鎖定整個隊列。

來源

2012-08-23 foxcub

我懷疑任何這樣的隊列要麼需要一個粗略的鎖，要麼需要很多細粒度的鎖，這兩個鎖都不會太高效。但是可能有另一種解決問題的方法。你的用例是什麼？ –

是的..我不能很快看到任何可靠的做這樣的事情的方式。是futex/criticalsection鎖這麼重要？它不能花費那麼長時間從樹中的一個地方移除一個指針並將其插入到其他地方（或者將指針從一個集合移動到另一個集合，或者在優先級列表實現中需要做什麼）？ –

嗯，我真的希望有一個無鎖的數據結構。至於更新，使用通常的數據結構它們相當重要：您不僅將指針從一個地方移動到另一個地方，而且還必須重新平衡一棵樹，或執行類似的操作。 – foxcub

併發優先級隊列通常使用skiplist實現，因此Facebook的ConcurrentSkipList可能符合您的要求。

來源

2012-08-23 18:58:06

優秀的建議。非常感謝你的指針。我只希望他們有這個課程的文檔頁面。 – foxcub

併發可變優先級隊列

回答

相關問題