6

2 つのスレッドを持つプログラムを想像してください。次のコードを実行しています (CAS はCompare and Swapを指します)。

// Visible to both threads
static int test;

// Run by thread A
void foo()
{
    // Check if value is 'test' and swap in 0xdeadbeef
    while(!CAS(&test, test, 0xdeadbeef)) {}
}

// Run by thread B
void bar()
{
    while(1) {
        // Perpetually atomically write rand() into the test variable
        atomic_write(&test, rand());
    }
}

0xdeadbeef が「テスト」に書き込まれないように、スレッド B がスレッド A の CAS を永続的に失敗させる可能性はありますか? それとも、自然なスケジューリングのジッタは、実際にはこれが決して起こらないことを意味するのでしょうか? スレッド A の while ループ内で何らかの作業が行われた場合はどうなるでしょうか。

4

2 に答える 2

6

理論的な問題として、はい。このように2つのスレッドをロックステップで実行することができれば

    時間 スレッド A スレッド B
    ---- -------- --------
     || キャス
     || atomic_write
     || キャス
     \/ atomic_write

その場合、CAS は決して true を返しません。

実際には、これはスレッドが CPU/コアを共有している場合には決して発生せず、スレッドが異なる CPU またはコアで実行されている場合には発生しそうにありません。実際には、それが数サイクル以上発生する可能性は 非常に低く、天文学的にスケジューラのクォンタム以上で発生する可能性は低いです。

そして、それはこのコードの場合です

void foo()
{
    // Check if value is 'test' and swap in 0xdeadbeef
    while(!CAS(&test, test, 0xdeadbeef)) {}
}

の現在の値を取得し、testそれを比較しtestて変更されたかどうかを確認します。現実の世界では、CAS の反復は、実際の作業を行うコードによって分離されます。このvolatileキーワードは、コンパイラーがまだレジスターに持っている可能性のあるコピーがまだ有効であると想定するのではなく、CAS を呼び出す前にコンパイラーがテストをフェッチしたことを保証するために必要です。

または、テストする値は、テストの現在の値ではなく、最後の既知の値のようなものになります。

言い換えれば、このコード例は理論のテストですが、実際にはこのように CAS を使用しないので、これを失敗させることができたとしても、それを使用したときにどのように失敗するかを必ずしも示しているわけではありません。現実世界のアルゴリズム。

于 2010-02-07T00:50:57.050 に答える
2

そのような場合、飢餓は確かに起こり得ます。ウィキペディアのページを引用すると、

また、広く利用可能なアトミック条件付きプリミティブである CAS および LL/SC では、スレッド数に比例してメモリ コストが増加することなく、多くの一般的なデータ構造のスタベーション フリー実装を提供できないことも示されています。したがって、待機のないアルゴリズムは、研究と実際の両方でまれです。

(数学的な証明については、問題のページのリンクを参照してください)。

于 2010-02-07T00:30:05.277 に答える