單生產者/消費者循環緩衝區，只阻止消費者

我想實現一個單一生產者和單個消費者的緩衝區，其中只有消費者可能被阻止。這裏重要的細節是，如果隊列已滿，生產者可以刪除更新。單生產者/消費者循環緩衝區，只阻止消費者

我已經考慮轉換一個等待免費的實現，但乍一看似乎沒有簡單的方法來通知消費者新數據已到達而不會丟失通知。所以，我在非常簡單的方法解決下面，使用計數信號（省略了一些錯誤處理細節的清晰度）：

Object ar[SIZE]; 
int head = 0, tail = 0; 
sem_t semItems; // initialized to 0 

void enqueue(Object o) { 
    int val; 
    sem_getvalue(&semItems, &val); 
    if (val < SIZE - 1) { 
     ar[head] = o; 
     head = (head + 1) % SIZE; 
     sem_post(&semItems); 
    } 
    else { 
     // dropped 
    } 
} 
Object dequeue(void) { 
    sem_wait(&semItems); 
    Object o = ar[tail]; 
    tail = (tail + 1) % SIZE; 
    return o; 
}

是否有與此代碼的任何安全問題？我很驚訝沒有在流行文獻中的任何地方看到它的實現。另外一個問題是sem_post()是否會阻塞（在linux下引用futex_wake()）。當然也歡迎更簡單的解決方案。

編輯：編輯代碼在閱讀器和作者之間留下空間（請參閱Mayurk的回覆）。

來源

2016-11-23 wds

我知道爲什麼你只需要阻止消費者？ –

@SumitGemini當有大量的流量時，消費者應該比生產者慢，因爲生產者會與硬件進行交談。這只是我看到的一種可能的方法，可能是隱含的CAS循環實際上使其變得更糟。 – wds

@SumitGemini剛剛遇到了一個針對本地C++信號量的提議，它更好地解釋了它：http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2043.html#SemaphoreTypes – wds

我可以看到這個實現中的一個問題。考慮以下順序。

假設緩衝區已滿，但消費者尚未啓動。所以（head = 0，tail = 0，sem_val = SIZE）。
從消費者線程調用dequeue（）。 sem_wait（）成功。所以就在這個例子中（head = 0，tail = 0，sem_val = SIZE-1）。消費者開始閱讀ar [0]。
現在有一個線程切換。從生產者線程調用enqueue（）。 sem_getvalue（）將返回SIZE-1。所以生產者在ar [0]處寫道。

基本上我認爲你需要讀寫操作的互斥鎖保護。但是添加互斥可能會阻塞這些線程。所以我不確定你是否從這個邏輯中得到預期的行爲。

來源

2016-11-23 08:30:57 MayurK

You are right ，但是通過犧牲緩衝區中的一個位置不能很容易地解決這個問題，即確保val wds

@ wds不可以。您可能隨時會遇到此問題。例子（head = 3，tail = 3，sem_val = SOMTHING）。即使在這種情況下，如果上述操作順序導致緩衝區損壞。 – MayurK

在隊列通過在信號量上發佈「發佈」之後，只能從緩衝區中的位置讀取隊列。我不明白你提到的情況會如何存在。 – wds

單生產者/消費者循環緩衝區，只阻止消費者

回答

相關問題