JUC-LinkedBlockingQueue

傷城~ 2022-12-20 02:16 96阅读 0赞

`LinkedBlockingQueue`是一个基于链表实现的阻塞队列

### 1. 成员 ###

节点类：

static class Node<E> {
        
            E item;// 节点值
            Node<E> next;// 后继指针
            Node(E x) {
         item = x; }
        }

成员：

private final int capacity;// 链表容量
        private final AtomicInteger count = new AtomicInteger();// 节点数量采用原子计数
        transient Node<E> head;// 头节点
        private transient Node<E> last;// 尾节点

实现阻塞队列采用两把锁+两个等待队列

private final ReentrantLock takeLock = new ReentrantLock();
        private final Condition notEmpty = takeLock.newCondition();
    		private final ReentrantLock putLock = new ReentrantLock();
        private final Condition notFull = putLock.newCondition();

### 2. 基本操作 ###

#### 2.1 构造方法 ####

默认构造方法

public LinkedBlockingQueue() {
        
            this(Integer.MAX_VALUE);// 默认传入的容量是整形的最大值，即其实是无界队列
        }
    
        public LinkedBlockingQueue(int capacity) {
        
            if (capacity <= 0) throw new IllegalArgumentException();
            this.capacity = capacity;
            last = head = new Node<E>(null);
        }

#### 2.2 入队 ####

public boolean offer(E e) {
        
            // offer方法传入元素不能为null，否则抛出异常
            if (e == null) throw new NullPointerException();
            final AtomicInteger count = this.count;
            if (count.get() == capacity)
                return false;
            int c = -1;
            Node<E> node = new Node<E>(e);
            // 入队使用的是putLock
            final ReentrantLock putLock = this.putLock;
            putLock.lock();
            try {
        
                if (count.get() < capacity) {
        
                    enqueue(node);// 真正执行入队
                    c = count.getAndIncrement();
                    if (c + 1 < capacity)
                        notFull.signal();// 唤醒等待的消费者
                }
            } finally {
        
                putLock.unlock();
            }
            if (c == 0)
                signalNotEmpty();
            return c >= 0;
        }

#### 2.3 出队 ####

public E poll() {
        
            final AtomicInteger count = this.count;
            if (count.get() == 0)
                return null;
            E x = null;
            int c = -1;
            final ReentrantLock takeLock = this.takeLock;
            takeLock.lock();// 注意，入队和出队用的
            try {
        
                // 只有队列size > 0才能执行出队
                if (count.get() > 0) {
        
                    x = dequeue();// 实际执行出队
                    c = count.getAndDecrement();// count是原子变量，cas执行自减
                    if (c > 1)
                        notEmpty.signal();// 如果队列不为空则唤醒消费者
                }
            } finally {
        
                takeLock.unlock();
            }
            if (c == capacity)
                signalNotFull();
            return x;
        }

实际出队：

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

### 3. 注意 ###

**count元素是AtomicInteger类型的，和ArrayBlockingQueue一样用Integer行不行？**

*  不行，因为`LinkedBlockingQueue`是两把锁，一把出队锁，一把入队锁，同一时刻可能有两个线程在执行操作，用`Integer`的话count会有线程安全的问题

**相比于ArrayBlockingQueue，因为引入两把锁提升了代码复杂性，为什么有这么多问题还要用两把锁呢？为什么可以引入两把锁呢？**

*  `LInkedBlockingQueue`出队和入队是基于链表不同位置进行操作的，队头和队尾，是互补打扰的
 *  使用两把锁其实是锁分离的思想，在执行出队的时候其他线程也可以入队，提高了效率