文档章节

哲学家就餐问题(java实现)

cchoop
 cchoop
发布于 2017/04/15 11:46
字数 1073
阅读 415
收藏 1

1 问题概述
哲学家就餐问题,是并行程序中的一个经典问题,其描述如下。
1. 圆桌上有五位哲学家,每两人中间有一个筷子。
2. 每个哲学家有两件事情要做:
    (1) 思考;
    (2) 吃饭。哲学家必须同时拿到两只筷子,才能吃饭。
3. 哲学家之间并不知道对方何时要吃饭,何时要思考,不能协商制定分时策略。
4. 设计一个拿筷子的策略,使得哲学家之间不会因为拿筷子而出现死锁或者活锁。

2代码实现

  • 版本一(没有很好的解决死锁问题)

       当五个哲学家同时拿起左筷子,进入死锁状态

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后,就会有哲学家会放下右筷子,死锁解除

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();
	}
}
  • 版本三(服务生解法)

    添加一个服务生,只有当经过服务生同意之后才能拿筷子,服务生负责避免死锁发生。

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解法)

    请自行百度

© 著作权归作者所有

cchoop
粉丝 0
博文 5
码字总数 2239
作品 0
赣州
程序员
私信 提问
聊一聊并发编程的那些事(内含源码及面试题)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/t4i2b10X4c22nF6A/article/details/82889698 导读:之前写了一系列关于并发编程的文章,也对今年的一些大型互...

JAVA高级架构v
2018/09/28
0
0
java中高级大公司多线程面试题

1)在Java中Lock接口比synchronized块的优势是什么?你需要实现一个高效的缓存,它允许多个用户读,但只允许一个用户写,以此来保持它的完整性,你会怎样去实现它? lock接口在多线程和并发编...

java成功之路
2018/10/30
0
0
PV操作和信号量机制实现进程同步(对多个临界资源的互斥访问)

进程同步是我们在多线程中讨论最多的一个话题,在大多数的开发语言中,他们都有自己实现进程同步的方法或者实现。但归根结底他们实现的方式都是基于操作系统的进程同步的方式。今天我们就一起...

长平狐
2012/11/12
676
0
15个顶级Java多线程面试题及回答

Java 线程面试问题 在任何Java面试当中多线程和并发方面的问题都是必不可少的一部分。如果你想获得任何股票投资银行的前台资讯职位,那么你应该准备很多关于多线程的问题。在投资银行业务中多...

LCZ777
2014/05/27
0
0
10 个精妙的 Java 编码最佳实践

(点击上方公众号,可快速关注) 来源:ImportNew - liken 这是一个比Josh Bloch的Effective Java规则更精妙的10条Java编码实践的列表。和Josh Bloch的列表容易学习并且关注日常情况相比,这...

ImportNew
2018/04/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

C# 视频多人脸识别的实现过程

整个项目是用虹软技术完成开发 上一篇内容的调整,提交到git了,https://github.com/catzhou2002/ArcFaceDemo 基本思路如下: 一、识别线程 1.获取当前图片 2.识别当前图片的人脸位置,并将结...

是哇兴哥棒棒哒
16分钟前
0
0
Spring Cloud Eureka 你还在让它裸奔吗??

前些天栈长在微信公众号Java技术栈分享了 Spring Cloud Eureka 最新版 实现注册中心的实战教程:Spring Cloud Eureka 注册中心集群搭建,Greenwich 最新版!,成功进入 Eureka 控制台页面。 ...

Java技术栈
33分钟前
1
0
linux gyp ERR! stack Error: EACCES: permission denied, mkdir ‘xxx’

在使用linux npm install的出现这个错误了,百度了下,没有权限加个参数即可 npm install --unsafe-perm

朝如青丝暮成雪
34分钟前
1
0
使用kubeadm 搭建K8s集群

1. 参考官网 https://kubernetes.io/docs/setup/independent/install-kubeadm/

whhbb
今天
2
0
Dubbo 3.0 !提升不止一点点!

Dubbo 自 2011 年 10 月 27 日开源后,已被许多非阿里系的公司使用,其中既有当当网、网易考拉等互联网公司,也不乏中国人寿、青岛海尔等大型传统企业。 自去年 12 月开始,Dubbo 3.0 便已正...

编程SHA
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部