并发理论基础

并发理论基础

并发理论基础-笔记

内容

并发解决的功能

分工、同步、互斥

分工

Java SDK 并发包里的 Executor、Fork/Join、Future 本质上都是一种分工方法。除此之外，并发编程领域还总结了一些设计模式，基本上都是和分工方法相关的，例如生产者 - 消费者、Thread-Per-Message、WorkerThread 模式

同步

一个线程执行完了一个任务，如何通知执行后续任务的线程开工。

Java SDK 并发包里的 Executor、Fork/Join、Future 本质上都是分工方法，但同时也能解决线程协作的问题。例如，用 Future 可以发起一个异步调用，当主线程通过 get() 方法取结果时，主线程就会等待，当异步执行的结果返回时，get() 方法就自动返回了。主线程和异步线程之间的协作，Future 工具类已经帮我们解决了。除此之外，Java SDK 里提供的 CountDownLatch、CyclicBarrier、Phaser、Exchanger 也都是用来解决线程协作问题的。

在 Java 并发编程领域，解决协作问题的核心技术是管程，上面提到的所有线程协作技术底层都是利用管程解决的。管程是一种解决并发问题的通用模型，除了能解决线程协作问题，还能解决下面我们将要介绍的互斥问题。

互斥

互斥，指的是同一时刻，只允许一个线程访问共享变量。

分工、同步主要强调的是性能，但并发程序里还有一部分是关于正确性的，用专业术语叫“线程安全”。

实现互斥的核心技术就是锁，Java 语言里 synchronized、SDK 里的各种 Lock 都能解决互斥问题。

虽说锁解决了安全性问题，但同时也带来了性能问题，那如何保证安全性的同时又尽量提高性能呢？可以分场景优化，Java SDK 里提供的 ReadWriteLock、StampedLock就可以优化读多写少场景下锁的性能。还可以使用无锁的数据结构，例如 Java SDK 里提供的原子类都是基于无锁技术实现的。
除此之外，还有一些其他的方案，原理是不共享变量或者变量只允许读。这方面，Java 提供了 Thread Local 和 final 关键字，还有一种 Copy-on-write 的模式。

01 可见性、原子性和有序性问题

语言中属于进阶知识。

会涉及很多底层知识。比如：操作系统

并发层序的Bug往往会诡异地出现，然后又诡异的消失。

1. CPU增加缓存，均衡与内存的速度差异
2. 操作系统增加了进程、线程，分时复用CPU，进而均衡CPU与I/O设备速度差异
3. 编译程序优化指令执行次序。

1.不同缓存导致的可见性问题

一个线程对共享变量的修改，另一个线程能够立刻看到，称为可见性。

多核时代，每颗CPU都有自己的缓存，这是就需要解决不同CPU的不同缓存可见性。

2.线程切换带来的原子性问题

一个操作或多个操作在执行过程中不可中断的特性称为原子性。

如：一条高级语言语句count++;，由三条CPU指令执行，线程可能在三条指令中任意一条执行完时切换。

3.编译优化带来的有序性问题

如：双重校验锁的并发问题。

public class Singleton {
	static Singleton instance;
	static Singleton getInstance(){
        if (instance == null) {
            synchronized(Singleton.class) {
            if (instance == null)
                instance = new Singleton();
            }
        }
        return instance;
	}
}

new 对象的指令。

• 分配内存M
• 初始化Singleton对象
• M的地址赋值给instance变量

出现问题的步骤：

1. 对象未实例化，线程A拿到锁，申请内存M；
2. 线程A 将M的地址赋值给instance变量，休眠。线程B开始执行，判断instance不为空，返回实例。
3. 线程B执行过程中发现成员变量为空，报NULLException

如果对instance进行volatile声明，禁止指令重排序，可以避免改情况发生。

02 Java内存模型

可见性、有序性的解决方法：禁用缓存和禁止编译优化指令重排。

全局禁用会导致程序性能低，Java内存模型提供了程序员按需禁用的方法。

按需禁用包含volatile、synchronized、final三个关键字，六项Happens-Before原则。

