Tim*_*Tim 3 computer-science synchronization operating-system semaphore monitor
我从操作系统概念的信号量上难以理解监视器的实现
5.8.3使用信号量实现监视器
现在，我们考虑使用信号量的监视机制的可能实现。
为每个监视器提供了信号量互斥锁（初始化为1）。进程必须在进入监视器之前执行wait（mutex），并且在离开监视器之后必须执行signal（mutex）。
由于信令过程必须等待，直到恢复的过程离开或等待，所以
next引入了一个额外的信号量，初始化为0。信令过程可以next用来挂起自身。next_count还提供了一个整数变量来计算上挂起的进程数next。因此，每个外部功能F都被替换为Run Code Online (Sandbox Code Playgroud)wait(mutex); ... body of F ... if (next count > 0) signal(next); else signal(mutex);确保在监视器内相互排斥。
现在我们可以描述条件变量是如何实现的。对于每种条件
x，我们都引入一个信号量x_sem和一个整数变量x_count，它们都初始化为0。 现在可以将操作x.wait()实现为Run Code Online (Sandbox Code Playgroud)x_count++; if (next_count > 0) signal(next); else signal(mutex); wait(x sem); x_count--;该操作
x.signal()可以实现为Run Code Online (Sandbox Code Playgroud)if (x_count > 0) { next_count++; signal(x_sem); wait(next); next_count--; }
引入信号量的原因是什么？平均意味着暂停的进程next数是多少？next_countnext
为什么会这样x.wait()并按x.signal()原样实施？
谢谢。
- - - - 注意 - - - -
在下面的解释中，WAIT（）和SIGNAL（）表示对监视器方法
wait（）的调用，而signal（）表示对信号量方法的调用。
-------注释结尾-------
我认为如果您举一个具体的例子，会更容易。但是在此之前，让我们首先尝试了解什么是监视器。如书中所述，监视器是一种抽象数据类型，这意味着它不是可用于实例化变量的实类型。相反，它就像是带有一些规则和准则的规范，基于该准则，不同的语言可以为流程同步提供支持。
信号量被引入作为一种基于软件的解决方案，用于通过TestAndSet（）或Swap（）等基于硬件的方法实现同步。即使使用信号量，程序员也必须确保以正确的顺序正确地调用wait（）和signal（）方法。因此，引入了一个称为监视器的抽象规范，将与同步相关的所有这些事情封装为一个原语，因此，在监视器内部执行的任何进程都将确保相应地使用这些方法（信号等待和信号）调用。
使用监视器时，所有共享变量和功能（使用共享变量）都将放入监视器结构中，并且在调用这些功能中的任何一个时，监视器实现均应确保确保共享资源免受相互排斥和任何同步问题的影响。
现在，使用与信号量或其他同步技术不同的监视器，我们不仅要处理关键部分的一部分，而且要处理许多不同功能的部分。此外，我们还具有在这些函数中访问的共享变量。对于监视器中的每个不同功能，要确保仅执行其中一个功能，并且不对任何一个功能执行其他进程，我们可以使用称为互斥量的全局信号量。
考虑下面使用监视器解决餐饮哲学家问题的解决方案示例。
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 ）方法。为了确保相互排斥，我们必须确保在任何给定时间仅在监视器内部运行一个进程。因此，要处理这些情况，我们有一个全局信号量互斥量，它封装了所有可调用（拾取和放置）方法。因此，这两种方法将实现如下：
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（） （但尚未将筷子放下 tp ），然后进程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实现与信号量的实现不同，因为它必须提供更多的功能，例如允许其他进程通过释放互斥量全局信号量来调用监视器的功能（等待时）。因此，当P2从Pickup（）方法调用WAIT时，它将调用signal（mutex），允许其他进程调用监视方法，并在特定于条件的信号量上调用wait（x_sem）。现在，P2在这里被阻止。另外，变量x_count跟踪条件变量（self）上等待的进程数。
因此，当P1调用putdown（）时，这将通过test（）方法调用SIGNAL 。当P1在其持有的筷子上调用signal（x_sem）时，在SIGNAL内部，它必须做另外一件事。它必须确保监视器中仅运行一个进程。如果只调用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);
**************/
}
因此，现在，在任何进程退出监视器功能之前，它会检查是否有任何正在等待的进程，如果有，则释放它们，而不是释放互斥量全局信号灯。最后的此类等待进程将释放互斥信号量，以允许新进程进入监视功能。
我知道这很长，但是我花了一些时间来理解，并想将其写成文字。我很快会在博客上发布它。
如果有任何错误，请通知我。
最好，
沙比尔
我同意这令人困惑。
我们先来理解第一段代码：
// 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_count的原因是什么？
假设您有一个进程正在执行一些 I/O，并且需要阻止它直到它完成。所以你让其他在就绪队列中等待的进程获取监视器并调用函数F。
next_count仅用于跟踪队列中等待的进程。
在下一个信号量上挂起的进程是发出等待条件变量的进程，因此它将被挂起，直到其他进程（下一个进程）唤醒它并恢复工作。
为什么 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--;
}
如果您有任何疑问，请评论。