Java并发编程笔记之LinkedBlockingQueue源码探究-低调大师

Java并发编程笔记之LinkedBlockingQueue源码探究

2018-06-22 537

LinkedBlockingQueue的实现是使用独占锁实现的阻塞队列。首先看一下LinkedBlockingQueue 的类图结构，如下图所示：

如类图所示：LinkedBlockingQueue是使用单向链表实现，有两个Node分别来存放首尾节点，并且里面有个初始值为0 的原子变量count，它用来记录队列元素个数。

另外里面有两个ReentrantLock的实例，分别用来控制元素入队和出队的原子性，其中takeLock用来控制同时只有一个线程可以从队列获取元素，其他线程必须等待，

putLock控制同时只能有一个线程可以获取锁去添加元素，其他线程必须等待。另外notEmpty 和 notFull 是信号量，内部分别有一个条件队列用来存放进队和出队的时候被阻塞的线程，

说白了，这其实就是一个生产者 - 消费者模型。

我们首先看一下独占锁的源码，如下所示：

　　/** 执行take, poll等操作时候需要获取该锁 */
    private final ReentrantLock takeLock = new ReentrantLock();

    /** 当队列为空时候执行出队操作（比如take）的线程会被放入这个条件队列进行等待 */
    private final Condition notEmpty = takeLock.newCondition();

    /** 执行put, offer等操作时候需要获取该锁*/
    private final ReentrantLock putLock = new ReentrantLock();

    /**当队列满时候执行进队操作（比如put)的线程会被放入这个条件队列进行等待 */
    private final Condition notFull = putLock.newCondition();

 　　/** 当前队列元素个数 */
    private final AtomicInteger count = new AtomicInteger(0);

接着我们要进入LinkedBlockingQueue 无参构造函数，源码如下：

public static final int   MAX_VALUE = 0x7fffffff;

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

从源码中可以看到，默认队列的容量为0x7fffffff; 用户也可以自己指定容量，所以一定程度上 LinkedBlockingQueue 可以说是有界阻塞队列。

接下来我们主要看LinkedBlockingQueue 的几个主要方法的源码，如下：

　　1.offer操作，向队列尾部插入一个元素，如果队列有空闲容量则插入成功后返回true，如果队列已满则丢弃当前元素然后返回false，如果 e元素为null，则抛出空指针异常(NullPointerException )，还有一点就是，该方法是非阻塞的。源码如下：

public boolean offer(E e) {

        //（1）空元素抛空指针异常
        if (e == null) throw new NullPointerException();

        //(2) 如果当前队列满了则丢弃将要放入的元素，然后返回false
        final AtomicInteger count = this.count;
        if (count.get() == capacity)
            return false;

        //(3) 构造新节点，获取putLock独占锁
        int c = -1;
        Node<E> node = new Node<E>(e);
        final ReentrantLock putLock = this.putLock;
        putLock.lock();
        try {
            //(4)如果队列不满则进队列，并递增元素计数
            if (count.get() < capacity) {
                enqueue(node);
                c = count.getAndIncrement();
                //(5)
                if (c + 1 < capacity)
                    notFull.signal();
            }
        } finally {
            //(6)释放锁
            putLock.unlock();
        }
        //(7)
        if (c == 0)
            signalNotEmpty();
        //(8)
        return c >= 0;
}

private void enqueue(Node<E> node) {   
 last = last.next = node;
}

代码（2）判断的是如果当前队列已满则丢弃当前元素并返回false。

代码（3）获取到putLock锁，当前线程获取到该锁后，则其他调用put 和 offer 的线程将会被阻塞（阻塞的线程被放到 putLock 锁的 AQS 阻塞队列）。

代码（4）这里又重新判断了一下当前队列是否满了，这是因为在执行代码（2）和获取到putLock锁期间，有可能其他线程通过put 或者 offer方法想队列里面添加了新的元素。重新判断队列确实不满则新元素入队，并递增计数器。