JDK1.5对volatile增强

线程 A 执行 writer() 方法，按照 volatile 语义，会把变量“v=true” 写入内存；假设线程 B 执行 reader() 方法，同样按照 volatile 语义，线程 B会从内存中读取变量 v，如果线程 B 看到 “v == true” 时，那么线程 B 看到的变量 x 是多少呢？

class VolatileExample {
	int x = 0;

    volatile boolean v = false;
        public void writer() {
        x = 42;
        v = true;
    }
    
    public void reader() {
        if (v == true) {
        // 这里 x 会是多少呢？
        }
    }
}

1.5之前，x可能是0，也可能是42。

Happens-Before原则

前一个操作对于后一个来说是可见的。

1. 程序的顺序性原则

2. 操作可见性的传递。x=42先执行，volatile v == true先执行，x就可以看到值为42

3. 管程中锁的规则

   线程B对于代码块加锁，可以看到线程A对代码块解锁前的x=12赋值操作。

   synchronized (this) { // 此处自动加锁
       // x 是共享变量, 初始值 =10
       if (this.x < 12) {
       this.x = 12;
       }
   } // 此处自动解锁

4. 线程start规则-线程启动

   子线程B可以看到主线程A调用start()之前的操作

   Thread B = new Thread(()->{
       // 主线程调用 B.start() 之前
       // 所有对共享变量的修改，此处皆可见
       // 此例中，var==77
   });
   // 此处对共享变量 var 修改
   var = 77;
   // 主线程启动子线程
   B.start();

5. 线程join规则-线程等待

   主线程 A 调用join()时，可以看到子线程 B 的操作。

   Thread B = new Thread(()->{
       // 此处对共享变量 var 修改
       var = 66;
   });
   // 例如此处对共享变量修改，
   // 则这个修改结果对线程 A 可见
   // 主线程启动子线程
   B.start();
   B.join()
   // 子线程所有对共享变量的修改
   // 在主线程调用 B.join() 之后皆可见
   // 此例中，var==66

final关键字

1.5 以后 Java 内存模型对 final 类型变量的重排进行了约束。现在只要我们提供正确构造函数没有“逸出”，就不会出问题了。

// 以下代码来源于【参考 1】
final int x;
// 错误的构造函数
public FinalFieldExample() {
    x = 3;
    y = 4;
    // 此处就是讲 this 逸出，
    global.obj = this;
}

在构造函数里面将 this 赋值给了全局变量 global.obj，这就是“逸出”，线程通过 global.obj 读取 x 是有可能读到 0的。

参考

JMM中文

03-04 互斥锁

原子性问题

保证原子性：对共享变量的修改是互斥的。

锁模型：

1. 我们要把临界区要保护的资源标注出来，如图中临界区里增加了一个元素：受保护的资源 R；
2. 我们要保护资源 R 就得为它创建一把锁 LR；
3. 针对这把锁 LR，我们还需在进出临界区时添上加锁操作和解锁操作。
4. 在锁 LR 和受保护资源之间，用一条线做了关联，这个关联关系非常重要。很多并发 Bug 的出现都是因为把它忽略了，然后就出现了类似锁自家门来保护他家资产的事情，这样的 Bug 非常不好诊断，因为潜意识里我们认为已经正确加锁了。

synchronized

锁是一种通用的技术方案，Java 语言提供的 synchronized 关键字，就是锁的一种实现。

synchronized 关键字可以用来修饰方法，也可以修饰代码块。

当修饰静态方法的时候，锁定的是当前类的 Class 对象。

当修饰非静态方法的时候，锁定的是类的当前实例对象 this。

// 锁失败案例。线程A addOne value+1成功，但未解锁时，线程B掉可调用get方法，且拿到的值未+1
class SafeCalc {
  long value = 0L;
  long get() {
  	return value;
  }
  synchronized void addOne() {
  	value += 1;
  }
}

