CoderMrWu

生活诚可期,爱情价更高!

操作系统中管程的条件变量

―、管程的提出

采用信号量及P、V同步机制来编写并发程序,对于共享变量及信号量变量的操作将被 分散于各个进程中,其缺点如下。

(1)程序易读性差,因为要了解对于一组共享变量及信号量的操作是否正确,则必须通 读整个系统或者并发程序。

(2)程序不利于修改和维护,因为程序的局部性很差,所以任一组变量或一段代码的修 改都可能影响全局。

(3)正确性难以保证,因为操作系统或并发程序通常很大,要保证这样一个复杂的系统 没有逻辑错误是很难的。

为了更易于编写正确的程序,Brinch Hansen和Hoare提出了一种高级同步机制,称为管程(Monitor)

二、管程的概念及组成

一个管程是一个由过程、变量及数据结构等组成的一个集合,它们组成一个特殊的模块或软件包。进程可在任何需要的时候调用管程中的过程,但它们不能在管程之外声明的过程 中直接访问管程内的数据结构。

一个管程由四个部分组成。它们是管程名称、共享数据的说明、对数据进行操作的一组 过程和对共享数据赋初值的语句。管程能保障共享资源的互斥执行,即一次只能有一个进程 可以在管程内活动。该性能是由管程本身实现的。因此,程序员可以不必显式地编写程序代 码去实现这种同步制约。图4-5给出管程的结构,它定义了一种共享数据结构。

图4-6展示了用一种抽象的、类Pascal语言描述的管程。这里不能使用C语言,因为管 程是语言特性而C语言并不支持它。

管程具有三个主要的特性。

(1)模块化,一个管程是一个基本程序单位,可以单独编译。

(2)抽象数据类型,管程是一种特殊的数据类型,其中不仅有数据,而且有对数据进行 操作的代码。

(3)信息隐蔽,管程是半透明的,管程中的外部过程函数)实现了某些功能,管程中的 外部过程(函数)实现了某些功能,至于这些功能是怎样实现的,在其外部则是不可见的。

管程中的共享变量在管程外部是不可见的,外部只能通过调用管程中所说明的外部过程 (函数)来间接地访问管程中的共享变量;为了保证管程共享变量的数据完整性,规定管程互斥进人;管程通常是用来管理资源的,因而在管程中应当设有进程等待队以及相应的等待 及唤醒操作

管程有一个很重要的特性,即任一时刻管程中只能有一个活跃进程,这一特性使管程能有效地完成互斥。管程是编程语言的组成部分,编译器知道它们的特殊性,因此可以采用与其他过程调用不同的方法来处理对管程的调用。典型的处理方法是,当一个进程调用管程过程时,该过程中的前几条指令将检查在管程中是否有其他的活跃进程。如果有,调用进程将被挂起,直到另一个进程离开管程将其唤醒。如果没有活跃进程在使用管程,则该调用进程可以进人。进人管程时的互斥由编译器负责,但通常的做法是用一个互斥量或二元信号量。 因为是由编译器而非程序员来安排互斥,所以出错的可能性要小得多。在任一时刻,编写管 程的人无须关心编译器是如何实现互斥的,他只需知道将所有的临界区转换成管程过程即 可,绝不会有两个进程同时执行临界区中的代码。

三、管程中的条件变量

尽管管程提供了一种实现互斥的简便途径,但这还不够。我们还需要一种办法使得进程在无法继续运行时被阻塞。

在生产者——消费者问题中,很容易将针对缓冲区满和缓冲区空的测试放到管程过程中,但是生产者在发现缓冲区满的时候如何阻塞呢?解决的方法是引入条件变量(Condition Variables)以及相关的两个操作:wait和signal。当一个管程过程发现 它无法继续运行时(例如,生产者发现缓冲区满),它会在某个条件变量上(如full)执行 wait操作。该操作导致调用进程自身阻塞,并且还将另一个以前等在管程之外的进程调人管程。另一个进程,比如消费者,可以唤醒正在睡眠的伙伴进程,这可以通过对其伙伴正在等待的一个条件变量执行signal完成。

条件变量不是计数器,条件变量也不能像信号量那样积累信号以便以后使用。所以,如果向一个条件变量发送信号,但是在该条件变量上并没有等待进程,则该信号会永远丢失。 换句话说,wait操作必须在signal之前。这条规则使得实现简单了许多。实际上这不是一个问题,因为在需要时,用变量很容易跟踪每个进程的状态。原本要执行signal的进程, 只要检查这些变量便可以知道该操作是否有必要。

如果在管程中出现多个进程时怎样考虑?例如,当一个进人管程的进程执行等待操作 时,它应当释放管程的互斥权,当一个进入管程的进程执行唤醒操作时(如P唤醒Q),管 程中便存在两个同时处于活动状态的进程。处理方法有三种:

(1)P等待Q继续,直到Q退出或等待

(2)Q等待P继续,直到P等待或退出;

(3)规定唤醒为管程中最后一个可执行的操作。

第一种方法是Hoare提出的,因此称为Hoarc管程。在设计Hoare管程时,由于管程是互斥进人的,所以当一个进程试图进人一个已被占用的管程时它应当在管程的入口处等待, 因而在管程的入口处应当有一个进程等待队列,称作入口等待队列。如果进程P唤醒进程 Q,则P等待Q继续,如果进程Q在执行又唤醒进程R,则Q等待R继续,……,如此, 在管程内部,由于执行唤醒操作,可能会出现多个等待进程,因而还需要有一个进程等待队 列,这个等待队列被称为紧急等待队列。它的优先级应当高于人口等待队列的优先级signal (c):如果c链为空,则相当于空操作,执行此操作的进程继续;否则唤醒第一个等待者, 执行此操作的进程的PCB人紧急等待队列的尾部。

第二种方法有一种实现称为Mesa管程;

第三种方法是Hansen提出的,称为Brinch Hansen 管程。

点赞