代码（5）判断的是如果新元素入队后还有空闲空间，则唤醒notFull的条件队列里面因为调用了notFull 的 await 操作（比如执行put方法而队列满了的时候）而被阻塞的一个线程，因为队列现在有空闲，所以这里可以提前唤醒一个入队线程。

代码（6）则释放获取的putLock锁，这里要注意锁的释放一定要在finally里面做，因为即使try块抛出异常了，finally也是会被执行到的。另外释放锁后其他因为调用put和offer而被阻塞的线程将会有一个获取到改锁。

代码（7）c == 0说明在执行代码（6）释放锁的时候队列里面至少有一个元素，队列里面有元素则执行signalNotEmpty，signalNotEmpty的源码如下：

private void signalNotEmpty() {
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lock();
        try {
            notEmpty.signal();
        } finally {
            takeLock.unlock();
        }
    }

通过上面代码可以看到其作用是激活notEmpty 的条件队列中因为调用notEmpty的await方法（比如调用 take 方法并且队列为空的时候）而被阻塞的一个线程，这里也说明了调用条件变量的方法前，要首先获取对应的锁。

offer的总结：offer方法中通过使用putLock锁保证了在队尾新增元素的原子性和队列元素个数的比较和递增操作的原子性。

　　2.put操作，向队列尾部插入一个元素，如果队列有空闲则插入后直接返回true,如果队列已经满则阻塞当前线程知道队列有空闲插入成功后返回true，如果在阻塞的时候被其他线程设置了中断标志，

则被阻塞线程会抛出InterruptedException 异常而返回，另外如果 e 元素为 null 则抛出 NullPointerException 异常。源码如下：

　　public void put(E e) throws InterruptedException {
        //（1）空元素抛空指针异常
        if (e == null) throw new NullPointerException();
        //(2) 构建新节点，并获取独占锁putLock
        int c = -1;
        Node<E> node = new Node<E>(e);
        final ReentrantLock putLock = this.putLock;
        final AtomicInteger count = this.count;
        putLock.lockInterruptibly();
        try {
            //(3)如果队列满则等待
            while (count.get() == capacity) {
                notFull.await();
            }
            //（4）进队列并递增计数
            enqueue(node);
            c = count.getAndIncrement();
            //(5)
            if (c + 1 < capacity)
                notFull.signal();
        } finally {
            //(6)
            putLock.unlock();
        }
        //(7)
        if (c == 0)
            signalNotEmpty();
    }

代码（2）中使用 putLock.lockInterruptibly() 获取独占锁，相比 offer 方法中这个获取独占锁方法意味着可以被中断，具体说是当前线程在获取锁的过程中，如果被其它线程设置了中断标志则当前线程会抛出 InterruptedException 异常，

所以put操作在获取锁过程中是可被中断的。

代码（3）如果当前队列已经满，则notFull 的 await() 把当前线程放入 notFull 的条件队列，当前线程被阻塞挂起并释放获取到的 putLock 锁，由于putLock锁被释放了，所以现在其他线程就有机会获取到putLock锁了。

代码（3）判断队列是否为空为何使用 while 循环而不是 if 语句呢？

这是因为考虑到当前线程被虚假唤醒的问题，也就是其它线程没有调用 notFull 的 singal 方法时候，notFull.await() 在某种情况下会自动返回。

如果使用if语句简单判断一下，那么虚假唤醒后会执行代码（4），元素入队，并且递增计数器，而这时候队列已经是满了的，导致队列元素个数大于了队列设置的容量，导致程序出错。

而使用使用 while 循环假如 notFull.await() 被虚假唤醒了，那么循环在检查一下当前队列是否是满的，如果是则再次进行等待。

　　3.poll操作，从队列头部获取并移除一个元素，如果队列为空则返回 null，该方法是不阻塞的。源码如下：

