Fober et al無鎖定FIFO隊列：多個消費者和生產者？

Question

我想知道Fober等人的論文http://nedko.arnaudov.name/soft/L17_Fober.pdf中提供的fifo隊列是否爲多用戶併產生fifo隊列。如果不是，哪個是最好記錄的多個消費者和生產者FIFO隊列？

感謝

Answer 1

是的。閱讀'3.1 Linearizability'部分 pop操作假定可能發生併發出隊。這意味着多個線程將能夠使用隊列。

Answer 2

我不知道「Fober隊列」，但已經寫了無鎖的FIFO作爲環緩衝區。 可能相對容易的是一個「無內聯鎖」隊列，這意味着讀者不會阻止編寫者，反之亦然，但是多個讀者必須被序列化並且多重編寫者也必須是。 所以它不是無鎖的，但讀者和作者之間仍然沒有鎖定/阻塞。

也許有更好的方法，甚至允許更少的鎖定，但也許這將已經幫助你。

Answer 3

我還沒有看過論文，但我在這裏做了一個大的假設：本文使用CAS（比較和交換）技術來實現併發。

鎖定免費並不意味着無障礙。 CAS的使用會阻止其他線程，但至少有一個線程會隨時「前進」。

多個生產者都寫入相同的隊列 - 這不是問題。技巧是多個消費者。如果每個消費者都必須訪問數據，那麼我會通過多個隊列來實現這些數據，並且數據將在一個隊列中處理完畢後進入下一個隊列。如果您的意思是多個消費者通過線程，那麼這將工作在上述方法