Notes
Search…
⌃K

Preface

管程

管程(Monitor)作为一种解决并发问题的模型,是继信号量模型之后的一项重大创新,它与信号量在逻辑上是等价的(可以用管程实现信号量,也可以用信号量实现管程),但是相比之下管程更易用。
管程,指的是管理共享变量以及对共享变量的操作过程,让他们支持并发。
管程有三种模型:Hasen 模型Hoare 模型MESA 模型

MESA 模型

应用最广泛的事 MESA 模型。
并发编程的两大核心问题:互斥同步

管程解决互斥问题

将共享变量及其对共享变量的操作统一封装起来。可以看出,管程和面向对象的思路类似,这可能也是 Java 选择管程模型的原因之一吧。

管程解决同步问题

  • 入口等待队列:当多个线程同时试图进入管程内部时,只允许一个线程进入,其他线程则在入口等待队列中等待。可参考 Java synchronized 实现中 ObjectMonitor 对象的 _EntryList 字段。
  • 条件变量
  • 条件变量等待队列:每个条件变量都对应有一个等待队列。可参考 Java synchronized 实现中 ObjectMonitor 对象的 _WaitSet 字段。
    • 进入条件变量等待队列:在 Java 里面采用 wait() 或 Condition.await() 实现。
    • 通知条件变量:在 Java 里面采用 notify()/notifyAll() 或 Condition.signal() 实现。

三种模型对比

管程的三种模型的核心区别在于如何通知相关线程:
  • Hasen 模型: 要求通知放在最后,线程 T2通知 T1后,T2就运行结束了,然后 T1执行。
  • Hoare 模型:T2 通知T1后,T2阻塞,T1执行;等 T1执行完,唤醒 T2。所以 T2多了一次阻塞唤醒操作。
  • MESA 模型:T2通知T1后,T2继续执行,T1从条件等待队列进入入口等待队列。
    • 优点:通知不用放在最后,T2也没有多余的阻塞唤醒操作。
    • 缺点:当 T1再次执行的时候,可能条件已经变化不满足了。所以 MESA 模型需要以循环的方式检验条件变量,有一个编程范式,见下面代码。
while(条件不满足) {
wait();
}

notify() 何时用

一般来说,除非经过深思熟虑,否则尽量使用 notifyAll()
当满足以下三个条件时,可以使用 notify():
  1. 1.
    所有等待线程拥有相同的等待条件;
  2. 2.
    所有等待线程被唤醒后,执行相同的操作;
  3. 3.
    只需要唤醒一个线程

Java 与 管程

管程有三种模型,Java 参考了 MESA 模型,并实现了它。
synchronizedwait()notify() 不过是操作系统领域里管程模型的一种实现而已。Java SDK 并发包里的 LockCondition 是管程的另一种实现。
  • 内置的 synchronized 是对 MESA 模型的精简,MESA 模型可以有多个条件变量,synchronized 只有一个。但是使用简单,会自动加锁、解锁。
  • JDK 并发包的 LockCondition 是另一套实现,支持多个条件变量,但是需要手动加锁和解锁。

信号量

信号量(Semaphore) 在1965年提出,之后一直都是并发编程领域的王者,直到管程模型被提出。
信号量模型
信号量模型:一个计数器、一个等待队列、三个方法。
  • init():设置计数器初始值。
  • down():计数器减 1;如果此时计数器的值小于 0,则当前线程进入等待队列阻塞,否则当前线程可以继续执行。
  • up():计数器的值加 1;如果此时计数器的值小于或者等于 0,则唤醒等待队列中的一个线程,并将其从等待队列中移除。
这三个方法都是原子性的,由实现方保证。
Java 的信号量由java.util.concurrent.Semaphore实现,up()对应acquire()down()对应release()

分工、同步、互斥

并发编程可以总结为三个核心问题:分工、同步、互斥。
为了性能,如 IO 等待的时候不能让 CPU 闲着,所以我们把任务拆分交替执行,有了分时操作系统,出现了并发,后来 CPU 多核了又有了并行计算,也就是分工。
线程之间需要通信,于是操作系统提供了一些让进程,线程之间通信的方式,也就是同步
并发和通信带来了多线程并发操作共享资源的问题,又要将对共享资源的访问串行化,所以设计了了锁,信号量等,也就是互斥

分工

分工指的是如何高效地拆解任务并分配给线程
Java SDK 并发包里的 Executor、Fork/Join、Future 本质上都是一种分工方法。
并发编程领域的设计模式:生产者 - 消费者、Thread-Per-Message、Worker Thread 模式等都是用来指导你如何分工的。

同步

同步指的是线程之间如何协作。
Java SDK 并发包里的 Executor、Fork/Join、Future 本质上都是分工方法,但同时也能解决线程协作的问题。Java SDK 里提供的 CountDownLatch、CyclicBarrier、Phaser、Exchanger 也都是用来解决线程协作问题的。
协作问题的本质:当某个条件不满足时,线程需要等待,当某个条件满足时,线程需要被唤醒执行。
解决协作问题的核心技术是管程,上面提到的所有线程协作技术底层都是利用管程解决的。

互斥

