1

これはよく知られている問題のようですが、私はそれに対する良い解決策を見つけることができませんでした（私の脳からもインターネットからも）。

まず、非常に簡単な例を見てみましょう。

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人のユーザーがほぼ同時にサービスを要求した場合、サービスは1回だけ安全に実行できます。

最初に頭に浮かぶのはこれです：

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であるため、余分な信号はすべて1に累積され、。によって削除されますtrywait。2番目の変更は、すべてのがブロック解除される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)リーダーライターは応答ロックを約束しているように見えましたが、すべてのユーザーがいつ自分の部分を通過したかはまだ不明です。
4

2 に答える 2

1

If I understand the problem description, the issue is that, sometimes, the Service doesn't actually need to do anything to compute a new result, but can just "reuse" previous results. (I see that you don't have the Service do anything until a request is made, so we don't have to worry about it having to update things independently of requests.) If that is the case, could you modify the original Service like so:

Service thread (Guy S):
    while not finished
        wait(request)
        If stuff needs to be re done
            do stuff
        signal(response)
于 2012-04-05T19:42:15.047 に答える
0

I finally came up with the following solution. Having request and response as semaphores:

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

I have to admit it is not perfect. Consider the following execution:

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

As you can see, in such a case, user 3 can "hijack" response of user 2. There would be no deadlock or anything, except user2 would stay blocked more than it deserves.

于 2012-04-06T12:47:27.877 に答える