为什么监视器以信号量的方式实现？

Question

我很难从操作系统概念的信号量方面理解监视器的实现

5.8.3使用信号量实现监视器

我们现在考虑使用信号量的监视器机制的可能实现。

对于每个监视器，都提供一个信号量互斥（初始化为1）。进程在进入监视器之前必须执行等待（互斥），在离开监视器之后必须执行信号（互斥）。

由于信令进程必须等待，直到恢复的进程离开或等待，因此引入了一个额外的信号量，Next，初始化为0。信令进程可以使用Next来挂起自己。还提供了一个整数变量next_count来计算在Next上挂起的进程数。因此，每个外部函数F被替换为

wait(mutex);
...
body of F
...
if (next count > 0)
    signal(next);
else
    signal(mutex);

确保监视器内的互斥。

我们现在可以描述条件变量是如何实现的。对于每个条件x，我们引入一个信号量x_sem和一个整数变量x_count，两者都初始化为0。操作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--;
}

引入信号量next和在next上挂起的进程的计数next\u count的原因是什么？

为什么x.wait（）和x.signal（）的实现方式是这样的？

谢谢

Answer 1

我同意这令人困惑。

让我们先了解第一段代码：

// if you are the only process on the queue just take the monitor and invoke the function F.
wait(mutex);
...
body of F
...
if (next_count > 0)
    // if some process already waiting to take the monitor you signal the "next" semaphore and let it take the monitor.
    signal(next);
else
    // otherwise you signal the "mutex" semaphore so if some process requested the monitor later.
    signal(mutex);

回到你的问题：

引入信号量next和next上挂起的进程计数next的原因是什么？

假设您有一个正在执行某些I/O的进程，它需要被阻止，直到完成为止。因此，您可以让等待在就绪队列中的其他进程使用监视器并调用函数F。

下一个计数仅用于跟踪队列中等待的进程。

在下一个信号量上挂起的进程是发出等待条件变量的进程，因此它将被挂起，直到其他进程（下一个进程）唤醒它并恢复工作。

为什么x.wait（）和x.signal（）是这样实现的？

让我们x.wait（）：

semaphore x_sem; // (initially = 0)
int x_count = 0; // number of process waiting on condition (x)


/*
 * This is used to indicate that some process is issuing a wait on the 
 * condition x, so in case some process has sent a signal x.signal()
 * without no process is waiting on condition x the signal will be lost signal (has no effect).
*/
x_count++;

/*
 *  if there is some process waiting on the ready queue,
 *  signal(next) will increase the semaphore internal counter so other processes can take the monitor.
 */
if (next_count > 0)
    signal(next);
/*
 *  Otherwise, no process is waiting.
 *  signal(mutex) will release the mutex.
 */
else
    signal(mutex);
/*
 * now the process that called x.wait() will be blocked until other process will release (signal) the
 * x_sem semaphore: signal(x_sem)
 */
wait(x_sem);
// process is back from blocking.
// we are done, decrease x_count.
x_count--;

现在让我们看x.signal（）

// if there are processes waiting on condition x.
if (x_count > 0) {
    // increase the next count as new blocked process has entered the queue (the one who called x.wait()). remember (wait(x_sem))
    next_count++;
    // release x_sem so the process waiting on x condition resume.
    signal(x_sem);
    // wait until next process is done.
    wait(next);
    // we are done.
    next_count--;
}

如果您有任何问题，请发表评论。

Answer 2

-------注-------

WAIT（）和SIGNAL（）表示对监视器方法的调用
WAIT（）和SIGNAL（）表示对信号量方法的调用，如下所示。

-------尾声-------

我认为如果你用一个具体的例子来思考，会更容易。但在此之前，让我们先尝试了解监视器是什么。正如书中所解释的，监视器是一种抽象数据类型，这意味着它不是一种可用于实例化变量的实类型。相反，它就像一个规范，其中包含一些规则和指导原则，不同的语言可以基于这些规则和指导原则为进程同步提供支持。

信号量是作为基于软件的解决方案引入的，用于通过基于硬件的方法（如TestAndSet（）或Swap（））实现同步。即使使用信号量，程序员也必须确保调用wait（）

使用监控器时，所有共享变量和函数（使用共享变量）都被放入监控器结构中，当调用这些函数时，监控器实现负责确保共享资源受到互斥和任何同步问题的保护。

