C++中是否有任何線程安全的圖形庫？

基本上我正在尋找一個圖形庫，它可以對圖形操作進行細密的鎖定，以便不同的線程可以同時觸及圖形的不同部分，並且可以阻止競爭性修改。C++中是否有任何線程安全的圖形庫？

我搜索了一下，找不到任何東西。也許這對我的需求太具體，但我會想象會有大量的科學應用程序可以在大圖上工作。

2009-12-21 drpepper

這裏的「圖」是計算機科學的抽象東西，還是另一個詞的「情節」？ – dmckee 2009-12-21 17:36:34

http://en.wikipedia.org/wiki/Graph_%28mathematics%29 – Yacoby 2009-12-21 17:44:45

@Yacoby：是的，我知道。但該標籤還包括像http://stackoverflow.com/questions/1879964/plotting-cartesian-plots-axis-inside-the-figure-possible-annotations和http://stackoverflow.com/questions/1878368/something -to-use-for-graphing-numbers是關於http://en.wikipedia.org/wiki/Graph_of_a_function。 O這是海報的意思嗎？ – dmckee 2009-12-21 17:47:37

假設你問關於圖的數學實體（例如，GraphBase處理的圖的類型） - 那麼我認爲你不會找到你要找的東西，至少在通用庫中。

問題是，「線程安全」在所有上下文中都不是一個明確定義的術語 - 至少它可能意味着程序可能不會在多線程併發處理時爆炸 - 但超出這個要求，即使是像「容易安全」的容器或算法這樣的東西，也會有一些額外的語義關於這意味着什麼 - 而且通用圖庫更加複雜，並且需要更加精確的（和可配置的）語義來滿足這一點。

例如（簡單對象這裏講的 - 比如一個容器）：

併發讀訪問允許在同一個對象？是否允許對同一個對象進行併發寫入訪問？讀者是否阻止讀者？讀者是否會阻止作家？做作家阻止作家？更一般地說，什麼操作會阻止其他操作？

儘管您可以爲簡單容器定義合理的語義 - 就像一個併發集合 - 即使您移動到類似地圖的地方，您也需要引入像「putIfAbsent」這樣的複合操作，以彌補許多應用程序需要超過線程安全 - 他們需要將通常在不同調用（搜索，然後添加）中執行的操作鏈接到邏輯原子操作中。

我懷疑像圖庫一樣，這個問題變得尖銳起來。您的應用程序需要定義哪些操作可以並行進行 - 哪些操作應該阻止其他操作，無論您是否需要獲取圖形的一致快照，是否需要圖形上操作的完全可串行化，或者是否需要放寬模型是適當的，所以它。

我很難將所有這種通用性建立到圖庫中，並且也許不可能提前預測實際需求在線程安全性方面的情況（以上只是可能考慮的一小部分），所以我懷疑大多數圖形庫只會提供有關行爲的弱保證（例如，允許併發讀取訪問）或根本沒有明確的安全性，並期望庫的使用者在頂層構建更高級別的同步構造。

另一個原因可能是高性能庫只能在線程不安全的版本中找到，是爲了避免懲罰不需要這種安全性的客戶（這可能對大多數給定類的大多數實例而言） - 假設該線程安全性可以由需要它的人在外部添加，但反向轉換（移除線程安全性）通常是不可能的。 Java一直在走這條道路，有些早期的線程安全類，如Vector支持ArrayList和StringBuffer與StringBuilder的有效棄用。

另一方面，客戶可以以有效的方式在外部向容器添加線程安全性（無法訪問內部部件）的假設通常是不正確的 - 這是構建自組合的基礎併發包中的線程安全容器。然而，我很懷疑你會在C++中找到與圖表操作等價的東西。

更新：鑑於其他答覆，我想我應該強調，我不認爲你會發現單線程庫的一般線程安全擴展 - 但顯然有幾個顯式並行線程庫，雖然我懷疑這些實現了更高級別的語義，並在內部執行並行性，而不是面向線程安全的單個圖形操作操作。

來源

2009-12-21 21:02:00 BeeOnRope

我明白你的意思了。也許將圖顯式分割成多個部分並將每個線程單詞放在一個部分中會更容易。然後，只有當操作涉及兩個部分之間的邊界或頂點時，才需要唯一的鎖定。我對這個想法的擔憂是圖表的某些部分可能比其他部分更有趣，這會使一些線程空轉。 – drpepper 2009-12-22 13:04:59

您提到的問題在並行算法中很常見，在該算法中，您對工作集進行分區，並且集中的不同分區可能需要大量不同的處理時間，並且確定此時間不可行。我將在下面描述兩個（類似的）策略。 – BeeOnRope 2009-12-23 00:21:59

一種策略是將工作集劃分爲比工作人員更多的部分 - 因此，如果您決定4名工人，則創建20個部分，這會增加作品執行類似工作量的機會（因爲一名工作人員可以完成17個工作「無趣的部分」）。然而，很難確定最佳的分區數量。您可以創建的分區數量也可能存在實際限制。 – BeeOnRope 2009-12-23 00:22:44

你可能想看看Parallel Boost Graph Library（也可能是MultiThreaded Graph Library）。我還沒有使用過自己，只是偶然發現它們，同時將並行機制作爲加速某些BGL代碼的選項。（啊...它看起來像Parallel-BGL現在正式in boost！有一個很好的architectural overview，但也許他們的「分佈圖」的概念是相當粗糙的比你想的）。

來源

2009-12-21 21:29:34 timday

感謝您的鏈接。並行BGL看起來非常好，但似乎更多的是在沒有共享內存的多處理器上進行並行計算。在我的情況下，我認爲這將是矯枉過正。至於MTGL，它看起來相當未完成。他們不斷提及他們必須穩定他們的「基本API」！但我會密切關注它。 – drpepper 2009-12-22 13:00:30

不幸的是，細粒度鎖定的代價可能高於多線程的加速。更不用說死鎖的風險，當你的互斥體數量非常少時，鎖定管理變得更加困難。

來源

2009-12-21 22:18:29

C++中是否有任何線程安全的圖形庫？

回答

相關問題