管程

2017/12/04 操作系统

Hoare管程

  • 一次只有一个进程可以进入管程;
  • cwait(x)的进程在管程等待区域阻塞;
  • 执行csignal的进程必须立即退出管程(没有进程等待条件x例外),或者阻塞在管程上(紧急队列,优先级较新进进程高);
  • 两个缺点:
    • 如果产生csignal的进程在管程内还没有结束,则需要两个额外的进程切换,阻塞这个进程需要一次切换,当管程可用是恢复这个进程又需要一次切换;
    • 与信号相关的进程调度必须非常可靠,当产生一个csignal时,来自相应条件队列中的一个进程必须立即被激活,调度程序必须确保在激活前没有其他进程进入管程,否则,进程被激活的条件又会改变。

Lampson/Redell管程

  • 解释:

    当一个正在管程中的进程执行cnotify(x)时,它使得x条件队列得到通知,但发信号的进程继续执行。通知的结果是使得位于条件队列头的进程在将来合适的时候且当处理器可用时被恢复执行。但是,由于不能保证在它之前没有其他进程进入管程,因而这个等待进程必须重新检查条件。

  • if语句被while循环取代,因此,这个方案导致对条件变量至少多一次额外的监测额。作为回报,它不再有额外的进程切换,并且对等待进程在cnotify之后什么时候运行没有任何限制。
    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(notfull);    //缓冲区空,防止下溢
      x = buffer[nextout];
      nextout = (nextout + 1) % N;
      count--;                              //缓冲区中数据项个数减
      cnotify(notfull);                     //通知正在等待的进程
    }
    
  • 相比于前者的优点:
    • 通过cbroadcast原语,广播可以使所有在该条件上等待的进程都被设置为就绪状态,当一个进程不知道有多少进程将被激活时,这种方式是非常方便的。例如,生产者产生一个cbroadcast信号,所有正在等待notempty的进程都得到通知并再次运行;
    • 在Lampson/Redell方法中,由于每个过程在收到信号后都检查管程变量,并且由于使用看while结构,一个进程不正确地发送广播或发信号,不会导致收到信号的程序出错;
    • 有助于在程序结构中采用更模块化的方法。例如,二级条件会随着程序的改变而不同,但是后者由于每个过程都会检查自己的二级条件,故不会产生错误的唤醒。而Hoare管程2级条件必须由等待者带到每个发信号的进程的代码中,违反了数据抽象和进程间的模块化原理。

Search

    Table of Contents