Java並行プログラミング(8) アトミック変数とノンブロッキング同期機構

アトミック変数とノンブロッキング同期メカニズム

1. ロックの欠点

1. マルチスレッド下: ロックの一時停止と回復のプロセスで多くのオーバーヘッドが発生します (やがて、最新の JVM がいつ使用するかを判断します)サスペンション) 開始、いつスピンして待機するか)

2.volatile: 軽量のレベル同期メカニズムですが、アトミックな複合操作の構築には使用できません

したがって: 競争を管理するときに、より詳細なレベルを持つ方法が必要です詳細には、揮発性メカニズムに似ており、アトミックな更新操作もサポートしています

2. CAS

排他的ロックは悲観的なテクノロジーです - 最悪のケースを想定しているため、各スレッドは排他的です

CAS比較と交換:compareAndSwap/Set(A,B): メモリ内の値は A であると考えます。それが A の場合は、それを B に変更します。そうでない場合は、メモリ内の元の値を返す操作は実行されません。変更は成功しました

例: CAS 操作をシミュレートします

//模拟的CASpublic class SimulatedCAS {private int value;public synchronized int get() {return value;
    }//CAS操作public synchronized int compareAndSwap(int expectedValue, int newValue) {int oldValue = value;if (oldValue == expectedValue) {
            value = newValue;
        }return oldValue;
    }public synchronized boolean compareAndSet(int expectedValue, int newValue) {return (expectedValue == compareAndSwap(expectedValue, newValue));
    }
}//典型使用场景public class CasCounter {private SimulatedCAS value;public int getValue() {return value.get();
    }public int increment() {int v;do {
            v = value.get();
        } while {
            (v != value.compareAndSwap(v, v + 1));
        }return v + 1;
    }
}

JAVA は CAS 操作を提供します

アトミック状態クラス: AtomicXXX の CAS メソッド

JAVA7/8: マップ操作: putIfAbsent、computerIfAbsent、computerIfPresent... 。 ..

3. アトミック変数クラス

AtomicRefence アトミック更新オブジェクト。次のようなものです。

public class CasNumberRange {private static class IntPair {// INVARIANT: lower <= upperfinal int lower;        //将值定义为不可变域final int upper;        //将值定义为不可变域public IntPair(int lower, int upper) {this.lower = lower;this.upper = upper;
        }
    }private final AtomicReference<IntPair> values = new AtomicReference<IntPair>(new IntPair(0, 0));    //封装对象public int getLower() {return values.get().lower;
    }public int getUpper() {return values.get().upper;
    }public void setLower(int i) {while (true) {
            IntPair oldv = values.get();if (i > oldv.upper) {throw new IllegalArgumentException("Can't set lower to " + i + " > upper");
            }
            IntPair newv = new IntPair(i, oldv.upper);  //属性为不可变域，则每次更新新建对象if (values.compareAndSet(oldv, newv)) {     //原子更新，如果在过程中有线程修改了，则其他线程不会更新成功，因为oldv与内存处值就不同了return;
            }
        }
    }//同上public void setUpper(int i) {while (true) {
            IntPair oldv = values.get();if (i < oldv.lower)throw new IllegalArgumentException("Can&#39;t set upper to " + i + " < lower");
            IntPair newv = new IntPair(oldv.lower, i);if (values.compareAndSet(oldv, newv))return;
        }
    }
}

パフォーマンスの問題: 中程度の同時実行性 (競合) でアトミック変数を使用する方が優れています。使用 ロック速度は、一般にロック速度よりも高速です

4. ノンブロッキング アルゴリズム

ノンブロッキング アルゴリズムは、多くの一般的なデータ構造で使用できます

ノンブロッキング アルゴリズム: マルチスレッドでは、作業の成功は不確実であり、CAS によるループ実行とアトミック操作が必要です

1. 上記の CasNumberRange

2. スタックのノンブロッキングアルゴリズム: ヘッドポインターと 1 つの状態のみを保存します

//栈实现的非阻塞算法：单向链表public class ConcurrentStack <E> {
    AtomicReference<Node<E>> top = new AtomicReference<Node<E>>();public void push(E item) {
        Node<E> newHead = new Node<E>(item);
        Node<E> oldHead;do {
            oldHead = top.get();
            newHead.next = oldHead;
        } while (!top.compareAndSet(oldHead, newHead));//CAS操作：原子更新操作,循环判断，非阻塞    }public E pop() {
        Node<E> oldHead;
        Node<E> newHead;do {
            oldHead = top.get();if (oldHead == null) {return null;
            }
            newHead = oldHead.next;
        } while (!top.compareAndSet(oldHead, newHead));//CAS操作：原子更新操作,循环判断，非阻塞return oldHead.item;
    }private static class Node <E> {public final E item;public Node<E> next;public Node(E item) {this.item = item;
        }
    }
}

3 , リンクリストのノンブロッキングアルゴリズム: 先頭と末尾への高速アクセス、2 つの状態の保存、より複雑

public class LinkedQueue <E> {private static class Node <E> {final E item;final AtomicReference<LinkedQueue.Node<E>> next;public Node(E item, LinkedQueue.Node<E> next) {this.item = item;this.next = new AtomicReference<LinkedQueue.Node<E>>(next);
        }
    }private final LinkedQueue.Node<E> dummy = new LinkedQueue.Node<E>(null, null);private final AtomicReference<LinkedQueue.Node<E>> head = new AtomicReference<LinkedQueue.Node<E>>(dummy);private final AtomicReference<LinkedQueue.Node<E>> tail = new AtomicReference<LinkedQueue.Node<E>>(dummy);  //保存尾节点public boolean put(E item) {
        LinkedQueue.Node<E> newNode = new LinkedQueue.Node<E>(item, null);while (true) {
            LinkedQueue.Node<E> curTail = tail.get();
            LinkedQueue.Node<E> tailNext = curTail.next.get();if (curTail == tail.get()) {if (tailNext != null) {// 处于中间状态，更新尾节点为当前尾节点的next                    tail.compareAndSet(curTail, tailNext);
                } else {// 将当前尾节点的next 设置为新节点：链表if (curTail.next.compareAndSet(null, newNode)) {/** * 此处即为中间状态，虽然在这里进行了两次原子操作，整体不是原子的，但是通过算法保证了安全：
                         * 原因是处于中间状态时，如果有其他线程进来操作，则上面那个if将执行；
                         * 上面if的操作是来帮助当前线程完成更新尾节点操作，而当前线程的更新就会失败返回，最终则是更新成功                         */// 链接成功，尾节点已经改变，则将当前尾节点，设置为新节点                        tail.compareAndSet(curTail, newNode);return true;
                    }
                }
            }
        }
    }
}

3. アトミックフィールドアップデータ

上記のロジックはリンクリストのノンブロッキングアルゴリズムを実装しており、 Nodeを使ってヘッドノードとテールノードを保存する

実際のConcurrentLinkedQueueでは、リフレクションベースのAtomicReferenceFiledUpdaterを使ってNodeをラップしている

5. ABAの問題

CASの運用で起こりやすい問題

判定値 A かどうか、YES の場合は更新操作を続行し、それを B に変更します。

ただし、スレッドが値 A を C に変更し、その後 A に戻すと、この時点で元のスレッドはA=A と判断し、更新操作を正常に実行します

A を C に変更してから A に戻す操作を変更とみなす必要がある場合は、アルゴリズムを最適化する必要があります

解決策: バージョン番号を追加します。値が同じであっても、更新操作ごとにバージョン番号を更新します

以上がJava並行プログラミング(8) アトミック変数とノンブロッキング同期機構の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。