LinkedBlockingQueue 源码分析

阳光穿透心脏的1/2处 2022-04-08 10:59 263阅读 0赞

LinkedBlockingQueue的结构如下，本质上是个单链表

> node(head)->node->node->node(last)

static class Node<E> {
            E item;
            Node<E> next;
            Node(E x) { item = x; }
        }

构造函数很简单

public LinkedBlockingQueue(int capacity) {
            if (capacity <= 0) throw new IllegalArgumentException();
            this.capacity = capacity;
            last = head = new Node<E>(null);
    }

LinkedBlockingQueue和ArrayBlockingQueue的区别

*  数据结构ArrayBlockingQueue使用数组，LinkedBlockingQueue使用单链表
 *  LinkedBlockingQueue使用双锁，放入锁和读取锁，而ArrayBlockingQueue使用单锁，放入和读取共享一把锁。这样就决定了ArrayBlockingQueue放入和读取互斥，而LinkedBlockingQueue在很大程度上是不会的，只有在队列已满或为空的极端情况下才会互斥。这样效率是要比ArrayBlockingQueue高。

下面分析LinkedBlockingQueue的put(offer) 和 take(get)的过程

put()

public void put(E e) throws InterruptedException {
            if (e == null) throw new NullPointerException();
            
            int c = -1;
            Node<E> node = new Node<E>(e);
            final ReentrantLock putLock = this.putLock;
            final AtomicInteger count = this.count;
            putLock.lockInterruptibly();
            try {
               //如果已经达到capacity，表示队列已经满了，阻塞等待
                while (count.get() == capacity) {
                    notFull.await();
                }
                //元素入队列
                enqueue(node);
                c = count.getAndIncrement();
                //有机会就判断下是否已经队列不满条件满足，如果是则唤醒，
                //如果这里还是不满足，则只能在take()里唤醒
                
                //为什么这里是c+1<capacity 而不是c<capacity?原因在于getAndIncrement是返回的未加之前的值，
                if (c + 1 < capacity)
                    notFull.signal();
            } finally {
                putLock.unlock();
            }
            //c == 0,c是加之前的值，如果c == 0,实际上队列里至少有一个元素。
            if (c == 0)
                signalNotEmpty();
        }

take()

public E take() throws InterruptedException {
            E x;
            int c = -1;
            final AtomicInteger count = this.count;
            final ReentrantLock takeLock = this.takeLock;
            takeLock.lockInterruptibly();
            try {
            //如果队列里没有元素，则阻塞等待
                while (count.get() == 0) {
                    notEmpty.await();
                }
                //元素出队列
                x = dequeue();
                c = count.getAndDecrement();
               //这里为什么c>1而不是c>0?因为count.getAndDecrement()返回的是没减之前的值，而能取代表至少count是1。
               //如果count减完还要非空，count至少是2,所以c>1。
                if (c > 1)
                    notEmpty.signal();
            } finally {
                takeLock.unlock();
            }
            //c == capacity,c是减完之前的值，如果c == capacity,实际上队列里至少有一个空位。
            if (c == capacity)
                signalNotFull();
            return x;
        }

clear()

public class LinkedBlockingQueue<E> extends AbstractQueue<E>
            implements BlockingQueue<E>, java.io.Serializable {
    
        public void clear() {
            fullyLock();
            try {
                for (Node<E> p, h = head; (p = h.next) != null; h = p) {
                //未什么h.next = h而不是h.next=null?
                    h.next = h;
                    p.item = null;
                }
                head = last;
                // assert head.item == null && head.next == null;
                if (count.getAndSet(0) == capacity)
                    notFull.signal();
            } finally {
                fullyUnlock();
            }
        }            
                
    }

clear执行的结果就是遍历将node里的item置空并且需要断开每个node的next，其实node.next指向自己，这里作者巧妙的运用了for循环。

for（表达式1;表达式2;表达式3）
    {
        //循环体
    }

> 先执行“表达式1”，再进行“表达式2”的判断，判断为真则执行 “循环体”，循环体执行完以后执行表达式3.  
> “表达式1只会执行一次

为什么h.next = h而不是h.next=null?在下面的方法里其实有help GC,这个让自己的next指向自己，应该是是帮助GC，知道结果不知道为什么。

private E dequeue() {
            Node<E> h = head;
            Node<E> first = h.next;
            h.next = h; // help GC
            head = first;
            E x = first.item;
            first.item = null;
            return x;
        }