条件变量与管程

我们已经有了基本的同步互斥机制实现，下面让我们用这些机制来实现一个管程，从而解决哲学家就餐问题。

为什么要使用管程呢？引入管程相当于将底层的同步互斥机制封装了起来，对外提供已经经过同步的接口供进程使用，大大降低了并行进程开发的门槛。管程主要由四个部分组成：

• 管程内部的共享变量

• 管程内部的条件变量

• 管程内部并发执行的进程

• 对局部于管程内部的共享数据设置初始值的语句

由此可见，管程把需要互斥访问的变量直接包装了起来，对共享变量的访问只能通过管程提供的相应接口，方便了多进程的编写。但是管程只有同步互斥是不够的，可能需要条件变量。条件变量类似于信号量，只不过在信号量中进程等待某一个资源可用，而条件变量中进程等待条件变量相应的资源为真。条件变量的结构体如下：

typedef struct condvar{
    // 信号量
    semaphore_t sem;
    // 正在等待的线程数
    int count;
    // 自己属于哪一个管程
    monitor_t * owner;
} condvar_t;

我们主要需要实现两个函数：wait函数，等待某一个条件；signal函数，提醒某一个条件已经达成。具体实现比较简单，可以参考代码如下：

// wait
cv.count++;
if(monitor.next_count > 0)
   sem_signal(monitor.next);
else
   sem_signal(monitor.mutex);
sem_wait(cv.sem);
cv.count -- ;

// signal
if( cv.count > 0) {
   monitor.next_count ++;
   sem_signal(cv.sem);
   sem_wait(monitor.next);
   monitor.next_count -- ;
}

管程的内部实现如下所示：

typedef struct monitor{
    // 保证管程互斥访问的信号量
    semaphore_t mutex;
    // 里面放着正在等待进入管程执行的进程
    semaphore_t next;
    // 正在等待进入管程的进程数
    int next_count;
    // 条件变量
    condvar_t *cv;
} monitor_t;

条件变量cv被设置时，会使得当前在管程内的进程等待条件变量而睡眠，其他进程进入管程执行。当cv被唤醒的时候，之前等待这个条件变量的进程也会被唤醒，进入管程执行。由于管程内部只能由一个条件变量，所以通过设置next来维护下一个要运行的进程是哪一个。

使用了管程，我们的哲学家就餐问题可以被实现为如下：

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_cv();
    }

    void putdown(int i) {
        state[i] = THINKING;
        test((i + 4) % 5);
        test((i + 1) % 5);
    }

    void test(int i) {
        if ((state[(i + 4) % 5] != EATING) &&
           (state[i] == HUNGRY) &&
           (state[(i + 1) % 5] != EATING)) {
              state[i] = EATING;
              self[i].signal_cv();
        }
    }

    initialization code() {
        for (int i = 0; i < 5; i++)
        state[i] = THINKING;
        }
}

具体的实现可以在sync/check_sync.c中找到。至此，我们实现并验证了ucore的同步互斥机制！