CAS算法

并发编程的目的是为了让程序运行得更快，但是，并不是启动更多的线程就能让程序最大限度地并发执行。在进行并发编程时，如果希望通过多线程执行任务让程序运行得更快，会面临非常多的挑战，比如上下文切换的问题、死锁的问题，以及受限于硬件和软件的资源限制问题，本章会介绍几种并发编程的挑战以及解决方案。

上下文切换
即使是单核处理器也支持多线程执行代码，CPU通过给每个线程分配CPU时间片来实现这个机制。时间片是CPU分配给各个线程的时间，因为时间片非常短，所以CPU通过不停地切换线程执行，让我们感觉多个线程是同时执行的，时间片一般是几十毫秒（ms）。
CPU通过时间片分配算法来循环执行任务，当前任务执行一个时间片后会切换到下一个任务。但是，在切换前会保存上一个任务的状态，以便下次切换回这个任务时，可以再加载这个任务的状态。所以任务从保存到再加载的过程就是一次上下文切换。
这就像我们同时读两本书，当我们在读一本英文的技术书时，发现某个单词不认识，于是便打开中英文字典，但是在放下英文技术书之前，大脑必须先记住这本书读到了多少页的第多少行，等查完单词之后，能够继续读这本书。这样的切换是会影响读书效率的，同样上下文切换也会影响多线程的执行速度。
多线程一定快吗
下面的代码演示串行和并发执行并累加操作的时间，请分析：下面的代码并发执行一定比串行执行快吗？
public class ConcurrentTest {
private static final long count=10001;
public static void main(String[] args) throws InterruptedException{
concurrency();
serial();
}
private static void concurrency() throws InterruptedException{
long start=System.currentTimeMillis();
Thread thread=new Thread(new Runnable(){
@Override
public void run(){
int a=0;
for(long i=0;i<count;i++){
a++;
}
}
});
thread.start();
int b=0;
for(long i=0;i<count;i++){
b–;
}
thread.join();
long time=System.currentTimeMillis()-start;
System.out.println(“concurrency:”+time);
}

private static void serial(){
	long start=System.currentTimeMillis();
	int a=0;
	for(long i=0;i<count;i++){
		a++;
	}
	int b=0;
	for(long i=0;i<count;i++){
		b--;;
	}
	long time=System.currentTimeMillis()-start;
	System.out.println("serial:"+time); 
}

}
测试结果（具体数据与运行环境相关）：
循环次数

串行执行耗时/ms

并发执行/ms

1万

1

2

一百万

7

4

一亿

172

90

当数据不超过一百万时，并发执行速度会比串行执行快慢。那么，为什么并发执行的速度会比串行慢呢？这是因为线程有创建和上下文切换的开销。
如何减少上下文切换
减少上下文切换的方法有无锁并发编程、CAS算法、使用最少线程和使用协程。

无锁并发编程：多线程竞争锁时，会引起上下文切换，所以多线程处理数据时，可以用一些办法来避免使用锁，如将数据的ID按照Hash算法取模分段，不同的线程处理不同段的数据。

CAS算法：Java的Atomic包使用CAS算法来更新数据，而不需要加锁。

使用最少线程：避免创建不需要的线程，如果任务很少 ，但是创建了很多的线程来处理，这样会造成大量线程都处于等待状态。

协程：在单线程里实现多任务的调度，并在单线程里维护多个任务间的切换。

死锁
锁是一个非常有用的工具，运用场景非常多，因为它使用起来非常简单，而且易于理解。但同时它也会带来一些困扰，那就是可能会引起死锁，一旦产生死锁，就会造成系统功能不可用。我们先看一段代码，这段代码会引起死锁，使线程threadA和线程threadB相互等待对方释放锁。

public class DeadLockDemo {
private static String A=“A”;
private static String B=“B”;
public static void main(String[] args){
new DeadLockDemo().deadLock();
}
private void deadLock(){
Thread threadA=new Thread(new Runnable(){
@Override
public void run(){
synchronized(A){
try {
Thread.currentThread().sleep(2000);
} catch (InterruptedException e) {
e.printStackTrace();
}
synchronized(B){
System.out.println(“AB”);
}
}
}
});
Thread threadB=new Thread(new Runnable(){
@Override
public void run(){
synchronized(B){
try {
Thread.currentThread().sleep(2000);
} catch (InterruptedException e) {
e.printStackTrace();
}
synchronized(A){
System.out.println(“BA”);
}
}
}
});
threadA.start();
threadB.start();
}
}
一旦出现死锁，业务是可以感知的，因为不能继续提供服务了。那么，这个时候我们需要通过dump线程查看到底是哪个线程出现了问题。

1、运行上述程序

2、在命令行下执行命令：jps -l

查看运行在虚拟机上的进程，找到进程的本地虚拟机唯一ID（5024）。

3、在命令行下执行命令：jstack -l 5204

生成虚拟机当前时刻的线程快照。

不难发现，两个线程都已经锁定了（Locked）一个String对象，同时又都在等待加锁(waiting to lock)另外一个线程已经锁定的一个String对象。因此产生了死锁（deadlock）。

避免死锁的常见方法

1、避免一个线程同时获取多个锁

2、避免一个线程在锁内同时占用多个资源，尽量保证每个锁只占用一个资源。

3、尝试使用定时锁，使用lock.tryLock(timeout)来替代使用内部锁机制。