多線程訪問數據結構

我正在使用C，pthreads和套接字在Linux中編寫應用程序。多線程訪問數據結構

這將是客戶端 - 服務器應用程序，服務器將具有N + 2個線程，其中N - 活動客戶端的數目，一個線程用於接受新連接併爲客戶創造和最後一個線程將被接受用戶輸入。

我將使用鏈表來保存一些數據，這將是有關我的應用程序，與每一位客戶都會有我的列表中相關聯的一個節點。那些客戶端線程會以一定的時間間隔更新存儲在其節點中的信息，可能是一秒鐘，可能是兩分鐘，它會動態更改。

現在問題在於，如果用戶請求它，存儲在鏈接列表中的信息需要寫入標準輸出。當然，在寫作時我應該獲得互斥體。我擔心整個列表中的一個互斥量會妨礙性能。

我在考慮將互斥鎖與每個節點關聯起來，但它會使一些指定節點的移除複雜化（首先，我需要確保'stdout writer'線程不會遍歷列表，我也會需要獲取我的節點的互斥體和前一個節點來改變指向下一個節點的指針，依此類推 - 或者我需要遍歷所有前一個節點，或者我需要創建雙鏈表）。

所以我想知道如果涉及多個互斥體的解決方案，甚至更好用更復雜的代碼，條件和這一切的鎖定，等待和解鎖。

來源

2012-06-08 Andna

你說得對，每個節點互斥會使代碼更復雜。這是一個折衷，你將不得不決定價值。您可以對整個列表使用一個鎖，這可能會導致鎖爭用，但代碼很大程度上不受鎖的存在的影響，因此更容易編寫，或者您可以擁有更多的鎖，爭奪的機會更少，導致更好的性能，但代碼很難寫入並得到正確。您甚至可以通過爲每組節點鎖定一些東西 - 將一些節點分配在一起併爲該組鎖定一個鎖定 - 但是，在跟蹤空閒列表和碎片的可能性時會遇到問題。

你需要考慮添加操作的相對頻率，刪除等操作，以及全名單迭代，以及其他（重組，搜索，其他任何應用程序都需要）。如果添加/刪除非常頻繁，但是每隔三個藍色月亮行走一次，單一鎖定可能很容易。但是，如果列表（無論是完整的數據轉儲，還是搜索或其他內容）非常普遍，更細化的方法會變得更具吸引力。你甚至可能需要考慮讀寫器鎖而不是互斥鎖。

來源

2012-06-08 18:29:12 twalberg

那麼這又怎麼樣呢，而不是物理地去除節點，我將它們標記爲「未使用」，這樣在寫入數據和刪除期間就不會有任何問題，因爲我不需要訪問任何其他節點，如果讀者想要遍歷他將鎖定它的列表，並且只有當列表沒有被讀者遍歷時纔會發生列表添加。 – Andna

你可以做到這一點 - 但考慮是否值得。添加新節點將搜索未使用節點，然後分配一個，如果沒有未使用的節點。遍歷列表必須足夠聰明以跳過未使用的列表。刪除會更容易一些，因爲您不必調整鏈接，但仍然需要使用鎖來標記未使用的節點，所以不妨將其從列表中拉出。到處都是，我認爲將節點標記爲未使用會使代碼變得更加複雜，而沒有太多收穫。 – twalberg

好吧，我想我會使用讀寫鎖，據我所知，我可以保證作者將有權限讀者訪問列表。 – Andna

如果你將有N個線程N個活動的客戶端，然後考慮使用pthread_setspecific和pthread_getspecific的選項。

來源

2012-06-08 18:04:32 Viswesn

它會工作，但有這個問題，我會neet在其他線程中檢索數據，用戶輸入線程將打印數據到標準輸出，如果這將是線程特定的，我不認爲我可以從每個線程在一個線程中。 – Andna

在這種情況下，pthread_setspecific將不起作用。在打算在列表節點中寫入內容之前，您需要鎖定和解鎖列表的頭部;我寧願建議你有樹實現而不是列表實現;因爲樹實現遍歷將提高系統的性能。 – Viswesn

你並不需要遍歷列表中的所有回來的路上：當你穿越它，你測試，如果下一個元素是，你要刪除的一個，然後你可以鎖定兩個節點 - 在同一直整個代碼的順序，所以你避免死鎖。此外，您可以使用雙重檢查成語，並在需要確定它具有的功能時鎖定互斥節點。

remove 
    for node in list 
     if node->next is the desired node 
      lock(node) 
      lock(node->next) 
       if node->next is the desired node 
        do removing stuff 
       else 
        treat concurrent modification - retry, maybe? 
      release(node->next) 
      release(node)

有了這個成語在閱讀它，你也並不需要鎖定整個列表檢查第一個測試和鎖定之間進行修改。我不相信代碼會因爲一組互斥體而變得複雜得多，並且鎖定開銷與您可能執行的操作（IO）相比毫無用處。

來源

2012-06-08 18:35:40

除非您有幾十個甚至幾十萬個用戶，否則讀取該列表不會花費太長的時間。您可能想創建一個本地中間列表，以便在寫入時原件不會被鎖定，其中可能需要一些時間。這也意味着您可以在某個時間點獲得列表的快照。如果您鎖定了各個節點，則可以刪除A，然後然後移除元素B，但是當B不存在時，A會出現在顯示的列表中。

據我所知，如果你做想要鎖定個別節點，你的列表必須單獨鏈接。添加和刪除變得相當棘手。在Java中，有幾個使用快速比較和交換技術的系統類。 C中必須有類似的代碼，但我不知道在哪裏尋找它。你會得到那些按時間順序挑戰的結果。

來源

2012-06-08 18:51:40 RalphChapin

多線程訪問數據結構

回答

相關問題