尋找在C右環形緩衝器實現

我尋找在C語言的環形緩衝器實現（或僞代碼）具有以下特徵：尋找在C右環形緩衝器實現

多個生產者單個消費者圖案（MPSC）
消費者塊對空
生產者阻斷全
無鎖（我期望高爭）

到目前爲止我我一直只使用SPSC緩衝區 - 每個生產者一個 - 但我想避免消費者連續旋轉以檢查所有輸入緩衝區上的新數據（也許是爲了擺脫我係統中的一些編組線程）。

我在英特爾機器上爲Linux開發。

2012-09-04 ziu

我不知道你在做什麼環境，但是在Win32中，你可以使用WaitForMultipleObjects讓消費者一下子等待所有的隊列而不旋轉。 –

我很抱歉，我沒有提到我主要在Linux上工作 – ziu

爲防萬一您不能得到真正的答案，使用以下命令同步多個緩衝區將會輕而易舉：http://neosmart.net/ blog/2011/waitformultipleobjects-and-win32-events-for-linux-and-read-write-locks-for-windows/ –

我想我有你在找什麼。它是一個無鎖環形緩衝區實現，它阻止生產者/消費者。你只需要訪問原子基元 - 在這個例子中，我將使用gcc的sync函數。

它有一個已知的錯誤 - 如果你超過緩衝區超過100％，它不能保證隊列仍然是FIFO（它仍然會處理它們全部）。

這實現依賴於讀/寫緩衝器的元件作爲一個原子操作（這是相當多保證指針）

struct ringBuffer 
{ 
    void** buffer; 
    uint64_t writePosition; 
    size_t size; 
    sem_t* semaphore; 
} 

//create the ring buffer 
struct ringBuffer* buf = calloc(1, sizeof(struct ringBuffer)); 
buf->buffer = calloc(bufferSize, sizeof(void*)); 
buf->size = bufferSize; 
buf->semaphore = malloc(sizeof(sem_t)); 
sem_init(buf->semaphore, 0, 0); 

//producer 
void addToBuffer(void* newValue, struct ringBuffer* buf) 
{ 
    uint64_t writepos = __sync_fetch_and_add(&buf->writePosition, 1) % buf->size; 

    //spin lock until buffer space available 
    while(!__sync_bool_compare_and_swap(&(buf->buffer[writePosition]), NULL, newValue)); 
    sem_post(buf->semaphore); 
}  

//consumer 
void processBuffer(struct ringBuffer* buf) 
{ 
    uint64_t readPos = 0; 
    while(1) 
    { 
     sem_wait(buf->semaphore); 

     //process buf->buffer[readPos % buf->size] 
     buf->buffer[readPos % buf->size] = NULL; 
     readPos++; 
    } 
}

來源

2012-09-05 05:47:27 charliehorse55

這個例子很有趣。讓我看看我是否理解得很好：索引增量和寫入是無鎖的，而當您使用信號形式的鎖來鎖定消費者時，無需消耗任何東西。雖然我不明白如何溢出這個緩衝區。此外，您是否在預計紡紗時間非常短的系統中使用此結構？紡紗環路的影響如何？ – ziu

您可以通過寫入數據的速度超過可以處理的速度來溢出緩衝區。最終，寫指數會出現並「傳遞」讀者。在這一點上，作者必須等待自旋鎖等待讀者追上（否則它將覆蓋緩衝區中的數據）。如果您將隊列溢出超過100％，則會發生該錯誤。在這種情況下，您有多個線程在等待自旋鎖中等待緩衝區變爲可用。不能保證哪個線程先寫入隊列。 – charliehorse55

重寫上面的循環不會更簡單，如下所示：（0） while while（1） {__ sync_bool_compare_and_swap（＆（buf-> buffer [writePosition]），NULL，newValue）== false）; sem_post（buf-> semaphore）; 休息; }' – ziu

參見liblfds，無鎖MPMC ringbuffer。它根本不會阻塞—無鎖數據結構不傾向於這樣做，因爲被鎖定的點是爲了避免阻塞; 你需要處理這個，當數據結構回來給你一個NULL —返回NULL如果你試圖讀空，但不符合你的要求時，寫滿;在這裏，它會扔掉最古老的元素，並給你的寫作。

但是，只需要稍作修改即可獲得該行爲。

但可能有更好的解決方案。循環緩衝區中棘手的部分是完全獲取最早的元素並重新使用它。你不需要這個。我認爲你可以採用SPSC內存屏障環形緩衝區並使用原子操作重寫它。這將是批次的更高性能，即liblfds（它是隊列和堆棧的組合）中的MPMC環緩衝區。

來源

2012-09-07 07:39:47

到目前爲止，我的SPSC實現相當簡單：它只依賴本地和全局位置計數器來同步編寫器和讀取器（本地計數器用於批量處理元素的推/拉和減少錯誤共享）。條件變量已經到位以減少旋轉（如果沒有數據可用，則沒有別的事情可做/如果目的地是滿的，背壓是不可避免的）。如果沒有適當的內存障礙，我的實現將不適用於另一種架構。請問您最後一點的細節？最後，環形緩衝區將始終是SPSC，對吧？ – ziu

有一個着名的SPSC循環緩衝區，例如在Linux內核中使用，它只使用內存屏障，當緩衝區滿或空時返回NULL。我猜想可以通過使用原子操作來製作MPMC。 – 2012-09-08 22:24:36

尋找在C右環形緩衝器實現

回答

相關問題