1 问题概述
哲学家就餐问题,是并行程序中的一个经典问题,其描述如下。
1. 圆桌上有五位哲学家,每两人中间有一个筷子。
2. 每个哲学家有两件事情要做:
(1) 思考;
(2) 吃饭。哲学家必须同时拿到两只筷子,才能吃饭。
3. 哲学家之间并不知道对方何时要吃饭,何时要思考,不能协商制定分时策略。
4. 设计一个拿筷子的策略,使得哲学家之间不会因为拿筷子而出现死锁或者活锁。
2代码实现
- 版本一(没有很好的解决死锁问题)
当五个哲学家同时拿起左筷子,进入死锁状态
java">package com.cch;
public class Philosopher extends Thread{
private static int[] chopsticks = {1,1,1,1,1};
private int id;
public Philosopher(int id){
this.id = id;
}
@Override
public synchronized void run() {
this.eat();
this.think();
}
public void think(){
//左筷子放下
this.chopsticks[this.id] = 1;
//右筷子放下
this.chopsticks[(this.id+1)%this.chopsticks.length] = 1;
System.out.println("哲学家_" + this.id + "正在思考");
//思考一秒时间
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
public void eat(){
//拿起左筷子
while(true){
if(this.chopsticks[this.id] != 0){
chopsticks[this.id] = 0;
System.out.println("哲学家_" + this.id + "拿起了左筷子");
break;
}else{
try {
this.wait(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}finally{
System.out.println("哲学家_" + this.id + "的左筷子正在被哲学家_"+((this.id-1+this.chopsticks.length)%this.chopsticks.length)+"使用,等待1000ms");
}
}
}
//拿起右筷子
while(true){
if(this.chopsticks[(this.id+1)%this.chopsticks.length] != 0){
chopsticks[(this.id+1)%this.chopsticks.length] = 0;
System.out.println("哲学家_" + this.id + "拿起了右筷子");
break;
}else{
try {
this.wait(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}finally{
System.out.println("哲学家_" + this.id + "的右筷子正在被哲学家_"+((this.id+1)%this.chopsticks.length)+"使用,等待1000ms");
}
}
}
System.out.println("哲学家_" + this.id + "正在吃饭");
//吃饭花一秒时间
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
this.notify();
}
public static void main(String[] args) {
new Philosopher(0).start();
new Philosopher(1).start();
new Philosopher(2).start();
new Philosopher(3).start();
new Philosopher(4).start();
}
}
- 版本二(超时释放法)
当五个哲学家同时拿起左筷子时,线程进入死锁,等待2s后,就会有哲学家会放下右筷子,死锁解除
java">package com;
public class Philosopher extends Thread{
private static int[] chopsticks = {1,1,1,1,1};
private int id;
public Philosopher(int id){
this.id = id;
}
@Override
public synchronized void run() {
this.eat();
this.think();
}
public void think(){
//左筷子放下
this.chopsticks[this.id] = 1;
//右筷子放下
this.chopsticks[(this.id+1)%this.chopsticks.length] = 1;
System.out.println("哲学家_" + this.id + "正在思考");
//思考一秒时间
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
public void eat(){
//拿起左筷子
while(true){
if(this.chopsticks[this.id] != 0){
chopsticks[this.id] = 0;
System.out.println("哲学家_" + this.id + "拿起了左筷子");
break;
}else{
try {
this.wait(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}finally{
System.out.println("哲学家_" + this.id + "的左筷子正在被哲学家_"+((this.id-1+this.chopsticks.length)%this.chopsticks.length)+"使用,等待1000ms");
}
}
}
//拿起右筷子
while(true){
if(this.chopsticks[(this.id+1)%this.chopsticks.length] != 0){
chopsticks[(this.id+1)%this.chopsticks.length] = 0;
System.out.println("哲学家_" + this.id + "拿起了右筷子");
break;
}else{
try {
this.wait(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}finally{
System.out.println("哲学家_" + this.id + "的右筷子正在被哲学家_"+((this.id+1)%this.chopsticks.length)+"使用,等待1000ms");
}
}
}
System.out.println("哲学家_" + this.id + "正在吃饭");
//吃饭花一秒时间
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
this.notify();
}
public static void main(String[] args) {
new Philosopher(0).start();
new Philosopher(1).start();
new Philosopher(2).start();
new Philosopher(3).start();
new Philosopher(4).start();
}
}
- 版本三(服务生解法)
添加一个服务生,只有当经过服务生同意之后才能拿筷子,服务生负责避免死锁发生。
java">package com.cch.Philosopher;
class Philosopher extends Thread{
private String name;
private Fork fork;
public Philosopher(String name,Fork fork){
super(name);
this.name=name;
this.fork=fork;
}
public void run(){
while(true){
thinking();
fork.takeFork();
eating();
fork.putFork();
}
}
public void eating(){
System.out.println("I am Eating:"+name);
try {
sleep(1000);//吃饭花一秒
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
public void thinking(){
System.out.println("I am Thinking:"+name);
try {
sleep(1000);//思考花一秒
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
class Fork{
private boolean[] used={false,false,false,false,false,false};
/*只有当左右手的筷子都未被使用时,才允许获取筷子,且必须同时获取左右手筷子*/
public synchronized void takeFork(){
String name = Thread.currentThread().getName();
int i = Integer.parseInt(name);
while(used[i]||used[(i+1)%5]){
try {
wait();//如果左右手有一只正被使用,等待
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
used[i ]= true;
used[(i+1)%5]=true;
}
/*必须同时释放左右手的筷子*/
public synchronized void putFork(){
String name = Thread.currentThread().getName();
int i = Integer.parseInt(name);
used[i ]= false;
used[(i+1)%5]=false;
notifyAll();//唤醒其他线程
}
}
public class ThreadTest {
public static void main(String []args){
Fork fork = new Fork();
new Philosopher("0",fork).start();
new Philosopher("1",fork).start();
new Philosopher("2",fork).start();
new Philosopher("3",fork).start();
new Philosopher("4",fork).start();
}
}
- 版本四(资源分级法)
请自行百度
- 版本五(Chandy/Misra解法)
请自行百度