背景
近年来，在并发算法领域的大多数研究都侧重于非阻塞算法，这种算法用底层的原子机器指令（例如比较并发交换指令）代替锁来确保数据在并发访问中的一致性。非阻塞算法被广泛的用于在操作系统和jvm中实现线程/进程调度机制、垃圾回收机制以及锁和其他并发数据结构。
与基于锁的方案相比，非阻塞算法在设计和实现上都要复杂的多，但他们在可伸缩性和活跃性上却拥有巨大的优势，由于非阻塞算法可以使多个线程在竞争相同数据时不会发生阻塞，因此它能在粒度更细的层次上面进行协调，并且极大的减少调度开销。锁虽然java语言锁定语法比较简洁，但jvm操作和管理锁时，需要完成的工作缺并不简单，在实现锁定时需要遍历jvm中一条复杂的代码路径，并可能导致操作系统级的锁定、线程挂起以及上下文切换等操作。
非阻塞算法
在基于锁的算法中可能会发生各种活跃性故障，如果线程在持有锁时由于阻塞i/o，内存页缺失或其他延迟执行，那么很可能所有线程都不能继续执行下去。如果在某种算法中，一个线程的失败或挂起不会导致其他线程也失败或挂起，那么这种算法就称为非阻塞算法。如果在算法的每个步骤中都存在某个线程能够执行下去，那么这种算法也被称为无锁算法。如果在算法中仅将cas用于协调线程之间的操作，并且能够正确的实现，那么他既是一种无阻塞算法，又是一种无锁算法。
java对非阻塞算法的支持：从java5.0开始，底层可以使用原子变量类（例如atomicinteger和atomicreference）来构建高效的非阻塞算法，底层实现采用的是一个比较并交换指令（cas）。
比较并交换（cas）
cas包括了三个操作数，需要读写的内存位置v，进行比较的值a和拟写入的新值b。当且仅当v的值等于a时，cas才会通过原子方式用新值b来更新a的值，否则不会执行任何操作。无论v的值是否等于a，都将返回v原有的值。cas的含义是：我认为v的值应该是a，如果是那么将v的值更新为b，否则不修改并告诉v的值实际为多少。
原子变量类
原子变量（对应内存模型中的原子性）比锁的粒度更细。量级更轻，并且对于在多处理器系统上实现高性能的并发代码来说是非常关键的。原子变量将发生竞争的范围缩小到单个变量上面，这是你获得的粒度最细的情况。更新原子变量的快速（非竞争）路径不会被获得锁的快速路径慢，并且通常会更快，而它的慢速路径肯定比锁的慢速路径块，因为他不需要挂起或者重新调度线程。在使用基于原子变量而非锁的算法中，线程在执行时更不易出现延迟，并且如果遇到竞争，也更容易恢复过来。
java中的13个原子操作类
java从jdk1.5开始提供了java.util.concurrent.atomic包（以下简称atomic包），这个包中的原子操作类提供了一种用法简单、性能高效、线程安全地更新一个变量的方式。因为变量的类型有很多种，所以在atomic包里一共提供了13个类，属于4种类型的原子更新方式，分别是原子更新基本类型、原子更新数组、原子更新引用和原子更新属性（字段）。atomic包里的类基本都是使用unsafe实现的包装类。
- 原子更新基本类型类
使用原子的方式更新基本类型，atomic包提供了以下3个类。
1.atomicboolean：原子更新布尔类型。
2.atomicinteger：原子更新整型。
3.atomiclong：原子更新长整型。
- 原子更新数组
通过原子的方式更新数组里的某个元素，atomic包提供了以下4个类。
1.atomicintegerarray：原子更新整型数组里的元素。
2.atomiclongarray：原子更新长整型数组里的元素。
3.atomicreferencearray：原子更新引用类型数组里的元素。
- 原子更新引用类型
原子更新基本类型的atomicinteger，只能更新一个变量，如果要原子更新多个变量，就需要使用这个原子更新引用类型提供的类。atomic包提供了以下3个类。
1.atomicreference：原子更新引用类型。
2.atomicreferencefieldupdater：原子更新引用类型里的字段。
3.atomicmarkablereference：原子更新带有标记位的引用类型。可以原子更新一个布尔类型的标记位和引用类型。构造方法是atomicmarkablereference（v initialref，booleaninitialmark）。
- 原子更新字段类
如果需原子地更新某个类里的某个字段时，就需要使用原子更新字段类，atomic包提供了以下3个类进行原子字段更新。
1.atomicintegerfieldupdater：原子更新整型的字段的更新器。
2.atomiclongfieldupdater：原子更新长整型字段的更新器。
3.atomicstampedreference：原子更新带有版本号的引用类型。该类将整数值与引用关联起来，可用于原子的更新数据和数据的版本号，可以解决使用cas进行原子更新时可能出现的
4.aba问题。
atomiclong源码分析
上面的4种原子类型都是基于cas实现，低层借助于unsafe实现原子操作。接下来结合源码，看一下比较有代表性的atomiclong源码
初始化
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
//保存atomiclong的实际值，用volatile 修饰保证可见性
private volatile long value;
// 获取value的内存地址的逻辑操作
static {
try {
valueoffset = unsafe.objectfieldoffset
(atomiclong.class.getdeclaredfield("value"));
} catch (exception ex) { throw new error(ex); }
}
//根据传入的参数初始化实际值，默认值为0
public atomiclong(long initialvalue) {
value = initialvalue;
}
|
接下来我们主要看一下几个更新方法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
//以原子方式更新值为传入的newvalue，并返回更新之前的值
public final long getandset(long newvalue) {
return unsafe.getandsetlong(this, valueoffset, newvalue);
}
//输入期望值和更新值，如果输入的值等于预期值，则以原子方式更新该值为输入的值
public final boolean compareandset(long expect, long update) {
return unsafe.compareandswaplong(this, valueoffset, expect, update);
}
//返回当前值原子加1后的值
public final long getandincrement() {
return unsafe.getandaddlong(this, valueoffset, 1l);
}
//返回当前值原子减1后的值
public final long getanddecrement() {
return unsafe.getandaddlong(this, valueoffset, -1l);
}
//返回当前值原子增加delta后的值
public final long getandadd(long delta) {
return unsafe.getandaddlong(this, valueoffset, delta);
}
|
上面列出来主要用的一些方法，可以看出基本都是调用unsafe.getandaddlong方法，接下来我们具体看下
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public native long getlongvolatile(object var1, long var2);
public final native boolean compareandswaplong(object var1, long var2, long var4, long var6);
/*
unsafe.getandaddlong(this, valueoffset, 1l)
var1 当前值
var2 value值在atomiclong对象中的内存偏移地址
*/
public final long getandaddlong(object var1, long var2, long var4) {
long var6;
do {
//根据var1和var2得出当前变量的值，以便接下来执行更新操作
var6 = this.getlongvolatile(var1, var2);
//如果当前值为var6，则将值加var4，这样做是确保每次更新时，变量的值是没有被其他线
//程修改过的值，如果被修改，则重新获取最新值更新，直到更新成功
} while(!this.compareandswaplong(var1, var2, var6, var6 + var4));
return var6;
}
|
从源码可以看出，获取当前值getlongvolatile方法，比较并交换compareandswaplong方法都是native方法。说明不是采用java实现原子操作的，具体各位同学可以继续去查看底层源码（应该是c++）实现，这里不在深入了（能力有限）。
比较并交换的缺陷
1、通过源码可以看出，原子更新时，会先获取当前值，确保当前值没被修改过后在进行更新操作，这也意味着如果竞争十分激烈，cas的效率是有可能比锁更低的（一般在实际中不会出现这种情况），jdk后面推出了longadd，粒度更小，竞争也会被分散到更低，具体实现各位同学可以自行了解。
2、aba是谈到cas不可避免的话题，比较并交换，会存在这样一个场景，当变量为值a时，将值执行更新。然而在实际中，有可能其他线程将值先改为b，然后又将值改回a，此时还是能够成功执行更新操作的（对于某些不在乎过程的没啥影响，对于链表之类的就不满足了）。解决方式是给变量打上版本号，如果版本号和值一致才执行更新操作（可使用atomicreference）。
总结
非阻塞算法通过底层的并发原语（例如比较交换而不是锁）来维持线程的安全性。这些底层的原语通过原子变量类向外公开，这些类也用做一种“更好的volatile变量”，从而为整数和对象引用提供原子的更新操作。
参考书籍：
《java并发编程实战》
《java并发编程的艺术》
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/dailingnan0827/article/details/84177050