计算机理论基础

操作系统（六）：管程（Monitor）

整理《Operating System Concepts》 第七版第六章 Monitor 部分的理论和概念，内容均为原书和中文版翻译的摘录，其中原书摘录部分由我 按个人理解简化、翻译为中文，可能存在一些不准确之处 。

  • 信号量提供了方便的机制处理进程同步，但不正确的使用信号量仍会导致时序错误，且难以检测。如：
    • 先对信号量 signal() 再 wait() 违反了互斥请求
    • 对信号量始终调用 wait() 将导致死锁
    • 一个进程遗漏了 wait() 或 signal() 将导致死锁且可能破坏互斥
  • 管程（monitor） 类型提供了一组由程序员定义的、在管程内互斥的操作。管程内定义的子程序只能访问位于管程内的局部变量和形式参数，管程内的局部变量也只能被管程内部的局部子程序访问。 管程结构确保了同时只能有一个进程在管程内活动 。
  • 管程内部可定义 condition 类型的变量以提供同步机制，称其为条件变量。条件变量可执行操作 wait() 和 signal()。
  • 我个人对条件变量的理解和信号量类似：
    • 条件变量存在于管程内部，对同一个条件变量调用操作的进程将和条件变量建立一定的联系，或者称之为绑定。对于管程内的条件变量 x，进程 P 调用 x.wait() 将时自身挂起到条件变量 x 上；当另一个进程调用 x.signal()时，在 x 上悬挂的进程会被重启，如果此时没有进程悬挂在 x 上，则 x.signal() 操作将被忽略。
    • 管程模式下的 x.signal() 和信号量的 signal() 区别在于： 信号量操作 signal() 会影响信号量的状态 ，而管程下的 x.signal() 在 x 不存在挂起进程的情况下没有任何影响。
  • 举例：进程 P 调用 x.signal()，且存在悬挂进程 Q 与条件变量 x 关联。根据管程的性质，若进程 Q 开始执行，则进程 P 必须等待。此时可能存在两种可能性，且两种可能性均有合理解释：
    • 进程 Q 重启且进程 P 等待：进程 P 将等待，直到进程 Q 离开管程或者等待另一个进程调用 x.signal()
    • 进程 P 唤醒进程 Q 且进程 P 继续执行：进程 Q 被唤醒，但仍然会等待，直到进程 P 离开管程，或者另一个触发条件。因为 P 已经在管程中执行，看起来此种方案更合理，但这破坏了进程 Q 正在等待的逻辑条件，进程 Q 已被触发但又未执行，因此状态难以描述
    • Pascal 语言采用折中方式，当进程 P 执行 x.signal() 时，它会立刻离开管程，且进程 Q 会立刻重新执行

哲学家进餐问题的管程解法

  • 使用 进程同步 中的一种策略：当哲学家在两只筷子均可用的情况下才拿起筷子，且拿起两只筷子的动作是非抢占的。
  • 为哲学家设置三种状态：enum {THINKING, HUNGRY, EATING} state[5]
  • 哲学家 i 只有在两个邻居都不进餐时才能将变量 state[i] 设置为 EATING，当他处在饥饿状态又无法进餐时可以使自己忍耐一段时间：(state[(i-1)%5] != EATING) && (state[(i+1)%5] != EATING)
  • 下面给出用管程解决的哲学家进餐问题，只解决了互斥问题，不会导致死锁，但可能导致某个哲学家过度饥饿而死。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
monitor dp{
    enum {THINKING, HUNGRY, EATING} state[5];
    condition self[5];
    void pickup(int i){
        state[i] = HUNGRY;
        test(i);
        if (state[i] != EATING)
            self[i].wait();
    }
    void putdown(int i){
        state[i] = THINKING;
        test((i-1) % 5);
        test((i+1) % 5);
    }
    void test(int i){
        if ((state[(i-1)%5] != EATING) && (state[(i+1)%5] != EATING)){
            state[i] = EATING;
            self[i].signal();
        }
    }
    initialization_code(){
        for (int i = 0; i < 5; i++)
            state[i] = THINKING;
    }
}
  • 一个改进版的 Monitor 解决方案如下。筷子本身并不属于 monitor 的一部分，否则同时只能有一个哲学家在进餐。代码中 NUM_PHILS 是哲学家数目。此代码解决了哲学家饥饿问题，来自西弗吉尼亚大学。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