　　public E poll() {
        //(1)队列为空则返回null
        final AtomicInteger count = this.count;
        if (count.get() == 0)
            return null;
        //(2)获取独占锁
        E x = null;
        int c = -1;
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lock();
        try {
            //(3)队列不空则出队并递减计数
            if (count.get() > 0) {//3.1
                x = dequeue();//3.2
                c = count.getAndDecrement();//3.3
                //(4)
                if (c > 1)
                    notEmpty.signal();
            }
        } finally {
            //(5)
            takeLock.unlock();
        }
        //(6)
        if (c == capacity)
            signalNotFull();
        //(7)返回
        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;
    }

代码(1) 如果当前队列为空，则直接返回 null。

代码（2）获取独占锁 takeLock，当前线程获取该锁后，其它线程在调用 poll 或者 take 方法会被阻塞挂起。

代码 (3) 如果当前队列不为空则进行出队操作，然后递减计数器。

代码（4）如果 c>1 则说明当前线程移除掉队列里面的一个元素后队列不为空（c 是删除元素前队列元素个数），那么这时候就可以激活因为调用 poll 或者 take 方法而被阻塞到notEmpty 的条件队列里面的一个线程。

代码（5）释放锁，一定要在finally里面释放锁。

代码（6）说明当前线程移除队头元素前当前队列是满的，移除队头元素后队列当前至少有一个空闲位置，那么这时候就可以调用signalNotFull激活因为调用put 或者 offer 而被阻塞放到 notFull 的条件队列里的一个线程，signalNotFull 源码如下：

　　private void signalNotFull() {
          final ReentrantLock putLock = this.putLock;
          putLock.lock();
          try {
              notFull.signal();
          } finally {
              putLock.unlock();
          }
   }

poll 代码逻辑比较简单，值得注意的是获取元素时候只操作了队列的头节点。

　　4.peek 操作，获取队列头部元素但是不从队列里面移除，如果队列为空则返回 null，该方法是不阻塞的。源码如下：

　　public E peek() {
        //(1)
        if (count.get() == 0)
            return null;
        //(2)
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lock();
        try {
            Node<E> first = head.next;
            //(3)
            if (first == null)
                return null;
            else
            //(4)
                return first.item;
        } finally {
           //(5)
            takeLock.unlock();
        }
    }

可以看到代码（3）这里还是需要判断下 first 是否为 null 的，不能直接执行代码（4）。

正常情况下执行到代码（2）说明队列不为空，但是代码（1）和（2）不是原子性操作，也就是在执行代码（1）判断队列不为空后，

在代码（2）获取到锁前，有可能其他线程执行了poll 或者 take 操作导致队列变为了空，然后当前线程获取锁后，直接执行 first.item 会抛出空指针异常。

　　5.take 操作，获取当前队列头部元素并从队列里面移除，如果队列为空则阻塞调用线程。如果队列为空则阻塞当前线程知道队列不为空，然后返回元素，如果在阻塞的时候被其他线程设置了中断标志，则被阻塞线程会抛出InterruptedException 异常而返回。源码如下：

　　public E take() throws InterruptedException {
        E x;
        int c = -1;
        final AtomicInteger count = this.count;
        //(1)获取锁
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lockInterruptibly();
        try {
            //(2)当前队列为空则阻塞挂起
            while (count.get() == 0) {
                notEmpty.await();
            }
            //(3)出队并递减计数
            x = dequeue();
            c = count.getAndDecrement();
            //(4)
            if (c > 1)
                notEmpty.signal();
        } finally {
           //(5)
            takeLock.unlock();
        }
        //(6)
        if (c == capacity)
            signalNotFull();
        //(7)
        return x;
    }

代码（1）当前线程获取到独占锁，其他调用take 或者 poll的线程将会被阻塞挂起。

代码（2）如果队列为空则阻塞挂起当前线程，并把当前线程放入 notEmpty 的条件队列。

代码（3）进行出队操作并递减计数。

代码（4）如果 c > 1 说明当前队列不为空，则唤醒notEmpty 的条件队列的条件队列里面的一个因为调用 take 或者 poll 而被阻塞的线程。

代码（5）释放锁。

代码（6）如果 c == capacity 则说明当前队列至少有一个空闲位置，则激活条件变量 notFull 的条件队列里面的一个因为调用 put 或者 offer 而被阻塞的线程。

