为什么以这种方式在信号量方面实现监视器? [英] Why is a monitor implemented in terms of semaphores this way?
问题描述
我很难根据操作系统概念的信号量来了解监视器的实现
I have trouble understanding the implementation of a monitor in terms of semaphores from Operating System Concepts
5.8.3使用信号量实现监视器
我们现在考虑监视机制的可能实现 使用信号量.
We now consider a possible implementation of the monitor mechanism using semaphores.
为每个监视器提供信号量互斥锁(初始化为1).一种 进程必须在进入监视器之前执行wait(mutex)，并且必须 离开显示器后执行signal(mutex).
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.
由于信令过程必须等待，直到恢复的过程离开或等待，因此引入了另外的信号量next，
初始化为0.信令进程可以使用next挂起
他们自己.还提供了整数变量next_count进行计数
next上挂起的进程数.因此，每个外部
函数F被替换为
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.
我们现在还可以描述条件变量的实现方式.
对于每个条件x，我们引入一个信号量x_sem和一个
整数变量x_count，都初始化为0.操作x.wait()现在可以实现为
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--;
操作x.signal()可以实现为
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的原因是什么?
What does the reason for introducing semaphore next and the count next_count of processes suspended on next mean?
为什么x.wait()和x.signal()是以其原样实现的?
Why are x.wait() and x.signal() implemented the way they are?
谢谢.
推荐答案
-------注意-------
WAIT()和 SIGNAL()表示对监视器方法的调用
在以下说明中， wait()和 signal()表示对信号量方法的调用.
WAIT() and SIGNAL() denote calls on monitor methods
wait() and signal() denote calls to semaphore methods, in the explanation that follows.
-------注释结尾-------
如果您以具体示例的方式考虑，我认为这会更容易.但是在此之前，让我们先尝试了解什么是监视器.正如本书中所解释的，监视器是抽象数据类型，这意味着它不是可用于实例化变量的实类型.相反，它就像是带有一些规则和准则的规范，基于该准则，不同的语言可以为流程同步提供支持.
I think it is easier if you think in terms of a concrete example. But before that let's first try to understand what a monitor is. As explained in the book a monitor is a Abstract Data Type meaning that it is not a real type which can be used to instantiate a variable. Rather it is like a specification with some rules and guidelines based on which different languages could provide support for process synchronization.
信号量作为基于软件的解决方案，用于通过 TestAndSet()或Swap()等基于硬件的方法实现同步.即使有信号灯，程序员也必须确保他们调用 wait()&以正确的顺序正确正确地使用signal()方法.因此，引入了一个称为 monitors 的抽象规范，将与同步相关的所有这些事情封装为一个原语，因此，在监视器内部执行的任何进程只需确保这些方法(信号灯等待和信号)调用相应地使用.
Semaphors were introduced as a software-based solution for achieving synchronization over hardware-based approaches like TestAndSet() or Swap(). Even with semaphores, the programmers had to ensure that they invoke the wait() & signal() methods in the right order and correctly. So, an abstract specification called monitors were introduced to encapsulate all these things related to synchronization as one primitive so simply any process executing inside the monitor will ensure that these methods (semaphore wait and signal) invocations are used accordingly.
对于监视器，所有共享变量和功能(使用共享变量)都放入监视器结构中，并且当调用这些功能中的任何一个时，监视器实现会确保确保共享资源免受相互排斥和任何问题的影响同步.
With monitors all shared variables and functions (that use the shared variables) are put into the monitor structure and when any of these functions are invoked the monitor implementation takes care of ensuring that the shared resources are protected over mutual exclusion and any issues of synchronization.
现在有了监控器，与信号灯或其他同步技术不同，我们不仅仅处理关键部分的一部分，而是根据不同功能来处理其中的许多部分.此外，我们还具有在这些函数中访问的共享变量.对于监视器中的每个不同功能，要确保仅执行其中一个功能，并且不对任何一个功能执行其他进程，可以使用名为 mutex 的全局信号量.
Now with monitors unlike semaphores or other synchronization techniques we are not dealing with just one portion of the critical section but many of them in terms of different functions. In addition, we do also have shared variables that are accessed within these functions. For each of the different functions in a monitor to ensure only one of them is executed and no other process is executing on any of the functions, we can use a global semaphore called mutex.
使用下面的监视器来考虑解决哲学家问题的示例.
Consider the example of the solution for the dining philosophers problem using monitors below.
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;
}
}
}
理想情况下，进程如何调用这些功能的顺序如下:
Ideally, how a process might invoke these functions would be in the following sequence:
DiningPhilosophers.pickup(i);
...
// do somework
...
DiningPhilosophers.putdown(i);
现在，当一个进程在 pickup()方法内部执行时，另一个进程可能会尝试调用 putdown() (甚至是拾取)方法.为了确保互斥，我们必须确保在任何给定时间，监视器中都只运行一个进程.因此，为了处理这些情况，我们有一个全局信号量 mutex ，该信号量封装了所有可调用的(pickup& putdown)方法.因此，这两种方法将实现如下:
Now, whilst one process is executing inside the pickup() method another might try to invoke putdown() (or even the pickup) method. In order to ensure mutual exclusion we must ensure only one process is running inside the monitor at any given time. So, to handle these cases we have a global semaphore mutex that encapsulates all the invokable (pickup & putdown) methods. So these two methods will be implemented as follows:
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() (但还没有筷子 putdown )然后处理 P2 (例如相邻的小餐馆)尝试进行 pickup():因为他/她的筷子(共享资源) 正在使用中，它必须 wait()才能使用.让我们看看监视器的条件变量的 WAIT 和 SIGNAL 实现:
Now only one process will be able to execute inside the monitor in any of its methods. Now, with this setup, if Process P1 has executed pickup() (but is yet tp putdown the chopsticks) and then Process P2 (say an adjacent diner) tries to pickup(): since his/her chopsticks (shared resource) is in use, it has to wait() for it to be available. Let's look at the WAIT and SIGNAL implementation of the monitor's conditional variables:
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实现与信号量的实现不同，因为它必须提供更多的功能，例如允许其他进程通过释放 mutex来调用监视器的功能(等待). 全局信号量.因此，当 P2 从 pickup()方法调用WAIT时，它将调用 signal(mutex)，允许其他进程调用监视器方法，并在特定于条件的信号量上调用 wait(x_sem).现在， P2 在此处被阻止.此外，变量 x_count 跟踪条件变量(self)上等待的进程数.
The WAIT implementation of the conditional variables is different from that of the Semaphore's because it has to provide more functionality, like allowing other processes to invoke functions of the monitor (whilst it waits) by releasing the mutex global semaphore. So, when WAIT is invoked by P2 from the pickup() method, it will call signal(mutex) allowing other processes to invoke the monitor methods and call wait(x_sem) on the semaphore specific to the conditional. Now, P2 is blocked here. In addition, the variable x_count keeps track of the number of Processes waiting on the conditional variable (self).
因此，当 P1 调用 putdown()时，这将通过 test()方法调用SIGNAL.当 P1 在其持有的筷子上调用 signal(x_sem)时，在SIGNAL内部，它必须做另外一件事.它必须确保监视器中仅运行一个进程.如果只调用 signal(x_sem)，则从那时起 P1 和 P2 都将在显示器内部开始工作.为防止此 P1 ，松开其筷子后，它会自行阻塞，直到 P2 完成.为了阻止自身，它使用信号灯 next .并使用 next_count 计数器通知 P2 或其他进程有人被阻止.
So when P1 invokes putdown(), this will invoke SIGNAL via the test() method. Inside SIGNAL when P1 invokes signal(x_sem) on the chopstick it holds, it must do one additional thing. It must ensure that only one process is running inside the monitor. If it would only call signal(x_sem) then from that point onwards P1 and P2 both would start doing things inside the monitor. To prevent this P1, after releasing its chopstick it will block itself until P2 finishes. To block itself, it uses the semaphore next. And to notify P2 or some other process that there is someone blocked it uses a counter next_count.
因此，现在 P2 将得到筷子，并且在退出 pickup()方法之前，它必须释放正在等待 P2 完成.因此，现在，我们必须更改 pickup()方法(以及监视器的所有功能)，如下所示:
So, now P2 would get the chopsticks and before it exits the pickup() method it must release P1 who is waiting on P2 to finish. So now, we must change the pickup() method (and all functions of the monitor) as follows:
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 信号量，允许新过程进入监视功能.
So now, before any process exits a function of the monitor, it checks if there are any waiting processes and if so releases them and not the mutex global semaphore. And the last of such waiting processes will release the mutex semaphore allowing new processes to enter into the monitor functions.
我知道这很长，但是我花了一些时间来理解并希望将其写成文字.我会尽快将其发布在博客上.
I know it's pretty long, but it took some time for me to understand and wanted to put it in writing. I will post it on a blog soon.
如果有任何错误，请告诉我.
If there are any mistakes please let me know.
最佳，
沙比尔
Best,
Shabir
这篇关于为什么以这种方式在信号量方面实现监视器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