// 优化。synchronized修饰get()方法后，线程A调用addOne()方法解锁前，线程B无法调用get()方法拿不到锁。
// sync锁的对象monitor指针指向一个ObjectMonitor对象，所有线程加入他的entrylist里面，去cas抢锁；更改state加1成功则拿到锁，执行完代码，state减1释放锁。和aqs机制差不多，只是所有线程不阻塞，cas抢锁，没有队列，属于非公平锁。
class SafeCalc {
  long value = 0L;
  synchronized long get() {
  	return value;
  }
  synchronized void addOne() {
  	value += 1;
  }
}

总结

必须深入分析锁定的对象和受保护资源的关系，综合考虑受保护资源的访问路径。

一把锁保护多个资源

// 单机多线程直接锁JVM启动时的class对象
class Account {
  private int balance;

  // 转账
  void transfer(Account target, int amt){
    synchronized(Account.class) {
      if (this.balance > amt) {
          this.balance -= amt;
          target.balance += amt;
      }
    }
  }
}

总结

原子性的本质是多个操作的一致性，中间状态对外不可见。

05细粒度锁&死锁

锁Account.class是串行化的粗粒度锁。

细粒度锁：如线程A先拿账户a的锁，拿到后，去拿账户b的锁，都拿到后执行转账操作；没有拿到就等待拿锁。

死锁

例如：线程A拿到账户a的锁，等待拿账户b的锁；线程B拿到账户b的锁，等待拿到账户a的锁，就会造成死锁。

死锁的四个条件：

1. 互斥，共享资源只能被一个线程占用
2. 占有且等待
3. 不可抢占
4. 循环等待

避免死锁：

1. 互斥。除非不再共享资源

2. 占有且等待。一次性申请所有资源

   增加资源管理员，由资源管理员一次性申请所有资源。

3. 不可抢占。可以在占有资源1，无法占有资源2时，先释放资源，等待一定的时间再抢资源。

   Java语言层面的synchronized无法解决。SDK的java.util.concurrent包下的Lock解决了。

4. 循环等待。可以对资源做从小到大序号排序，先申请资源序号小的，再申请资源序号大的，线性化申请资源。

总结

我们可以利用现实中的模型来构思解决方案， 这样方案更容易理解，看清本质。

现实中的模型中的细节容易被忽视，现实世界中，人太智能了，人之间智能的交流，会让我我们忽视死锁的产生，但两个线程不会智能的交流。

06 “等待-通知”机制，优化循环等待

// 一次性申请转出账户和转入账户，直到成功
while(!actr.apply(this, target))；

如果apply耗时非常短，并发量不大，这个方案还不错。循环几次到几十次就一次性获取到转出账户和转入账户。

如果耗时长，或者兵法冲突量大时，循环等待就不适用了，这是拿锁需要上万次的循环，很消耗CPU。这是拿不到锁应该阻塞自己，拿到锁的线程释放资源后唤醒阻塞的线程。

用synchronized实现“等待-通知”

synchronized 配合 wait()、notify()、notifyAll() 这三个方法就能实现。

1. 当调用 wait() 方法后，当前线程就会被阻塞，并且进入到右边的等待队列中，这个等待队列也是互斥锁的等待队列。 线程在进入等待队列的同时，会释放持有的互斥锁；
2. 拿到锁的线程释放资源后调用 notify()，会通知等待队列（互斥锁的等待队列）中的线程。

注意点：

1. notify() 只能保证在通知时间点，条件是满足的。而被通知线程的执行时间点和通知的时间点基本上不会重合，所以当线程执行的时候，很可能条件
   已经不满足了（保不齐有其他线程插队）。
2. 被通知的线程要想重新执行，仍然需要获取到互斥锁（因为曾经获取的锁在调用 wait() 时已经释放了）。

class Allocator {
  private List<Object> als;
    // 一次性申请所有资源
    synchronized void apply(Object from, Object to){
      // 经典写法
      while(als.contains(from) ||als.contains(to)){
        try{
          wait();
        }catch(Exception e){
        }
      }
      als.add(from);
      als.add(to);
    }
    // 归还资源
    synchronized void free(Object from, Object to){
      als.remove(from);
      als.remove(to);
      notifyAll();
  	}
}

