-1

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

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
   }    
}

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

4

1 回答 1

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()挂起直到资源被释放，那么互斥锁将永远不会被释放，并且其他哲学家都无法取得进展，因此一次只有一个哲学家会吃东西。

于 2017-08-13T04:31:56.650 回答