多線程用C鏈表++

首先我試圖做一些解釋：多線程用C鏈表++

我的計劃是寫一個程序，一個套接字流使用它來實現的解析器將資料提供了boost :: ASIO庫實現使用boost：spirit :: qi。解析器將獲取數據包並填充數據包對象，然後將該對象追加到數據包對象鏈表的末尾。數據包處理器將讀取列表中的第一個對象並執行處理，然後移到下一個項目並刪除第一個項目。

我決定使用一個鏈表，因爲如果我使用了一個std ::隊列，我將不得不鎖定整個容器，每當流添加一個數據包或處理器刪除一個會使兩個線程運行更多或不太系列，我想避免。此外，隊列類有一個複製整個對象的趨勢，而鏈表概念有一個創建對象的好處，然後指向它。爲了避免序列化整個業務，我打算在每個節點中放置boost：mutex互斥鎖，並從那裏鎖定它們。這個想法是讓套接字流創建列表並立即鎖定第一個節點，從解析器填充節點，創建下一個節點並鎖定它，然後解鎖第一個節點並轉到下一個節點上工作。這樣一來，從來就沒有一個解鎖的節點懸在末尾，數據包處理器可能跳到並在套接字流鼻子下刪除。數據包處理器將檢查第一個節點並嘗試鎖定它，如果它鎖定它，則它將執行處理，然後解鎖它，獲取下一個節點，然後刪除第一個節點。這種串行化被限制在分組處理器已經追上套接字流類的那些時間。

所以現在我的問題是，在我做實際執行這項工作之前，這聽起來像一個好主意嗎？我試過它在一個簡單的測試，它似乎工作正常，我不能想到任何嚴重的問題，只要我實現異常處理並注意釋放我分配的任何內存，但如果任何人都可以想到我忽略了這個想法的任何問題，我將不勝感激。此外，我希望任何其他建議任何人可能作爲替代或可能使這個想法更好地工作。

在此先感謝！

來源

2011-07-02 jacobkaulike

檢查這篇文章，它是關於多個消費者，但還是高明：

Measuring Parallel Performance: Optimizing a Concurrent Queue

來源

2011-07-02 14:50:18

非常棒的文章，謝謝！我認爲這會非常有幫助。 – jacobkaulike

我不認爲你有什麼建議將工作。請記住，當您從鏈接列表中刪除節點時，您需要更新指向已刪除節點的其他節點。同樣，添加節點時，還需要更新其他節點以指向新節點。所以只需鎖定被刪除或添加的節點是不夠的。

有無鎖排隊，但他們很難得到正確的。例如，請查看文章here的初始評論，其中描述了獲取已發佈算法的額外工作。

來源

2011-07-02 14:51:50

鏈表是單向的。每個節點只指向下一個節點，所以當我向前移動然後刪除當前節點時，沒有任何指向我刪除的節點，所以這不是問題。 – jacobkaulike

想象一下列表中有一個元素。那時生產者線程試圖添加一個新節點，並且消費者線程試圖刪除單個元素。生產者線程會將新節點更新爲指向被刪除的節點。兩個線程都會嘗試更新指向列表中第一個元素的變量。 –

這就是爲什麼流線程始終鎖定列表中的最後一個元素，以便處理器線程無法對其執行任何操作。我還打算在完成處理後始終創建下一個元素，這樣就不會有包處理器線程可以工作的節點，除非它不能訪問它，因爲流線程擁有鎖定。 – jacobkaulike

即使您正在調用此鏈接列表，實際上這是一個隊列。

如果您願意使用固定大小的緩衝區，則可以實現Single Producer Single Consumer無鎖隊列。這使您可以控制內存使用情況，但費用是讓消費者速度不夠快時，讓Producer等待。

除了這一點，你的設計看起來不錯，它可能比無鎖選擇更容易。

請記住終止條件（例如next字段中的空指針），以便生產者可以向消費者發信號通知消費者沒有更多要處理的事情。

來源

2011-07-02 15:02:17

關於終止條件，這是一個好主意。我沒有想到這一點，所以我會確保將其納入我的最終實施中。是的，它實際上是一個隊列，我只是不喜歡每當一個線程被推動或其他彈出時鎖定整個容器。即使讀取和寫入std :: queue也是必需的，甚至微軟的新concurrency_queue也不能保證容器從一次調用到另一次調用將佔用相同的內存。加上覆制到緩衝區的所有內存開銷並... – jacobkaulike

