多個請求單個響應同步

Question

這似乎是它應該是一個衆所周知的問題，但我一直沒能找到一個很好的解決方案，這（既不是來自我的大腦也不是互聯網）。

首先，讓我們一個很簡單的例子：

mutex request <-- init to 0 
mutex response <-- init to 0 

Service thread (Guy S): 
    while not finished 
     wait(request) 
     do stuff 
     signal(response) 

Someone requestion service (Guy U): 
    signal(request) 
    wait(response) 
    do stuff with results 

到目前爲止好。 U（用戶）信號S（服務），並等待其響應。一切都很好。

現在想象一下，如果有很多用戶，請求相同的服務。現在，服務的性質使得結果隨時間變化（更確切地說週期性）。因此，如果10個用戶要求的服務更多或在同一時間少，該服務可以安全地只運行一次。

，想到的第一件事情是這樣的：

Guy S: 
    while not finished 
     wait(request) 
     do stuff 
     trywait(request) 
     broadcast(response) 

Guy U: 
    signal(request) 
    wait(response) 
    do stuff with results 

的不同，這裏是這樣的，首先Strywait S於請求時，它有效地設置爲0，因此，如果很多人已經暗示它，只有一個請求會通過。當然，互斥量的上限爲1，所以所有額外的信號累積到1，這將被trywait刪除。第二個變化是，S將broadcast的響應，這樣所有的U s就可以解鎖。

看起來不錯乍一看，但有一個問題吧。試想一下，處決的順序如下：

Guy S:    Guy U1:    Guy U2: 
wait(request) 
        signal(request) 
working 
             signal(request) 
        wait(response) 
working 
trywait(request) 
broadcast(response) 
             wait(response) 
        working 
(loop) 

如果你仔細觀察，U2被阻止，除非有人再次發送一個請求（上帝知道將來時）。很壞。

即使單個用戶，這可能發生：

Guy S:    Guy U: 
wait(request) 
        signal(request) 
working 
trywait(request) 
broadcast(response) 
        wait(response) 
(loop) 

誰能想出了一個好主意，或直接我一個已知的算法？

---

附加信息：

• S只是定期有新的數據提供，而是基於應用程序，用戶可以決定得到零星的數據（通過請求），而不是週期性的。如果用戶請求太快，我會讓他等待下一段時間，所以這不是問題。
• 我有機會，以饗讀者 - 寫鎖，條件變量，信號燈和互斥。讀者作家看起來很有希望獲得響應鎖定，但仍不清楚所有用戶何時通過了他們的wait(response)部分。

Answer 1

我終於想出了以下解決方案。有request和response信號量：

Service thread (Guy S): 
    while not finished 
     wait(request) 
     do stuff 
     users_waiting = 1 
     while (trywait(request)) 
      ++users_waiting 
     for i = 0 to users_waiting 
      signal(response) 

Someone requestion service (Guy U): 
    signal(request) 
    wait(response) 
    do stuff with results 

我不得不承認這是不完美的。請看下面的執行：

Guy S    Guy U1    Guy U2    Guy U3 
Cycle 1: 
wait(request) 
        signal(request) 
        wait(response) 
do stuff 
              signal(request) 
trywait(request) 
signal(response) 
signal(response) 
        working            
                   signal(request) 
                   wait(response) 
                   working 
              wait(response) 
Cycle 2: 
wait(request) 
do stuff 
signal(response) 
              working 

正如你所看到的，在這種情況下，用戶可以3「劫持」用戶2反應將不會有任何死鎖或任何東西，除了比它值得用戶2會留更多受阻。

Answer 2

如果我理解這個問題的描述，問題是，有時，該服務實際上並不需要做任何事情來計算一個新的結果，但也僅僅是「重用」以前的結果。 （我發現你在服務請求之前沒有做任何事情，所以我們不必擔心它必須獨立於請求更新東西。）如果是這樣的話，你可以修改原始服務：

Service thread (Guy S): 
    while not finished 
     wait(request) 
     If stuff needs to be re done 
      do stuff 
     signal(response)