Parallele Java-Programmierung (8) Atomare Variablen und nicht blockierender Synchronisationsmechanismus

Atomvariablen und nicht blockierender Synchronisationsmechanismus

1. Nachteile von Sperren

1. Unter Multithreading: Der Prozess der Sperrenaufhebung und -wiederherstellung verursacht viel Overhead ( Modernes JVM bestimmt, wann „Suspend“ und wann „Spin“ und „Warten“ verwendet werden sollen eine Möglichkeit sein, den Wettbewerb zwischen Threads mit einer feineren Granularität zu verwalten, ähnlich dem flüchtigen Mechanismus, und gleichzeitig atomare Aktualisierungsvorgänge zu unterstützen

2. CAS

Exklusives Sperren ist eine pessimistische Technik – es geht davon aus Im schlimmsten Fall ist jeder Thread exklusiv

, wohingegen CAS vergleicht und tauscht: CompareAndSwap/Set(A,B): Wir gehen davon aus, dass der Wert im Speicher A ist. Wenn es A ist, ändern Sie ihn in B, andernfalls Es wird keine Operation ausgeführt. Geben Sie den ursprünglichen Wert im Speicher zurück oder ob die Änderung erfolgreich ist 🎜> JAVA stellt CAS-Operationen bereit

Atomare Zustandsklasse: CAS-Methode von AtomicXXX

JAVA7/8: Kartenoperationen: putIfAbsent, computerIfAbsent, computerIfPresent .........

3. Atomare Variablenklasse

Das atomare Aktualisierungsobjekt AtomicRefence kann ein benutzerdefiniertes Objekt sein, wie zum Beispiel:

//模拟的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;
    }
}

Leistungsproblem : Die Verwendung atomarer Variablen ist schneller als die Verwendung von Sperren bei mittlerer und geringer Parallelität (Konkurrenz). Im Allgemeinen ist sie schneller als die Sperrgeschwindigkeit

4 > Nicht blockierende Algorithmen können in vielen gängigen Datenstrukturen verwendet werden

Nicht blockierende Algorithmen: Bei Multithreads besteht Unsicherheit darüber, ob die Arbeit erfolgreich sein wird. Sie muss in einer Schleife ausgeführt werden und atomar ausgeführt werden Operationen über CAS

1. Der obige CasNumberRange

2. Nicht blockierender Algorithmus des Stapels: Nur der Kopfzeiger wird gespeichert und es gibt nur einen Status

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;
        }
    }
}

3. Nicht blockierender Algorithmus der verknüpften Liste: schneller Zugriff auf Kopf und Ende, Speichern von zwei Zuständen, komplexer

3. Atomic Domain Updater

Die obige Logik implementiert den nicht blockierenden Algorithmus der verknüpften Liste und verwendet Node, um den Kopfknoten und den Endknoten zu speichern

Die eigentliche ConcurrentLinkedQueue verwendet den reflexionsbasierten

AtomicReferenceFiledUpdater

, um Node zu umschließen

//栈实现的非阻塞算法：单向链表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;
        }
    }
}

5. ABA-Probleme

Probleme, die bei CAS-Vorgängen auftreten können:

Bestimmen Sie, ob der Wert A ist. Wenn ja, setzen Sie den Aktualisierungsvorgang fort und ändern Sie ihn in B.

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;
                    }
                }
            }
        }
    }
}

Ändert ein Thread jedoch den Wert A in C und ändert ihn dann wieder in A Zu diesem Zeitpunkt beurteilt der ursprüngliche Thread A = A, um den Aktualisierungsvorgang erfolgreich durchzuführen.

Wenn der Vorgang des Änderns von A in C und dann zurück in A ebenfalls als Änderung betrachtet werden muss, muss der Algorithmus berücksichtigt werden muss optimiert werden

Lösung: Versionsnummer hinzufügen bei jedem Aktualisierungsvorgang, auch wenn der Wert derselbe ist

　　　

Das obige ist der detaillierte Inhalt vonParallele Java-Programmierung (8) Atomare Variablen und nicht blockierender Synchronisationsmechanismus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!