Java多线程问题

线程与进程

线程是一个轻量级的子进程，线程类属于java.lang.包。是利用机器多个cpu的一种方式。例如 一个任务用一个线程需要100毫秒完成，那么可以使用10个线程让时间减少到10毫秒。

一个进程可以有多个线程。线程可以执行进程的任何部分。进程的同个部分可以由多个线程执行。进程有自己的地址，由进程创建的线程可以共享进程的地址空间。

线程在进程中有自己的堆栈，所有线程共享一个常见的系统资源，如堆内存。

Java中实现多线程的方法

1.实现Runnable接口，创建Thread对象。

2.继承Thread类。

用实现Runnable接口的方式比较好。Java不支持多继承，但是可以实现多个接口。实现Runnable接口时，我们可以继承其他类，Runnable只有一个run方法，很适合继承。

线程的生命周期

创建线程时，线程是new状态。启动后，线程处于runnable状态，表示准备运行。执行线程取决于ThreadSchedule。ThreadSchedule复制将cpu分配给Runnable线程池中的线程，并将线程状态改成running。线程还有waiting、blocked和dead状态。

sleep和wait方法的区别

wait方法释放锁，sleep方法不释放锁。

wait方法属于java.lang.Object类，sleep方法属于java.lang.Thread类。

start方法和run方法的区别

start：用start方法启动线程，真正实现了多线程运行。这时无需等待run方法体代码执行完毕就直接执行下面的代码。通过start方法启动线程，线程处于就绪(runnable)状态，一旦得到cpu时间片，就开始执行run方法中的代码，这里的run称谓线程体，包含了要执行的这个线程的内容，run方法运行结束，线程终止。

run：run方法只是一个普通的方法，如果直接调用run方法，程序依然只有主线程一个线程，需要等到run方法执行完再执行下面的代码。

用户线程(User Thread)和守护线程(Deamon Thread)

任何一个守护线程都是整个JVM中所有非守护线程的保姆。

守护线程又称为“服务线程”，它的优先级比较低。它不依赖与终端，但是依赖于系统。

只要jvm中有一个非守护线程在工作，守护线程就全部工作；只有最后一个非守护线程结束时，守护线程随jvm一起结束。

守护线程的作用就是为为守护线程提供服务，典型的应用就是GC(垃圾回收器)。

守护线程并非只有jvm内部提供，用户可以手动创建守护线程。方法就是调用thread.setDeamon(true)。调用该方法必须在调用start方法前。所有守护线程中创建的线程都是守护进程。并不是所有的应用都可以分配给守护线程来服务，如读写操作或逻辑计算。因为你不可能知道是否所有的用户进程完成前，守护进程是否完成了预期的任务，一旦用户进程推出了，守护进程可能还有大量的数据没来的急读写，就要随jvm一起推出运行。

volatile关键字

声明一个变量为volatile，所有的线程直接从内存中读取它的值，而不是缓存它。这确保共享变量始终是最新的。

一个线程能否启动两次

不能，如果这么做，会抛出异常。

什么是同步

同步是控制多个线程访问任何共享资源的功能。

同步可以避免一些数据一致性问题，可以避免线程干扰。

同步块优于同步方法。

死锁

两个线程正在等待对方释放持有的锁的情况称为死锁。如：

线程1：持有资源A锁，等待资源B。

线程2：持有资源B锁，等待资源A。

如何避免死锁：

锁定类的特定成员变量，而不是锁定整个类。

尝试使用join方法。

尝试避免使用嵌套同步块。

示例代码：

public class DeadLockDemo {
    private static Object lockA = new Object();
    private static Object lockB = new Object();

    private static void startThreadA() {
        Thread aThread = new Thread() {

            @Override
            public void run() {
                synchronized (lockA) {
                    try {
                        Thread.sleep(1000);
                    } catch (InterruptedException e) {
                    }
                    synchronized (lockB) {
                    }
                }
            }
        };
        aThread.start();
    }

    private static void startThreadB() {
        Thread bThread = new Thread() {
            @Override
            public void run() {
                synchronized (lockB) {
                    try {
                        Thread.sleep(1000);
                    } catch (InterruptedException e) {
                    }
                    synchronized (lockA) {
                    }
                }
            }
        };
        bThread.start();
    }

    public static void main(String[] args) {
        startThreadA();
        startThreadB();
    }
}

Thread优先级

每个线程都有优先级。值为int，取值范围为1~10。1最低，10最高。

通常较高优先级的线程获得较高的执行顺序，这取决于操作系统的ThreadScheduler实现。

我们可以手动指定线程的优先级，但不能保证优先级较高的线程一定在优先级较低的线程前执行。只是相对的。

Callable和Runnable

Callable可调用throws检查异常，而Runnable不抛出受检异常。

