C语言 多个请求单个响应同步

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

这里的不同之处在于，首先S trywait请求有效地将其设置为 0，因此如果很多人发出信号，只有一个请求会通过。当然，互斥锁的上限为 1，因此所有额外的信号都会累积到 1，这将被trywait删除。第二个变化是，S将broadcast响应，以便所有U都将被解锁。

乍一看不错，但有问题。想象一下以下执行顺序：

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

如果我理解问题描述，问题是，有时，服务实际上不需要做任何事情来计算新结果，而只是可以"重用"以前的结果。 （我看到在发出请求之前，您不会让服务执行任何操作，因此我们不必担心它必须独立于请求进行更新。 如果是这种情况，您能否像这样修改原始服务：

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

Answer 2

我终于想出了以下解决方案。将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 的响应。不会有死锁或任何东西，除了 user2 会保持比它应得的更多的阻塞。