首页 > 代码库 > Java并发编程实战 第15章 原子变量和非阻塞同步机制

Java并发编程实战 第15章 原子变量和非阻塞同步机制

非阻塞的同步机制

简单的说,那就是又要实现同步,又不使用锁。

与基于锁的方案相比,非阻塞算法的实现要麻烦的多,但是它的可伸缩性和活跃性上拥有巨大的优势。

实现非阻塞算法的常见方法就是使用volatile语义和原子变量。

硬件对并发的支持

原子变量的产生主要是处理器的支持,最重要的是大多数处理器架构都支持的CAS(比较并交换)指令。

模拟实现AtomicInteger的++操作

 

首先我们模拟处理器的CAS语法,之所以说模拟,是因为CAS在处理器中是原子操作直接支持的。不需要加锁。

  1. public synchronized int compareAndSwap(int exceptValue, int newValue){
  2.         int oldValue = http://www.mamicode.com/count;>
  3.         if(oldValue =http://www.mamicode.com/= exceptValue){>
  4.             count = newValue;
  5.         }
  6.         return oldValue;
  7.     }

注意:CAS总是返回oldValue。

使用上面的方法模拟AtomicInteger的++操作。

  1. class MyAtomicInteger{
  2.    private int value;
  3.    public int incrementAndGet()
  4.    {
  5.       int v ;
  6.       do{
  7.          v = value;
  8.       }while(v != compareAndSwap(v,v+1));
  9.  
  10.       return v + 1;
  11.    }
  12. }

注意:Java的AtomicInteger大概实现机制就是这样的,不会阻塞,使用处理器的CAS功能,但是要轮询尝试。

看起来轮询尝试性能会更差,其实不然,当竞争不是非常高的时候,基于CAS的算法更胜一筹。

原子类

AtomicBoolean AtomicInteger AtomicLong AtomicReference

原子数组类:AtomicIntegerArray AtomicLong AtomicReferenceArray。

使用volatile语法修饰的数组只能保证数组变量本身的volatile语义,不能保证元素的volatile语义。这个时候应该使用,原子数组类。

注意:AtomicBoolean AtomicInteger AtomicLong和非原子的对应数值类如Integer截然不用。实现机制完全不一样,也没有对应关系。最重要的一个差别:这个三个原子类是可变的。而且是使用的Object的hashCode和equals方法,没有自己扩展。

性能比较:锁与原子变量

 

在中低程度的竞争下,原子变量能提供很高的可伸缩性,原子变量性能超过锁;而在高强度的竞争下,锁能够更有效地避免竞争,锁的性能将超过原子变量的性能。但在更真实的实际情况(一般没有那么高强大的竞争)中,原子变量的性能将超过锁的性能。

注意:不论是锁还是原子变量,都远远比不上避免共享状态(如使用线程封闭技术,但是使用场景计较局限),彻底消除竞争的效率。

两个非阻塞的算法示例

 

  1. /**
  2.  * 使用Treiber算法构造的非阻塞栈
  3.  */
  4. public class ConcurrentStack<E> {
  5.     private AtomicReference<Node<E>> top = new AtomicReference<ConcurrentStack.Node<E>>();
  6.  
  7.     public void push(E item){
  8.         Node<E> newHead = new Node<E>(item);
  9.         Node<E> oldHead;
  10.  
  11.         do{
  12.             oldHead = top.get();
  13.             newHead.next = oldHead;
  14.         } while (!top.compareAndSet(oldHead, newHead));
  15.     }
  16.  
  17.     public E pop(){
  18.         Node<E> oldHead;
  19.         Node<E> newHead;
  20.  
  21.         do {
  22.             oldHead = top.get();
  23.             if (oldHead == null)
  24.                 return null;
  25.             newHead = oldHead.next;
  26.         } while (!top.compareAndSet(oldHead, newHead));
  27.         return oldHead.item;
  28.     }
  29.  
  30.     private static class Node<E>{
  31.         public final E item;
  32.         public Node<E> next;
  33.  
  34.         public Node(E item){
  35.             this.item = item;
  36.         }
  37.     }
  38. }

 

下面这个没有看懂,留在这里记录,以后再看:

  1. /**
  2.  * 链表中非阻塞算法中的插入排序,来自Michael-Scott
  3.  */
  4. public class LinkedQueue<E> {
  5.     private static class Node<E>{
  6.         final E item;
  7.         final AtomicReference<Node<E>> next;
  8.  
  9.         public Node(E item, Node<E> next){
  10.             this.item = item;
  11.             this.next = new AtomicReference<>(next);
  12.         }
  13.     }
  14.  
  15.     private final Node<E> dummy = new Node<E>(null, null);
  16.     private final AtomicReference<Node<E>> head =
  17.                         new AtomicReference<>(dummy);
  18.     private final AtomicReference<Node<E>> tail =
  19.                         new AtomicReference<>(dummy);
  20.  
  21.     public boolean put(E item){
  22.         Node<E> newNode = new Node<E>(item, null);
  23.         while (true){
  24.             Node<E> curTail = tail.get();
  25.             Node<E> tailNext = curTail.next.get();
  26.             if (curTail == tail.get()){ //尾部还未修改
  27.                 if (tailNext != null){
  28.                     // 队列处于中间状态(即新节点已经接上,尾节点还未更新),推进尾节点
  29.                     tail.compareAndSet(curTail, tailNext);
  30.                 } else{
  31.                     // 处于稳定状态, 尝试插入新节点
  32.                     if (curTail.next.compareAndSet(null, newNode)){
  33.                         // 插入成功后,推进尾节点
  34.                         tail.compareAndSet(curTail, tailNext);
  35.                         return true;
  36.                     }
  37.                 }
  38.             }
  39.         }
  40.     }
  41. }

 

 

 

 

 

 

 

 

 

 

 

 

 

Java并发编程实战 第15章 原子变量和非阻塞同步机制