Programmation simultanée Java (8) Variables atomiques et mécanisme de synchronisation non bloquant

Variables atomiques et mécanisme de synchronisation non bloquant

1. Inconvénients des verrous

1. Sous multi-threading : il y a beaucoup de frais généraux dans le processus de suspension et de récupération du verrou ( JVM moderne déterminera quand utiliser la suspension et quand tourner et attendre)

　2.volatile : mécanisme de synchronisation de niveau léger, mais ne peut pas être utilisé pour construire des opérations composites atomiques

Par conséquent : il faut être un moyen de gérer la compétition entre les threads avec une granularité plus fine, similaire au mécanisme volatile, tout en prenant également en charge les opérations de mise à jour atomique

2. CAS

Le verrouillage exclusif est une technique pessimiste - il suppose le dans le pire des cas, donc chaque thread est exclusif

alors que CAS compare et swap : compareAndSwap/Set(A,B) : on pense que la valeur en mémoire C'est A. Si c'est A, modifiez-la en B, sinon aucune opération ne sera effectuée ; renvoyer la valeur d'origine en mémoire ou si la modification est réussie

Par exemple : simuler l'opération 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 fournit des opérations CAS

Classe d'état atomique : méthode CAS d'AtomicXXX

JAVA7/8 : Opérations cartographiques : putIfAbsent, ComputerIfAbsent, ComputerIfPresent .........

3. Classe de variable atomique

L'objet de mise à jour atomique AtomicRefence peut être un objet personnalisé tel que :

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

Performance ; problème : L'utilisation de variables atomiques est plus rapide que l'utilisation de verrous dans des conditions de concurrence moyenne et faible (concurrence), et est généralement plus rapide que les verrous

Algorithmes non bloquants

Non. -Les algorithmes bloquants peuvent être utilisés dans de nombreuses structures de données courantes

Algorithmes non bloquants : dans les multithreads, il existe une incertitude quant à la réussite du travail. Il doit être exécuté en boucle et effectuer des opérations atomiques via. CAS

1. Le CasNumberRange ci-dessus

2. Algorithme non bloquant de la pile : seul le pointeur de tête est enregistré, et il n'y a qu'un seul état

//栈实现的非阻塞算法：单向链表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. Algorithme non bloquant de liste chaînée : accès rapide à la tête et à la queue, sauvegarde de deux états, plus complexe

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. Mise à jour de domaine atomique

La logique ci-dessus implémente l'algorithme non bloquant de la liste chaînée, en utilisant Node pour enregistrer le nœud principal et le nœud de queue

Le réel ConcurrentLinkedQueue utilise le AtomicReferenceFiledUpdater basé sur la réflexion pour envelopper Node

5. Problèmes ABA

Problèmes susceptibles de se produire dans les opérations CAS :

Déterminez si la valeur est A, si c'est le cas, continuez l'opération de mise à jour et changez-la en B

Mais si un fil change la valeur A en C, puis la renouvelle en A, à cette fois, le fil d'origine jugera A=A pour réussir l'opération de mise à jour

Si l'opération consistant à changer A en C puis à revenir à A doit également être considérée comme un changement, l'algorithme doit le faire. être optimisé

Solution : Ajouter le numéro de version Le numéro de version doit être mis à jour à chaque opération de mise à jour, même si la valeur est la même

　　　

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!