为什么监视器的实现要用这种方式来表示信号量？

Question

我在操作系统概念中遇到了一个问题，就是关于使用信号量实现监视器的实现方式我无法理解。

5.8.3 Implementing a Monitor Using Semaphores

We now consider a possible implementation of the monitor mechanism using semaphores.

For each monitor, a semaphore mutex (initialized to 1) is provided. A process must execute wait(mutex) before entering the monitor and must execute signal(mutex) after leaving the monitor.

Since a signaling process must wait until the resumed process either leaves or waits, an additional semaphore, next, is introduced, initialized to 0. The signaling processes can use next to suspend themselves. An integer variable next_count is also provided to count the number of processes suspended on next. Thus, each external function F is replaced by

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

Mutual exclusion within a monitor is ensured.

We can now describe how condition variables are implemented as well. For each condition x, we introduce a semaphore x_sem and an integer variable x_count, both initialized to 0. The operation x.wait() can now be implemented as

x_count++;
if (next_count > 0)
    signal(next);
else
    signal(mutex);
wait(x sem);
x_count--;

The operation x.signal() can be implemented as

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

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

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

谢谢。

- Tim

Answer 1

------- 注意 -------

WAIT() 和 SIGNAL() 表示调用监视器方法
wait() 和 signal() 表示调用信号量方法，在下面的解释中。

------- 注意结束 -------

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

信号量 被引入作为一种软件解决方案，用于实现基于硬件的方法，例如 TestAndSet() 或 Swap()。即使使用信号量，程序员也必须确保正确按照顺序调用 wait() 和 signal() 方法。因此，引入了一个名为 监视器 的抽象规范，将所有与同步相关的事物封装为一个原语，因此，在监视器内执行的任何进程都将确保相应地使用这些方法 (信号量等待和信号量)。

使用监视器，所有共享变量和函数（使用共享变量的函数）都被放置在监视器结构中，当调用其中任何一个函数时，监视器实现会负责确保共享资源受到互斥保护，并解决任何与 同步 相关的问题。

现在，与信号量或其他同步技术不同，我们不仅要处理关键部分的一部分，而是要处理多个关键部分，以及涉及这些函数的 共享变量。为了确保监视器中的每个不同函数只执行一个函数且没有其他进程在任何函数上执行，我们可以使用称为 mutex 的全局信号量。

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

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()方法内部正在执行一个进程时，另一个进程可能会尝试调用putdown()(甚至是pickup)方法。为了确保互斥性，在任何给定时间内只能有一个进程正在监视器内运行。因此，为了处理这些情况，我们有一个全局信号量mutex，该信号量封装了所有可调用的(pickup& putdown)方法。因此，这两种方法将被实现如下：

     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已执行pickup() （但尚未放下筷子），然后进程P2 （例如相邻的就餐者） 尝试执行pickup()：由于他/她的筷子 （共享资源） 正在使用中，因此必须等待它可用。 让我们看看监视器条件变量的WAIT和SIGNAL实现：

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 条件变量的实现与 Semaphore 不同，因为它必须提供更多功能，例如通过释放互斥全局信号量允许其他进程在等待期间调用监视器的函数。所以，当 P2 从 pickup() 方法中调用 WAIT 时，它将调用 signal(mutex) 允许其他进程调用监视器方法，并在特定于条件的信号量上调用 wait(x_sem)。现在，P2 在此被阻塞。此外，变量 x_count 跟踪等待条件变量（self）的进程数量。

因此，当 P1 调用 putdown() 时，这将通过 test() 方法调用 SIGNAL。在 SIGNAL 中，当 P1 在其持有的筷子上调用 signal(x_sem) 时，它必须执行一项额外操作。它必须确保只有一个进程在监视器内运行。如果它只调用 signal(x_sem)，那么从那时起，P1 和 P2 都会开始在监视器内执行操作。为了防止这种情况，P1 在释放其筷子后将自己阻塞，直到 P2 完成。为了阻塞自己，它使用信号量 next。为了通知 P2 或其他进程有人被阻塞，它使用计数器 next_count。

因此，现在 P2 将获取筷子，在退出 pickup() 方法之前，它必须释放正在等待 P2 完成的 P1。因此，现在我们必须将 pickup() 方法（以及监视器的所有函数）更改如下：

     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);
         **************/
     }

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

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

如果有任何错误，请告诉我。

最好的祝福， Shabir

- Shabirmean

Answer 2

我同意这很令人困惑。

首先让我们理解第一段代码：

// 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_count挂起进程数的原因是什么？

假设有一个正在进行一些I/O操作的进程，需要阻塞直到完成。因此，您让其他在就绪队列中等待的进程获取监视器，并调用函数F。

next_count仅为了跟踪等待队列中的进程而存在。

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

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--;
}

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

- yakout

---

我不明白为什么下一个信号量要这样使用。假设进程P首先调用x.wait()，运行到wait(x_sem)并在那里等待，然后Q调用x.signal()。Q肯定会让P完成，但由于P在if语句的false条件下没有调用signal(next)，所以Q本身将在wait(next)处等待。那么Q是否必须一直停留在监视器中，直到另一个进程调用x.wait()？ - GreenPenguin