管程和信号量都能解决并发问题,它们是等价的。所谓等价指的是用管程能够实现信号量,也能用信号量实现管程。但是管程在信号量所实现功能的基础上提供条件同步,使用更容易,所以 Java 采用的是管程技术。synchronized 关键字及 wait()、notify()、notifyAll() 这三个方法都是管程的组成部分。
1.信号量 vs 管程
1.1 相关概念
- 临界资源:虽然多个进程可以共享系统中的各种资源,但其中许多资源一次只能为一个进程所使用,我们把一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源,如打印机等。此外,还有许多变量、数据等都可以被若干进程共享,也属于临界资源。
- 临界区:对临界资源的访问,必须互斥地进行,在每个进程中,访问临界资源的那段代码称为临界区。
- 互斥:只有一个线程能访问临界区。
1.2 信号量 vs 管程
并发编程这个技术领域已经发展了半个世纪了,相关的理论和技术纷繁复杂,实际上锁机制的实现方案有两种:
- 信号量(Semaphere):操作系统提供的一种协调共享资源访问的方法。和用软件实现的同步比较,软件同步是平等线程间的的一种同步协商机制,不能保证原子性。而信号量则由操作系统进行管理,地位高于进程,操作系统保证信号量的原子性。
- 管程(Monitor):解决信号量在临界区的 PV 操作上的配对的麻烦,把配对的 PV 操作集中在一起,生成的一种并发编程方法。其中使用了条件变量这种同步机制。
说明: 信号量将共享变量 S 封装起来,对共享变量 S 的所有操作都只能通过 PV 进行,,封装共享变量是并发编程的常用手段。
在信号量中,当 P 操作无法获取到锁时,将当前线程添加到 同步队列(syncQueue) 中。当其余线程 V 释放锁时,从同步队列中唤醒等待线程。但当有多个线程通过信号量 PV 配对时会异常复杂,所以管程中引入了 等待队列(waitQueue) 的概念,进一步封装这些复杂的操作。
2. 信号量(Semaphere)
2.1 原理
信号中包括一个整型变量,和两个原子操作 P 和 V。其原子性由操作系统保证,这个整形变量只能通过 P 操作和 V 操作改变。
- 信号量由一个整形变量 S 和两个原子操作 PV 组成。
- P(Prolaag,荷兰语尝试减少):信号量值减 1,如果信号量值小于 0,则说明资源不够用的,把进程加入等待队列。
- V (Verhoog,荷兰语增加):信号量值加 1,如果信号量值小于等于 0,则说明等待队列里有进程,那么唤醒一个等待进程。
说明: 共享变量 S 只能由 PV 操作,PV 的原子性由操作系统保证。P 相当获取锁,可能会阻塞线程,而 V 相当于释放锁,不会阻塞线程。根据同步队列中唤醒线程的先后顺序,可以分为公平和非公平两种。
信号量分类:
- 二进制信号量:资源数目为 0 或 1。
- 资源信号量:资源数目为任何非负值。
2.2 代码实现
private class Semaphore {
private int sem;
private WaitQueue q;
void P() {
sem--;
if (sem < 0) {
// add this thread t to q;
block(t);
}
}
void V() {
sem++;
if (sem <= 0) {
// remove a thread t from q;
wakeup(t);
}
}
}
说明: Semaphere 的思路很简单,就是将共享变量 S 及其所有操作 PV 统一封装起来。事实上,封装共享变量是并发编程的常用手段。
2.3 使用场景
2.3.1 互斥访问
Semaphore mutex = new Semaphore(1);
mutex.P();
// do something
mutex.V();
实现临界区的互斥访问注意事项: 一是信号量的初始值必须为 1;二是 PV 必须配对使用。
2.3.2 条件访问
Semaphore condition = new Semaphore(0);
// ThreadA,进行等待队列中
condition.P();
// ThreadB,唤醒等待线程 ThreadA
condition.V();
实现临界区的条件访问注意事项: 初始信号量必须为 0,这样所有的线程调用 P 操作时都无法获取到锁,只能进行等待队列(相当于管程中的等待队列),当其余线程 B 调用 V 操作时会唤醒等待线程。
2.3.3 阻塞队列
阻塞队列是典型的生产者-消费者模式,任何时刻只能有一个生产者线程或消费都线程访问缓冲区。并且当缓冲区满时,生产者线程必须等待,反之消费者线程必须等待。
- 任何时刻只能有一个线程操作缓存区:互斥访问,使用二进制信号量 mutex,其信号初始值为 1。
- 缓存区空时,消费者必须等待生产者:条件同步,使用资源信号量 notEmpty,其信号初始值为 0。
- 缓存区满时,生产者必须等待消费者:条件同步,使用资源信号量 notFull,其信号初始值为 n。
private class BoundedBuffer {
private int n = 100;
private Semaphore mutex = new Semaphore(1);
private Semaphore notFull = new Semaphore(n);
private Semaphore notEmpty = new Semaphore(0);
public void product() throws InterruptedException {
notFull.P(); // 缓冲区满时,生产者线程必须等待
mutex.P();
// ...
mutex.V();
notEmpty.V(); // 唤醒等待的消费者线程
}
public void consume() throws InterruptedException {
notEmpty.P(); // 缓冲区空时,消费都线程等待
mutex.P();
// ...
mutex.V();
notFull.V(); // 唤醒等待的生产者线程
}
}
总结: 直接使用信号量,当多个 Semaphore 条件同步时,PV 配对比较困难而且容易写错。为了解决 PV 配对困难的问题,管程登场了。管程实际上是对条件同步的进一步封装。
3. 管程(Monitor)
Monitor 直译过来就是 “监视器”,操作系统领域一般都翻译成 “管程”。所谓管程,指的是管理共享变量以及对共享变量的操作过程,让他们支持并发。 翻译为 Java 领域的语言,就是管理类的成员变量和成员方法,让这个类是线程安全的。
3.1 MESA 模型
在管程的发展史上,先后出现过三种不同的管程模型,分别是:Hasen 模型、Hoare 模型和 MESA 模型。其中,现在广泛应用的是 MESA 模型,并且 Java 管程的实现参考的也是 MESA 模型。所以今天我们重点介绍一下 MESA 模型。
在并发编程领域,有两大核心问题:一个是互斥,即同一时刻只允许一个线程访问共享资源;另一个是同步,即线程之间如何通信、协作。这两大问题,管程都是能够解决的。
3.2 互斥
管程和信号量关于互斥的实现完全一样,都是将共享变量及其操作统一封装起来。
3.3 同步
在上述用信号量实现生产者-消费者模式的代码中,为了实现阻塞队列的功能,即等待-通知(wait-notify),除了使用互斥锁 mutex 外,还需要两个判断队满和队空的资源信号量 fullBuffers 和 emptyBuffers,使用起来不仅复杂,还容易出错。
管程在信号量的基础上,更进一步,增加了条件同步,将上述复杂的操作封起来。
JUC AQS 也是基于管程实现的,我们基于 ReentrantLock 实现一个阻塞队列,重点比较和信号量的区别。阻塞队列有两个操作分别是入队和出队,这两个方法都是先获取互斥锁,类比管程模型中的入口。
- 对于入队操作,如果队列已满,就需要等待直到队列不满,即 notFull.await();。
- 对于出队操作,如果队列为空,就需要等待直到队列不空,即 notEmpty.await();。
- 如果入队成功,那么队列就不空了,就需要通知条件变量:队列不空 notEmpty 对应的等待队列。
- 如果出队成功,那就队列就不满了,就需要通知条件变量:队列不满 notFull 对应的等待队列。
public class BlockedQueue<T> {
final Lock lock = new ReentrantLock();
// 条件变量:队列不满
final Condition notFull = lock.newCondition();
// 条件变量:队列不空
final Condition notEmpty = lock.newCondition();
// 入队
void enq(T x) {
lock.lock();
try {
while (队列已满) {
// 等待队列不满
notFull.await();
}
// add x to queue
// 入队后,通知可出队
notEmpty.signal();
} finally {
lock.unlock();
}
}
// 出队
void deq() {
lock.lock();
try {
while (队列已空) {
// 等待队列不空
notEmpty.await();
}
// remove the first element from queue
// 出队后,通知可入队
notFull.signal();
} finally {
lock.unlock();
}
}
}
总结: 对于用信号量实现阻塞队列,是不是感觉要简单些。这里的 notFull 相当于之前的 fullBuffers,notEmpty 相当于之前的 emptyBuffers。
3.4 wait() 的正确姿势
对于 MESA 管程来说,有一个编程范式,就是需要在一个 while 循环里面调用 wait()。这个是 MESA 管程特有的。所谓范式,就是前人总结的经验。
while (条件不满足) {
wait();
}
Hasen 模型、Hoare 模型和 MESA 模型的一个核心区别就是当条件满足后,如何通知相关线程。管程要求同一时刻只允许一个线程执行,那当线程 T2 的操作使线程 T1 等待的条件满足时,T1 和 T2 究竟谁可以执行?
- Hasen 模型里面,要求 notify() 放在代码的最后,这样 T2 通知完 T1 后,T2 就结束了,然后 T1 再执行,这样就能保证同一时刻只有一个线程执行。
- Hoare 模型里面,T2 通知完 T1 后,T2 阻塞,T1 马上执行;等 T1 执行完,再唤醒 T2,也能保证同一时刻只有一个线程执行。但是相比 Hasen 模型,T2 多了一次阻塞唤醒操作。
- MESA 管程里面,T2 通知完 T1 后,T2 还是会接着执行,T1 并不立即执行,仅仅是从条件变量的等待队列进到入口等待队列里面。这样做的好处是 notify() 不用放到代码的最后,T2 也没有多余的阻塞唤醒操作。但是也有个副作用,就是当 T1 再次执行的时候,可能曾经满足的条件现在已经不满足了,所以需要以循环方式检验条件变量。
思考1:wait() 方法,在 Hasen 模型和 Hoare 模型里面,都是没有参数的,而在 MESA 模型里面,增加了超时参数,你觉得这个参数有必要吗?
有必要。Hasen 是执行完再去唤醒另外一个线程,能够保证线程的执行。Hoare 是中断当前线程,唤醒另外一个线程,执行完再去唤醒,也能够保证完成。而 MESA 是进入等待队列,不一定有机会能够执行,产生饥饿现象。
3.5 notify() 何时可以使用
除非经过深思熟虑,否则尽量使用 notifyAll(),不要使用 notify()。
那什么时候可以使用 notify() 呢?需要满足以下三个条件:
- 所有等待线程拥有相同的等待条件;
- 所有等待线程被唤醒后,执行相同的操作;
- 只需要唤醒一个线程。
比如上面阻塞队列的例子中,对于“队列不满”这个条件变量,其阻塞队列里的线程都是在等待“队列不满”这个条件,反映在代码里就是下面这 3 行代码。对所有等待线程来说,都是执行这 3 行代码,重点是 while 里面的等待条件是完全相同的。
3.6 AQS 和 synchronized 原理
JUC AQS 就是基于管程实现的,内部包含两个队列,同步队列和等待队列:
Condition 的具体实现之一是 AQS 的内部类 ConditionObject,每个 Condition 都对应着一个等待队列,也就是说如果在一个锁上创建了多个 Condition 对象,也就存在多个等待队列。当调用 ConditionObject 的 await() 方法后,线程将会加入等待队列中,当调用 ConditionObject 的 signal() 方法后,线程将从等待队列转移动同步队列中进行锁竞争。
- 同步队列:锁被占用时,会将该线程添加到同步队列中。当锁释放后,会从队列中唤醒一个线程,又分为公平和非公平两种。
- 等待队列:当调用 await 是,会将该线程添加到等待队列中。当其它线程调用 notify 时,会将该线程从等待队列移动到同步队列中,重新竞争锁。
synchronized 也是基于管程实现的,核心的数据结构见 ObjectMonitor。synchronized对 MESA 模型进行了精简。MESA 模型中,条件变量可以有多个,Java 语言内置的管程里只有一个条件变量。
ObjectMonitor() {
_header = NULL;
_count = 0; //记录个数
_waiters = 0,
_recursions = 0;
_object = NULL;
_owner = NULL;
_WaitSet = NULL; //处于wait状态的线程,会被加入到_WaitSet
_WaitSetLock = 0 ;
_Responsible = NULL ;
_succ = NULL ;
_cxq = NULL ;
FreeNext = NULL ;
_EntryList = NULL ; //处于等待锁block状态的线程,会被加入到该列表
_SpinFreq = 0 ;
_SpinClock = 0 ;
OwnerIsThread = 0 ;
}
JVM中的同步是基于进入和退出管程(Monitor)对象实现的,每个对象实例都会有一个Monitor,并且可以和对象一个创建和销毁。java中的Monitor是由C++ 的ObjectMonitor.hpp 实现,当多个线程访问该ACC_SYNCHRONIZED时,多个线程会先放入ContentionList和_EntryList中,处于block状态的线程都会被加入到该列表。
ObjectMonitor是靠底层的Mutex Lock来实现互斥的,线程申请 Mutex 成功,则持有该 Mutex,其它线程将无法获取到该 Mutex,竞争失败的线程会再次进入 ContentionList 被挂起;线程调用wait就会释放当前持有的Mutex Lock并且当前线程进入WaitSet集合。ObjectMonitor依赖底层的操作系统实现,所以存在用户态和内核态的切换,所以性能开销比较大
AQS 和 synchronized 都是管程 MESA 模型在 Java 中的应用。一切都套路,有章可循。
锁原理 - 信号量 vs 管程:JDK 为什么选择管程
并发编程基础 - MESA管程模型和synchronized原子性
JUC多线程:AQS抽象队列同步器原理