Interviewfragen zu Java-Multithreading und Parallelität (Frage 4, mit Antworten)

4. ConcurrentLinkedQueue, nicht blockierende, unbegrenzte verknüpfte Listenwarteschlange

ConcurrentLinkedQueue ist eine threadsichere Warteschlange, die auf der Struktur verknüpfter Listen basiert. und ist eine unbegrenzte Warteschlange. Theoretisch kann die Länge der Warteschlange unendlich erweitert werden.

Wie andere Warteschlangen verwendet auch ConcurrentLinkedQueue die FIFO-Einreihungsregel (First-In-First-Out), um Elemente zu sortieren. (Empfohlene Studie: Java-Interviewfragen)

Wenn wir Elemente zur Warteschlange hinzufügen, wird das neu eingefügte Element am Ende der Warteschlange eingefügt wird vom Kopf der Warteschlange entfernt.

Da es sich bei ConcurrentLinkedQueue um eine verknüpfte Listenstruktur handelt, erstrecken sich die eingefügten Elemente beim Eintritt in die Warteschlange nach hinten, um beim Entfernen aus der Warteschlange beim ersten Element der verknüpften Liste zu beginnen und der Reihe nach zuzunehmen.

Es ist erwähnenswert, dass bei der Verwendung von ConcurrentLinkedQueue, wenn es um die Beurteilung geht, ob die Warteschlange leer ist, daran gedacht werden sollte, size()==0 nicht zu verwenden, da in der size()-Methode die gesamte verknüpfte Liste durchlaufen wird . Wenn viele Warteschlangenelemente vorhanden sind, verbraucht die Methode size () einfach viel Leistung und Zeit. Verwenden Sie einfach isEmpty (), um einfach zu beurteilen, ob die Warteschlange leer ist.

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/>

Eine Ausgabe:

入队元素为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/>

ConcurrentLinkedQuere-Klassendiagramm

Wie in gezeigt In der Abbildung gibt es zwei flüchtige Knotenknoten in ConcurrentLinkedQueue, die zum Speichern des ersten und des letzten Knotens der Liste verwendet werden. Der Kopfknoten speichert den Knoten, dessen erstes Element in der verknüpften Liste null ist, und der Endknoten zeigt nicht immer darauf letzter Knoten.

Der Node-Knoten verwaltet intern ein Variablenelement, um den Wert des Knotens zu speichern, und next wird zum Speichern des nächsten Knotens verwendet, wodurch er mit einer einseitig unbegrenzten Liste verknüpft wird.

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

Wenn der obige Code initialisiert wird, wird ein leerer Knoten mit einem Element von NULL als Kopf- und Endknoten der verknüpften Liste erstellt.

Angebotsoperation Die Angebotsoperation besteht darin, ein Element am Ende der verknüpften Liste hinzuzufügen

Werfen wir einen Blick auf das Implementierungsprinzip.

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/>

Vom Konstruktor wissen wir, dass es am Anfang einen Sentinel-Knoten mit einem Nullelement gibt und sowohl Kopf als auch Schwanz auf diesen Knoten zeigen.

Das obige ist der detaillierte Inhalt vonInterviewfragen zu Java-Multithreading und Parallelität (Frage 4, mit Antworten). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!