现在，与信号量或其他同步技术不同，监视器不仅仅是处理关键部分的一部分，而是根据不同的功能处理其中的许多部分。此外，我们也有在这些函数中访问的共享变量。对于监视器中的每个不同函数，为了确保只执行其中一个函数，并且没有其他进程在任何函数上执行，我们可以使用称为互斥锁的全局信号量。

考虑下面使用监视器解决哲学家进餐问题的例子。

monitor dining_philopher
{
     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;
          }
     }
}

理想情况下，进程如何调用这些函数将按以下顺序进行：

DiningPhilosophers.pickup(i);
...
  // do somework
...
DiningPhilosophers.putdown(i);

现在，当一个进程在pickup（）方法内执行时，另一个进程可能会尝试调用putton（）方法（甚至是pickup）方法。为了确保互斥，我们必须确保在任何给定时间监视器内只运行一个进程。因此，为了处理这些情况，我们有一个全局信号量互斥体，它封装了所有可调用的（拾取）信号

     void pickup(int i) {
         // wait(mutex);

         state[i] = HUNGRY;
         test(i);

         if (state[i] != EATING)
             self[i].WAIT();

         // signal(mutex);
     }

     void putdown(int i) {
         // wait(mutex);

         state[i] = THINKING;
         test((i + 4) % 5);
         test((i + 1) % 5);

         // signal(mutex);
     }

现在，只有一个进程可以在监视器中的任何方法中执行。现在，在这个设置中，如果进程P1已经执行了pick（）（但还没有放下筷子），然后进程P2（比如说相邻的用餐者）尝试拾取（）：因为他/她的筷子（共享资源）正在使用中，它必须等待（）它才可用。让我们看看监视器条件变量的等待和信号实现：

WAIT(){
    x_count++;

    if (next_count > 0)
        signal(next);
    else
        signal(mutex);

    wait(x_sem);
    x_count--;
}

SIGNAL() {
    if (x_count > 0) {
        next_count++;
        signal(x_sem);
        wait(next);
        next_count--;
    }
}

条件变量的WAIT实现不同于信号量的WAIT实现，因为它必须提供更多的功能，比如允许其他进程通过释放互斥全局信号量来调用监视器的函数（在等待时）。因此，当P2从pick（）方法调用WAIT时，它将调用signal（mutex），允许其他进程调用monitor方法，并对特定于条件的信号量调用WAIT（x_sem）。现在，P2在这里被阻塞。此外，变量x_count跟踪等待条件变量（self）的进程数。

因此，当P1调用putdown（）时，它将通过test（）方法调用SIGNAL。在SIGNAL内部，当P1调用它所持筷子上的信号（x_sem）时，它必须做一件额外的事情。它必须确保只有一个进程在监视器内运行。如果它只呼叫信号（x_sem），那么从那时起，P1和P2都将开始在监视器内做事情。为了防止这种P1，在松开筷子后，它会阻塞自己，直到P2完成。为了阻止自己，它接下来使用信号量。为了通知P2或其他进程有人阻止，它使用计数器next_count。

所以，现在P2会得到筷子，并且在它退出皮卡（）方法之前，它必须释放等待P2完成的P1。因此，现在，我们必须更改picup（）方法（以及监视器的所有功能）如下：

     void pickup(int i) {
         // wait(mutex);

         state[i] = HUNGRY;
         test(i);

         if (state[i] != EATING)
             self[i].WAIT();

         /**************
         if (next_count > 0)
             signal(next);
         else
             signal(mutex);
         **************/
     }

     void putdown(int i) {
         // wait(mutex);

         state[i] = THINKING;
         test((i + 4) % 5);
         test((i + 1) % 5);

         /**************
         if (next_count > 0)
             signal(next);
         else
             signal(mutex);
         **************/
     }

所以现在，在任何进程退出监视器的函数之前，它会检查是否有任何正在等待的进程，如果有，就会释放它们，而不是互斥全局信号量。最后一个等待进程将释放互斥信号量，允许新进程进入监控函数。

我知道它很长，但我花了一些时间去理解，并想把它写下来。我很快会在博客上发布。

如果有任何错误，请让我知道。

最佳，
沙比尔