monitor dp{
    condition self[NUM_PHILS];
    enum states {THINKING, HUNGRY, EATING} state[NUM_PHILS-1];
    int index;
    initialization_code(){
        for (index=0; index<NUM_PHILS; index++)
            flags[index] = THINKING;
    }
    void pickup(int i) {
        state[i] = HUNGRY;
        if ((state[(i-1)%NUM_PHILS] != EATING) &&
            (state[(i+1)%NUM_PHILS] != EATING))
            state[i] = EATING;
        else {
            // 挂起，等待相邻哲学家改变状态时唤醒
            self[i].wait;
            // wait 操作被唤醒后可以改变状态为 EATING
            state[i] = EATING;
        }
    }
    void putdown(int i) {
        state[i] = THINKING;
        // 唤醒左侧哲学家
        if ((state [(i-1)%NUM_PHILS] == HUNGRY) &&
            (state [(i-2)%NUM_PHILS] != EATING))
            self[(i-1)%NUM_PHILS].signal;
        // 唤醒右侧哲学家
        if ((state [(i+1)%NUM_PHILS] == HUNGRY) &&
            (state [(i+2)%NUM_PHILS] != EATING))
            self[(i+1)%NUM_PHILS].signal;
    }
}

使用信号量实现管程

  • 要实现的管程对于重启进程采用的策略是： 调用 x.signal() 的进程挂起自己，直到重新启动的进程离开或者等待 。
  • 每个管程都有一个信号量 mutex 初始化为 1，进程进入管程之前必须通过 wait() 获得允许，离开时需要调用 signal() 释放权限。
  • 信号量 next 初始化为 0，供线程在唤醒重启进程时挂起自己，整数变量 next_count 用于对挂起在 next 上的进程数量计数。
  • 进入管程的外部子程序结构 F 如下：
1
2
3
4
5
6
7
8
9
10
void F(){
    wait(mutex);
    // 子程序执行
    // ...
    // 子程序执行结束
    if (next_count > 0)
        signal(next);    //     此前有进程挂起，重启该进程
    else
        signal(mutex);   //     管程内无进程挂起，释放控制权
}
  • 对每个管程内的条件变量 x，引入信号量 x_sem 和整数变量 x_count 记录信号量 x 上挂起的进程数量，均初始化为 0。x.wait() 和 x.signal() 实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void x.wait(){
    x_count++;            // 将进程挂起到 x 上
    if (next_count > 0)   // 当前仍有进程挂起在管程中
        signal(next);
    else
        signal(mutex);    // 无进程在等待，释放管程控制权
    wait(x_sem);          // 等待信号量 x_sem，由信号量决定唤醒哪个挂起进程
    x_count--;            // 等待结束，进程被唤醒
}

void x.signal(){
    if (x_count > 0){     // 当前有程序挂起在条件变量 x
        next_count ++;    // 自己将要被阻塞，故管程挂起数增加
        signal(x_sem);    // 释放信号量，唤醒一个挂起进程
        wait(next);       // 将自身阻塞到管程中
        next_count--;     // 被唤醒，继续执行
    }
    // 没有程序挂起在条件变量 x，不产生任何影响
}

专栏目录：计算机理论基础
此专栏的上一篇文章：操作系统（五）：进程同步
此专栏的下一篇文章：操作系统（七）：死锁

参考资料：《操作系统概念 英文第七版》，恐龙书，英文名《Operating System Concepts》，作者 Abraham Silberschatz、Peter Baer Galvin、Greg Gagne

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(http://blog.forec.cn/2016/11/24/os-concepts-6/) 、作者信息（Forec）和本声明。

分享到