Questions d'entretien sur le multithreading et la concurrence Java (question 4, avec réponses)

4. ConcurrentLinkedQueue file d'attente de liste chaînée non bloquante et illimitée

ConcurrentLinkedQueue est une file d'attente thread-safe, implémentée sur la base de la structure de liste chaînée, et est une file d'attente illimitée. Théoriquement, la longueur de la file d'attente peut être étendue à l'infini.

Comme les autres files d'attente, ConcurrentLinkedQueue utilise également la règle de mise en file d'attente premier entré, premier sorti (FIFO) pour trier les éléments. (Étude recommandée : questions d'entretien Java)

Lorsque nous ajoutons des éléments à la file d'attente, l'élément nouvellement inséré sera inséré à la fin de la file d'attente et lorsque nous obtiendrons un élément, il ; sera supprimé de la tête de la file d'attente.

Comme ConcurrentLinkedQueue est une structure de liste chaînée, lors de l'entrée dans la file d'attente, les éléments insérés s'étendent vers l'arrière afin de former une liste chaînée lors de la sortie de la file d'attente, ils commencent à partir du premier élément de la liste chaînée et augmentent en séquence ;

Il est à noter que lors de l'utilisation de ConcurrentLinkedQueue, s'il s'agit de juger si la file d'attente est vide, n'oubliez pas de ne pas utiliser size()==0, car dans la méthode size(), toute la liste chaînée est parcourue . En pratique, lorsqu'il y a de nombreux éléments de file d'attente, la méthode size() consomme beaucoup de performances et de temps. Vous pouvez simplement utiliser isEmpty() pour déterminer si la file d'attente est vide.

public class ConcurrentLinkedQueueTest {<br/>    public static int threadCount = 10;<br/>    public static ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<String>();<br/>    static class Offer implements Runnable {<br/>        public void run() {<br/>            //不建议使用 queue.size()==0，影响效率。可以使用!queue.isEmpty()<br/>            if (queue.size() == 0) {<br/>                String ele = new Random().nextInt(Integer.MAX_VALUE) + "";<br/>                queue.offer(ele);<br/>                System.out.println("入队元素为" + ele);<br/>            }<br/>        }<br/>    }<br/>    static class Poll implements Runnable {<br/>        public void run() {<br/>            if (!queue.isEmpty()) {<br/>                String ele = queue.poll();<br/>                System.out.println("出队元素为" + ele);<br/>            }<br/>        }<br/>    }<br/>    public static void main(String[] agrs) {<br/>        ExecutorService executorService = Executors.newFixedThreadPool(4);<br/>        for (int x = 0; x < threadCount; x++) {<br/>            executorService.submit(new Offer());<br/>            executorService.submit(new Poll());<br/>        }<br/>        executorService.shutdown();<br/>    }<br/>}<br/>

Une sortie :

入队元素为313732926<br/>出队元素为313732926<br/>入队元素为812655435<br/>出队元素为812655435<br/>入队元素为1893079357<br/>出队元素为1893079357<br/>入队元素为1137820958<br/>出队元素为1137820958<br/>入队元素为1965962048<br/>出队元素为1965962048<br/>出队元素为685567162<br/>入队元素为685567162<br/>出队元素为1441081163<br/>入队元素为1441081163<br/>出队元素为1627184732<br/>入队元素为1627184732<br/>

Diagramme de classes ConcurrentLinkedQuere

Comme indiqué dans la figure Il existe deux nœuds Node volatiles dans ConcurrentLinkedQueue, qui sont utilisés pour stocker le premier et le dernier nœuds de la liste. Le nœud principal stocke le nœud dont le premier élément de la liste chaînée est nul, et la queue ne pointe pas toujours vers le nœud. dernier nœud.

Le nœud Node conserve un élément variable en interne pour stocker la valeur du nœud, et next est utilisé pour stocker le nœud suivant, le liant ainsi à une liste illimitée unidirectionnelle.

public ConcurrentLinkedQueue(){<br/>    head=tail=new Node<E>(null);<br/>}<br/>

Lorsque le code ci-dessus est initialisé, un nœud vide avec un élément NULL sera construit comme nœuds de tête et de queue de la liste chaînée.

Opération d'offre L'opération d'offre consiste à ajouter un élément à la fin de la liste chaînée

Regardons le principe de mise en œuvre.

public boolean offer(E e) {<br/>    //e 为 null 则抛出空指针异常<br/>    checkNotNull(e);<br/>    //构造 Node 节点构造函数内部调用 unsafe.putObject，后面统一讲<br/>    final Node<E> newNode = new Node<E>(e);<br/>    //从尾节点插入<br/>    for (Node<E> t = tail, p = t; ; ) {<br/>        Node<E> q = p.next;<br/>        //如果 q=null 说明 p 是尾节点则插入<br/>        if (q == null) {<br/>            //cas 插入（1）<br/>            if (p.casNext(null, newNode)) {<br/>                //cas 成功说明新增节点已经被放入链表，然后设置当前尾节点（包含 head，1，3，5.。。个节点为尾节点）<br/>                if (p != t)// hop two nodes at a time<br/>                    casTail(t, newNode); // Failure is OK. return true;<br/>            }<br/>            // Lost CAS race to another thread; re-read next<br/>        } else if (p == q)//(2)<br/>            //多线程操作时候，由于 poll 时候会把老的 head 变为自引用，然后 head 的 next 变为新 head，所以这里需要<br/>            //重新找新的 head，因为新的 head 后面的节点才是激活的节点<br/>            p = (t != (t = tail)) ? t : head;<br/>        else<br/>            // 寻找尾节点(3)<br/>            p = (p != t && t != (t = tail)) ? t : q;<br/>    }<br/>}<br/>

D'après le constructeur, nous savons qu'il existe un nœud sentinelle avec un élément nul au début, et que la tête et la queue pointent vers ce nœud.

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!