餐饮哲学家饥饿的可能性 [英] possibility of starvation of Dining Philosophers

问题描述

如果需要保证满足以下所有条件，我需要检查我的解决用餐哲学家问题的算法：

I need to check my algorithm of solving the dining philosopher problem if it guarantees that all of the following are satisfied or not:

• 没有饥饿的可能性。

我正在使用信号量。

这是我的代码（算法）：

Here is my code (the algorithm):

while(true)
{
    // He is Hungry
    pickup_chopsticks(i);

    // He is Eating...
    drop_chopsticks(i);

    // He is thinking
}

// ...

void pickup_chopsticks(int i)
{
    if(i % 2 == 0) /* Even number: Left, then right */
    {
        semaphore_wait(chopstick[(i+1) % NUM_PHILOSOPHERS]);
        semaphore_wait(chopstick[i]);
    }
    else /* Odd number: Right, then left */
    {
        semaphore_wait(chopstick[i]);
        semaphore_wait(chopstick[(i+1) % NUM_PHILOSOPHERS]);
    }
}

void drop_chopsticks(int i)
{
    semaphore_signal(chopstick[i]);
    semaphore_signal(chopstick[(i+1) % NUM_PHILOSOPHERS]);
}

我确定这里没有死锁的可能性，但是有可能这里有饥饿问题？如果是，该如何解决？

I am sure there is no possibility of deadlock here, but is it possible to have a starvation problem here? If yes, how can I solve it?

推荐答案

定义。哲学家启用，前提是他不等待不可用的信号灯。 execution （执行）是使能的哲学家采取的一系列步骤。如果每个无限启用的哲学家经常采取无限多的步骤，那么执行是非常公平的。餐饮哲学家的解决方案是无饥饿，只要在每次公平公正的执行中，每个哲学家都会无限次用餐。

Definitions. A philosopher is enabled iff he is not waiting for an unavailable semaphore. An execution is an infinite sequence of steps taken by enabled philosophers. An execution is strongly fair iff every philosopher enabled infinitely often takes infinitely many steps. A dining philosophers solution is starvation-free iff, in every strongly fair execution, every philosopher dines infinitely often.

定理。每个非用餐哲学家都不持有信号量的无循环，无死锁的用餐哲学家解决方案都是无饥饿的。

Theorem. Every loop-free deadlock-free dining philosophers solution in which non-dining philosophers do not hold semaphores is starvation-free.

证明。

Proof. Assume for the sake of obtaining a contradiction that there exists a strongly fair execution in which some philosopher, call him Phil, dines only finitely often. We show that this execution is in fact deadlocked.

由于 pickup_chopsticks 和 drop_chopsticks code>没有循环，Phil仅采取有限的多个步骤。最后一步是 semaphore_wait ，在筷子i上说。因为执行是非常公平的，所以从某个有限的时间开始，筷子i就一直连续不可用。让昆汀成为筷子i的最后持有人。如果Quentin采取了无限多的步骤，那么他将 semaphore_signal 用作筷子i，因此Quentin也采取了有限的步骤。昆汀反过来正在等待筷子j，根据相同的论点，筷子j直到时间结束一直不可用，由罗伯特（Robert）持有。通过跟踪有限的许多哲学家中的 semaphore_wait s链，我们必然到达一个循环，这是一个僵局。

Since pickup_chopsticks and drop_chopsticks have no loops, Phil takes only finitely many steps. The last step is a semaphore_wait, say on chopstick i. Because the execution is strongly fair, chopstick i is necessarily continuously unavailable from some finite time onward. Let Quentin be the last holder of chopstick i. If Quentin took infinitely many steps, then he would semaphore_signal chopstick i, so Quentin takes finitely many steps as well. Quentin, in turn, is waiting on a chopstick j, which, by the same argument, is continuously unavailable until the end of time and held by (say) Robert. By following the chain of semaphore_waits among finitely many philosophers, we necessarily arrive at a cycle, which is a deadlock.

QED

这篇关于餐饮哲学家饥饿的可能性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！