Runnable返回类型为void，而Callable可以返回future对象。

原子变量和CAS

对于count++这种操作来说，使用synchronzied成本太高了，需要先获取锁，最后还要释放锁，获取不到锁的情况下还要等待，还会有线程的上下文切换，这些都需要成本。

对于这种情况，完全可以使用原子变量代替，Java并发包中的基本原子变量类型有：

• AtomicBoolean：原子Boolean类型
• AtomicInteger：原子Integer类型
• AtomicLong：原子Long类型
• AtomicReference：原子引用类型

这是我们主要介绍的类，除了这四个类，还有一些其他的类，我们也会进行简要介绍。

针对Integer, Long和Reference类型，还有对应的数组类型：

• AtomicIntegerArray
• AtomicLongArray
• AtomicReferenceArray

为了便于以原子方式更新对象中的字段，还有如下的类：

• AtomicIntegerFieldUpdater
• AtomicLongFieldUpdater
• AtomicReferenceFieldUpdater

AtomicReference还有两个类似的类，在某些情况下更为易用：

• AtomicMarkableReference
• AtomicStampedReference

你可能会发现，怎么没有针对char, short, float, double类型的原子变量呢？大概是用的比较少吧，如果需要，可以转换为int/long，然后使用AtomicInteger或AtomicLong。比如，对于float，可以使用如下方法和int相互转换：

public static int floatToIntBits(float value)
public static float intBitsToFloat(int bits);

以AtomicInteger为例：

之所以称为原子变量，是因为其包含一些以原子方式实现组合操作的方法，比如：

//以原子方式获取旧值并设置新值
public final int getAndSet(int newValue)
//以原子方式获取旧值并给当前值加1
public final int getAndIncrement()
//以原子方式获取旧值并给当前值减1
public final int getAndDecrement()
//以原子方式获取旧值并给当前值加delta
public final int getAndAdd(int delta)
//以原子方式给当前值加1并获取新值
public final int incrementAndGet()
//以原子方式给当前值减1并获取新值
public final int decrementAndGet()
//以原子方式给当前值加delta并获取新值
public final int addAndGet(int delta)

这些方法的实现都依赖另一个public方法：

public final boolean compareAndSet(int expect, int update)

这是一个非常重要的方法，比较并设置，我们以后将简称为CAS。该方法以原子方式实现了如下功能：如果当前值等于expect，则更新为update，否则不更新，如果更新成功，返回true，否则返回false。

与synchronized锁相比，这种原子更新方式代表一种不同的思维方式。

synchronized是悲观的，它假定更新很可能冲突，所以先获取锁，得到锁后才更新。原子变量的更新逻辑是乐观的，它假定冲突比较少，但使用CAS更新，也就是进行冲突检测，如果确实冲突了，那也没关系，继续尝试就好了。

synchronized代表一种阻塞式算法，得不到锁的时候，进入锁等待队列，等待其他线程唤醒，有上下文切换开销。原子变量的更新逻辑是非阻塞式的，更新冲突的时候，它就重试，不会阻塞，不会有上下文切换开销。

对于大部分比较简单的操作，无论是在低并发还是高并发情况下，这种乐观非阻塞方式的性能都要远高于悲观阻塞式方式。

原子变量是比较简单的，但对于复杂一些的数据结构和算法，非阻塞方式往往难于实现和理解，幸运的是，Java并发包中已经提供了一些非阻塞容器，我们只需要会使用就可以了，比如：

• ConcurrentLinkedQueue和ConcurrentLinkedDeque：非阻塞并发队列
• ConcurrentSkipListMap和ConcurrentSkipListSet：非阻塞并发Map和Set

但compareAndSet是怎么实现的呢？我们看代码：

public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

它调用了unsafe的compareAndSwapInt方法，unsafe是什么呢？它的类型为sun.misc.Unsafe，定义为：

private static final Unsafe unsafe = Unsafe.getUnsafe();

它是Sun的私有实现，从名字看，表示的也是”不安全”，一般应用程序不应该直接使用。原理上，一般的计算机系统都在硬件层次上直接支持CAS指令，而Java的实现都会利用这些特殊指令。从程序的角度看，我们可以将compareAndSet视为计算机的基本操作，直接接纳就好。

使用CAS方式更新有一个ABA问题，该问题是指，一个线程开始看到的值是A，随后使用CAS进行更新，它的实际期望是没有其他线程修改过才更新，但普通的CAS做不到，因为可能在这个过程中，已经有其他线程修改过了，比如先改为了B，然后又改回为了A。

ABA是不是一个问题与程序的逻辑有关，如果是一个问题，一个解决方法是使用AtomicStampedReference，在修改值的同时附加一个时间戳，只有值和时间戳都相同才进行修改，其CAS方法声明为：

public boolean compareAndSet(
    V expectedReference, V newReference, int expectedStamp, int newStamp)

