多个请求单个响应同步

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)