使用信号量实现 Hoare 监视器？

Question

使用信号量实现 Hoare 监视器？

concurrencyoperating-systemsemaphoreconcurrent-programmingbinary-semaphore

4

在4天内我有一场考试，我刚刚和我的讲师交谈，他对课程的这一部分非常不清楚，我和许多学生一样很难理解这个问题。

基本上，如果你想使用信号量实现Hoare监视器，涉及哪些步骤？

以下是伪代码

]3 更新：

我开始明白了

所以第一张幻灯片是用于访问监视器的进程

如果你是唯一的一个人，那么你就调用 wait(mutex)

进入监视器并完成你的工作再离开

如果有人在等待进入监视器，那么你就会唤醒下一个信号量，即等待进程的队列。否则，如果你是唯一的一个在监视器中的人，则退出并唤醒mutex，以便其他人可以进入mutex。

对于带有wait(condition)和signal(condition)的第二张幻灯片：

当你wait(c)时: c_count++ //等待此条件的进程数，增加1 if(next_count>0) up(next) //如果想要进入监视器的等待进程数量大于零，则up(next)，解除一个等待进程的阻塞

否则up(mutex) //如果你是唯一的一个人，则up mutex以便其他人进入 down(c_sem) //阻止自己入睡 c_count-- //您醒来后，等待此条件的进程数减少

对于signal(c)部分：

如果(c_count>0) //如果等待此条件的进程数大于0

next_counter++ //想要进入监视器的进程数增加1 up(c_sem); //解除一个等待此条件的进程的阻塞 down(next) //如果有空位，则down此处，否则被阻塞并加入等待进程列表 next_count--; //您醒来并尝试进入监视器

- Tom chan

我们不知道的一件事是，你的信号量定义了什么操作？如果未被获取，则你的信号量需要将进程放在等待状态（显然不是你的示例），或者你需要知道信号量的值（在你的示例中从未执行）。 next_count 和 c_count 变量是多余的。在多线程环境中，不应该以非原子方式（即使用 ++）增加变量。 - user3344003

信号量的基本原理是，如果它为零并且已经被占用，则将进程放入等待进程列表（阻塞），否则减少资源。对于“up”操作，如果有等待的进程，则将其取出并开始运行，否则增加资源。 - Tom chan

一个信号量是访问监视器的任务数量（1或0）。另一个信号量是等待获取监视器访问权的任务数量（0 … n）。 - user3344003

你说的锁是用哪种信号量实现的？它是不是只是一个二进制信号量，用于表示能够访问监视器的任务数量（1或0）？ - Tom chan

如果您要使用基本的信号量实现锁，则需要两个信号量，就像在带有错误的示例中所示。 - user3344003

我最困惑的是，每个进程都会进入并锁定互斥量，如果只有一个进程尝试访问监视器而没有其他进程尝试，则它会解锁互斥量，否则它会解锁下一个。那么如果互斥量从未被解锁，其他进程如何进入呢？ - Tom chan

2个回答

0

首先，两个小时并不是让你冷静下来的时间很长，我猜想 - 所以我甚至不会尝试。

另一方面：这是一场考试，而不是黑客马拉松。话虽如此，...为什么不坚持你教授幻灯片的学术水平呢。

如果你想要一个不同版本的解释天才C.A.R. Hoare的基本工作，请看看这个PowerPoint - 你可以阅读所有内容，但对你最重要的页面应该是第15页：MonitorPPT

还有：如果你想在考试后阅读原始论文 - 为了争取你没有得到的分数或者只是为了好玩 - 这里是链接：C.A.R. Hoare - Monitors: An Operating System Structuring Concept

祝你考试顺利，汤姆！

- dr. rAI

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user3344003 · Accepted Answer

哎呀，我能理解你为什么感到困惑。这个例子合并了两个概念。

信号量是互斥锁的一种形式。在抽象层面上，互斥锁只是一个可以原子性地增加或减少的变量。up函数会进行增加操作，down函数会进行减少操作，即使有多个进程同时进行up或down操作。如果你只是让up等同于count = count + 1，那么当多个进程同时尝试增加时，你会得到随机结果。

在现实世界（学术界以外），信号量除了增加操作外还可以进行等待操作。

因此，如果我执行以下操作：

 real_world_down (semaphore)

我的过程会减少信号量。如果没有进程(或线程)锁定信号量(通常=0，1为起点)，我的过程会继续执行。如果另一个进程已经锁定了信号量(down后的值<0)，我的过程就会等待。

当锁定信号量的进程完成并且...

 real_world_up (semaphore)

操作系统会自动选择一个等待的进程来运行。

因此，你的Hoare监视器应该如下所示：

  var 
     semaphore ; 
  Procedure Monitor

       real_world_down (semaphore) ;

       /* do whatever you want */

       real_world_up (semaphore) ;

 End ;

或者我们可以这样写：

或者我们可以将其写成：

  var 
     semaphore ; 
  Procedure Monitor

       lock (semaphore) ;

       /* do whatever you want */

       unlock (semaphore) ;

 End ;

这是关于监视器部分的内容。你例子中令人困惑的部分是，它是一个使用学术信号量编写的锁/解锁方式，只是原子地增加和减少，并且不知道谁在等待它们。

它的wait相当于我的lock。它相当于我的unlock完全失败了。

现在，我留给你的练习是创建一个锁函数，该函数将使用一对信号量允许一个进程/线程获取锁定，但允许多个进程等待，并在解锁时允许一个等待的进程/线程继续执行。

它需要一个解锁函数，该函数将解锁互斥对以允许一个进程/线程继续执行。