显式锁

显式锁接口Lock的定义为：

public interface Lock {
    void lock();
    void lockInterruptibly() throws InterruptedException;
    boolean tryLock();
    boolean tryLock(long time, TimeUnit unit) throws InterruptedException;
    void unlock();
    Condition newCondition();
}

我们解释一下：

• lock()/unlock()：就是普通的获取锁和释放锁方法，lock()会阻塞直到成功。
• lockInterruptibly()：与lock()的不同是，它可以响应中断，如果被其他线程中断了，抛出InterruptedException。
• tryLock()：只是尝试获取锁，立即返回，不阻塞，如果获取成功，返回true，否则返回false。
• tryLock(long time, TimeUnit unit) ：先尝试获取锁，如果能成功则立即返回true，否则阻塞等待，但等待的最长时间为指定的参数，在等待的同时响应中断，如果发生了中断，抛出InterruptedException，如果在等待的时间内获得了锁，返回true，否则返回false。
• newCondition：新建一个条件，一个Lock可以关联多个条件，关于条件，我们留待下节介绍。

Lock接口的主要实现类是ReentrantLock，它的基本用法lock/unlock实现了与synchronized一样的语义，包括：

• 可重入，一个线程在持有一个锁的前提下，可以继续获得该锁
• 可以解决竞态条件问题
• 可以保证内存可见性

ReentrantLock有两个构造方法：

public ReentrantLock()
public ReentrantLock(boolean fair)

参数fair表示是否保证公平，不指定的情况下，默认为false，表示不保证公平。所谓公平是指，等待时间最长的线程优先获得锁。保证公平会影响性能，一般也不需要，所以默认不保证，synchronized锁也是不保证公平的，待会我们还会再分析实现细节。

使用tryLock()，可以避免死锁。在持有一个锁，获取另一个锁，获取不到的时候，可以释放已持有的锁，给其他线程机会获取锁，然后再重试获取所有锁。

相比synchronized，ReentrantLock可以实现与synchronized相同的语义，但还支持以非阻塞方式获取锁、可以响应中断、可以限时等，更为灵活。

不过，synchronized的使用更为简单，写的代码更少，也更不容易出错。

synchronized代表一种声明式编程，程序员更多的是表达一种同步声明，由Java系统负责具体实现，程序员不知道其实现细节，显式锁代表一种命令式编程，程序员实现所有细节。

声明式编程的好处除了简单，还在于性能，在较新版本的JVM上，ReentrantLock和synchronized的性能是接近的，但Java编译器和虚拟机可以不断优化synchronized的实现，比如，自动分析synchronized的使用，对于没有锁竞争的场景，自动省略对锁获取/释放的调用。

简单总结，能用synchronized就用synchronized，不满足要求，再考虑ReentrantLock。

ConcurrentHashMap

ConcurrentHashMap，它是HashMap的并发版本，与HashMap相比，它有如下特点：

• 并发安全
• 直接支持一些原子复合操作
• 支持高并发、读操作完全并行、写操作支持一定程度的并行
• 与同步容器Collections.synchronizedMap相比，迭代不用加锁，不会抛出ConcurrentModificationException
• 弱一致性

ConcurrentHashMap是为高并发设计的，它是怎么做的呢？具体实现比较复杂，我们简要介绍其思路，主要有两点：

• 分段锁
• 读不需要锁

同步容器使用synchronized，所有方法，竞争同一个锁，而ConcurrentHashMap采用分段锁技术，将数据分为多个段，而每个段有一个独立的锁，每一个段相当于一个独立的哈希表，分段的依据也是哈希值，无论是保存键值对还是根据键查找，都先根据键的哈希值映射到段，再在段对应的哈希表上进行操作。

采用分段锁，可以大大提高并发度，多个段之间可以并行读写。默认情况下，段是16个，不过，这个数字可以通过构造方法进行设置，如下所示：

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)

concurrencyLevel表示估计的并行更新的线程个数，ConcurrentHashMap会将该数转换为2的整数次幂，比如14转换为16，25转换为32。

在对每个段的数据进行读写时，ConcurrentHashMap也不是简单的使用锁进行同步，内部使用了CAS、对一些写采用原子方式，实现比较复杂，我们就不介绍了，实现的效果是，对于写操作，需要获取锁，不能并行，但是读操作可以，多个读可以并行，写的同时也可以读，这使得ConcurrentHashMap的并行度远远大于同步容器。

ConcurrentHashMap的迭代器创建后，就会按照哈希表结构遍历每个元素，但在遍历过程中，内部元素可能会发生变化，如果变化发生在已遍历过的部分，迭代器就不会反映出来，而如果变化发生在未遍历过的部分，迭代器就会发现并反映出来，这就是弱一致性。

SkipList

