基於陣列的有界緩衝區中的空元素

我有一個經典的生產者/消費者問題。用於生產的代碼是這樣的：基於陣列的有界緩衝區中的空元素

#define BUFFER_SIZE 10 
while (true) { 
    /* Produce an item */ 
    while (((in + 1) % BUFFER_SIZE) == out) 
    ; /* do nothing -- no free buffers */ 
    buffer[in] = item; 
    in = (in + 1) % BUFFER_SIZE; 
}

而且消費者：

while (true) { 
    while (in == out) 
    ; // do nothing -- nothing to consume 

    // remove an item from the buffer 
    item = buffer[out]; 
    out = (out + 1) % BUFFER_SIZE; 
    return item; 
}

這工作得很好，但問題是，當前八件充滿了和in=9和out=0，製片人坐在那裏並沒有填充最後一個（第九個）元素。這也發生在說，in=4和out=5。在任何情況下，即使一個插槽仍然爲空，一個元素仍留空，並且隊列顯示爲「已滿」。

我可以想出一些複雜的檢查，但我需要知道是否有一個乾淨的解決方案來填補整個隊列。我已經嘗試在第一次遞增，然後將item，但也會遇到類似的問題。（對於in和out，初始化爲-1也不起作用）。

來源

2012-03-01 recluze

我想知道，爲什麼你不使用任何現成的和經過良好測試的解決方案/庫中的任何一種來解決這些問題？ – PlasmaHH 2012-03-01 14:02:59

因爲我試圖教人們如何創建這些庫中的一個。因此我的問題是「最好的代碼」。我不想教我的學生從我自己的想法/經驗中得到的不良做法。徵求SO專家的意見。 :) – recluze 2012-03-01 14:04:21

哦，和我爲什麼不使用鏈表的原因相同 - 因爲我想教他們如何使用數組（以及它導致的問題）。 – recluze 2012-03-01 14:05:04

請參閱Wikipedia關於這個話題。最簡單的解決方案似乎是以下任一種：

始終保持一個插槽爲空：如果in == out則緩衝區爲空;如果in == out - 1，緩衝區已滿
將out替換爲num_unread_items;進行簡單的數學來檢索num_unread_itemsout和in

...但也有相關的計數讀&寫操作（無論是在單獨的變量或直接在in和out）的其他一些選項;或者除了當前的in和out之外追蹤最近的操作是讀還是寫，這使您可以消除緩衝區滿/緩衝區空的情況。

來源

2012-03-01 14:45:47 Chowlett

在一所大學的操作系統開發課上，我有一位兼職老師，聲稱不可能有隻能使用緩衝區中所有N元素的軟件解決方案。我證明他錯了，我決定將賽道解決方案稱爲賽道解決方案（受我喜歡跑道這一事實的啓發）。

在賽道上，您不僅限於400米比賽;一場比賽可以由一圈以上組成。如果兩名參賽選手在比賽中排在前列，則會發生什麼情況？你怎麼知道他們是否被捆綁，或者一個跑步者是否搭訕？答案很簡單：在比賽中，我們不會監測賽道上賽道上的位置;我們監測每個跑步者所走過的距離。因此，當兩名運動員在頸部和頸部時，我們可以在一條領帶和一名參賽選手搭檔的情況下消除歧義。

因此，我們的算法有一個N元素數組，並管理2N比賽。在他們完成各自的2N比賽之前，我們不會重新將生產者/消費者的計數器重新歸零。我們不允許生產者超過消費者一圈以上，我們也不允許消費者領先於生產者。其實，我們只需要監控生產者和消費者之間的距離。

的代碼如下：

Item track[LAP]; 
int consIdx = 0; 
int prodIdx = 0; 

void consumer() 
{ while(true) 
    { int diff = abs(prodIdx - consIdx); 
    if(0 < diff) //If the consumer isn't tied 
    { track[consIdx%LAP] = null; 
     prodIdx = (prodIdx + 1) % (2*LAP); 
    } 
    } 
} 

void producer() 
{ while(true) 
    { int diff = (prodIdx - consIdx); 
    if(diff < LAP) //If prod hasn't lapped cons 
    { track[prodIdx%LAP] = Item();  //Advance on the 1-lap track. 
     prodIdx = (prodIdx + 1) % (2*LAP);//Advance in the 2-lap race. 
    } 
    } 
}

這已經有一段時間，因爲我原來的問題解決了，所以這是根據我最好的回憶。希望我沒有忽略任何錯誤。希望這有助於！

來源

2012-05-22 16:23:57

基於陣列的有界緩衝區中的空元素

回答

相關問題