4

以下は、Intel CPU で GNU 組み込みの比較およびスワップを使用して実装された並行スタックで発生している問題を示す簡略化された C プログラムです。何が起こっているのかを理解するのにしばらく時間がかかりましたが、今では、アトミックな比較とスワップによって提供される保証の範囲内であることがわかります.

ノードがスタックからポップされ、変更されてからスタックに戻されると、変更された値がスタックの新しい先頭になり、破損する可能性があります。test_get のコメントは、これを引き起こすイベントの順序を説明しています。

同じノードを同じスタックで確実に複数回使用する方法はありますか? これは誇張された例ですが、変更されていないノードを gHead に返すだけでも、他のノードがリークする可能性があります。このデータ構造の元のポイントは、同じノードを繰り返し使用することでした。

typedef struct test_node {
    struct test_node *next;
    void *data;
} *test_node_p;

test_node_p gHead = NULL;
unsigned gThreadsDone = 0;

void test_put( test_node_p inMemory ) {
    test_node_p scratch;

    do {
        scratch = gHead;
        inMemory->next = scratch;
    } while ( !__sync_bool_compare_and_swap( &gHead , scratch , inMemory ) );
}

test_node_p test_get( void ) {
    test_node_p result;
    test_node_p scratch;

    do {
        result = gHead;
        if ( NULL == result ) break;
        //  other thread acquires result, modifies next
        scratch = result->next;     //  scratch is 0xDEFACED...
        //  other thread returns result to gHead
    } while ( !__sync_bool_compare_and_swap( &gHead , result , scratch ) );
    //  this thread corrupts gHead with 0xDEFACED... value

    if ( NULL == result ) {
        result = (test_node_p)malloc( sizeof(struct test_node) );
    }

    return result;
}

void *memory_entry( void *in ) {
    test_node_p node;
    int index , count = 1000;
    for ( index = 0 ; index < count ; ++index ) {
        node = test_get();
        *(uint64_t *)(node) |= 0xDEFACED000000000ULL;
        test_put( node );
    }

    __sync_add_and_fetch(&gThreadsDone,1);

    return NULL;
}

void main() {
    unsigned    index , count = 8;
    pthread_t   thread;

    gThreadsDone = 0;

    for ( index = 0 ; index < count ; ++index ) {
        pthread_create( &thread , NULL , memory_entry , NULL );
        pthread_detach( thread );
    }

    while ( __sync_add_and_fetch(&gThreadsDone,0) < count ) {}
}

8 つの論理コアでこのテストを実行しています。4 つのスレッドのみを使用する場合、問題はめったに発生しませんが、8 の場合は簡単に再現できます。Intel Core i7 を搭載した MacBook を使用しています。

これを解決したライブラリやフレームワークを使用することに興味はありません。どのように解決されたか知りたいです。ありがとうございました。

編集：

私の場合、うまくいかない2つの解決策があります。

一部のアーキテクチャは、値ではなくアドレスに対してアトミック テストを実行する ll/sc 命令ペアを提供します。同じ値であっても、アドレスへの書き込みは成功を妨げます。

一部のアーキテクチャでは、ポインター サイズより大きい比較とスワップが提供されます。これにより、モノトニックカウンターは、使用されるたびにアトミックにインクリメントされるポインターとペアになり、値が常に変化します。一部の Intel チップはこれをサポートしていますが、GNU ラッパーはありません。

これが問題のプレイバイプレイです。2 つのスレッド A と B はtest_get、 で同じ値をresult持ち、 ではない点に到達しNULLます。次に、次のシーケンスが発生します。

  1. スレッド A は比較とスワップを渡し、resultから戻ります。test_get
  2. スレッド A は、result
  3. スレッド B が逆参照resultし、スレッド A がそこに置いたものを取得します
  4. スレッド A は終了しresult、呼び出しますtest_put
  5. test_putスレッド A は結果を元に戻す際に比較とスワップを渡しますgHead
  6. スレッド B は比較に到達し、スワップインtest_getしてパスします
  7. gHeadスレッド B は、スレッド A からの値で破損しています

これは、スレッド A を変更する必要のない 3 つのスレッドを使用した同様のシナリオですresult。

  1. スレッド A は比較とスワップを渡し、resultから戻ります。test_get
  2. スレッド A はコンテンツを変更しません。result
  3. スレッド B が逆参照resultし、有効な値を取得しますscratch
  4. 無関係な値でスレッド C を呼び出しtest_put、成功する
  5. スレッド A が呼び出し、元に戻すtest_putことに成功するresultgHead
  6. スレッド B は比較に到達し、スワップインtest_getしてパスします
  7. gHeadスレッド B は、スレッド C が追加したものを漏らして破損しました

どちらのシナリオでも、問題は、スレッド B が get の比較とスワップに到達する前に、スレッド A が比較とスワップを 2 回 (get で 1 回、次に put で) 渡すことです。スレッド B が持つスクラッチの値は破棄する必要がありますが、gHead の値が正しいように見えるため、破棄する必要はありません。

実際に防止せずにこの可能性を低くする解決策は、バグの追跡を困難にするだけです。

スクラッチ変数は、アトミック命令が開始する前に結果の参照解除された値が配置される場所の単なる名前であることに注意してください。名前を削除すると、中断される可能性のある逆参照と比較の間のタイム スライスが削除されます。

アトミックとは、全体として成功または失敗することを意味することにも注意してください。問題のハードウェアでは、ポインターのアライメントされた読み取りは暗黙的にアトミックです。他のスレッドに関する限り、ポインターの半分だけが読み取られた割り込み可能ポイントはありません。

4

3 に答える 3

4

単純な評価を通じてアトミック変数にアクセスしないでください。また、あなたのような比較と交換ループの場合__sync_val_compare_and_swapは、より便利だと思います。

/* read the head atomically */
result = __sync_val_compare_and_swap(&gHead, 0, 0);
/* compare and swap until we succeed placing the next field */
while ((oldval = result)) {
   result = __sync_val_compare_and_swap(&gHead, result, result->next);
   if (oldval == result) break;
}
于 2013-06-22T07:25:45.497 に答える