ConcurrentHashMap不能排序，容器类中可以排序的Map和Set是TreeMap和TreeSet，但它们不是线程安全的。Java并发包中与TreeMap/TreeSet对应的并发版本是ConcurrentSkipListMap和ConcurrentSkipListSet。

ConcurrentSkipListMap是基于SkipList实现的，SkipList称为跳跃表或跳表，是一种数据结构，待会我们会进一步介绍。并发版本为什么采用跳表而不是树呢？原因也很简单，因为跳表更易于实现高效并发算法。

ConcurrentSkipListMap有如下特点：

• 没有使用锁，所有操作都是无阻塞的，所有操作都可以并行，包括写，多个线程可以同时写。
• 与ConcurrentHashMap类似，迭代器不会抛出ConcurrentModificationException，是弱一致的，迭代可能反映最新修改也可能不反映，一些方法如putAll, clear不是原子的。
• 与ConcurrentHashMap类似，同样实现了ConcurrentMap接口，直接支持一些原子复合操作。
• 与TreeMap一样，可排序，默认按键自然有序，可以传递比较器自定义排序，实现了SortedMap和NavigableMap接口。

我们先来介绍下跳表的结构，跳表是基于链表的，在链表的基础上加了多层索引结构。我们通过一个简单的例子来看下，假定容器中包含如下元素：

3, 6, 7, 9, 12, 17, 19, 21, 25

对Map来说，这些值可以视为键。ConcurrentSkipListMap会构造类似下图所示的跳表结构：

第二层索引	———	———	——>	9	———	———	——>	21	———	——>	null
第一层索引	——>	6	——>	9	——>	17	——>	21	———	——>	null
基本链表	3	6	7	9	12	17	19	21	25	——>	null

最下面一层，就是最基本的单向链表，这个链表是有序的。虽然是有序的，但我们知道，与数组不同，链表不能根据索引直接定位，不能进行二分查找。

为了快速查找，跳表有多层索引结构，这个例子中有两层，第一层有5个节点，第二层有2个节点。高层的索引节点一定同时是低层的索引节点，比如9和21。

高层的索引节点少，低层的多，统计概率上，第一层索引节点是实际元素数的1/2，第二层是第一层的1/2，逐层减半，但这不是绝对的，有随机性，只是大概如此。

对于每个索引节点，有两个指针，一个向右，指向下一个同层的索引节点，另一个向下，指向下一层的索引节点或基本链表节点。

有了这个结构，就可以实现类似二分查找了，查找元素总是从最高层开始，将待查值与下一个索引节点的值进行比较，如果大于索引节点，就向右移动，继续比较，如果小于，则向下移动到下一层进行比较。

这个结构是有序的，查找的性能与二叉树类似，复杂度是O(log(N))，不过，这个结构是如何构建起来的呢？

与二叉树类似，这个结构是在更新过程中进行保持的，保存元素的基本思路是：

1. 先保存到基本链表，找到待插入的位置，找到位置后，先插入基本链表
2. 更新索引层。

对于索引更新，随机计算一个数，表示为该元素最高建几层索引，一层的概率为1/2，二层为1/4，三层为1/8，依次类推。然后从最高层到最低层，在每一层，为该元素建立索引节点，建的过程也是先查找位置，再插入。

对于删除元素，ConcurrentSkipListMap不是一下子真的进行删除，为了避免并发冲突，有一个复杂的标记过程，在内部遍历元素的过程中会真正删除。

以上我们只是介绍了基本思路，为了实现并发安全、高效、无锁非阻塞，ConcurrentSkipListMap的实现非常复杂，具体我们就不探讨了，感兴趣的读者可以参考其源码，其中提到了多篇学术论文，论文中描述了它参考的一些算法。

对于常见的操作，如get/put/remove/containsKey，ConcurrentSkipListMap的复杂度都是O(log(N))。

并发包中的各种队列

Java并发包提供了丰富的队列类，可以简单分为：

• 无锁非阻塞并发队列：ConcurrentLinkedQueue和ConcurrentLinkedDeque
• 普通阻塞队列：基于数组的ArrayBlockingQueue，基于链表的LinkedBlockingQueue和LinkedBlockingDeque
• 优先级阻塞队列：PriorityBlockingQueue
• 延时阻塞队列：DelayQueue
• 其他阻塞队列：SynchronousQueue和LinkedTransferQueue

无锁非阻塞是这些队列不使用锁，所有操作总是可以立即执行，主要通过循环CAS实现并发安全，阻塞队列是指这些队列使用锁和条件，很多操作都需要先获取锁或满足特定条件，获取不到锁或等待条件时，会等待(即阻塞)，获取到锁或条件满足再返回。

这些队列迭代都不会抛出ConcurrentModificationException，都是弱一致的，后面就不单独强调了。