　　6.remove操作，删除队列里面指定元素，有则删除返回 true，没有则返回 false，源码如下：

public boolean remove(Object o) {
    if (o == null) return false;

    //（1）双重加锁
    fullyLock();
    try {

        //（2)遍历队列找则删除返回true
        for (Node<E> trail = head, p = trail.next;
             p != null;
             trail = p, p = p.next) {
             //(3)
            if (o.equals(p.item)) {
                unlink(p, trail);
                return true;
            }
        }
        //(4)找不到返回false
        return false;
    } finally {
        //(5)解锁
        fullyUnlock();
    }
}

代码（1）通过fullyLock获取双重锁，当前线程获取后，其他线程进行入队或者出队的操作就会被阻塞挂起。双重锁方法fullyLock的源码如下：

void fullyLock() {
    putLock.lock();
    takeLock.lock();
}

代码（2）遍历队列寻找要删除的元素，找不到则直接返回false,找到则执行unlink操作，unlink的源码如下：

　　void unlink(Node<E> p, Node<E> trail) {
      p.item = null;
      trail.next = p.next;
      if (last == p)
          last = trail;
      如果当前队列满，删除后，也不忘记唤醒等待的线程
      if (count.getAndDecrement() == capacity)
          notFull.signal();
    }

可以看到删除元素后，如果发现当前队列有空闲空间，则唤醒 notFull 的条件队列中一个因为调用 put 或者 offer 方法而被阻塞的线程。

代码（5）调用 fullyUnlock 方法使用与加锁顺序相反的顺序释放双重锁，源码如下：

void fullyUnlock() {
    takeLock.unlock();
    putLock.unlock();
}

　　7.size操作，获取当前队列元素个数。源码如下：

public int size() {
   return count.get();
}

总结：由于在操作出队入队的时候操作Count的时候加了锁，因此相比ConcurrentLinkedQueue 的size方法比较准确。

最后用一张图来加深LinkedBlockingQueue的理解，如下图：

因此我们要思考一个问题：为何 ConcurrentLinkedQueue 中需要遍历链表来获取 size 而不适用一个原子变量呢？

这是因为使用原子变量保存队列元素个数需要保证入队出队操作和操作原子变量是原子操作，而ConcurrentLinkedQueue 是使用 CAS 无锁算法的，所以无法做到这个。

微信关注我们

原文链接：https://yq.aliyun.com/articles/603485

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

Python爬虫(三)——对豆瓣图书各模块评论数与评分图形化分析

文化　经管 ....略结论：一个模块的评分与评论数相关，评分为 [8.8——9.2] 之间的书籍评论数往往是模块中最多的

2018-06-23

567

sklearn调包侠之无敌小抄

scikit-learn（以下简称为sklearn）是用Python开发的机器学习库，其中包含大量机器学习算法、数据集，是数据挖掘方便的工具。本教程参考《Python机器学习及实战》、《scikit-learn机器学习》和sklearn的官方文档，详细讲解如何使用sklearn实现机器学习算法。首先，依旧讲讲写本系列教程的原因：第一，相比于直接编写各种算法，sklearn简单容易上手；第二，参考书籍有些部分讲解不细致，sklearn版本的更新，官方文档虽然齐全，但是是英文等等，希望通过编写这个教程，可以让读者轻松上手机器学习；第三，依旧是本人的学习记录过程。本系列教程特点：好学易用案例实操多哪些读者可以使用：了解机器学习的基本术语会Python语言会numpy和pandas库的使用 sklearn小抄在愉悦的做一个调包侠之前，老衲给予施主一份绝世宝典（sklearn小抄），之后你的任督二脉将会打开，在sklearn调包的路上所向披靡。首先上宝典，高清pdf请前往此处下载：（链接：https://pan.baidu.com/s/12c0CIP6c6rgc4Y5zEnUJ...

2018-06-23

599

发表评论

资源下载

更多资源

优质分享App

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。