阅读更多

1 管程 MONITOR

1.1 为什么引入管程

信号量机制的不足：程序编写困难、易出错

出现了两种解决方案–管程

Brinch Hansen(1973)
Hoare（1974）

在程序设计语言中引入管程成分
一种高级同步机制

1.2 管程的定义

管程的特点

是一个特殊的模块
有一个名字
由关于共享资源的数据结构及在其上操作的一组过程组成

进程与管程：进程只能通过调用管程中的过程来间接地访问管程中的数据结构。相当于在共享变量上提供统一的互斥同步操作。因此管程 = 共享变量 + 互斥同步操作

1.3 管程要保证什么

作为一种同步机制，管程要解决两个问题

互斥
- 管程是互斥进入的——为了保证管程中数据结构的数据完整性
- 管程的互斥性是由编译器负责保证的
同步
- 管程中设置条件变量及等待/唤醒操作以解决同步问题
- 可以让一个进程或线程在条件变量上等待（此时，应先释放管程的使用权），也可以通过发送信号将等待在条件变量上的进程或线程唤醒

1.4 应用管程时遇到的问题

设问：是否会出现这样一种场景，有多个进程同时在管程中出现？

场景：当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权。当后面进入管程的进程执行唤醒操作时（例如P唤醒Q），管程中便存在两个同时处于活动状态的进程

三种处理方法：

P等待Q执行
Q等待P继续执行
规定唤醒操作为管程中最后一个可执行的操作

2 HOARE管程

因为管程是互斥进入的，所以当一个进程试图进入一个已被占用的管程时，应当在管程的入口处等待

为此，管程的入口处设置一个进程等待队列，称作入口等待队列
如果进程P唤醒进程Q，则P等待Q执行；如果进程Q执行中又唤醒进程R，则Q等待R执行；…，如此，在管程内部可能会出现多个等待进程
在管程内需要设置一个进程等待队列，称为紧急等待队列，紧急等待队列的优先级高于入口等待队列的优先级

2.1 条件变量的实现

条件变量——在管程内部说明和使用的一种特殊类型的变量var c:condition;

对于条件变量，可以执行wait和signal操作

wait©：如果紧急等待队列非空，则唤醒第一个等待者；否则释放管程的互斥权，执行此操作的进程进入c链末尾
signal©：如果c链为空，则相当于空操作，执行此操作的进程继续执行；否则唤醒第一个等待者，执行此操作的进程进入紧急等待队列的末尾

2.2 用HOARE管程解决生产者消费者问题

HOARE管程定义如下

monitor ProducerConsumer
    condition full, empty;
    integer count;
    
    procedure insert (item: integer);
    begin
        if count == N then wait(full);
        insert_item(item); count++;
        if count ==1 then signal(empty);
    end;

    function remove: integer;
    begin
        if count ==0 then wait(empty);
        remove = remove_item; count--;
        if count==N-1 then signal(full);
    end;
    count:=0;
end monitor;

生产者消费者定义如下

procedure producer;
begin
    while true do
    begin
        item = produce_item;
        ProducerConsumer.insert(item);
    end
end;

procedure consumer;
begin
    while true do
    begin
        item=ProducerConsumer.remove;
        consume_item(item);
    end
end;

3 MESA管程

Hoare管程的一个缺点

两次额外的进程切换

解决：

signal → notify
notify：当一个正在管程中的进程执行notify(x)时，它使得x条件队列得到通知，发信号的进程继续执行

3.1 使用notify要注意的问题

notify的结果：位于条件队列头的进程在将来合适的时候且当处理器可用时恢复执行。在满足某个条件时被通知，但是当其重新上cpu时，该条件是否满足是未知的，因为可能有其他进程在此之前上了CPU。因此必须用while循环取代if语句，用于包裹条件

导致对条件变量至少多一次额外的检测（但不再有额外的进程切换），并且对等待进程在notify之后何时运行没有任何限制

3.2 用MESA管程解决生产者消费者问题

void append (char x)
{
    while(count == N) cwait(notfull);
    buffer[nextin] = x;
    nextin = (nextin + 1) % N;
    count++;
    cnotify(notempty);
}

void take (char x)
{
    while(count == 0) cwait(notempty);
    x = buffer[nextout];
    nextout = (nextout + 1) % N;
    count--;
    cnotify(notfull);
}

3.3 改进notify

对notify的一个很有用的改进

给每个条件原语关联一个监视计时器，不论是否被通知，一个等待时间超时的进程将被设为就绪态
当该进程被调度执行时，会再次检查相关条件，如果条件满足则继续执行

超时可以防止如下情况的发生：

当某些进程在产生相关条件的信号之前失败时，等待该条件的进程就会被无限制地推迟执行而处于饥饿状态

3.4 引入broadcast

broadcast：使所有在该条件上等待的进程都被释放并进入就绪队列

当一个进程不知道有多少进程将被激活时，这种方式是非常方便的
例子：生产者/消费者问题中，假设insert和remove函数都适用于可变长度的字符块，此时，如果一个生产者往缓冲区中添加了一批字符，它不需要知道每个正在等待的消费者准备消耗多少字符，而仅仅执行一个broadcast，所有正在等待的进程都得到通知并再次尝试运行
当一个进程难以准确判定将激活哪个进程时，也可使用广播

3.5 HOARE管程和MESA管程的比较

Mesa管程优于Hoare管程之处在于Mesa管程错误比较少

在Mesa管程中，由于每个过程在收到信号后都重新检查管程变量，并且由于使用了while结构，一个进程不正确的broadcast广播或发信号notify，不会导致收到信号的程序出错

收到信号的程序将检查相关的变量，如果期望的条件没有满足，它会重新继续等待

4 进程间通信

5 参考

《MOOC-操作系统原理-陈向群》

Liuye Notebook

操作系统原理-同步机制2