转载

非阻塞算法-简单的计数器

1.为什么要用非阻塞算法？我们知道为了避免并发环境下操作共享变量的问题，可以采用同步（synchronize）和锁（Lock）的方式做到线程安全，但是JVM处理锁竞争时对于竞争失败的线程采用的是挂起稍后调度的策略，这样会带来额外的线程上下文切换成本。同时和CAS（Compare And Set）这种非阻塞算法相比，CAS是在底层硬件（CPU）层面实现，只需要锁定独立的内存位置，更细的同步粒度使得CAS失败的线程可以立即重试而不用挂起。总的来说，大多数场景下非阻塞算法和同步锁相比能带来更好的性能，最小化串行代码的粒度是并行性能的关键。

2.非阻塞算法的弊端CAS算法是先compare再set，如果compare结果为false的话就不会执行set直接返回false，也就是说非阻塞算法可能会失败，因此非阻塞算法往往需要放在循环里不断重试直到成功，所以在锁竞争非常严重时非阻塞算法的性能可能会严重下降，甚至不如阻塞算法。

3.最简单的CAS用法CAS的全称是Compare and Set，是现代主流CPU都支持的一个CPU原子语义操作，简单来说就是先跟某个值对比，如果等于这个值就设置成新的值，如果不等于这个值就放弃操作同时返回失败。这里我们看一下最常用的计数器，首先我们看一个单线程的计数器：

public class SingleThreadCounter implements Counter {  @Override  public void increment() {   this.counter++;  }  @Override  public int getCounter() {   return counter;  }  private int counter = 0; }

这个计数器在单线程下完全没有问题，但是一旦有多个线程并发执行increment，就会出现问题，因为counter++ 是先取值，再赋值，如果A线程取出1，B线程也取出1，A设置counter为2，B后设置counter也为2，最终B把A的结果覆盖了。

接下来我们看同步的计数器

public class SynchronizedCounter implements Counter {  private volatile int counter = 0;  public synchronized void increment() {   counter = counter + 1;  }  @Override  public int getCounter() {   return counter;  } }

这个计数器解决了前面一个多线程并发increment的问题，因为increment方法是同步的，不会有两个线程同时执行increment操作，实际上increment操作是串行的。这种方式保证了线程安全，但是牺牲了并发度。

最后我们看无锁算法的计数器

public class CasCounter implements Counter {  private AtomicInteger counter = new AtomicInteger(0);  @Override  public void increment() {   for (; ; ) {    int cur = counter.get();    int next = cur + 1;    if (counter.compareAndSet(cur, next)) {     return;    }   }  }  @Override  public int getCounter() {   return counter.get();  } }

我们看这个类里的increment方法，其实这个方法和AtomicInteger里的incrementAndGet方法是一样的，就是在每个循环里做一次CAS操作，先取出当前拿到的值cur，然后CAS(cur,cur+1)，如果返回成功的话说明更新成功了，那就直接return；如果失败的话说明其他线程已经改变了counter的值，就继续循环执行前面的操作直到成功为止。这里需要注意的是counter.get方法返回的底层变量是一个volatile的值，可以保证内存的可见性，因此不会出现读到脏值的问题。

4.总结

CAS算法和同步锁相比，把串行的粒度从方法级别降低到CPU的CAS原子操作，提高了并发度，因此提高了系统的容量，但是CAS在失败时是需要重试的，因此如果并发度很高，竞争十分严重的情况下，因为需要大量重试操作，CAS的效率可能甚至不如同步方法。

下一节我们继续讲如何把CAS算法用在一些更复杂一些的数据结构上。

正文到此结束