管程和信号量都能解决并发问题,它们是等价的。所谓等价指的是用管程能够实现信号量,也能用信号量实现管程。但是管程在信号量所实现功能的基础上提供条件同步,使用更容易,所以 Java 采用的是管程技术。synchronized 关键字及 wait()、notify()、notifyAll() 这三个方法都是管程的组成部分。

1.信号量 vs 管程

1.1 相关概念

  1. 临界资源:虽然多个进程可以共享系统中的各种资源,但其中许多资源一次只能为一个进程所使用,我们把一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源,如打印机等。此外,还有许多变量、数据等都可以被若干进程共享,也属于临界资源。
  2. 临界区:对临界资源的访问,必须互斥地进行,在每个进程中,访问临界资源的那段代码称为临界区。
  3. 互斥:只有一个线程能访问临界区。

1.2 信号量 vs 管程

并发编程这个技术领域已经发展了半个世纪了,相关的理论和技术纷繁复杂,实际上锁机制的实现方案有两种:

  • 信号量(Semaphere):操作系统提供的一种协调共享资源访问的方法。和用软件实现的同步比较,软件同步是平等线程间的的一种同步协商机制,不能保证原子性。而信号量则由操作系统进行管理,地位高于进程,操作系统保证信号量的原子性。
  • 管程(Monitor):解决信号量在临界区的 PV 操作上的配对的麻烦,把配对的 PV 操作集中在一起,生成的一种并发编程方法。其中使用了条件变量这种同步机制。
    image-1663602318417

说明: 信号量将共享变量 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,则说明等待队列里有进程,那么唤醒一个等待进程。
    image-1663602493235

说明: 共享变量 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 阻塞队列

阻塞队列是典型的生产者-消费者模式,任何时刻只能有一个生产者线程或消费都线程访问缓冲区。并且当缓冲区满时,生产者线程必须等待,反之消费者线程必须等待。

  1. 任何时刻只能有一个线程操作缓存区:互斥访问,使用二进制信号量 mutex,其信号初始值为 1。
  2. 缓存区空时,消费者必须等待生产者:条件同步,使用资源信号量 notEmpty,其信号初始值为 0。
  3. 缓存区满时,生产者必须等待消费者:条件同步,使用资源信号量 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,使用起来不仅复杂,还容易出错。

管程在信号量的基础上,更进一步,增加了条件同步,将上述复杂的操作封起来。
image-1663602610446

JUC AQS 也是基于管程实现的,我们基于 ReentrantLock 实现一个阻塞队列,重点比较和信号量的区别。阻塞队列有两个操作分别是入队和出队,这两个方法都是先获取互斥锁,类比管程模型中的入口。

  1. 对于入队操作,如果队列已满,就需要等待直到队列不满,即 notFull.await();。
  2. 对于出队操作,如果队列为空,就需要等待直到队列不空,即 notEmpty.await();。
  3. 如果入队成功,那么队列就不空了,就需要通知条件变量:队列不空 notEmpty 对应的等待队列。
  4. 如果出队成功,那就队列就不满了,就需要通知条件变量:队列不满 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 究竟谁可以执行?

  1. Hasen 模型里面,要求 notify() 放在代码的最后,这样 T2 通知完 T1 后,T2 就结束了,然后 T1 再执行,这样就能保证同一时刻只有一个线程执行。
  2. Hoare 模型里面,T2 通知完 T1 后,T2 阻塞,T1 马上执行;等 T1 执行完,再唤醒 T2,也能保证同一时刻只有一个线程执行。但是相比 Hasen 模型,T2 多了一次阻塞唤醒操作。
  3. MESA 管程里面,T2 通知完 T1 后,T2 还是会接着执行,T1 并不立即执行,仅仅是从条件变量的等待队列进到入口等待队列里面。这样做的好处是 notify() 不用放到代码的最后,T2 也没有多余的阻塞唤醒操作。但是也有个副作用,就是当 T1 再次执行的时候,可能曾经满足的条件现在已经不满足了,所以需要以循环方式检验条件变量。

思考1:wait() 方法,在 Hasen 模型和 Hoare 模型里面,都是没有参数的,而在 MESA 模型里面,增加了超时参数,你觉得这个参数有必要吗?

有必要。Hasen 是执行完再去唤醒另外一个线程,能够保证线程的执行。Hoare 是中断当前线程,唤醒另外一个线程,执行完再去唤醒,也能够保证完成。而 MESA 是进入等待队列,不一定有机会能够执行,产生饥饿现象。

3.5 notify() 何时可以使用

除非经过深思熟虑,否则尽量使用 notifyAll(),不要使用 notify()。

那什么时候可以使用 notify() 呢?需要满足以下三个条件:

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

比如上面阻塞队列的例子中,对于“队列不满”这个条件变量,其阻塞队列里的线程都是在等待“队列不满”这个条件,反映在代码里就是下面这 3 行代码。对所有等待线程来说,都是执行这 3 行代码,重点是 while 里面的等待条件是完全相同的。

3.6 AQS 和 synchronized 原理

JUC AQS 就是基于管程实现的,内部包含两个队列,同步队列和等待队列:

Condition 的具体实现之一是 AQS 的内部类 ConditionObject,每个 Condition 都对应着一个等待队列,也就是说如果在一个锁上创建了多个 Condition 对象,也就存在多个等待队列。当调用 ConditionObject 的 await() 方法后,线程将会加入等待队列中,当调用 ConditionObject 的 signal() 方法后,线程将从等待队列转移动同步队列中进行锁竞争。

  1. 同步队列:锁被占用时,会将该线程添加到同步队列中。当锁释放后,会从队列中唤醒一个线程,又分为公平和非公平两种。
  2. 等待队列:当调用 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依赖底层的操作系统实现,所以存在用户态和内核态的切换,所以性能开销比较大
image-1663604090140

AQS 和 synchronized 都是管程 MESA 模型在 Java 中的应用。一切都套路,有章可循。

锁原理 - 信号量 vs 管程:JDK 为什么选择管程
并发编程基础 - MESA管程模型和synchronized原子性
JUC多线程:AQS抽象队列同步器原理