互斥是保证同一时刻只允许一个线程访问共享资源。
分工、同步主要强调的是性能,但并发程序里还有一部分是关于正确性的,用专业术语叫“线程安全”。
不正确的主要源头是可见性问题、有序性问题和原子性问题。Java 引入内存模型可以避免可见性问题、有序性问题,但是还不足以完全解决线程安全问题。解决线程安全问题的核心方案还是互斥
实现互斥的核心技术就是,Java 语言里 synchronized、SDK 里的各种 Lock 都能解决互斥问题。
CountDownLatch 就是一种典型的同步方式,而可重入锁则是一种互斥手段。

微观

CPU、内存、I/O 设备这三者的速度差别非常大,为了合理利用 CPU 的性能,平衡三者的速度,一般有如下措施:
  • 硬件:CPU 增加缓存,均衡 CPU 与内存的速度。会带来可见性问题。
  • 操作系统:增加进程、线程,分时复用 CPU,均衡 CPU 与 IO 设备的速度。会带来原子性问题。
  • 编译器:优化指令执行顺序,使缓存能更加合理利用。会带来有序性问题。
但是这三个优化又带来了问题。

可见性

CPU 缓存导致可见性问题。一个线程对共享变量的修改,另外一个线程能够立刻看到,我们称为可见性
单核 CPU 倒是没什么问题,但是多核 CPU 每核有自己的缓存,会导致可见性问题。

原子性

分时操作系统的线程切换带来原子性问题。一个或者多个操作在 CPU 执行的过程中不被中断的特性称为原子性。CPU 能保证的原子操作是 CPU 指令级别的,而不是高级语言的操作符。
32位机器上对 long 进行操作不具有原子性。所以对 long 和 double 类型的变量,如有并发操作,最好加 volatile 或加锁。

有序性

编译优化带来有序性问题。
如下代码是双重检查机制创建单例对象,但是有问题。在 new 一个对象时,重排序后可能的执行方式为:
  1. 1.
    分配一块内存 M;
  2. 2.
    将 M 的地址赋值给 instance 变量;
  3. 3.
    最后在内存 M 上初始化 Singleton 对象。
若线程 A 拿到锁,执行了 new 方法,然后切换到线程 B,那么有可能线程 B 判断 instance 不为 null(锁外面的检查),但是 instance 的内容还没初始化。可以用 volatile 解决,禁止指令重排序。
public class Singleton {
static Singleton instance;
static Singleton getInstance(){
if (instance == null) {
synchronized(Singleton.class) {
if (instance == null)
instance = new Singleton();
}
}
return instance;
}
}

宏观

并发编程中我们需要注意的问题有很多,主要是:安全性问题活跃性问题性能问题

安全性问题

线程安全本质上就是正确性,而正确性的含义就是程序按照我们期望的执行。上文已经提到并发 Bug 的源头是原子性、可见性、有序性。但并不是所有的代码都需要分析上面三个问题,只有一种情况需要:存在共享数据并且该数据会发生变化,通俗地讲就是有多个线程会同时读写同一数据
所以若能做到不共享数据或者数据状态不发生变化,也能够保证线程安全。这类技术方案有线程本地存储(Thread Local Storage,TLS)、不变模式等等。
当多个线程同时访问同一数据,并且至少有一个线程会写这个数据的时候,叫做数据竞争Data Race)。
竞态条件(Race Condition)程序的执行结果依赖线程执行的顺序。也可以这样理解竞态条件,在并发场景中,程序的执行依赖于某个状态变量,当某个线程发现状态变量满足执行条件后,开始执行操作;可是就在这个线程执行操作的时候,其他线程同时修改了状态变量,导致状态变量不满足执行条件了。
面对数据竞争和竞态条件问题,都可以用互斥这个技术方案,逻辑上可以统一为:

活跃性问题

活跃性问题:某个操作无法执行下去。有三种情况:
  • 死锁:一组互相竞争资源的线程因互相等待,导致“永久”阻塞的现象。
  • 活锁:线程虽然没有发生阻塞,但仍然会存在执行不下去。可以用一个随机等待时间解决。Raft 分布式一致性算法中也用到了。
  • 饥饿:线程因无法访问所需资源而无法执行下去。
    • 若线程优先级不均匀,低优先级线程执行机会很小,则可能发生饥饿;
    • 持有锁的线程,执行时间太长,也可能导致饥饿;
    • 解决方案:一保证资源充足,二公平分配资源,三避免持有锁的线程执行过长。一、三比较难满足,第二点可以用公平锁(先来后到的方案,线程的等待是有顺序的)来解决。

性能问题

锁的过度使用可能导致串行化的范围过大,这样就不能够发挥多线程的优势了。
  • 无锁的算法和数据结构:线程本地存储 (Thread Local Storage, TLS)、写入时复制 (Copy-on-write)、乐观锁等;原子类是无锁的数据结构;Disruptor 是一个无锁的内存队列。
  • 减少锁持有的时间:使用细粒度的锁(如 ConcurrentHashMap 1.8之前),读写锁等。
性能指标:
  • 吞吐量:单位时间内能处理的请求数量。
  • 延迟:从发出请求到收到响应的时间。
  • 并发量:能同时处理的请求数量。一般来说随着并发量的增加、延迟也会增加。所以延迟这个指标,一般都会是基于并发量来说的。例如并发量是 1000 的时候,延迟是 50 毫秒。