使用二进制信号量用餐哲学家

Question

此伪代码能否以最大并行度解决哲学家就餐问题？这里 mutex 是一个初始化为 1 的二进制信号量。假定叉子编号从 0 到 (N-1)。共有 N 位哲学家，编号从 0 到 (N-1)。

void philosopher(int i)    // ith philosopher
{   
   while (true)
   {
        think();
        down(&mutex);          // acquire lock
        take_fork(i);            // take left fork
        take_fork((i+1)%N);        // take right fork
        up(&mutex);          // release the lock
        eat();
        down(&mutex);       // acquire lock
        put_fork(i);
        put_fork((i+1)%N);
        up(&mutex);        // release the lock
   }    
}

这应该以最大并行度解决哲学家用餐问题，因为在一个哲学家获得两个叉子后锁被释放。但是会吗？会不会有活泼的问题？我很困惑。

Answer 1

为了回答您的问题，我想提供一些事件的痕迹，这些事件似乎将您的哲学家带入了一种不受欢迎的状态。

考虑一个具有 N>2 个哲学家 Ph(0),...,Ph(N-1) 和以下操作序列的系统：

Ph(1).think();
Ph(0).think();
Ph(1).down(&mutex);
Ph(1).take_fork(1);
Ph(1).take_fork(2);
Ph(1).up(&mutex);
Ph(0).down(&mutex);
Ph(0).take_fork(0);
Ph(0).take_fork(1);

回想一下 fork(1) 已经被 Ph(1) 收购了。现在，根据 take_fork() 的语义，可能会出现不同的行为。

如果take_fork()在无法获得分叉的情况下立即失败，那么fork(0)将永远不会被释放。

如果 take_fork() 挂起直到资源被释放，那么互斥量将永远不会被释放，并且 none 的其他哲学家将能够取得进展，因此只有一个哲学家会在同一时间进食时间。

使用二进制信号量用餐哲学家

Dining philosophers using binary semaphores

concurrency

semaphore

dining-philosopher

binary-semaphore