其他
哲学家进餐问题及其 3 种解决方案
（给算法爱好者加星标，修炼编程内功）
来源：qsyan
zhuanlan.zhihu.com/p/34553097
背景：n哲学家进餐问题描述有五个哲学家，他们的生活方式是交替地进行思考和进餐，n哲学家们共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五支筷子，n平时哲学家进行思考，饥饿时便试图取其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐，n进餐完毕，放下筷子又继续思考。
约束条件：
(1)只有拿到两只筷子时，哲学家才能吃饭。
(2)如果筷子已被别人拿走，则必须等别人吃完之后才能拿到筷子。
(3)任一哲学家在自己未拿到两只筷子吃饭前，不会放下手中拿到的筷子。
死锁现象：当每个科学家都一起拿起了左边的筷子时候死锁发生了，都想拿自己右边的筷子，但是科学家每个人左手都不松手。导致都吃不了饭
下面用java代码演示上面的死锁现象：
package ThreadDemo;
public class Fiveeat {
public static void main(String[] args) {
Thread perple0=new Thread(new eatAndThink(FiveLock.lock0,FiveLock.lock1),"科学家0");
Thread perple1=new Thread(new eatAndThink(FiveLock.lock1,FiveLock.lock2),"科学家1");
Thread perple2=new Thread(new eatAndThink(FiveLock.lock2,FiveLock.lock3),"科学家2");
Thread perple3=new Thread(new eatAndThink(FiveLock.lock3,FiveLock.lock4),"科学家3");
Thread perple4=new Thread(new eatAndThink(FiveLock.lock4,FiveLock.lock0),"科学家4");
perple0.start();
perple1.start();
perple2.start();
perple3.start();
perple4.start();
}
}
class eatAndThink implements Runnable{
private Object lockL;
private Object lockR;
public eatAndThink(Object lockL,Object lockR){
this.lockL=lockL;
this.lockR=lockR;
}
@Override
public void run() {
while (true){
synchronized (lockL){ //先拿左边的筷子
System.out.println(Thread.currentThread().getName()+" 我拿到了左边的筷子");
try {
Thread.sleep(2);//让死锁发生更快
} catch (InterruptedException e) {
e.printStackTrace();
}
synchronized (lockR){ //然后拿右边的筷子
System.out.println(Thread.currentThread().getName()+" 我拿到了右边的筷子");
System.out.println(Thread.currentThread().getName() +" 开始吃饭了");
}
}
System.out.println(Thread.currentThread().getName()+" 科学家放下手中的筷子，开始去思考了");
try {
Thread.sleep(2);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
package ThreadDemo;
//五只筷子
public class FiveLock {
static Object lock0=new Object();
static Object lock1=new Object();
static Object lock2=new Object();
static Object lock3=new Object();
static Object lock4=new Object();
}
结果：每个科学家都拿到了一只筷子，然后想拿另外一只筷子，但是都不松手。
解决科学家进餐方案一：规定奇数号科学家先拿左边的筷子，然后拿右边的筷子。偶数号科学家先拿右边的筷子，然后那左边的筷子。导致0，1科学家竞争1号筷子，2，3科学家竞争3号筷子。四号科学家无人竞争。最后总有一个科学家能获得两只筷子。
代码;
public class Fiveeat {
public static void main(String[] args) {
Thread perple0=new Thread(new eatAndThink(FiveLock.lock1,FiveLock.lock0),"科学家0");
Thread perple1=new Thread(new eatAndThink(FiveLock.lock1,FiveLock.lock2),"科学家1");
Thread perple2=new Thread(new eatAndThink(FiveLock.lock3,FiveLock.lock2),"科学家2");
Thread perple3=new Thread(new eatAndThink(FiveLock.lock3,FiveLock.lock4),"科学家3");
Thread perple4=new Thread(new eatAndThink(FiveLock.lock0,FiveLock.lock4),"科学家4");
perple0.start();
perple1.start();
perple2.start();
perple3.start();
perple4.start();
}
}
解决科学家进餐方案二：仅当科学家左右两只筷子都能用的时候，才允许他进餐：ReentrantLock tryLock()
代码如下所示：
package ThreadDemo;
import java.util.concurrent.locks.ReentrantLock;
public class Fiveeat {
public static void main(String[] args) {
Thread perple0=new Thread(new eatAndThink(FiveLock.lock0,FiveLock.lock1),"科学家0");
Thread perple1=new Thread(new eatAndThink(FiveLock.lock1,FiveLock.lock2),"科学家1");
Thread perple2=new Thread(new eatAndThink(FiveLock.lock2,FiveLock.lock3),"科学家2");
Thread perple3=new Thread(new eatAndThink(FiveLock.lock3,FiveLock.lock4),"科学家3");
Thread perple4=new Thread(new eatAndThink(FiveLock.lock4,FiveLock.lock0),"科学家4");
perple0.start();
perple1.start();
perple2.start();
perple3.start();
perple4.start();
}
}
class eatAndThink implements Runnable{
private ReentrantLock lockL;
private ReentrantLock lockR;
public eatAndThink(ReentrantLock lockL,ReentrantLock lockR){
this.lockL=lockL;
this.lockR=lockR;
}
@Override
public void run() {
while (true){
synchronized (this){
/*if ((!lockR.isLocked())&&(!lockL.isLocked())){
lockL.lock();*/
if (lockR.tryLock()&&lockL.tryLock()){
System.out.println(Thread.currentThread().getName()+" 我拿到了左边的筷子");
try {
Thread.sleep(2);
} catch (InterruptedException e) {
e.printStackTrace();
}
lockR.lock();//然后拿右边的筷子
System.out.println(Thread.currentThread().getName()+" 我拿到了右边的筷子");
System.out.println(Thread.currentThread().getName() +" 开始吃饭了");
}
/*
lockR.unlock();*/
System.out.println(Thread.currentThread().getName()+" 科学家放下手中的筷子，开始去思考了");
try {
Thread.sleep(2);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}
package ThreadDemo;
import java.util.concurrent.locks.ReentrantLock;
public class FiveLock {//分别代表无双筷子
static ReentrantLock lock0=new ReentrantLock();
static ReentrantLock lock1=new ReentrantLock();
static ReentrantLock lock2=new ReentrantLock();
static ReentrantLock lock3=new ReentrantLock();
static ReentrantLock lock4=new ReentrantLock();
}
这里利用了tryLock（）
请自行查找 lock,tryLock Java中Lock，tryLock，lockInterruptibly有什么区别？
解决科学家进餐方案三：
至多允许四个哲学家同时去拿左边的筷子，最终保证至少有一个科学家能进餐，并且用完之后释放筷子，从而使更多的哲学家能够拿到筷子。
代码：
package ThreadDemo;
import java.util.Random;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.locks.ReentrantLock;
public class Fiveeat {
public static void main(String[] args) {
ExecutorService executorService= Executors.newFixedThreadPool(4);//定义一个线程池，四个线程。保证最多四个哲学家同时拿到左边的筷子。
Object [] lock=new Object[5];//定义五个筷子
for (int i=0;i<5;i++){
lock[i]=new ReentrantLock();
}
while (true){
int a=new Random().nextInt(5); //定义一个随机数，用来获取某一哲学家左右两只筷子
executorService.submit(new eatAndThink((ReentrantLock)lock[a],(ReentrantLock)lock[(a+1)%5]));
}
}
}
class eatAndThink implements Runnable{
private ReentrantLock lockL;
private ReentrantLock lockR;
public eatAndThink(ReentrantLock lockL,ReentrantLock lockR){
this.lockL=lockL;
this.lockR=lockR;
}
@Override
public void run() {
synchronized (lockL){
System.out.println(Thread.currentThread().getName()+" 我拿到了左边的筷子");
try {
Thread.sleep(2);
} catch (InterruptedException e) {
e.printStackTrace();
}
synchronized (lockR){
System.out.println(Thread.currentThread().getName()+" 我拿到了右边的筷子");
System.out.println(Thread.currentThread().getName() +" 开始吃饭了");
}
}
System.out.println(Thread.currentThread().getName()+" 科学家放下手中的筷子，开始去思考了");
try {
Thread.sleep(2);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
- EOF -
觉得本文有帮助？请分享给更多人
推荐关注「算法爱好者」，修炼编程内功
点赞和在看就是最大的支持❤️