《哲学家进餐问题的一种解决方案.doc》由会员分享，可在线阅读，更多相关《哲学家进餐问题的一种解决方案.doc（2页珍藏版）》请在三一办公上搜索。
1、关键词: Java; 多线程; 同步; 临界资源; 死锁中图分类号: TP 301文献标识码: A文章编号: 1009- 3044(2006)14- 0163- 02A Arithme tic to S olve the Dining P roble m of the P hilos ophe rsJIA Yu- zhen1,WAN G Xiang- luo2(1.N anyang Science and Technology University,N anyang 473000,China;2.Luoyang N ormal College,Luoyang 471022,China)Abs
2、tra ct:The key to The dining problem of philosophers is make Processes or Threads synchronized and avoid the forming of DeadLock. In this article, the author briefly introduces a way to solve this problem by adding a restrictively rule. The integrated code is offered.Ke y words :Java;multithread;syn
3、chrony;critical resource;DeadLock1 J a va 中的多线程技术线程是进程中的一个实体, 是被系统独立调度和分派的基本 单位。因为它具有许多传统进程所具有的特征, 又称为轻型进程( Light- Weight Process) 或进程元。多线程指使单个程序内部也可 以在同一时刻执行多个代码段, 完成不同的任务的机制。多线程技术的出现极大地提高了程序的效率和相应时间。Java 语言全面地支持多线程机制, 可以方便地生成多线程应 用程序, 而且运行环境也利用多线程的技术并发地提供多 项 服 务, 如“垃圾”回收等。Java 语言中提供了 Thread 类, 在类中
4、封装了 许 多 关 于 线 程 操 作 的 方 法 , 如 线 程 的 启 动 、运 行 、休 眠 、挂 起 、恢 复、退出和终止以及对线程优先级的控制, 并提供了 synchronized 关键字来处理线程之间的共享互斥问题。由于 Java 语言具备功能强大的多线程管理机制, 本文中采用Java语言编写实现代码。2 哲学家进餐问题哲学家进餐问题是一个典型的同步问题。这个问题由 Dijk- stra 提出: 五个哲学家围坐在一张圆桌周围, 他们的生活方式是交替地进行思考和进餐。桌上有五支筷子, 每两个哲学家之间放一支。哲学家和筷子的编号都为 1 至 5, 1 号哲学家左右分别是 1, 2 号筷
5、子, 依次类推, 5 号哲学家左右则分别是 5, 1 号筷子。哲学家 饥饿时便试图拿起他左边和右边的筷子准备进餐, 只有同时取得 两支筷子后方可进餐。进餐后便放下两支筷子继续思考。假设五个哲学家同时感到饥饿, 各自拿起自己左边的筷子, 当他们试图拿起自己右边的筷子时会发现右边的筷子已经 被 自 己右边的同伴拿走。这样的话, 每个哲学家都因为无法同时取得 两支筷子而无法进餐, 从而进入死锁状态。3 一种解决方案为了避免进入死锁状态, 我们给该问题添加一条限制规则:规定在同一时刻至多允许四名哲学家同时竞争筷子。这样的话就 总有一名哲学家可以顺利获得两支筷子而开始进餐, 从而有效地预防了死锁的产生。
6、接下来我们用 Java 语言来实现该刚才描述的策略。在实现代 码中用五个线程表示五个哲学家的活动, 用一个逻辑型数组表示 筷子的状态。在此问题中, 筷子是临界资源, 必须互斥地进行访问。我们为 筷子定义一个类, 其中包含了表示筷子状态的逻辑型数组, 也包 含拿起筷子, 放下筷子的方法, 由于这些方法涉及对临界资源的访问, 我们把它定义为 synchronized, 使多个哲学家线程可以同步地进行访问。另外, 为了统计正在竞争筷子的哲学家线程数目, 定 义了一个整型变量 sum。class Chopsticks/* 用 used1至 used5五个数组元素分别代表编号 1 至 5 的 五支筷子的
7、状态 */* false 表示未被占用, true 表示已经被占用。used0元素在程 序中未使用 */privateboolean used=true,false,false,false,false,false;/* 变量 sum 记录正在参与竞争的哲学家线程数目 */private int sum=0;/* 拿起筷子的操作 */public synchronized void takeChopstick()/* 根据哲学家进程的名称获取该哲学家应该使用的筷子编 号 */* i 为左手边筷子编号, j 为右手边筷子编号 */String name=Thread.currentThread()
8、.getName();int i=Integer.parseInt(name);int j=i=5?1:i+1;/* 如果现在正在参与竞争的哲学家线程数目达到了四个, 就 不允许本线程参与竞争,而是进入等待区等待其他线程的结束 */while(sum=4) trywait(); catch(InterruptedException e)/* 条件满足后本线程退出等待区也参与竞争, 故 sum 变量增1 */sum+;/* 首先竞争左手边的筷子 */while(usedi) trywait(); catch(InterruptedException e)收稿日期: 2006- 01- 21作者简
9、介: 贾玉珍( 1978- ) , 女, 河南南阳人, 助教, 主要从事计算机技术应用开发与教学; 王祥雒( 1977- ) , 男, 河南洛阳人, 助 教, 主要从事信息安全与 O S 核心研究。usedi=true;/* 然后竞争右手边的筷子 */while(usedj) trywait(); catch(InterruptedException e)usedj=true;public synchronized void putChopstick()String name=Thread.currentThread().getName();int i=Integer.parseInt(nam
10、e);int j=i=5?1:i+1;/* 将相应筷子的标志置为 fasle 表示使用完毕,他等待线程来竞争 */usedi=false;usedj=false;eating();chopsticks.putChopstick();public void thinking()/* 显示字符串输出正在思考的哲学家, 用线程休眠 1 秒钟来 模拟思考时间 */System.out.println (Philosopher +Thread.currentThread ().get- Name()+ is thinking.);tryThread.sleep(1000);catch(Interrupt
11、edException e)public void eating()/* 显示字符串输出正在进餐的哲学家, 并用线程休眠 1 秒钟 来模拟进餐时间 */System.out.println (Philosopher +Thread.currentThread ().get- Name()+ is eating.);tryThread.sleep(1000);catch(InterruptedException e)在运行时, 用 Philosopher 类产生五个线程模拟五个哲学家,每个线程不停地执行思考、拿起筷子、进餐、放下筷子的方法。线 程的名称依次为“1”, “2”, “3”, “4”,
12、 “5”( 字符串类型) 。主程序如下:public class Mainzpublic static void main(String args)并且通知其/* 进餐完毕放下筷子, 退出竞争, 故 sum 变量减一 */sum- - ;notifyAll();当某一哲学家线程执行取得筷子方法时, 程序会根据该线程 的名称来确定该线程需要使用哪两支筷子, 在取得这两支筷子进餐之前需要对三个条件进行检验:条件一, 此时参与竞争筷子的哲学家线程数目小于四个;条件二, 左手边的筷子未被占用;条件三, 右手边的筷子未被占用。这三个条件均满足的话, 该哲学家线程即可取得两支筷子进 餐, 否则会在不满足条
13、件处执行 wait()操作进入 Chopsticks 类实例/* 产生筷子类的实例 chopsticks */的等待区,直到其他的哲学家线程进餐完毕放下筷子时用 noti-Chopsticks chopsticks=new Chopsticks();/* 用筷子类的实例作为参数, 产生五个哲学家线程并启动 */* 五个哲学家线程的名称为 15 */new Philosopher(1,chopsticks).start(); new Philosopher(2,chopsticks).start(); new Philosopher(3,chopsticks).start(); new Phil
14、osopher(4,chopsticks).start(); new Philosopher(5,chopsticks).start();运行后, 从输出的结果可以看到五个哲学家线程交替地进行 思考和进餐, 互斥地使用筷子, 不会进入死锁状态, 哲学家进餐问题得到了解决。按 Ctrl+C 可以中止程序的运行。4 结束语我们利用 Java 语言的多线程机制建立了哲学家进餐问题的 模型, 通过附加的竞争规则预防了在该问题中出现死锁。该问题还有其他的解决方案, 如规定所有哲学家先竞争奇数号筷子, 获 得后才能去竞争偶数号筷子, 或规定每位哲学家所请求的两支筷子必须一次性分配完毕。另外, 利用管程机制
15、也可以解决该问 题。参考文献:1Harvey M.Deitel,Paul J.Deitel.Java 程 序 设 计 教 程 M. 北 京 :机械工业出版社,2002.2结 城 浩.Java 多 线 程 设 计 模 式M. 北 京: 中 国 铁 道 出 版 社 ,2005.3汤子瀛等.计算机操作系统M. 西安:西安电子科技大学出 版社,1996.fyAll()将其唤醒。当某一哲学家线程放下筷子时, 该线程会将放下的筷子所对应的数组元素值置为 false, 表示使用完毕, 可以交给 其他线程使用, 并将 sum 变量减一, 最后用 notifyAll()唤醒在等待 区里的其他线程。如果将条件一对
16、应的代码删除掉, 读者会观察到在本程序运 行不久后所有线程都会因为条件二或条件三不满足而进入等待 区, 整个程序进入死锁状态。接下来定义出哲学家类class Philosopher extends ThreadChopsticks chopsticks;public Philosopher(String name,Chopsticks chopsticks)/* 在 构 造 实 例 时 将 name 参 数 传 给 Thread 的 构 造 函 数 作 为 线程的名称 */super(name);/* 所有哲学家线程共享同一个筷子类的实例 */this.chopsticks=chopsticks;public void run()/* 交替地思考、拿起筷子、进餐、放下筷子 */while(true) thinking(); chopsticks.takeChopstick();
