帶鎖的隊列數據結構包含什麼？

Question

我想了解不同的數據結構與並行編程爲面試做準備。

我想知道是否要用鎖實現一個隊列，我必須擴展哪種功能？

我問的原因是，似乎我只需要確保一個線程在任何給定的時間都被允許訪問隊列，那還有更多嗎？

Answer 1

擴展串行數據結構以適合並行或併發編程的問題是一個棘手的問題。這不像實施和保護每個功能或方法的鎖一樣簡單;只要確保只有一個線程被允許在任何給定時間訪問/修改容器是不夠的。

例如，讓我們從標準C++庫中獲取隊列：std::queue。代碼的典型片彈出元件e出隊列q的是以下內容：

if (!q.empty()) { 
    e = q.front(); 
    q.pop(); 
} 

讓我們假設一個鎖被添加到隊列中執行和所述隊列中的每個方法在內部與鎖定保護。不幸的是，這段代碼對於併發仍然不安全。如果多個線程從隊列中彈出元素，則只要鎖在方法內部釋放，empty()的結果就變得不可靠，因爲另一個線程可能會彈出該線程之前的最後一個元素。另一個問題是兩個或多個線程可能會從front()中獲得相同的值，但是會將不同的項目排出隊列。

爲了正常工作，上面的代碼作爲一個整體應該用鎖來保護，這意味着鎖應該在隊列的外部。或者，實施上述操作的新方法應該被添加到隊列中，並且現有方法應該被移除或被宣佈爲不安全的;即容器的界面可能需要改變螺紋安全性。