java并发性能(四)之非阻塞操作(下)

小孩子 我们都是小青蛙 2018-06-05

点击蓝字,关注我们


关注

本人水平有限,如果在文中发现任何问题或疑惑,请留言,相互学习,相互进步哈~


本篇文章不是java语法的基本教程!在阅读之前,请保证你有面向对象的编程基础,熟悉封装、继承、多态,否则的话,你不适合阅读本篇文章,先学一下基础吧~

本公众号的文章都是需要被系统性学习的,这篇文章是建立在之前的几篇文章之上的,如果你没有读过,务必读后再看本篇,要不然可能会有阅读不畅的体验:


非阻塞算法

之前使用锁来保持多个线程的同步时,获取不到锁的线程会进入阻塞状态,我们现在可以使用原子变量来构建所谓的非阻塞算法,也就是不会因为一个线程持有锁而导致别的线程进入阻塞状态。我们下边据两个例子来看一下非阻塞算法的实际运用。

非阻塞累加器

我们之前对于i++操作采用的是用锁来保护的阻塞算法,我们现在改成底层使用CAS操作的原子变量的非阻塞算法来实现一下:

import java.util.concurrent.atomic.AtomicInteger;

public class UnBlockedIncrement {

   private AtomicInteger counter = new AtomicInteger(0);

   public void increase() {    //累加操作
       while (true) {
           int cur = counter.get();
           if (counter.compareAndSet(cur, cur+1)) {    //比较并交换,如果失败则立即重试
               break;
           }
       }
   }

   public int getCounter() {
       return counter.get();
   }

   public static void main(String[] args) throws Exception{
       UnBlockedIncrement increment = new UnBlockedIncrement();

       for (int i = 0;i < 20; i++) {   //创建20个线程
           Thread t = new Thread(new Runnable() {
               @Override
               public void run() {
                   for (int i = 0; i < 100000; i++) {   //累加100000次
                       increment.increase();
                   }
               }
           });
           t.start();
           t.join();
       }
       System.out.println("20个线程,每个线程累加100000次的执行结果是:" + increment.getCounter());
   }
}

执行结果是:

20个线程,每个线程累加10000次的执行结果是:2000000

很显然结果是符合我们预期的,大家重点关注一下累加操作increase方法,它内部调用了原子变量countercompareAndSet方法,如果检测到已经有别人修改过counter的值,那就什么都不做只返回false而已,返回了false之后我们再重试就好了,这再一次体现了CAS操作的精神:直接进行操作,如果在执行时检测到有别的线程的干扰,那么返回false之后重试

非阻塞链表

上边的累加器increase方法每次只会更新一个变量,也就是counter变量,如果一个原子性操作中要更新多个变量的值,那使用CAS操作的无阻塞算法不就无法保证更新多个变量的过程是原子性的了么?

是的,这也是CAS操作的劣势之一,不过在有的时候我们还可以用一些小技巧来保证更新多个变量的过程是原子性的,下边我们来分析一下如何使用无阻塞算法来实现一下队列add方法。

我们知道队列内部其实是一个链表,而链表是由一个个节点组成的,节点的类可以定义成这样:

public class Node<E> {
   E e;
   Node next;

   public Node(E e, Node next) {
       this.e = e;
       this.next = next;
   }
}

每个节点都会维护一个指向下一个节点的引用,然后在队列里维护一个指向头节点的引用,一个指向尾节点的引用,再定义上一系列队列的操作,比如插入操作和移除操作等等,我们先定义一个队列并实现一下它的add方法:

public class PlainQueue<E> {

   private Node head;   //头节点引用
   private Node tail;   //尾节点引用

   public boolean add(E e) {
       Node node = new Node<>(e, null); //创建一个新的节点
       if (tail == null) {  //如果队列为空
           head = node;
       } else {    //队列不为空
           tail.next = node;
       }
       tail = node;
       return true;
   }

但是这样的链表有个问题,add操作需要队列为空和非空这两种情况需要分别处理

  1. 如果队列为空,也就是说是这样的:


    那么在插入第一个节点的时候需要经过下边这么两步:


  • 让头节点引用指向这个新插入的节点

  • 让尾节点引用指向这个新插入的节点

这个过程就像这样:

  • 如果队列不为空,假设当前有两个节点:

    那么在新插入一个节点的时候需要经过这么两步:

    • 让最后一个节点的next字段指向这个新插入的节点

    • 让尾节点引用指向这个新插入的节点

    这个过程就像这样:

    为了省略这种分情况讨论的步骤,我们提出一个哨兵的概念,或者说是一个哑节点。也就是说在队列为空的时候头节点引用尾节点引用都指向这个所谓的哨兵节点,队列为空时的情况就是这样:

    这样的话头节点引用尾节点引用都没有为null的情况了,所以之后的插入操作就无需判断队列是否为空,而是直接执行下边这两个步骤:

    • 让最后一个节点的next字段指向这个新插入的节点

    • 让尾节点引用指向这个新插入的节点

    让我们改写一下引入了哨兵节点后的PlainQueue的代码:

    public class PlainQueue<E> {

       private Node sentinel = new Node<>(null, null); //哨兵节点

       private Node head = sentinel;   //头节点引用
       private Node tail = sentinel;   //尾节点引用

       public boolean add(E e) {
           Node node = new Node<>(e, null); //创建一个新的节点
           tail.next = node;
           tail = node;
           return true;
       }
    }    

    在有哨兵节点的情况下插入第一个节点的过程就像下边这样:

    但是不管怎么样,add操作的这两个操作是省不了的:

    • 第1步,让最后一个节点的next引用指向这个新插入的节点,对应上边的代码就是:tail.next = node;

    • 第2步,让尾节点引用指向这个新插入的节点,对应上边的代码就是:tail = node;

