哲学家就餐问题之java解决
前言
哲学家就餐问题是在计算机科学中的一个经典问题,用来演示在并行计算中多线程同步(Synchronization)时产生的问题。
有五个哲学家,他们共用一张圆桌,分别坐在五张椅子上。在圆桌上有五个碗和五支筷子,平时一个哲学家进行思考,饥饿时便试图取用其左、右最靠近他的筷子,只有在他拿到两支筷子时才能进餐。进餐完毕,放下筷子又继续思考。
代码描述:
public class PhilosopherThread extends Thread {
private Chopsticks left;
private Chopsticks right;
private int index;
public PhilosopherThread(Chopsticks left, Chopsticks right, int index) {
this.left = left;
this.index = index;
this.right = right;
}
@Override
public void run() {
synchronized (left) {
try {
Thread.sleep(3000L);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(index + "等待获取筷子RIGHT进行吃饭");
synchronized (right) {
System.out.println(index + "获取筷子RIGHT进行吃饭");
}
}
}
public static void main(String[] args) {
Chopsticks chopsticks1 = new Chopsticks();
Chopsticks chopsticks2 = new Chopsticks();
Chopsticks chopsticks3 = new Chopsticks();
Chopsticks chopsticks4 = new Chopsticks();
Chopsticks chopsticks5 = new Chopsticks();
PhilosopherThread philosopherThread1 = new PhilosopherThread(chopsticks1, chopsticks2, 1);
PhilosopherThread philosopherThread2 = new PhilosopherThread(chopsticks2, chopsticks3, 2);
PhilosopherThread philosopherThread3 = new PhilosopherThread(chopsticks3, chopsticks4, 3);
PhilosopherThread philosopherThread4 = new PhilosopherThread(chopsticks4, chopsticks5, 4);
PhilosopherThread philosopherThread5 = new PhilosopherThread(chopsticks5, chopsticks1, 5);
philosopherThread1.start();
philosopherThread2.start();
philosopherThread3.start();
philosopherThread4.start();
philosopherThread5.start();
}
}
通过运行代码,我们发现每一个哲学家都持有左边的筷子取去取右边的筷子,到第五个人的时候,他需要获取的右边筷子是第一个哲学家左手的筷子,最终形成死锁。
如何解决这个问题呢
1. 线程粗化,一个哲学家同时拥有左右筷子时才允许进餐。
2. 奇偶互反,奇数哲学家先取右边,偶数先取左边。
3. 最少保证,最多只有4名哲学家同时去获取左边筷子,最后一名先获取右边筷子,也就是说最少保证有一个哲学家和其他哲学家的取筷顺序是相反的。
1.线程粗化
看代码,我们得知每一个哲学家都是先持有左边的筷子,然后再去获取右边的筷子,如果我们让哲学家同时持有左右筷子的时候在进餐,是不是就能保证不会出现死锁的情况呢。
在java中,没办法同时获取两个对象的锁,必须先获取左边或者右边筷子,才能获取另外一只筷子的锁,这时候我们抽象一下,把左右筷子当成一整个变量,谁获取到了这个变量的锁,就当谁同时持有了左右两只筷子。
也就是说通过一个全局变量,使用互斥锁的方式,谁先获得了,谁就允许进餐。
这种方式可不可行呢,我们看看代码
public class PhilosopherThread extends Thread {
private Chopsticks left;
private Chopsticks right;
private int index;
private String mutex;
public PhilosopherThread(Chopsticks left, Chopsticks right, int index, String mutex) {
this.left = left;
this.index = index;
this.right = right;
this.mutex = mutex;
}
@Override
public void run() {
try {
Thread.sleep(3000L);
} catch (InterruptedException e) {
e.printStackTrace();
}
synchronized (mutex) {
System.out.println(index + " :获取筷进行吃饭:" + left + ":" + right);
}
}
public static void main(String[] args) {
Chopsticks chopsticks1 = new Chopsticks();
Chopsticks chopsticks2 = new Chopsticks();
Chopsticks chopsticks3 = new Chopsticks();
Chopsticks chopsticks4 = new Chopsticks();
Chopsticks chopsticks5 = new Chopsticks();
String mutex="lock";
PhilosopherThread philosopherThread1 = new PhilosopherThread(chopsticks1, chopsticks2, 1,mutex);
PhilosopherThread philosopherThread2 = new PhilosopherThread(chopsticks2, chopsticks3, 2,mutex);
PhilosopherThread philosopherThread3 = new PhilosopherThread(chopsticks3, chopsticks4, 3,mutex);
PhilosopherThread philosopherThread4 = new PhilosopherThread(chopsticks4, chopsticks5, 4,mutex);
PhilosopherThread philosopherThread5 = new PhilosopherThread(chopsticks5, chopsticks1, 5,mutex);
philosopherThread1.start();
philosopherThread2.start();
philosopherThread3.start();
philosopherThread4.start();
philosopherThread5.start();
}
}
2.奇偶互反
奇偶互反实际上就是针对哲学家编号,奇偶数获取相反的顺序,
比如哲学家编号从1到5,奇数的先取左边筷子,偶数的取右边筷子。那么1号哲学家取左边,2号哲学家取右边,3号哲学家取左边,以此类推,通过这样编号得到的结果就是,1号获取到左右筷子,开始进餐,2号获取到右边筷子,等待1号吃完放下在获取左边筷子(1号的右边是2号的左边),3号等待获取左边筷子,4号这时候又能同时拥有左右筷子开始进餐。
public class PhilosopherThread extends Thread {
private Chopsticks left;
private Chopsticks right;
private int index;
public PhilosopherThread(Chopsticks left, Chopsticks right, int index) {
this.left = left;
this.index = index;
this.right = right;
}
@Override
public void run() {
if (index % 2 == 0) {
synchronized (right) {
try {
Thread.sleep(3000L);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(index + "等待获取筷子LEFT进行吃饭");
synchronized (right) {
System.out.println(index + "获取筷子LEFT进行吃饭");
}
}
} else {
synchronized (left) {
try {
Thread.sleep(3000L);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(index + "等待获取筷子RIGHT进行吃饭");
synchronized (right) {
System.out.println(index + "获取筷子RIGHT进行吃饭");
}
}
}
}
public static void main(String[] args) {
Chopsticks chopsticks1 = new Chopsticks();
Chopsticks chopsticks2 = new Chopsticks();
Chopsticks chopsticks3 = new Chopsticks();
Chopsticks chopsticks4 = new Chopsticks();
Chopsticks chopsticks5 = new Chopsticks();
PhilosopherThread philosopherThread1 = new PhilosopherThread(chopsticks1, chopsticks2, 1);
PhilosopherThread philosopherThread2 = new PhilosopherThread(chopsticks2, chopsticks3, 2);
PhilosopherThread philosopherThread3 = new PhilosopherThread(chopsticks3, chopsticks4, 3);
PhilosopherThread philosopherThread4 = new PhilosopherThread(chopsticks4, chopsticks5, 4);
PhilosopherThread philosopherThread5 = new PhilosopherThread(chopsticks5, chopsticks1, 5);
philosopherThread1.start();
philosopherThread2.start();
philosopherThread3.start();
philosopherThread4.start();
philosopherThread5.start();
}
}
3.最少保证
最少保证,最多只有4名哲学家同时去获取左边筷子,最后一名先获取右边筷子,也就是说最少保证有一个哲学家和其他哲学家的取筷顺序是相反的。这实际上和奇偶的思路是一致的,每次保证有一个人哲学家获取筷子的顺序和其他哲学家相反,这样死锁的条件就不成立。
public class PhilosopherThread extends Thread {
private Chopsticks left;
private Chopsticks right;
private int index;
public PhilosopherThread(Chopsticks left, Chopsticks right, int index) {
this.left = left;
this.index = index;
this.right = right;
}
@Override
public void run() {
if (index==5) {
synchronized (right) {
try {
Thread.sleep(3000L);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(index + "等待获取筷子LEFT进行吃饭");
synchronized (right) {
System.out.println(index + "获取筷子LEFT进行吃饭");
}
}
} else {
synchronized (left) {
try {
Thread.sleep(3000L);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(index + "等待获取筷子RIGHT进行吃饭");
synchronized (right) {
System.out.println(index + "获取筷子RIGHT进行吃饭");
}
}
}
}
public static void main(String[] args) {
Chopsticks chopsticks1 = new Chopsticks();
Chopsticks chopsticks2 = new Chopsticks();
Chopsticks chopsticks3 = new Chopsticks();
Chopsticks chopsticks4 = new Chopsticks();
Chopsticks chopsticks5 = new Chopsticks();
PhilosopherThread philosopherThread1 = new PhilosopherThread(chopsticks1, chopsticks2, 1);
PhilosopherThread philosopherThread2 = new PhilosopherThread(chopsticks2, chopsticks3, 2);
PhilosopherThread philosopherThread3 = new PhilosopherThread(chopsticks3, chopsticks4, 3);
PhilosopherThread philosopherThread4 = new PhilosopherThread(chopsticks4, chopsticks5, 4);
PhilosopherThread philosopherThread5 = new PhilosopherThread(chopsticks5, chopsticks1, 5);
philosopherThread1.start();
philosopherThread2.start();
philosopherThread3.start();
philosopherThread4.start();
philosopherThread5.start();
}
本文地址:https://blog.csdn.net/kissfox220/article/details/109602882
上一篇: DB2编程序技巧 (七)