【详解】Java高并发之CAS
一、CAS机制
CAS机制当中使用了3个基本操作数：内存地址V，旧的预期值A，要修改的新值B。
更新一个变量的时候，只有当变量的预期值A和内存地址V当中的实际值相同时，才会将内存地址V对应的值修改为B。
从思想上来说，Synchronized属于悲观锁，悲观地认为程序中的并发情况严重，所以严防死守。
CAS属于乐观锁，乐观地认为程序中的并发情况不那么严重，所以让线程不断去尝试更新。
二、举例
当前有两个线程，执行System.out.println(i++);
接下来是时间片
------线程0------
i = 0;
------线程1------
i = 0;
------线程0------
i add => 1
i flush => 1
------线程1------
i add => 1
i flush => 1
- 可以发现两个线程同时执行i++操作时，可能有一次的操作是失败的
- 因为第一个线程的i++操作没有执行完，第二个线程就开始了执行i++
当前有两个线程，执行System.out.println(i.getAndIncrement());
接下来是时间片
------线程0------
i = 0;
------线程1------
i = 0;
------线程0------
i want to add => 1
i old value = i now value = 0
i add => 1
i flush => 1
------线程1------
i want to add => 1
i old value = 0
i now value = 1
i now value != i old value
refuse add
i old value load => 1
i want to add => 2
i old value = 1
i now value = 1
i now value = i old value
i add => 2
i flush => 2
- 可以发现CAS在执行赋值操作是，会比较原来的load的数值和此时load的数值
- 原来的赋值操作的流程是：
load => add => assign，在assign的时候，可能已经被修改了，此时的修改会破坏原来的修改 - CAS操作的流程是
load => add => loadAndCompare => assign，在assign的时候多了一步比较，判断当前的数值是否被修改过，防止破坏其他线程的修改，破坏原子性
三、CAS的缺点
1.在竞争激烈的时候，CPU开销较大
在并发量比较高的情况下，如果许多线程反复尝试更新某一个变量，却又一直更新不成功，循环往复，会给CPU带来很大的压力。
2.不能保证代码块的原子性
CAS机制所保证的只是一个变量的原子性操作，而不能保证整个代码块的原子性。比如需要保证3个变量共同进行原子性的更新，就不得不使用Synchronized了
四、利用CAS实现TryLock
需求
- 正常的synchronized是没有抢到锁，就会陷入阻塞
- 利用CAS机制，实现尝试加锁，如果加锁失败，可以执行其他的操作
编码
public class AtomicIntegerTest {
private static final CompareAndSetLock LOCK = new CompareAndSetLock();
public static void main(String[] args) throws InterruptedException {
for (int i = 0; i < 10; i++) {
new Thread(()->{
while (!Thread.interrupted()){
try {
while (!LOCK.tryLock()){
System.out.println(Thread.currentThread().getName() + " begin to do otherthing.");
LOCK.unLock();//尝试强行破坏锁
Thread.sleep(10000);
}
doSomething();
} catch (InterruptedException e) {
e.printStackTrace();
}finally {
LOCK.unLock();
}
}
}).start();
}
}
private synchronized static void doSomething() throws InterruptedException {
System.out.println(Thread.currentThread().getName() + " do something. ");
Thread.sleep(10000000);
}
}
结果
Thread-0get the lock.
Thread-3 begin to do otherthing.
Thread-2 begin to do otherthing.
Thread-4 begin to do otherthing.
Thread-5 begin to do otherthing.
Thread-1 begin to do otherthing.
Thread-7 begin to do otherthing.
Thread-0 do something.
Thread-6 begin to do otherthing.
Thread-8 begin to do otherthing.
Thread-9 begin to do otherthing.
五、ABA问题
CAS的机制是在赋值的时候进行比较，如果此时的数值没有修改，则可以完成修改
但是，会出现以下问题：
接下来是时间片
------线程0------
i = 0;
i want to add => 1
i old value = i now value = 0
i add => 1
i flush => 1
------线程1------
i = 1;
i want to add => 0
i old value = i now value = 1
i add => 0
i flush => 0
------线程2------
i = 0;
i want to add => 5
i old value = 0
i now value = 0
i add => 1
i flush => 1
在多线程情况下，如果一个对象或者变量出现了：A => B => ...... => A，此时CAS算法进行比较，会没有任何问题，进行修改。但是此时可能已经被修改过了无数次，其他线程的修改就丢失了
在内存释放上可能也会出问题，但是Java一般不会
- 在没有垃圾回收机制的内存模型中（如C++），程序员可随意释放内存。
- 假设如下事件序列：
线程 1 从内存位置V中取出A，A指向内存位置W。
线程 2 从位置V中取出A。
线程 2 进行了一些操作，释放了A指向的内存。
线程 2 重新申请内存，并恰好申请了内存位置W，将位置W存入C的内容。
线程 2 将内存位置W写入位置V。
线程 1 进行CAS操作，发现位置V中仍然是A指向的即内存位置W，操作成功
- 这里比问题 1.1 的后果更严重，实际内容已经被修改了，但线程 1 无法感知到线程 2 的修改。
- 更甚，如果线程 2 只释放了A指向的内存，而线程 1 在 CAS之前还要访问A中的内容，那么线程 1 将访问到一个野指针。
基本问题
- 在复杂的数据结构比如链表，队列，栈、树等都可能出现不可预知的问题
- 比如下面举一个链表的例子：
------线程0------
header = A
A.previous = null
A.next= B
B.previous = A
B.next= null
------线程1------
header = A
header want to set => B
B.previous = null
B.next= null
CAS => true
header = B
B.previous = null
B.next= null
------线程2------
header = B
header want to set => A
A.previous = null
A.next= B
B.previous = A
B.next= C
C.previous = B
C.next= null
CAS => true
header = A
A.previous = null
A.next= B
B.previous = A
B.next= C
C.previous = B
C.next= null
------线程0------
A.next want to set null
CAS => true
header = A
A.previous = null
A.next= null
可以看到：线程1和线程2的操作，此时就被覆盖，可能造成严重不可预知的问题
解决方式–AtomicStampedReference
可以加一个版本号，每一次修改都会更改当前版本号
- 除了对象值，AtomicStampedReference内部还维护了一个“状态戳”。
- 状态戳可类比为时间戳，是一个整数值，每一次修改对象值的同时，也要修改状态戳，从而区分相同对象值的不同状态。
- 当AtomicStampedReference设置对象值时，对象值以及状态戳都必须满足期望值，写入才会成功。
AtomicStampedReference的几个API在AtomicReference的基础上新增了有关时间戳的信息：
//比较设置 参数依次为：期望值 写入新值 期望时间戳 新时间戳
public boolean compareAndSet(V expectedReference, V newReference,
int expectedStamp, int newStamp)
//获得当前对象引用
public V getReference()
//获得当前时间戳
public int getStamp()
//设置当前对象引用和时间戳
public void set(V newReference, int newStamp)
使用：
public class AtomicStampedReferenceTest {
public static void main(String[] args) {
final AtomicStampedReference<Integer> reference = new AtomicStampedReference<Integer>(100, 0);
new Thread() {
@Override
public void run() {
Integer num = reference.getReference();
int oldStamp = reference.getStamp();
try {
Thread.sleep(500);
boolean b = reference.compareAndSet(num, 500, oldStamp, ++oldStamp);
if (!b) {
System.out.println("更改失败！！");
System.out.println("此时的旧值：" + reference.getReference());
System.out.println("此时的版本：" + reference.getStamp());
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}.start();
new Thread() {
@Override
public void run() {
Integer num = reference.getReference();
int oldStamp = reference.getStamp();
try {
reference.compareAndSet(num, 500, oldStamp, ++oldStamp);
} catch (Exception e) {
e.printStackTrace();
}
}
}.start();
new Thread() {
@Override
public void run() {
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
Integer num = reference.getReference();
int oldStamp = reference.getStamp();
reference.compareAndSet(num, 100, oldStamp, ++oldStamp);
}
}.start();
}
}
结果：
更改失败！！
此时的旧值：100
此时的版本：2
字节跳动公司氛围 560人发布