一個可變長度的無鎖隊列？

我一直在C/C++中使用一個無鎖隊列，但其中大多數必須指定最大數量的元素，包括boost :: lockfree。一個可變長度的無鎖隊列？

任何人都可以給我一些關於可變長度和多個產品和多個消費者無鎖隊列的信息嗎？

2013-08-27 user2720721

傳統的解決方案由Michael-Scott描述並由Orlarey-Fober-Letz改進。 –

這已被問及之前，這裏的一些答案似乎仍然是有效的和維護：[是否有一個生產就緒無鎖隊列或哈希實現在C + +]（http://stackoverflow.com/questions/1164023/is生產就緒鎖無自由隊列或哈希執行in-c） –

最大長度的主要原因是一旦創建了隊列，就不能創建新的對象（無需在new或malloc或任何用於創建新對象的任何可能的阻塞）。

我不確定有沒有解決方案。如果分配鎖定是可以接受的，那麼創建一個受可用內存量限制的無鎖隊列並不困難。

boost::lockfree確實有reserve(n)和reserve_unsafe(n)可用於增長隊列。

編輯迴應評論：

是，真正的問題開始時兩位製片人試圖在同一時間增加新的元素，因爲在一定程度上或其他，內存分配將被阻塞，直到「領先「線程已完成其分配。這在某些情況下當然是可以接受的，但一般來說，使用無鎖隊列的原因是爲了避免鎖定，並且鎖定在new或malloc內不是鎖。

如果它僅發生在相對較少的時間間隔內，則可能不是什麼大問題（取決於用例）。但如果它經常發生，這將是一個問題。

即使只有一個生產者，也不能保證其他某個線程不會在某處調用malloc或new，導致在「向隊列中添加更多內容」中出現「等待」。

我認爲唯一真正的解決方案是創建一個足夠大的固定大小隊列來處理任何可能的工作負載。如果隊列本身擁有（智能）指向對象的指針/引用，那麼可能不會佔用超過實際存儲在隊列中的對象的太多內存。畢竟，如果您要存儲1000個元素，則無論隊列是動態還是固定大小，都至少需要1000個元素的存儲空間。

來源

2013-08-27 09:02:43

實際上我發現了一個動態大小的lockfree，但它是單生產者，單個消費者。[link] （http://moodycamel.com/blog/2013/a-fast-lock-free-queue-for-c++）我猜測隊列會創建新節點並在元素數量超過高級時自行調整大小。 – user2720721

我再看看boost文檔。它說：「從操作系統分配內存不是無鎖的，這使得不可能實現真正的動態大小的非阻塞數據結構。」動態大小的隊列可以自行調整大小，因爲它是單個生產者？ – user2720721

@ user2720721：請參閱編輯答案。 –

一個可變長度的無鎖隊列？

回答

相關問題