并发编程-并发的基础知识

1. 线程状态转换

重点注意：

• Waiting和 Blocked

从linux内核来看，线程Waiting和 Blocked都是等待状态，都是暂停线程，都需要进行上下文切换没区别，他们的区别在于唤醒方式不同，Waiting 是用户唤醒，而 Blocked 是系统唤醒。

通常我们在系统级别说线程的Blocked，是说线程操作I/O，被暂停了，这种线程由linux内核来唤醒，例如：I/O设备报告数据来了，内核把Blocked线程放进可运行的进程队列，依次得到处理器时间；而Waiting是说，该线程在等待一个内核mutex对象，另个线程signal这个mutex后，这个线程才可以继续运行。区别在于由谁唤醒，是操作系统，还是另一个线程。

• sleep(long) 不释放锁，而wait()会释放锁，都进入WAITING状态，wait()返回后，重新竞争锁，进入BLOCKED状态。

2. 如何减少上下文切换

上下文切换指的是单个处理器处理多个线程时，时间片分配给不同的线程引起的处理器当前状态的保存和加载。发生在线程切换的时刻，保存当前线程运行状态，加载即将执行的线程状态。

锁竞争会引起上下文的切换，要减少上下文切换可以使用：

• 无锁并发编程，例如将数据分段处理
• CAS算法，CAS没有竞争锁的过程，自然也不会引起线程切换。
• 避免创建不必要的线程
• 协程：在单线程里实现多任务调度，在单线程里维持多任务间的切换。

3. 避免死锁

• 避免一个线程同时获取多个锁
• 避免一个线程在一个锁内占用多个资源
• 尝试使用定时锁，使用lock.tryLock(timeout)来替代使用内部锁
• 对于数据库锁，加锁和解锁必须在一个数据库连接里，否则会出现解锁失败

4. CAS操作

compare and set

• 原子操作，实现不被打断的数据交换操作，避免多线程同时改写某数据时由于执行顺序不确定以及中断的不可预知性而产生数据不一致问题
• 操作方式：将内存中的值与预期值进行比较，如果两个值一致，可以写入新的值；否则什么都不做或者重试

  CAS有3个操作数：
  
  内存值V
  旧的预期值A
  要设置的新值B
  
  当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值(A和内存值V相同时，将内存值V修改为B)，
  而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试(或者什么都不做)。

5. 重量级锁Synchronized

在JDK1.5之前都是使用synchronized关键字保证同步的，Synchronized 的作用相信大家都已经非常熟悉了；

它可以把任意一个非NULL的对象当作锁：

• 作用于方法时，锁住的是对象的实例(this)；
• 当作用于静态方法时，锁住的是Class实例，又因为Class的相关数据存储在永久带PermGen（jdk1.8则是metaspace），永久带是全局共享的，因此静态方法锁相当于类的一个全局锁，会锁所有调用该方法的线程；
• synchronized作用于一个对象实例时，锁住的是所有以该对象为锁的代码块。

它有多个队列，当多个线程一起访问某个对象监视器的时候，对象监视器会将这些线程存储在不同的容器中。

• Contention List：竞争队列，所有请求锁的线程首先被放在这个竞争队列中；
• Entry List：锁池，Contention List中那些有资格成为候选资源的线程被移动到Entry List中；
• Wait Set：等待池，哪些调用wait方法的线程被放置在这里进行WAITING；
• OnDeck：任意时刻，最多只有一个线程正在竞争锁资源，该线程被成为OnDeck；
• Owner：当前已经获取到所资源的线程被称为Owner；
• !Owner：当前释放锁的线程。

JVM每次从队列的尾部取出一个数据用于锁竞争候选者（OnDeck），但是并发情况下，ContentionList会被大量的并发线程进行CAS访问，为了降低对尾部元素的竞争，JVM会将一部分线程移动到EntryList中作为候选竞争线程。Owner线程会在unlock时，将ContentionList中的部分线程迁移到EntryList中，并指定EntryList中的某个线程为OnDeck线程（一般是最先进去的那个线程）。Owner线程并不直接把锁传递给OnDeck线程，而是把锁竞争的权利交给OnDeck，OnDeck需要重新竞争锁。这样虽然牺牲了一些公平性，但是能极大的提升系统的吞吐量，在JVM中，也把这种选择行为称之为“竞争切换”。

