計數信號量的使用案例

要清楚：我主要是嵌入的東西，即它是C和微控制器中的某種實時內核;但實際上這個問題應該是平臺無關的。 Mutexes and Semaphores Demystified，以及本related answer on StackOverflow：計數信號量的使用案例

我由邁克爾·巴爾讀好文章。我清楚地明白什麼是二進制信號量，什麼是互斥量。那很棒。

但說實話，我從來不知道，還是不能懂，還有什麼所謂的計數信號量（即，最大信號計數> 1）可以。我應該在什麼情況下使用它？很久以前，在我讀過邁克爾巴爾的前述文章之前，我已經告訴過類似於「」的東西，你可以在有的時候使用它，比如有一定數量的牀的旅館房間。是信號量的最大計數，就像該房間的一些鍵號「。

這可能聽起來好聽，但實際上我從來沒有在我的編程實踐中有過這樣的情況（和無法想象任何）和邁克爾·巴爾說，這種做法是錯誤的，他似乎是正確的。

然後，我讀過的文章後，我認爲當我有，說出來可能會被使用，某種FIFO緩存。假設緩衝區的容量是10個元素，我們有兩個任務：A（生產者）和B（消費者）。然後：

信號量的最大數應該設置爲10;
當A希望將數據放入緩衝區，它signal S中的信號。
當B想要從緩衝區獲取數據時，它是wait的信號量。

好，但它不工作：

如果A試圖把新的數據到FIFO，但沒有房呢？它如何等待這個地方：它應該在撥出新數據之前撥打signal（並且signal然後應該能夠等到最大計數爲<最大計數）？如果是這樣，信號量將在數據實際存入FIFO之前發出，這是錯誤的。
信號量不足以實現正確的同步：FIFO本身也需要同步。然後，它產生了經典的TOCTTOU問題：有一段時間信號量已經被髮送或等待，但是FIFO尚未被修改。

那麼，我應該什麼時候使用那個野獸，計數信號量呢？

來源

2014-10-06 Dmitry Frank

「經典」的例子是，確實是，生產者 - 消費者隊列。

無界隊列需要一個信號量（對隊列條目進行計數）和一個受互斥鎖保護的線程安全隊列（或等效的無鎖線程安全隊列）。信號量初始化爲零。生產者鎖定互斥鎖，將對象推入隊列，解鎖互斥鎖併發出信號。消費者等待信號量，鎖定互斥鎖，彈出對象並解鎖互斥鎖。

一個有界的隊列需要兩個信號量（一個'count'來計數條目，另一個'可用'來計算可用空間）和一個互斥體保護的線程安全隊列（或者等效的無鎖定線程 - 安全隊列）。'count'被初始化爲零，'可用'爲空隊列中的空閒空間數量。生產者等待'可用'，鎖定互斥鎖，將對象推入隊列，解鎖互斥鎖併發出'計數'信號。消費者等待'計數'，鎖定互斥鎖，彈出對象，解鎖互斥鎖併發出'可用'信號。

這是一個信號量的經典用途，並一直存在，因爲永遠，（自從Dijkstra，無論如何:)。它已經嘗試了數十億次，並且對於任何數量的生產者/消費者都可以正常工作。

沒有TOCTTOU問題，沒有角落案例，沒有比賽。

'互斥'功能可能由另一個信號量提供，初始化爲1.這允許'兩個信號量'無界，'三個信號量'有界實現。

來源

2014-10-06 18:25:22

好吧，從生產者P1完成等待「可用」並鎖定互斥鎖的那一刻起，所以，可能有其他生產者P2中斷了這個序列（並首先鎖定了互斥體）。然後，P1鎖定互斥鎖，但隊列已滿，P1必須解鎖互斥鎖並再次等待「可用」。這真的很好嗎？哇，只有一個數據隊列的三個對象。我使用的實時內核（TNeoKernel：https：//bitbucket.org/dfrank/tneokernel）提供了提供原子等待和放置數據以及原子等待和獲取數據操作的數據隊列。 – 2014-10-07 08:56:52

好吧，從生產者P1完成等待「可用」並鎖定互斥鎖的那一刻起，因此，在這種情況下，可能有其他生產者P2中斷了該序列（並且先鎖定互斥體）'，因爲這兩個線程都從'可用'信號量獲得了單元，所以在該隊列中必須有兩個空閒空間，所以兩者線程可以推送他們的對象而不會溢出隊列。您建議的實時內核 - 它允許與任意數量的生產者/消費者進行阻塞，有界的隊列？ – 2014-10-08 02:32:37

此外，你可以用'無鎖'隊列替換'簡單隊列和互斥'。只要無鎖隊列類對於多個生產者和消費者是無條件安全的。 – 2014-10-08 02:37:43

我想這可能可能會使用，當我有，比如說，某種FIFO緩衝區。假設緩衝區的容量是10個元素，我們有兩個任務：A（生產者）和B（消費者）。然後：

信號量的最大數應該設置爲10;

當A想要將數據放入緩衝區時，它會發出信號燈信號。

當B想從緩衝區獲取數據時，它等待信號量。

這不是信號量在生產者 - 消費者場景中使用的方式。標準解決方案是使用兩個計數信號量，一個用於空槽（初始化爲可用槽數），另一個用於填充槽（初始化爲0）。

生產者嘗試分配空插槽放入項目，因此它們以分配給空插槽的信號量開始wait -ing。消費者嘗試「分配」（獲得）已填充的插槽，因此他們從分配給已填充插槽的信號量開始wait。

完成他們的工作後，他們都會發出另一個信號量的信號，因爲他們分別將空插槽從空變爲空，並且從空變爲空。

標準解決方案：

semaphore mutex = 1; 
semaphore filled = 0; 
semaphore empty = SIZE; 

producer() { 
    while (true) { 
     item = produceItem(); 
     wait(empty); 

     wait(mutex); 
     putItemIntoBuffer(item); 
     signal(mutex); 

     signal(filled); 
    } 
} 

consumer() { 
    while (true) { 
     wait(filled); 

     wait(mutex); 
     item = removeItemFromBuffer(); 
     signal(mutex); 

     signal(empty); 
     consumeItem(item); 
    } 
}

我覺得計數信號在這種情況下，服好務。

另一個，也許更簡單，例如可以使用避免了哲學家就餐情景僵局計數信號。只有當所有的哲學家同時坐下並選擇他們（比如說）左叉時，纔會發生死鎖，因爲不允許他們全部同時進入餐廳，所以可以避免死鎖。這可以通過將計數信號量（enter）初始化爲小於哲學家數量來實現。

一個哲學家的協議變爲：

wait(enter) 

wait(left_fork) 
wait(right_fork) 
eat() 
signal(left_fork) 
signal(right_fork) 

signal(enter)

這確保了所有哲學家不能在餐廳同時。

來源

2014-10-08 09:29:24 xxa

計數信號量的使用案例

回答

相關問題