4

私は、ロックフリーの単一リンクリストを実装する方法を考えてきました。そして正直なところ、私はそれを行うための多くの防弾方法を見ていません。使用するより堅牢な方法でさえ、CASある程度のABA問題が発生することになります。

それで私は考え始めました。部分的にロックフリーのシステムは、常にロックを使用するよりも優れているのではないでしょうか。一部の操作はアトミックでロックフリーにすることができますか？それができれば、それでもスレッドセーフになるはずです。

だから、質問に。私は単純な単一リンクリストを考えています。2つの主な操作。 pushおよびpop。push常に前面に挿入します。このようなもの：

void push(int n) {
    T *p = new T;
    p->n = n;
    p->next = root;
    root = p;
}

そして、常に最初の要素を取るポップ。このようなもの：

T *pop() {
    T *p = root;
    root = root->next;
    return p;
}

明らかに、プッシュは自明ではないので、単純なロックフリーのアプローチはおそらく起こらないでしょう。しかし、ポップはおそらく実行可能に見えます。gcc-intrinsicsを使用して、私はこれについて考えました：

T *pop() {
    return __sync_lock_test_and_set(&root, root->next);
}

機能的に同等ですか？うん。ロックフリー？うん。スレッドセーフ？わからない。私の腸の反応はノーです、そしてここに理由があります。

test_and_setのパラメータの1つがメモリを逆参照する必要があるという事実が心配です。ルートがroot->nextとの間で変更された場合はどうなりますか__sync_lock_test_and_set。

このコードはこれと同等だと思います：

T *pop() {
    T *temp = root->next;
    // are we broken if a push/pop happens here?
    return __sync_lock_test_and_set(&root, temp);
}

だから、私が言ったように、私はこのコードが正しくないと思います。しかし、私が正しい結論を導き出していることを誰もが確かに言うことができます（うまく機能するものを書き留めるのは嫌です）。私が思うようにそれが実際に壊れている場合。簡単な解決策はありますか？

4

3 に答える 3

2

あなたは正しいです。root->nextC ++では、関数の引数は任意の順序で評価されますが、コンパイラーには、それがシーケンス内の不可分操作であることを知る方法がありません。

2つのスレッドを呼び出すことを検討してください。1つのスレッドがをpop()評価しroot->next、次にもう1つのスレッドがを評価root->nextし、両方がを呼び出しますtest_and_set()。これで、1つのノードのみをポップしました。

于 2010-05-24T21:11:55.693 に答える
1

2つのこと：（1）test＆setのコンセンサス番号は2のみです。このような弱い同期プリミティブの場合、特殊な命令のオーバーヘッドを発生させることなく、読み取り/書き込みメモリバリアを使用するだけで十分です。（2）ABA問題は、解決策が非常に少ない実際の問題です。ただし、CAS（32ビットシステムではcmpxchg8b、x86 / -64では64ビットシステムではcmpxchg16b）を使用すると、レジスタの上部に十分なスペースがあり、ABAが実際には発生しないほど大きなタイムスタンプを格納できます。 （かなり工夫された設定でも、1つのスレッドが数日または数週間ストールし、正確に正しいタイミングでウェイクアップする必要があります）。

ただし、リストではなく、ロックフリーキューを実装しようとしていると思います。キューはリストよりも実装がはるかに簡単です。EdyaLazan-MozesとNirShavitによる「ロックフリーFIFOキューへの楽観的なアプローチ」と、MagedM.MichaelとMichaelL.Scottによる「シンプルで高速かつ実用的な非ブロッキングおよびブロッキングコンカレントキューアルゴリズム」の論文はどちらもロックフリーキューの実装については、非常に有益でアプローチが簡単です。

ただし、ロックフリーのリンクリストを主張する場合は、MichailFomitchevとEricRuppertによる「ロックフリーのリンクリストとスキップリスト」の実装を検討してください。ダミアン・デチェフのロックフリー動的配列を調べることもできます（ウィキペディアからのリンクがあります）。

于 2010-05-24T23:41:24.587 に答える
0

の両方のバージョンでpop：

T *pop() {
    T *p = root;
    root = root->next;
    return p;
}

と

T *pop() {
    return __sync_lock_test_and_set(&root, root->next);
}

すでにエラーが発生しています。これは、想定されるルートノードから読み取る前に、リスト/スタックが空でないことを確認していないことです。

rootこれは、 test_and_setが発生する前に、次に取得するために逆参照する必要があることについて言及した問題を悪化させます。これは本質的にtest_and_then_test_and_set操作になり、and_thenは複数のステップが必要であることを示します。

popの最初のバージョンは次のとおりである必要があります。

T *pop() {
    T *p = root;
    if (root) {
        root = root->next;
    }
    return p;
}

そして、あなたが見ることができると確信しているように、これはミックスにさらに多くのステップを入れます。

于 2010-05-24T21:12:36.880 に答える