野蛮人进餐问题——信号量和互斥量

Question

我遇到过野蛮人进食的问题和解决方案，但我似乎不明白该解决方案如何处理当野蛮人试图在锅还是空的时候从锅里吃东西的情况。来自信号量小书的问题及解决方案：

A tribe of savages eats communal dinners from a large pot that can hold M servings of stewed missionary. When a savage wants to eat, he helps himself from the pot, unless it is empty. If the pot is empty, the savage wakes up the cook and then waits until the cook has refilled the pot. Any number of savage threads run the following Unsynchronized savage code:

while True :
    getServingFromPot()
    eat()

And one cook thread runs this Unsynchronized cook code:

while True:
    putServingsInPot(M)

同步约束为：

Savages cannot invoke getServingFromPot if the pot is empty.

The cook can invoke putServingsInPot only if the pot is empty.

Puzzle: Add code for the savages and the cook that satisfies the synchronization

解决方案（烹饪）：

while True:
    emptyPot.wait()
    putServingsInPot(M)
    fullPot.signal()

解决方案（野蛮人）：

while True:
    mutex.wait()
    if servings == 0:
        emptyPot.signal ()
        fullPot.wait ()
        servings = M
    servings -= 1
    getServingFromPot ()
    mutex.signal()

    eat()

我的问题 - 当我们第一次到达 servings = 0 时，在 M 个野蛮人吃完锅后，我们到达 emptyPot.signal() 然后 fullPot.wait() - 两个信号量；然后，从我的角度来看，可能存在一个极端情况，我们可能会在厨师有机会获得上下文并填满锅之前到达 getServingsFromPot。我错过了什么吗？

Answer 1

我假设 signal 和 wait 是通常的 V 和 P 信号量操作。

我想你可能漏掉了每个信号量的要点。

emptyPot: 厨师不会装满锅，除非野人发出信号，锅已经空了；
fullPot: 除非厨师发出锅已满的信号，否则发出锅空信号的野人将得不到一份服务；
mutex: 一个想吃东西的野人不会继续，除非另一个野人发出他们已经吃完自己的信号。

因此：

多个野人可以同时进食；
没有两个野蛮人会同时为自己服务；
如果锅是空的，野人不会尝试为自己服务；
野人叫醒厨师后，如果锅没有满，野人是不会自己上菜的.

因此，不可能存在竞争条件。由于呼叫 fullPot.wait()，野蛮人无法到达 getServingsFromPot，直到厨师醒来，装满锅并呼叫 fullPot.signal()。

野蛮人进餐问题——信号量和互斥量

Dining savages problem - Semaphores and Mutexes

operating-system

synchronization

semaphore