OnDeck线程获取到锁资源后会变为Owner线程，而没有得到锁资源的仍然停留在EntryList中。如果Owner线程调用wait方法，则转移到WaitSet队列中，直到某个时刻通过notify或者notifyAll唤醒，会重新进去EntryList中。

处于ContentionList、EntryList中的线程都处于阻塞状态，该阻塞是由操作系统来完成的（Linux内核下采用pthread_mutex_lock内核函数实现的）。

Synchronized是非公平锁。
Synchronized在线程进入ContentionList时，等待的线程会先尝试自旋获取锁，如果获取不到就进入ContentionList，这明显对于已经进入队列的线程是不公平的，还有一个不公平的事情就是自旋获取锁的线程还可能直接抢占OnDeck线程的锁资源。

5.1 Synchronized的作用

在JDK1.5之前都是使用synchronized关键字保证同步的，
它可以把任意一个非NULL的对象当作锁。

• 作用于方法时，锁住的是对象的实例(this)；
• 当作用于静态方法时，锁住的是Class实例，又因为Class的相关数据存储在永久带PermGen（jdk1.8则是metaspace），永久带是全局共享的，因此静态方法锁相当于类的一个全局锁，会锁所有调用该方法的线程；
• 当作用于一个对象实例时，锁住的是所有以该对象为锁的代码块。

5.2 Synchronized的实现

它有多个队列，当多个线程一起访问某个对象监视器的时候，对象监视器会将这些线程存储在不同的容器中，如下如所示：

1. Contention List：竞争队列，所有请求锁的线程首先被放在这个竞争队列中；
2. Entry List：Contention List中那些有资格成为候选资源的线程被移动到Entry List中；
3. Wait Set：哪些调用wait方法被阻塞的线程被放置在这里；
4. OnDeck：任意时刻，最多只有一个线程正在竞争锁资源，该线程被成为OnDeck；
5. Owner：当前已经获取到所资源的线程被称为Owner；
6. !Owner：当前释放锁的线程。

JVM每次从队列的尾部取出一个数据用于锁竞争候选者（OnDeck），但是并发情况下，ContentionList会被大量的并发线程进行CAS访问，为了降低对尾部元素的竞争，JVM会将一部分线程移动到EntryList中作为候选竞争线程。Owner线程会在unlock时，将ContentionList中的部分线程迁移到EntryList中，并指定EntryList中的某个线程为OnDeck线程（一般是最先进去的那个线程）。Owner线程并不直接把锁传递给OnDeck线程，而是把锁竞争的权利交给OnDeck，OnDeck需要重新竞争锁。这样虽然牺牲了一些公平性，但是能极大的提升系统的吞吐量，在JVM中，也把这种选择行为称之为“竞争切换”。

OnDeck线程获取到锁资源后会变为Owner线程，而没有得到锁资源的仍然停留在EntryList中。如果Owner线程被wait方法阻塞，则转移到WaitSet队列中，直到某个时刻通过notify或者notifyAll唤醒，会重新进去EntryList中。

处于ContentionList、EntryList、WaitSet中的线程都处于阻塞状态，该阻塞是由操作系统来完成的（Linux内核下采用pthread_mutex_lock内核函数实现的）。

5.3 Synchronized的非公平性

• Synchronized在线程进入ContentionList时，等待的线程会先尝试自旋获取锁，如果获取不到就进入ContentionList，这明显对于已经进入队列的线程是不公平的
• 自旋获取锁的线程还可能直接抢占OnDeck线程的锁资源。

6.等待/通知机制

帮助理解：每个对象都有一个等待池与锁池，并发编程访问临界资源时（共享对象），

• 当共享对象调用wait函数时，当前线程阻塞进入等待池，等待池中的线程处于Waiting状态
• 当共享对象调用notify函数时，随机从等待池中唤醒一个线程，该线程进入到锁池参与锁竞争，若没有立即获取到锁，此时处于Blocked状态；
• 当共享对象调用notifyAll函数时，唤醒等待池中所有的线程，所有线程进入到锁池参与锁竞争。
  开发中常建议使用notifyAll()