...可能將整個緩衝區移動到內存中讓我感到非常不愉快。 – jacobkaulike

@jacobkaulike：你錯在抽象和給定的實現。如果設計一種類型的對象以單向方式流動（即推向一側並從另一側彈出），並且無法訪問中間的對象，則您有一個隊列，無論它是使用動態數組實現的還是鏈接列表不會改變它。請注意，您可以通過存儲指向您的對象的指針而不是對象本身來解決內存問題（對象移動和大緩衝區），從而使Microsoft的'concurrency_queue'成爲可能。 –

這實現了我尖叫三件事情：

太容易得到僵局，因爲插入和刪除需要同時鎖定多個互斥的，你不能這樣做同時進行。那麼你可以，但是你需要在你的互斥體周圍放置互斥體。
太容易腐敗。導致僵局的問題也可能導致腐敗。
慢，慢，慢。想想你可憐的名單步行者。每個步驟都涉及解鎖，鎖定，另一個解鎖和另一個鎖定。在邁步時必須非常小心，而男士則會很貴。鎖定並解鎖每個項目，並以正確的順序進行操作？哎喲。

這看起來像一個過早優化和過早pessimization並行操作的情況。什麼推動了這個建築？

我建議先從簡單的解決方案開始。每當你想觸摸它的任何部分時，就鎖定整個事物。看看是否讓你陷入困境。如果沒有，問題就解決了。如果是這樣，下一步就是從互斥鎖切換到讀寫鎖。只有一個，而不是一個巨大的。現在你必須考慮一下你是否想要共享鎖或排他鎖。如果您一直在努力研究常量正確性，請嘗試爲您的const方法使用共享鎖（讀鎖），爲非常量方法使用排它鎖（寫鎖）。

來源

2011-07-02 15:11:19

考慮到這一點之後，我想到第一個問題是不可能的，因爲流線程在包處理器線程獲取對象之前創建對象，並且在釋放下一個包處理器節點之前總是鎖定一個節點可以做的工作，使死鎖是不可能的，除非沒有任何數據包處理器的工作。 – jacobkaulike

如果是導致腐敗的僵局，那麼下一個原因同樣是不可能的。第三個是不公開的，因爲我沒有像這樣鎖定和解鎖，如果我正在鎖定和解鎖整個容器，除了這有利於減少內存開銷，不會將對象複製到隊列中，並且不會隨着容器自動調整大小，整個容器中的內存上的潛在移動操作。 – jacobkaulike

嗯..爲什麼這麼複雜的解決一個共同的問題？有很多生產者 - 消費者隊列類 - 選擇一個適用的參考/指針/詮釋大小（即沒有數據複製）。

從您的流中獲取字節，直到根據您的協議組裝了「數據包對象」。將分組對象參考推到隊列上，並立即將new（）的另一個分組用於下一個分組。數據包處理器使用隊列中的數據包對象。

該隊列僅鎖定了推送/彈出隊列中對象引用所用的時間。由套接字/流回調組裝的數據包對象和由數據包處理器處理的數據包對象總是不同的，因此不需要鎖定。

試圖對已經在隊列中的對象（或類似隊列的鏈表）聽起來像是我的噩夢，（和其他海報似乎一致）。有什麼其他的原因你需要這樣做嗎？

Rgds， Martin Martin

來源

2011-07-02 16:16:23

我試過的這個概念的簡單測試表明，對已經在隊列中的對象進行操作將非常容易，我只需要在列表中進行操作，然後操作我所在的節點，然後獲取下一個節點並刪除當前節點當我完成時。我期待的主要優點是套接字流將始終具有優先級，並且永遠不需要等待數據包處理器完成其所需的工作。我的主要目標是給套接字流優先。在concurrent_queue中，這是不可能的。 – jacobkaulike

好吧，我明白了，但是如果一個32位/ 64位引用的concurrent_queue推送和一個同步對象（condvar，信號量，監視器等）的信號傳遞在現代CPU上花費超過1uS，我會感到驚訝/ OS，假設沒有爭用。我擔心，數據包對象的組裝（包括網絡堆棧/驅動程序活動）平均需要比這更長的時間。您的數據包對象非常小，網絡速度非常快嗎？ –

儘管如此，我認爲內存重新分配和可能會持續發生的重定位，因爲concurrent_queue必須動態調整大小，但會比使用替代方法消耗更多的週期。 – jacobkaulike

多線程用C鏈表++

回答

相關問題