1

Interlocked.Exchangeの正しい使用法を理解しようとしているので、追加および削除機能を備えた単純なソート済みLinkedListを実装しています。

これがスレッドセーフリストではなかった場合、明らかに挿入ポイントを見つけるには、次のようなものを使用して、挿入する正しいポイントを見つけてから、新しいノードを見つける必要があります。

    public void Insert(int newValue)
    {
        var prev = _header;
        Node curr = _header.Next;

        while(curr != null && curr.value > newValue )
        {
            prev = curr;
            curr = curr.Next;
        }
        var newNode = new Node(newValue, curr);
        prev.Next = newNode;
    }

以下は、同時リストに対してこれを行う必要がある方法についての私の見解です。Interlocked.Exchangeが多すぎますか？これがなくても、インサートはスレッドセーフですか？数百または数千のインターロック操作がパフォーマンスの低下を引き起こしますか？

    public void InsertAsync(int newValue)
    {
        var prev = _header;
        Node curr = new Node(0, null);
        Interlocked.Exchange(ref curr, _header.Next);

        while (curr != null && curr.value > newValue)
        {
            prev = Interlocked.Exchange(ref curr, curr.Next);
        }
        //need some locking around prev.next first, ensure not modified/deleted, etc..
        //not in the scope of this question.
        var newNode = new Node(newValue, prev.Next);
        prev.Next = newNode;
    }

たとえば、curr = curr.nextはアトミック読み取りであることを理解していますが、特定のスレッドがインターロックなしでcurr.nextの最新の値を読み取ることを確認できますか？

4

3 に答える 3

5

メソッドを使用すると、次のInterlocked2 つのことが行われます。

  1. 通常はアトミックではない一連の操作を実行し、それらを効果的にアトミックにします。Exchangeと同等のことを行う場合:var temp = first; first=second; return temp;ただし、実行中にいずれかの変数が別のスレッドによって変更されるリスクはありません。
  2. メモリバリアを導入します。コンパイラ、ランタイム、またはハードウェアの最適化により、技術的には共有メモリ内にある値のローカル "コピー" を持つさまざまなスレッドが発生する可能性があります (通常は変数のキャッシュの結果として)。これにより、あるスレッドが別のスレッドでの書き込みの結果を「見る」のに長い時間がかかる可能性があります。メモリバリアは基本的に、同じ変数のこれらの異なるバージョンをすべて同期します。

だから、あなたのコードに具体的に。2 番目の解決策は、実際にはスレッド セーフではありません。個々のInterlocked操作はそれぞれアトミックですが、さまざまなInterlocked呼び出しに対する任意の数の呼び出しはアトミックではありません。メソッドが行っているすべてのことを考えると、クリティカル セクションは実際にははるかに大きくなります。lockコードのセクションへのアクセスを 1 つのスレッドのみに制限するには、 または別の同様のメカニズム (つまり、セマフォまたはモニター) を使用する必要があります。あなたの特定のケースでは、メソッド全体がクリティカルセクションであると思います。本当に慎重に行えば、いくつかの小さなクリティカル ブロックを作成できるかもしれませんが、結果として競合状態が発生しないようにすることは非常に困難です。

パフォーマンスに関しては、まあ、このままではコードが動かないので、パフォーマンスは関係ありません。

于 2012-10-19T17:38:57.283 に答える
4

ロックフリー リンク リストの実装は、これよりもかなり複雑です。しないことを強くお勧めします。代わりに、普通の古いモニターを使用してください。これが興味のためだけである場合は、ロックフリーアルゴリズムについて調査する必要があります。

あなたの質問にもっと直接的に答えるために、インターロック操作のコストは、変数に対する競合の量に依存します。競合のないシナリオ (シングル スレッドなど) では、コストはごくわずかです。同時アクセス数が増えると、コストが増加します。その理由は、連動操作は実際にはロックフリーではないからです。ソフトウェアロックではなく、ハードウェアロックを使用しているだけです。このため、ロックフリー アルゴリズムは、多くの場合、直感的に期待するほどには機能しません。

于 2012-10-19T17:41:32.003 に答える
3

割り当てを保護しているだけですが、とにかくアトミックです。Exchanged が実際に成功したかどうかを確認する必要があります。

しかし、それでもリストをスレッドセーフにすることはできません。同時スレッドは、挿入ポイントの前に newValue よりも大きな新しい値を挿入する可能性があります。リストが壊れてしまう可能性さえあると思います。

于 2012-10-19T17:36:50.713 に答える