wait和sleep的区别 todo

1. wait回释放资源，sleep不会释放资源

07 并发宏观角度的安全性、活跃性、性能问题

安全性

实际开发时关注是否对共享资源既修改又读取。

解决：互斥。CPU 提供了相关的互斥指令，操作系统、编程语言也会提供相关的 API。也称为锁

活跃性

死锁、活锁、饥饿

活锁

• 描述：互相同时争抢和释放资源。
• 解决：争强资源等待随机时间

饥饿

• 描述
• 解决：
  1. 保证资源充足
  2. 公平的分配资源，公平锁
  3. 避免持有锁的线程长时间执行。

性能

并发提升效率公式：S=1/((1-a)+a/n) （阿姆达尔定律）

S：提升的效率倍数

a：可并行百分比

n：并行核数

解决：

1. 使用无锁的算法和数据结构
2. 减少锁持有的时间。如：ConcurrentHashMap的分段锁；共享读，排他写。

三个重要的性能指标：

1. 吞吐量
2. 延迟
3. 并发量

08 管程

MESA模型

public class MonitorSallProduce {
    private final Lock lock = new ReentrantLock();

    private final Condition condition = lock.newCondition();

    private int count;

    public void sall(){
        lock.lock();
        try {
            while (count == 0){
                System.out.println("库存为0，等待进货");
                condition.await();
                System.out.println("被唤醒后，开始执行await之后的代码");
            }
            count--;
            System.out.println("卖出一件商品，库存为：" + count);
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
    }

    public void produce(){
        lock.lock();
        try {
            count+=3;
            System.out.println("进货3件商品，库存为：" + count);
            condition.signalAll();
        } finally {
            lock.unlock();
        }
    }

    public static void main(String[] args) {
        MonitorSallProduce monitorSallProduce = new MonitorSallProduce();

        IntStream.range(0, 6).forEach(i -> {
            new Thread(monitorSallProduce::sall).start();
        });

        IntStream.range(0, 2).forEach(i -> {
            new Thread(monitorSallProduce::produce).start();
        });
    }
}

notify使用注意

尽量使用notifyAll()

1. 所有等待线程拥有相同的等待条件
2. 所有等待线程被换唤醒后，执行相同的操作
3. 只需要唤醒一个线程

参考

https://juejin.cn/post/7067876796775006215

09-10-11 Java线程

生命周期

生命周期：各个状态，和状态间转换机制

通用生命周期

初始化，可运行，运行，休眠，结束

• 初始化：操作系统无这个状态，JAVA中指的是JAVA线程被创建，操作系统线程还没创建
• 可运行：操作系统线程以创建，可分配CPU执行
• 运行：可运行状态的线程得到CPU，状态变为运行
• 休眠：运行状态的线程调用一个阻塞的API或者等待某个事件（LOCK的CONDITION)，线程进入休眠状态，释放CPU使用权。
• 终止：线程执行完，或者出现异常会进入终止状态。

Java生命周期

初始化NEW，运行RUNNABLE，休眠(BLOCKED,WAITING,TIMED_WAITING)，结束TERMINATED

Java线程状态转换

• NEW→RUNNABLE

  1. 继承Thread对象，重写run方法，调用start()
  2. 实现Runnable接口，实现run方法，创建线程对象，调用start()

• RUNNABLE与BLOCKED

  RUNNABLE→BLOCKED线程等待synchronized的隐式锁；BLOCKED→RUNNABLE线程拿到synchronized的隐式锁；

• RUNNABLE→WAITING

  1. 获得 synchronized 隐式锁的线程，调用无参数的 Object.wait()
  2. 调用无参数的 Thread.join() 方法
  3. 调用 LockSupport.park() 方法。Java 并发包中的锁，都是基于LockSupport.park()实现的

• RUNNABLE→TIMED_WAITING

  1. 调用带超时参数的 Thread.sleep(long millis) 方法；
  2. 获得 synchronized 隐式锁的线程，调用带超时参数的 Object.wait(long timeout) 方

  法；

  3. 调用带超时参数的 Thread.join(long millis) 方法；
  4. 调用带超时参数的 LockSupport.parkNanos(Object blocker, long deadline) 方法；
  5. 调用带超时参数的 LockSupport.parkUntil(long deadline) 方法

