沒有優先級反轉的環形緩衝區

我有一個高優先級進程，需要將數據傳遞給低優先級進程。我寫了一個基本的環形緩衝區來處理數據的傳遞：沒有優先級反轉的環形緩衝區

class RingBuffer { 
    public: 
    RingBuffer(int size); 
    ~RingBuffer(); 

    int count() {return (size + end - start) % size;} 

    void write(char *data, int bytes) { 
     // some work that uses only buffer and end 
     end = (end + bytes) % size; 
    } 

    void read(char *data, int bytes) { 
     // some work that uses only buffer and start 
     start = (start + bytes) % size; 
    } 

    private: 
    char *buffer; 
    const int size; 
    int start, end; 
};

這是問題所在。假設低優先級進程有一個oracle，告訴它需要讀取多少數據，所以不需要調用count()。然後（除非我錯過了什麼）沒有併發問題。但是，只要低優先級線程需要調用count()（高優先級線程可能想要調用它以檢查緩衝區是否太滿），則count（）中的數學或更新爲結束不是原子，引入了一個錯誤。

我可以在開始和結束的訪問周圍放置一個互斥量，但如果高優先級線程必須等待低優先級線程獲取的鎖定，則會導致優先級反轉。

我可能能夠使用原子操作工作，但我不知道有一個很好的跨平臺庫提供這些。

是否有避免這些問題的標準環形緩衝設計？

來源

2011-04-21 user168715

提供了跨平臺的原子功能是否有在平臺上的任何約束的使用？ – 2011-04-21 16:39:20

@Peter讓我們假設x86（其中IIRC 32位寫入對齊的地址是原子的），儘管越便攜越好。 – user168715 2011-04-21 17:22:36

這裏是一個等待免費的隊列http://software.intel.com/zh-cn/articles/single-producer-single-consumer-queue/ – 2011-04-21 20:41:16

你應該確定什麼，只要你堅持以下原則：

只有一個線程可以執行寫操作。
只有一個線程可以讀取。
更新和訪問start和end是原子。這可能是自動的，例如微軟指出：

簡單的讀取和寫入正確對齊的32位變量原子操作。換句話說，你的不會最終只有一個部分的變量更新;所有位以原子方式更新爲。

您允許的事實，count可能是過時的，即使你得到的價值。在讀線程中，count會返回最小值您可以依賴的值;對於寫作線程count將返回最大計數和真實計數可能會更低。

來源

2011-04-21 16:11:47

是否有編譯器將更新分爲非原子序列的步驟？也就是說，將write（）的最後一行變成'end + = bytes;結束％=大小;'？ – user168715 2011-04-21 16:19:41

編譯器可以非原子方式計算RHS，並且根據您的平臺甚至可以非原子方式存儲int（即，在8位平臺上使用兩個8位寫入來存儲16位整數）。 – 2011-04-21 16:52:56

@ user168715，如果你絕對不相信你的編譯器做正確的事情，那麼創建一個'volatile'臨時變量來保存計算，然後複製它以進行更新。 – 2011-04-21 18:22:37

Boost提供了一個循環緩衝區，但它不是線程安全的。不幸的是，我不知道有任何實施。

即將到來的C++標準將原子操作添加到標準庫中，所以它們將在未來可用，但大多數實現還不支持它們。

我沒有看到任何跨平臺的解決方案來保持count同時保持兩個線程都寫入它，除非你實現鎖定。

通常情況下，您可能會使用消息傳遞系統並強制低優先級線程請求高優先級線程進行更新或類似的操作。例如，如果低優先級線程消耗15個字節，它應該請求高優先級線程將計數減少15.

本質上，您將限制對高優先級線程的「寫入」訪問，並且只允許低優先級線程讀取。這樣，您可以避免所有鎖定，並且高優先級線程不必擔心等待寫入由底層線程完成，從而使高優先級線程真正具有高優先級。

來源

2011-04-21 16:16:45

boost::interprocess在boost/interprocess/detail/atomic.hpp

來源

2011-04-21 16:25:43

沒有優先級反轉的環形緩衝區

回答

相關問題