操作系统概念学习笔记 12

进程同步（二）

管程

基本的、高级的同步构造，即管程（monitor）类型。

使用：

管程类型提供了一组由程序员定义的、在管程内互斥的操作。管程类型的表示包括一组变量的声明（这些变量的值定义了一个类型实例的状态）和对这些变量操作的子程序和函数的实现。管程的类型表示不能直接为各个进程所使用。因此，在管程内定义的子程序只能访问位于管程内那些局部声明的变量和形式参数。类似的，管程的局部变量能被局部子程序访问。

管程结构确保一次只有一个进程能在管程内活动。不需要显示的编写同步代码。而对于特定同步方案，需要额外的同步机制，这些由条件（condition）结构来提供。

condition x,y;
x.wait();
x.signal();

管程的语法：

monitor monitor name{

  //shared variable declarations

  procedure P1(…){

…

}

procedure P2(…){

…

}

…

procedure Pn(…){

…

}

initialization code(…){

…

}

}

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

这个解决方案要求哲学家在两只筷子都可以使用时才会拿起筷子。

为此，引入如下数据结构：

enum {THINKING, HUNGRY, EATTING} state[5];

加入条件，哲学家i只有在其两个邻居不再进餐时才能将变量state[i]设置为eating：

（state[(i+4)%5]!=eating）和（state[i+1]%5!=eating）

哲学家i必须按以下顺序来调用操作

dp.pickup(i)

...

eat

...

dp.putdown(i)

基于信号量的管程实现

基于信号量的哲学家进餐问题的管程解法：每个管程都有一个信号量mutex（初始化为1），进程在进入管程之前，必须执行wait(mutex)，在离开管程后必须执行signal(mutex)。

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+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();

}

}

initialization_code(){

  for(int i=0;i<5;i++)

    state[i]=THINKING;

}

}

条件变量的实现：对于每个条件变量x，引入信号量x_sem和整数变量x_count，两者均初始化为0。由于信号进程必须等待，引入另一个信号量next以供信号进程挂起自己，next_count以对挂起在next上的进程进行计数。

x.wait()的实现：

x_count++;

if(next_count > 0)

  signal(next);

else

  signal(mutex);

wait(x_sem);

x_count--;

x.signal()的实现：

if(x_count>0){

  next_count++;

  signal(x_sem);

  wait(next);

  next_count--;

}

管程内的进程重启

等待最长的进程先重新运行。也可以使用条件等待构造。

x.wait(c);其中c表示优先值（priority number），会与悬挂进程的名称一起存储。

使用管程来管理资源时，为确保系统的正确，有两个条件是必须检查的：

第一，用户进程必须总是按正确顺序来对管程进行调用；

第二，必须确保一个不合作的进程不能简单地忽略由管程所提供的互斥关口，以及在不遵守协议的情况下直接访问共享资源。