5

単一のスレッドに投稿されて処理される複数のスレッドからの要求を含むリンクリストの形式でCで記述されたロックレスキューがあります。数時間のストレスの後、最後のリクエストの次のポインタがそれ自体を指すようになり、無限ループが作成され、処理スレッドがロックされます。

アプリケーションはLinuxとWindowsの両方で実行されます（そして失敗します）。私はWindowsでデバッグしており、InterlockedCompareExchangePointerCOMPARE_EXCHANGE_PTRにマップしています。

これは、リクエストをリストの先頭にプッシュするコードであり、いくつかのスレッドから呼び出されます。

void push_request(struct request * volatile * root, struct request * request)
{
    assert(request);

    do {
        request->next = *root;
    } while(COMPARE_EXCHANGE_PTR(root, request, request->next) != request->next);
}

これは、リストの最後からリクエストを取得するコードであり、それらを処理する単一のスレッドによってのみ呼び出されます。

struct request * pop_request(struct request * volatile * root)
{
    struct request * volatile * p;
    struct request * request;

    do {
        p = root;
        while(*p && (*p)->next) p = &(*p)->next; // <- loops here
        request = *p;
    } while(COMPARE_EXCHANGE_PTR(p, NULL, request) != request);

     assert(request->next == NULL);

     return request;
}

でテールポインタを処理する必要があるという複雑さを避けたかったので、テールポインタを使用していないことに注意してくださいpush_request。ただし、問題はリストの最後を見つける方法にあるのではないかと思います。

リクエストをキューにプッシュする場所はいくつかありますが、それらはすべて一般的に次のように見えます。

// device->requests is defined as struct request * volatile requests;
struct request * request = malloc(sizeof(struct request));
if(request) {
    // fill out request fields
    push_request(&device->requests, request);
    sem_post(device->request_sem);
}

リクエストを処理するコードはそれ以上のことを行っていますが、本質的にはループでこれを行います。

if(sem_wait_timeout(device->request_sem, timeout) == sem_success) {
    struct request * request = pop_request(&device->requests);
    // handle request
    free(request);
}

また、各操作の前後で重複がないかリストをチェックする関数を追加しましたが、このチェックによってタイミングが変わるので、失敗することはありません。（これを書いている間、私はそれが壊れるのを待っています。）

ぶら下がっているプログラムを壊すと、ハンドラースレッドpop_requestはマークされた位置でループします。1つ以上のリクエストの有効なリストがあり、最後のリクエストの次のポインタがそれ自体を指しています。リクエストキューは通常短く、10を超えることはありません。また、デバッガーでこの障害を確認できたのは1回と3回だけです。

私はこれをできる限り考え、同じリクエストを2回プッシュしない限り、リスト内でループが発生することは決してないはずだという結論に達しました。私はこれが決して起こらないと確信しています。また、（完全ではありませんが）ABA問題ではないこともかなり確信しています。

同時に複数のリクエストをポップする可能性があることは知っていますが、これはここでは無関係であると信じており、それが発生するのを見たことがありません。（これも修正します）

どうすれば関数を壊すことができるかについて、長く懸命に考えましたが、ループに陥る方法がわかりません。

だから問題は：誰かがこれがどのように壊れることができるかを見ることができますか？誰かがこれができないことを証明できますか？

最終的に私はこれを解決します（おそらくテールポインタまたは他の解決策を使用することによって-ポストするスレッドはロックされるべきではないのでロックは問題になりますが、私は手元にRWロックを持っています）が、それを確認したいと思いますリストを変更すると、実際に私の問題が解決します（タイミングが異なるために問題が発生する可能性が低くなります）。

4

1 に答える 1

8

微妙ですが、競合状態があります。

1つの要素を含むリストから始めreq1ます。だから私たちは持っています：

device->requests == req1;
req1->next == NULL;

ここで、新しい要素をプッシュし、req2同時にキューをポップしようとします。のプッシュreq2が最初に始まります。whileループ本体が実行されるため、次のようになります。

device->requests == req1;
req1->next == NULL;
req2->next == req1;

次にCOMPARE_EXCHANGE_PTR実行するので、次のようになります。

device->requests == req2;
req1->next == NULL;
req2->next == req1;

...そしてCOMPARE_EXCHANGE_PTR()戻り値req1。さて、この時点で、条件での比較の前にwhile、プッシュが中断され、ポップが実行を開始します。

ポップは正しく完了し、ポップオフしreq1ます。つまり、次のようになります。

device->requests == req2;
req2->next == NULL;

プッシュが再開されます。request->next比較を行うためにフェッチするようになりました-そして、の新しい値でreq2->nextある。をフェッチしますNULL。と比較req1しNULL、比較は成功し、whileループが再び実行され、次のようになります。

device->requests == req2;
req2->next == req2;

今回はテストが失敗し、whileループが終了し、ループが作成されます。

これで修正されるはずです：

void push_request(struct request * volatile * root, struct request * request)
{
    struct request *oldroot;

    assert(request);

    do {
        request->next = oldroot = *root;
    } while(COMPARE_EXCHANGE_PTR(root, request, oldroot) != oldroot);
}
于 2010-04-27T06:07:55.727 に答える