HICSC
008 进程管理:管程

虽然信号量机制是一种既方便、又有效的进程同步机制,但不正确的使用信号量,不仅会导致进程的时序错误,且难以检测,而且也让进程管理变得异常苦难。其主要存在的问题是:

而管程(Monitors)就是解决上述问题的一种同步工具。

什么是管程?

系统中的各种软硬件资源,均可用数据结构抽象地描述其资源特性,简单来说,就是用少量信息和对该资源的各种操作来表示该资源,而忽略其内部结构以及实现细节。就如同一个类,可以用变量和方法来分别表示其对象的各种属性和各种操作。

就比如,一台打印机,可用与分配该打印机有关的状态信息、对它执行请求和释放的操作、等待打印机的进程队列来描述,伪代码如下:

打印机 {
    // 当前状态,busy或者free
    int state;
    // 请求打印机操作
    void request();
    // 释放打印机操作
    void release();
    // 等待打印机的进程队列
    process[] waitList;
}

又比如,一个FIFO队列,可用其队列长度、队首与队尾、入队与出队等操作来描述。

如果把上述的资源替换成临界共享资源,即利用共享数据结构抽象地表示系统中的共享资源,而把对该共享数据结构的一系列操作定义为一组过程 (比如,资源的请求与释放过程)。进程对共享资源的申请、释放和其他操作,都是通过这组过程来实现的。这组过程还可以根据资源的情况,接受或者阻塞进程的访问,确保每次仅有一个进程使用共享资源,这样就可以统一管理对贡献资源的所有访问,实现进程的互斥。

代表共享资源的数据结构、对共享数据结构进行操作的一组过程 (管理程序),共同构成了一个操作系统的资源管理模块,我们称之为管程。管程被请求和释放资源的进程调用。

如果把管程的概念翻译为Java领域的语言,就是管理类的成员变量和成员方法,让这个类是线程安全的。这样是不是好理解了,而我们所熟知的一些线程安全的数据结构和并发工具来都是基于管程机制来实现的,比如:ArrayBlockingQueue和LinkedBlockingQueue等阻塞队列。

管程如何解决同步互斥问题?

在并发编程领域,有两大核心问题:一个是互斥,即同一时刻只允许一个进程(或线程)访问共享资源;另一个是同步,即进程(或线程)之间如何通信、协作。这两大问题,管程都是能够解决的。

解决互斥问题的思路很简单,就是将对共享变量的操作封装起来,任何时候,只允许一个进程(或线程)进入管程。而解决同步问题,则要复杂得多。

一个简单的解决办法是,在管程入口旁放置一个等待队列,当多个进程试图同时进入管程内部时,只允许一个进程进入,同时调用wait原语让其他进程等待并插入到等待队列中。直到该进程释放共享资源后,管程才调用signal原语,唤醒等待队列中队首进程。

这个方法很简单,但存在很严重的问题,比如:当一个进程调用了管程,在管程中时被阻塞或挂起,直到阻塞或挂起的原因解除,而在此期间,如果该进程不释放管程, 则其它进程无法进入管程,被迫长时间地等待。为了解决这个问题,引入了条件变量condition。通常,一个进程被阻塞或挂起的条件(原因)可有多个,因此在管程中设置了多个条件变量。

管程中的每个条件变量都对应有一个等待队列,用于记录因该条件变量而阻塞的所有进程。同时提供的两个PV操作,可表示为 x.wait 和 x.signal:

在管程的发展史上,先后出现过三种不同的管程模型,分别是:Hasen模型、Hoare模型和Mesa模型,这三种模型的区别主要集中在x.signal上,即不同的模型在条件满足后,对如何选择唤醒其它进程的处理方式有所不同,三种模型主要区别如下图所示。

三种管程模型对比

有两个进程T1和T2,T1执行管程的ProcedureA操作,T2执行管程的ProcedureB操作。首先T1进入管程,发现不满足条件变量,T1阻塞等待;此时,T2进入管程,执行完对应的操作后,发现条件变量对于T1来说,已经满足,这时,T2唤醒T1,告诉它需要的条件已经满足。

Hansen模型,T2唤醒T1后,T2马上结束,紧接着T1再执行。因此,Hansen模型要求唤醒操作必须放在临界区的最后,在实现上多了这样一个限制。

Hoare模型,则可以解决Hansen模型中的限制,它的解决办法是,增加一个signal队列。T2唤醒T1后,T2阻塞并插入signal队列中,T1马上执行;等T1执行完成后,再重新唤醒T2。这种思路虽然解决了前面的限制,但每次操作都要增加一个唤醒操作,抑制了效率。

Mesa模型,则在执行效率和实现灵活上作了平衡的选择,它在入口增加了一个等待队列。当T2唤醒T1,告诉它需要的条件已经满足时,T1会从等待队列里面出来,但是出来之后不是马上执行,而是重新进入到入口等待队列里面。

正是因为Mesa模型在效率和灵活相对平均,现在广泛应用的也是Mesa模型,并且Java管程的实现也是Mesa模型,这里用一段Java代码来说明以加深印象。下面的代码实现一个阻塞队列,阻塞队列有两个操作分别是入队和出队,这两个方法都通过锁来实现互斥。

// 示例来自:极客时间-Java并发编程实战第8讲
public class BlockedQueue<T> {

    final Lock lock = new ReentrantLock();
    // 条件变量:队列不满
    final Condition notFull = lock.newCondition();
    // 条件变量:队列不空
    final Condition notEmpty = lock.newCondition();

    /**
     * 对于入队操作,如果队列已满,就需要等待直到队列不满,所以这里用了notFull.await();
     * 如果入队成功,那么队列就不空了,就需要通知条件变量:队列不空notEmpty对应的等待队列。
     */
    void enqueue(T t) {
        lock.lock();
        try {
            while (队列已满) {
                notFull.await();
            }
            // 入队
            // 入队后,通知可出队
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
    }

    /**
     * 对于出队操作,如果队列为空,就需要等待直到队列不空,所以就用了notEmpty.await();
     * 如果出队成功,那就队列就不满了,就需要通知条件变量:队列不满notFull对应的等待队列。
     */
    T dequeue() {
        lock.lock();
        try {
            while (队列已空) {
                // 等待队列不空
                notEmpty.await();
            }
            // 出队
            // 出队后,通知可入队
            notFull.signal();
        } finally {
            lock.unlock();
        }
    }
}

结尾

Java语言内置的同步机制Synchronized就参考了Mesa模型,但对其进行了精简。Mesa模型中,条件变量可以有多个,而Synchronized中只有一个条件变量。使用Synchronized关键字修饰的代码块,在编译期会自动生成相关加锁和解锁的代码;而 Java SDK 并发包实现的管程支持多个条件变量,不过并发包里的锁,需要开发人员自己进行加锁和解锁操作。

并发编程里两大核心问题——互斥和同步,都可以由管程来帮你解决。学好管程,理论上所有的并发问题你都可以解决,并且很多并发工具类底层都是管程实现的。因此,下一篇文章会介绍如何使用管程来解决经典的同步问题:生产者-消费者问题、哲学家进餐问题、读者-写者问题。

参考资料

Java并发编程实战 ( 第8讲:管程:并发编程的万能钥匙) - 极客时间
《操作系统》第18讲:“信号量与管程”总结 | 张慕晖的博客
操作系统(六):管程(Monitor) | Forec’s Notes

封面图:oakie on Unsplash

Comments

Post a Message

人生在世,错别字在所难免,无需纠正。

提交评论