• RUNNABLE→FINISH

stop与interrupt方法

stop()会直接杀死线程，不会调用程序员写的显示锁，如：调用ReentrantLock的unlock()释放锁。已标记为过期

interrupt()

// 未休眠需要主动判断中断状态，休眠时抛出异常并重置中断状态
// 休眠后，调用interrupt()，抛出InterruptedException异常，并重置中断状态

try { 
	Thread.sleep(100); 
} catch(InterruptedException e){ 
// 重新设置中断标志位 
th.interrupt(); 
}

线程数

使用多线程的目的是提升性能。

性能度量：降低延迟，提高吞吐量

性能优化：Tomcat的连接数，Jdbc连接池链接数量

性能提升的方法：

1. 优化算法
2. 提升CPU、I/O综合使用率

理论线程数：

​ I/O密集型：CPU逻辑核数 * （1+（I/O耗时 / CPU耗时））

​ CPU密集型：CPU逻辑核数+1

实际线程数：

1. 不同场景的压测
2. 计算CPU、I/O设备利用率和性能指标（响应时间、吞吐量）之间的关系。定时查看线程池利用率。

I/O密集型：无特殊场景设置为 2*CPU核数+1。后续可压测，跟进线程池实际利用率

测试I/O耗时、CPU耗时：APM工具

线程池设置？

1. 线程数
2. 队列数？

每次列表查询新开多线程是否会有问题？

线程内部

每个线程都有自己的调用栈，调用栈各自的栈帧地址对应不同内存区域，局部变量在不同的内存区域中。

12 如何写好并发程序

面对对象思想写并发程序

1. 封装共享变量

   public class Counter {
       private long value;
       synchronized long get(){
       	return value;
       }
       synchronized long addOne(){
       	return ++value;
       }
   }

   不会发生变化的共享变量，建议用 final 关键字修饰 。

   既能避免并发问题，也能表明字段不变的含义。

2. 识别多个共享变量间的约束条件

   public class StockUpperLower {
   
       private final AtomicLong upper = new AtomicLong(0);
   
       private final AtomicLong lower = new AtomicLong(0);
   
       public void setUpper(long v){
           if (v < lower.get()){
               throw new IllegalArgumentException("upper < lower");
           }
           upper.set(v);
       }
   
       public void setLower(long v){
           if (v > upper.get()){
               throw new IllegalArgumentException("lower > upper");
           }
           lower.set(v);
       }
   
       public static void main(String[] args) {
           StockUpperLower stockUpperLower = new StockUpperLower();
           stockUpperLower.setUpper(10);
           stockUpperLower.setLower(2);
           new Thread(() -> {
               stockUpperLower.setUpper(5);
               System.out.println("此线程执行upper.set(v)时，另一个线程执行lower.set(v); 可以越过if的判断条件设置出 upper < lower");
           }).start();
   
           new Thread(() -> {
               stockUpperLower.setLower(7);
           }).start();
   
   
   
           System.out.println("库存上限：" + stockUpperLower.upper.get());
           System.out.println("库存下限：" + stockUpperLower.lower.get());
       }
   }

   共享变量之间的约束条件，反映在代码里，基本上都会有 if 语句。

3. 制定共享变量访问策略

   1. 避免共享
   2. 不变模式。JAVA领域少。其他领域如：Actor模式，CSP模式，函数式编程的基础
   3. 管程及其他同步工具。JAVA并发包提供的读写锁，并发容器同步工具

写并发程序规则

1. 优先使用已有成熟的并发包，而不是自己实现

2. 迫不得已时菜使用低级的同步原语？

   低级同步源语指：synchronized、Lock、Semaphore

3. 避免过早优化。安全第一，并发程序首先要保证安全，出现性能瓶颈后再优化。 性能瓶颈难以预估

参考

JSR 133

JSR133中文