9

LWARXおよびSTWCX（PowerPCプロセッサにある）と同等のもの、またはx86プラットフォームに同様の機能を実装する方法を探しています。また、そのようなことを知るのに最適な場所はどこですか（つまり、ロック/待機なしのプログラミングのための優れた記事/ Webサイト/フォーラム）。

編集
CAS（コンペアアンドスワップ）操作を探しているだけであると想定されているため、詳細を説明する必要があると思います。私がやろうとしているのは、複数のスレッドからアクセスして変更できるスマートポインターを使用して、ロックフリーの参照カウントシステムを実装することです。基本的に、x86プロセッサに次の関数を実装する方法が必要です。

int * IncrementAndRetrieve（int ** ptr）
{{
  int val;
  int * pval;
  行う
  {{
    //値へのポインタをフェッチします
    pval = * ptr;

    // NULLの場合は、スマートポインタであるNULLを返します
    //その後もNULLになります
    if（pval == NULL）
      NULLを返します。

    //参照カウントを取得します
    val = lwarx（pval）;

    //値を取得したポインタを確認します
    //'ptr'によって参照されるものと同じです
    if（pval！= * ptr）
      継続する;

    //他のスレッドがある場合は、「stwcx」を介して参照カウントをインクリメントします
    //壊れる可能性のあることは何でもしたので、
    //失敗して再試行します
  } while（！stwcx（pval、val + 1））;
  pvalを返します。
}

これを実現するには、LWARXとSTWCXをかなり正確に模倣するものが本当に必要です（これまでにx86で見つけたCompareExchange、スワップ、または追加関数を使用してこれを行う方法がわかりません）。

ありがとう

4

6 に答える 6

11

Michael が述べたように、おそらく探しているのはcmpxchg命令です。

ただし、これを実現する PPC 方式はLoad Link / Store Conditional (LL/SC) として知られているのに対し、x86 アーキテクチャはCompare And Swap (CAS)を使用していることを指摘しておくことが重要です。LL/SC は CAS よりも強力なセマンティクスを持っており、条件付きアドレスの値を変更すると、他の変更によって値がロードの条件と同じ値に置き換えられたとしても、ストアが失敗します。一方、CAS はこの場合成功します。これは ABA 問題として知られています (詳細については、CAS リンクを参照してください)。

x86 アーキテクチャでより強力なセマンティクスが必要な場合は、x86s double-width compare-and-swap (DWCAS) 命令cmpxchg8bを使用するかcmpxchg16b、x86_64 の下で近似できます。これにより、通常の単語だけでなく、連続する 2 つの「自然なサイズの」単語を一度にアトミックに交換できます。基本的な考え方は、2 つの単語の 1 つに対象の値が含まれ、もう 1 つの単語には常に増加する「突然変異カウント」が含まれているというものです。これで問題が技術的に解消されるわけではありませんが、試行間でミューテーション カウンターが折り返される可能性は非常に低いため、ほとんどの目的の妥当な代替手段となります。

于 2009-07-20T12:45:03.883 に答える
2

x86は、PPCのように「楽観的同時実行性」を直接サポートしていません。むしろ、x86の同時実行性のサポートは、「ロックプレフィックス」に基づいています。ここを参照してください。（XCHGなどのいわゆる「アトミック」命令は、アセンブリコードプログラマーが実際にコード化したかどうかに関係なく、本質的にLOCKプレフィックスをアサートすることによって実際にアトミック性を取得します）。外交的に言えば、それは正確に「防爆」ではありません（実際、それはかなり事故を起こしやすいと思います;-)。

于 2009-07-18T16:30:21.257 に答える
1

64ビットを使用していて、ヒープを1 TBに制限している場合は、カウンターを未使用の上位24ビットにパックできます。ワードアラインされたポインタがある場合は、下の5ビットも使用できます。

int* IncrementAndRetrieve(int **ptr)
{
  int val;
  int *unpacked;
  do
  {   
    val = *ptr;
    unpacked = unpack(val);

    if(unpacked == NULL)
      return NULL;
    // pointer is on the bottom
  } while(!cas(unpacked, val, val + 1));
  return unpacked;
}
于 2009-09-26T17:18:07.690 に答える
1

あなたはおそらくcmpxchgファミリーの指示を探しています。

同等の動作を得るには、これらの前にロック命令を付ける必要があります。

利用可能なものの概要については、こちらをご覧ください。

あなたはおそらくこれに似たものになってしまうでしょう：

mov ecx,dword ptr [esp+4]
mov edx,dword ptr [esp+8]
mov eax,dword ptr [esp+12]
lock cmpxchg dword ptr [ecx],edx
ret 12

あなたはこの論文を読むべきです...

編集

更新された質問に答えて、Boost shared_ptrのようなことをしたいとお考えですか？もしそうなら、そのコードとそのディレクトリ内のファイルを見てください-それらは間違いなくあなたを始めるでしょう。

于 2009-07-18T16:31:23.923 に答える
1

LWARX と STWCX がキャッシュ ライン全体を無効にするかどうかはわかりませんが、CAS と DCAS は無効です。つまり、大量のメモリ (独立した "ロック可能な" ポインターごとに 64 バイト) を破棄する意思がない限り、ソフトウェアを本当にストレスにさらしている場合、大きな改善は見られません。私がこれまでに見た中で最良の結果は、人々が意識的に 64b を犠牲にし、その周りに構造を計画し (競合の対象にならないものを詰め込み)、すべてを 64b 境界に揃え、明示的な読み取りと書き込みのデータバリアを使用したときでした。キャッシュ ラインの無効化には約 20 ～ 100 サイクルのコストがかかる可能性があり、実際のパフォーマンスの問題が大きくなり、ロック回避だけになります。

また、制御されたリーク（コードを論理的な「リクエスト処理」に分割できる場合-1つのリクエストが「リーク」し、最後にすべてのメモリバルクを解放する場合）またはデータ化された割り当て管理のいずれかを管理するために、さまざまなメモリ割り当て戦略を計画する必要があります。競合している 1 つの構造が、同じ構造/コレクションの要素によって実現されたメモリを受信しないようにします (ABA を防ぐため)。その中には非常に直感に反するものもありますが、それはそれであるか、GC の代償を払っているかのどちらかです。

于 2010-08-10T13:34:49.237 に答える
0

あなたがやろうとしていることはあなたが期待するようには機能しません。上記で実装したことは、InterlockedIncrement関数（Win32関数;アセンブリ：XADD）を使用して実行できます。

コードが思ったとおりに動作しない理由は、別のスレッドが、stwcxを無効にすることなく、*ptrとstwcxの2回目の読み取りの間で値を変更できるためです。

于 2009-07-25T15:30:34.420 に答える