algorithm - 如何通过消息传递模拟信号量...？

Question

我想模拟信号量(等待和信号过程)，消息仅以算法(而不是代码)的形式传递。

谁能帮我...？

Answer 1

您是否需要了解实现临界区和信号量原语的算法？参见 Process Synchronization (PDF)。请注意，有时您可能会看到使用临界区实现的信号量以确保测试修改操作的原子性。

消息队列建立在同步原语之上。你找的消息队列在优秀的第4章Little Book of Semaphores (pdf)。

编辑添加:

我必须猜测您所说的“邮箱”是什么意思，所以如果这个答案不好，那么定义邮箱是什么会对您有所帮助。我是否理解为练习是通过使用消息队列等高级同步机制来实现P和V？由于消息队列必须针对并发问题进行保护，因此这是一个简单的练习。

给定一个保证线程安全且具有以下方法的 Mailbox 类:

• enqueue(message) - 添加一条消息到邮箱。如果有任何线程在出队时被阻塞，则唤醒一个。
• dequeue - 从邮箱中删除一条消息，如果邮箱为空则阻塞。

然后信号量类将具有这些方法:

initialize(count):
  mailbox = Mailbox.new
  count.times do
    v

v:
  mailbox.enqueue(any_message)

p:
  mailbox.dequeue

any_message 是任何消息。它是什么并不重要，因为我们只是使用消息队列来唤醒阻塞的线程。

该算法模拟一个不能有负值的信号量。可以用负值创建的信号量将需要做更多的工作。你需要哪个？