哲学家就餐问题什么情况下会触发饥饿死锁海量资源.pdfVIP

本文由简悦SimpRead转码，原文地址

这一讲给你带来的面试题目是：什么情况下会触发饥饿和死锁？

读题可知，这道题目在提问“场景”，从表面来看，解题思路是列举几个例子。但是在回答这类面试题前

你一定要想面试官在什么，往往在题目中看到“什么情况下”时，其实的是你总结和概括信

息的能力。

关于上面这道题目，如果你只回答一个场景，而没有输出概括性的总结内容，就很容易被面试官认为对

知识理解，因而挂掉面试。另外，提问死锁和饥饿还有一个更的意思，就是你在实战中

对并发控制算法的理解，是否具备设计并发算法来解决死锁问题并且兼顾性能（并发量）的思维和能

力。

要学习这部分知识有一个非常不错的模型，就是哲学家就餐问题。1965年，计算机科学家Dijkstra为

了帮助学生更好地学习并发编程设计的一道练习题，后来逐渐成为大家广泛讨论的问题。

哲学家就餐问题

问题描述如下：有5个哲学家，围着一个圆桌就餐。圆桌上有5份意大利面和5份叉子。哲学家比较

笨，他们必须拿到左手和右手的2个叉子才能吃面。哲学不饿的时候就在思考，饿了就去吃面，吃面的

必须前提是拿到2个叉子，吃完面哲学家就去思考。

假设每个哲学家用一个线程实现，求一种并发控制的算法，让哲学家们按部就班地思考和吃面。当然我

这里做了一些改动，比如Dijkstra那个年代线程还没有普及，最早的题目每个哲学家是一个进程。

问题的抽象

接下来请你继续思考，我们对问题进行一些抽象，比如哲学是一个数组，编号0~4。我这里用Java语

言给你演示，哲学家是一个类，代码如下：

staticclassPhilosopherimplementsRunnable{

privatestaticPhilosopher[]philosophers;

static{

philosophers=newPhilosopher[5];

}

}

这里考虑叉子也使用编号0~4，代码如下：

privatestaticInteger[]forks;

privatestaticPhilosopher[]philosophers;

static{

for(inti=0;i5;i++){

philosophers[i]=newPhilosopher(i);

forks[i]=-1;

}

}

forks[i]的值等于x，相当于编号为i的叉子被编号为x的哲学家拿起；如果等于-1，那么叉子目前

放在桌子上。

我们经常需要描述左、右的关系，为了方便计算，可以设计1个帮助函数（helperfunctions），帮助

我们根据一个编号，计算它左边的编号。

privatestaticintLEFT(inti){

returni0?4:i-1;

}

假设和哲学家编号一致的叉子在右边，这样如果要判断编号为id哲学家是否可以吃面，需要这样做：

if(forks[LEFT(id)]idforks[id]id){

}

然后定义一个_take函数拿起编号为i叉子;再设计一个_put方法放下叉子：

void_take(inti)throwsInterruptedException{

Thread.sleep(10);

forks[i]=id;

}

void_put(inti){

if(forks[i]id)

forks[i]=-1;

}

_take函数之所以会等待10ms，是因为哲学家就餐问题的实际意义，是I/O处理的场景，拿起叉子好

比磁盘，需要有一等的时间开销，这样思考才有意义。

然后是对think和eat两个方法的抽象。首先我封装了一个枚举类型，描述哲学家的状态，代码如下：

enumPHIS{

THINKING,

HUNGRY,

EATING

}

然后实现think方法，think方法不需要并发控制，但是这里用Thread.sleep模拟实际思考需要的

开销，代码如下：

voidthink()throwsInterruptedEx