6

比較とスワップ関数を使用して、変数をアトミックに交換できますか? x86_64 RedHat Linux、特に __sync ビルトインで gcc 経由で C/C++ を使用しています。例：

   int x = 0, y = 1; 
   y = __sync_val_compare_and_swap(&x, x, y);

これは、x が &x と x; の間で変化できるかどうかにかかっていると思います。たとえば、&x が操作を構成する場合、x が引数で &x と x の間で変化する可能性があります。上記の暗黙の比較は常に真であると仮定したいと思います。私の質問は、私ができるかどうかです。明らかに CAS の bool バージョンがありますが、古い x を y に書き込むことができません。

より便利な例は、リンクされたリストの先頭に挿入または削除することです (gcc はポインター型をサポートすると主張しているので、それが elem と head であると仮定します):

   elem->next = __sync_val_compare_and_swap(&head, head, elem); //always inserts?
   elem = __sync_val_compare_and_swap(&head, head, elem->next); //always removes?

参照: http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html

4

3 に答える 3

3

操作は、実際には新しい値を保存先に保存しない可能性があります。これは、しようとしているのと同時に値を変更する別のスレッドと競合するためです。CAS プリミティブは、書き込みが発生することを保証しません。値が既に期待どおりである場合にのみ、書き込みが発生します。プリミティブは、値が期待どおりでない場合、正しい動作が何であるかを知ることができないため、その場合は何も起こりません。戻り値をチェックして、操作が機能したかどうかを確認して問題を修正する必要があります。

だから、あなたの例：

elem->next = __sync_val_compare_and_swap(&head, head, elem); //always inserts?

必ずしも新しい要素を挿入するとは限りません。別のスレッドが同時に要素を挿入すると、競合状態が発生し、このスレッドの呼び出しが__sync_val_compare_and_swap()更新されない可能性がありますhead(ただし、正しく処理すれば、このスレッドの要素も他のスレッドの要素も失われません)。

ただし、そのコード行には別の問題があります。更新されたとしても、挿入された要素を指すhead短い瞬間がありますheadが、その要素のnextポインターはリストの前のヘッドを指すように更新されていません。その瞬間に別のスレッドが急襲してリストをたどろうとすると、悪いことが起こります。

リストを正しく更新するには、そのコード行を次のように変更します。

whatever_t* prev_head = NULL;
do {
    elem->next = head;  // set up `elem->head` so the list will still be linked 
                        // correctly the instant the element is inserted
    prev_head = __sync_val_compare_and_swap(&head, elem->next, elem);
} while (prev_head != elem->next);

またはbool、もう少し便利だと思うバリアントを使用します。

do {
    elem->next = head;  // set up `elem->head` so the list will still be linked 
                        // correctly the instant the element is inserted
} while (!__sync_bool_compare_and_swap(&head, elem->next, elem));

ちょっと醜いので、正しく理解できていることを願っています (スレッドセーフ コードの詳細につまずくのは簡単です)。関数でラップする必要がありinsert_element()ます (または、適切なライブラリを使用することをお勧めします)。

ABA 問題への対処:

ABAの問題は、この「リストの先頭に要素を追加する」コードに関連しているとは思いません。Xスレッドがオブジェクトをリストに追加しようとしていてelem->next = head、それが実行されたときにhead値があるとしましょうA1。

次に、__sync_val_compare_and_swap()が実行される前に、別のスレッドのセットが来て、次のようになります。

  • を指摘してA1、リストから削除しますheadB
  • オブジェクトに対して何でも行いA1、それを解放します
  • A2たまたま同じアドレスにあるA1別のオブジェクトを割り当てます
  • A2をリストに追加するのでhead、A2

A1とは同じ識別子/アドレスを持っているためA2、これは ABA 問題のインスタンスです。

ただし、オブジェクトを追加するスレッドは、開始時とは異なるオブジェクトへXのポイントを気にしないため、この場合は問題ではありません。気にするのは、いつキューに入れられるかだけです。headX

  • リストは一貫しており、
  • リスト上のオブジェクトが失われていない
  • X(このスレッドによって) リストに追加された以外のオブジェクトはありません
于 2010-06-04T16:15:50.197 に答える
0

インターロック比較交換ではなく、インターロック交換プリミティブを探しているようです。これにより、無条件に保持レジスタがターゲット メモリ ロケーションとアトミックにスワップされます。

ただし、 への割り当て間の競合状態の問題はまだありますy。がローカルの場合もありyますが、その場合は安全ですが、xとの両方yが共有されている場合は大きな問題があり、解決するにはロックが必要になります。

于 2013-10-04T20:28:11.673 に答える
0

いいえ。x86 の CAS 命令は、レジスタから値を取得し、それをメモリ内の値と比較/書き込みします。

2 つの変数をアトミックに交換するには、2 つのメモリ オペランドを使用する必要があります。

と の間でx変更できるかどうかは? はい、もちろん可能です。&xx

がなくても&、変わる可能性があります。

のような関数でも、Foo(x, x)x の 2 つの異なる値を取得できます。これは、コンパイラが関数を呼び出すために次のことを行う必要があるためです。

  • x の値を取得し、呼び出し規則に従って、最初のパラメーターの位置に格納します
  • x の値を取得し、呼び出し規則に従って、2 番目のパラメーターの位置に格納します。

これら 2 つの操作の間に、別のスレッドが の値を簡単に変更できますx。

于 2010-06-04T15:39:08.257 に答える