7

次に、compareAndSet (Java) を使用したロックフリー キューのコードを示します。

public void enq(T value) {
    Node newNode = new Node(value);
    while(true) {
        Node last = tail.get();
        Node next = last.next.get();

        if(last != tail.get())
            continue;   //???       

        if (next != null) { //improve tail
            tail.compareAndSet(last, next);
            continue;
        }

        if (last.next.compareAndSet(null, newNode)) {   //update last node
            tail.compareAndSet(last, newNode);  //update tail
            return;
        }
    }
}

public T deq() throws EmptyException {
    while(true) {
        Node first = head.get();
        Node last = tail.get();
        Node next = first.next.get();

        if(first != head.get())
            continue;   //???

        if(first == last) {
            if (next == null)
                throw new EmptyException();

            tail.compareAndSet(last, next);
            continue;
        }

        T value = next.value;
        if (head.compareAnsdSet(first, next)) {
            return value;
        }
    }
}

(head と tail はキューのメンバーです)

deq 関数と enq 関数の両方で、最初のチェックは不要に思えます。("???" でコメントしたもの) ある種の最適化のためだけにあるのではないかと思います。

ここで何か不足していますか？これらのチェックはコードの正確さに影響しますか?

(コードは「Art of Multi-processor Programming」から取られていますが、コード スタイルをリファクタリングして、ネストされた if と else を減らし、コードを同等に保ちます)

4

3 に答える 3

3

ええ、Java では、ガベージ コレクションがあることを考えると、これらの if には最適化としての真の価値しかありません。それはちょっと大きなものです。CAS はメモリからの読み取りに比べて信じられないほど高価です。その間、後続の CAS で失敗する可能性が減るため、CAS の再試行回数が減り、パフォーマンスが向上します。

さらなる最適化として、最初の == 最後 && テール更新チェックを head.CAS の内部に移動することもできます。テールは、ヘッドが更新された場合にのみ遅れる可能性があるため、CAS が成功した場合にのみチェックすることは理にかなっています。他の場所では必要ないので、tail.get をそこに移動することもできます。以下のコード例。お役に立てれば！

public T deq() throws EmptyException {
while(true) {
    Node first = head.get();
    Node next = first.next.get();

    if (first != head.get())
        continue;

    if (next == null) {
        throw new EmptyException();
    }

    T value = next.value;

    if (head.compareAndSet(first, next)) {
        Node last = tail.get();

        if (first == last) {
            tail.compareAndSet(last, next);
        }

        return value;
    }
}

}

于 2011-03-23T13:43:13.157 に答える
2

これらは必須ではありませんが、パフォーマンス上の理由から使用されます。アトミック操作を使用せずにチェックが行われることに注意してください。

MSDNのコストの例:

  • MemoryBarrier は 20 ～ 90 サイクルかかると測定されました。
  • InterlockedIncrement は、36 ～ 90 サイクルかかると測定されました。
  • クリティカル セクションの取得または解放には、40 ～ 100 サイクルかかると測定されました。
  • ミューテックスの取得または解放には、約 750 ～ 2500 サイクルかかると測定されました。

この特定の手法の参照:

[Rudolph & Segall 84] Rudolph, L. および Segall, Z. MIMD 並列プロセッサ用の動的分散型キャッシュ スキーム。Invù roceedings of theíúvúth Annual Symposium on Computer Architecture, pages 340i›347, 1984.

于 2011-03-23T13:38:19.123 に答える
0

これはノンブロッキング リンク リスト アルゴリズムです。詳細な説明は、JCP book (15.4.2. A Nonblocking Linked List) にあります。

于 2011-03-25T09:21:43.683 に答える