    也就是说如果多个线程同时调用这个队列的add方法,多个线程可能交替操作这两步,所以会产生安全性问题。比如线程t1插入节点1,线程t2插入节点2,一种可能的时序就是:

    所以最后结果就是只插入了节点2,而节点1却被无情的抛弃了。面对这样需要保证原子性的两个操作组成的复合操作,我们之前一直都是使用加锁保证安全的,现在我们尝试使用基于CAS原子变量来把add方法设计为一个无阻塞的操作,首先我们修改一下Node类:

    public class Node<E> {
       E e;
       AtomicReference> next;

       public Node(E e, Node next) {
           this.e = e;
           this.next = new AtomicReference<>(next);
       }
    }

    我们把next引用定义成一个AtomicReference的原子引用。我们前边说过插入一个节点要先修改最后一个节点的next字段,然后再修改tail的值,所以这个过程中有一个中间状态,就是已经修改了最后一个节点的next字段,但是还没有修改tail的值,看一下插入操作过程中的状态变化:

    也就是说如果当前处于中间状态的话,tail.next 是不为null的,如果处于稳定状态,tail.next 是等于 null的,在多线程环境中,我们可以根据这个条件来判断是否正在有别的线程进行插入操作,如果一个线程t2在执行插入操作的时候检测到队列正处于中间状态,就意味着另一个线程在执行插入动作,假设这个线程是t1,那么线程t2就可以帮助线程t1完成剩余的操作,也就是修改 tail 字段的值之后再继续完成它的操作,具体的代码如下:

    public class UnBlockedQueue<E> {

       private Node sentinel = new Node<>(null, null);  //哨兵节点

       private AtomicReference> head = new AtomicReference<>(sentinel);    //头节点引用
       private AtomicReference> tail = new AtomicReference<>(sentinel);    //尾节点引用

       public boolean add(E e) {
           Node node = new Node<>(e, null); //即将插入的节点

           while (true) {
               Node tailNode = tail.get();  //当前的尾节点
               Node tailNext = tailNode.next.get(); //尾节点的下一个节点

               if (tailNext == null) {     //处于稳定状态,尝试插入新节点
                   if (tailNode.next.compareAndSet(tailNext, node)) {
                       tail.compareAndSet(tailNode, node);
                       return true;
                   }

               } else {    //处于中间状态,帮助上一个线程设置tail的值
                   tail.compareAndSet(tailNode, tailNext);
               }
           }
       }
    }    

    正是由于add方法有中间状态的存在,一个线程在检测到中间状态的时候并不是等待另一个线程全部操作之后再执行,而是帮助另一个线程完成剩余操作后再进行自己的操作,这样就不会有阻塞的发生了。

    CAS操作的缺点

    CAS虽然很高效的解决原子操作,但是还是有缺点的

    1. ABA问题。

      CAS操作需要检查在操作前给定的变量的值是否和指定的值相同,比如一个变量原来的值是A,变成了B,又变成了A,那么使用CAS进行检查时会发现它的值没有发生变化,所以直接返回false代表操作失败。在一些使用场景下需要的是检测给定的变量的值是否发生变化,如果变量值变化情况是A-B-A的这种,虽然实际变化了,但是无法检测到,这一点很尴尬。

      解决的方案就是所谓的版本号,也就是说每一次操作都会记录一次操作的版本号,比如第一次将变量设置成A,则把操记录成A1,第二次操作记录成B2,第三次操作记录成A3,这样原来的A-B-A问题就转换成A1-B2-A3的问题,所以就避免了ABA问题的发生。设计java的大叔给我们提供了AtomicStampedReference这个原子变量来解决ABA问题,具体使用情况请参考相关文档。

    2. 循环时间长开销大。

      如果在竞争非常激烈的多线程环境下使用CAS操作,会导致有的线程长时间的进行空循环,虽然什么都没做,但是还是在浪费处理器的执行时间。所以如果在竞争非常激烈的情况下,还不如用锁来进行隔离,起码线程阻塞之后是不会浪费处理器的执行时间的,具体使用锁效率更高还是CAS操作效率更高需要经过实际测试后用数据说话。

    3. 只能保证一个共享变量的原子操作。

      一个CAS操作只针对一个变量,如果需要保证更新多个共享变量过程的原子性,有得时候可以像处理链表add方法那样,多线程根据中间状态来协助完成最后的目标,不过复杂度显然远高于使用锁来保护这些操作。

      或者还有一个取巧的办法,就是可以把这些变量都放在一个对象里,比如我们同时想更新ij两个变量,那么可以新创建一个类,包含ij两个字段,再使用AtomicReference来原子更新这个新对象,就达到了原子更新的目的了。

    题外话

    写文章挺累的,有时候你觉得阅读挺流畅的,那其实是背后无数次修改的结果。如果你觉得不错请帮忙转发一下,万分感谢~


      觉得不错,分享给更多人看到
      我们都是小青蛙 热门文章:

      java并发编程之原子性操作    阅读/点赞 : 0/0

      我们都是小青蛙,呱呱呱呱呱    阅读/点赞 : 0/0

      活跃性(死锁、饥饿、活锁)    阅读/点赞 : 0/0

      指令重排序    阅读/点赞 : 0/0

      InnoDB的Buffer Pool简介    阅读/点赞 : 0/0

      一些比较重要的数字电路模块    阅读/点赞 : 0/0

      抽象的艺术    阅读/点赞 : 0/0

      内存可见性    阅读/点赞 : 0/0

      存储程序(二)之存储函数简介    阅读/点赞 : 0/0

      线程间通信(下)    阅读/点赞 : 0/0

      我们都是小青蛙 微信二维码

      我们都是小青蛙 微信二维码