操作系统课程设计利用多线程和信号量解决哲学家进餐问题 java实现

操作系统课程设计操作系统课程设计 课程设计报告课程设计报告 课课题 题 利用信号量和多线程机制实现利用信号量和多线程机制实现 哲学家进餐哲学家进餐 问题问题 所在学院 信息工程学院信息工程学院 班 级 计科计科 12011201 学 号 121404112140411414 姓 名 魏魏 祥祥 指导教师 徐向英徐向英 2015 年 1 月 1 日 目录目录 一 课程设计目标 3 二 课题内容 3 三 设计思路 3 四 源代码 5 五 运行与测试 9 六 心得体会 10 一 课程设计目标一 课程设计目标 学习多线程编程 使用线程的同步机制实现 哲学家进餐 问题 具体要求 1 创建 POSIX 线程 实现多线程的并发执行 验证多线程共享进程资源的特 性 2 使用互斥量和条件变量 或使用信号量实现线程的同步互斥 3 验证 哲学家进餐 问题中的死锁情况 并加以解决 二 课题内容二 课题内容 哲学家进餐问题由 Dijkstra 提出 问题描述有五个哲学家共用一张圆桌 分别坐在周围的五张椅子上 在圆桌上有五个碗和五支筷子 他们的生活方式 是交替地进行思考和进餐 平时 一个哲学家进行思考 饥饿时便试图取用其 左右最靠近他的筷子 只有在他拿到两只筷子时才能进餐 进餐完毕 放下筷 子继续思考 本次课题要求使用多线程和信号量解决哲学家进餐问题 并演示产生死锁 的情况 三 设计思路三 设计思路 经分析可知 放在桌子上的筷子是临界资源 在一段时间内只允许以为 哲学家使用 为了实现对筷子的互斥 可以用一个信号量表示一只筷子 由着 五个信号量构成信号量数组 当哲学家饥饿时总是先去拿左筷子 成功后在拿右筷子 当五位哲学家 同时拿起左筷子 这是每位哲学家都没有右筷子可以拿 就会造成死锁 思路思路 1 利用记录型信号量 利用记录型信号量 设置值为 4 的记录型信号量 至多只允许四位哲学家同时去拿左筷 子 leftStick getSema acquire 只有拿到左筷子 才能继续拿右筷子 rightStick getSema acquire 拿到两双筷子之后便可以用餐 用餐完毕 先 放下左筷子 leftStick getSema release 再放下右筷子 rightStick getSema release 这样便可以避免思索问题 思路思路 2 利用 利用 AND 型信号量型信号量 要求每个哲学家必须获取两个筷子的时候才能够进餐 只得到一只 筷子不能进餐时 要求释放那一只筷子 可以使用 AND 型信号量将左筷子和 右筷子信号量的获取组成一个原子操作 如此也可以避免死锁问题 本次课程设计是在 windows 系统下完成 编程语言为 java 开发环境 Eclipse 由于在 java 语言中使用记录型信号量更为方便 所以本次课题我使用的 是思路一 static Semaphore room new Semaphore 4 设置值为 4 的记录型信号量 至多只允许四个哲学家同时拿起左筷子 private Semaphore semaphore new Semaphore 1 在筷子类中为筷子设置值为 1 信号量 room acquire 获取值为4的信号量 leftStick getSema acquire 获取左筷子信号量 Thread sleep 1000 1 拿到左筷子之后等待2秒 观察死锁 rightStick getSema acquire 获取右筷子信号量 eat Thread sleep 1000 2 用完餐后等待2秒 继续思考 finishEat leftStick getSema release 释放左筷子信号量 rightStick getSema release 释放右筷子信号量 room release 释放值为4的信号量 当需要演示死锁的情况是 只需要将 room acquire 和 room release 这两行注释掉 取消至多只允许四位哲学家一起拿起左筷子的限制 就会产生 死锁 ChopStick chopStick new ChopStick 5 for int i 0 i 5 i chopStick i new ChopStick i New 出编号 0 到 4 的五支筷子 Philosopher ph0 new Philosopher 0 chopStick 0 chopStick 1 Philosopher ph1 new Philosopher 1 chopStick 1 chopStick 2 Philosopher ph2 new Philosopher 2 chopStick 2 chopStick 3 Philosopher ph3 new Philosopher 3 chopStick 3 chopStick 4 Philosopher ph4 new Philosopher 4 chopStick 4 chopStick 0 New 出编号 0 到 4 的五位哲学家 他们分别对应着自己的左 右两支筷子 ExecutorService excutor Executors newFixedThreadPool 5 5 位哲学家用餐 所以需要 5 个线程同时执行 创建容量为 5 的线程池 四 源代码四 源代码 在 Windows 下运行 筷子类筷子类 ChopStick java import java util concurrent Semaphore public class ChopStick private int ID private boolean available private Semaphore semaphore new Semaphore 1 public ChopStick int ID this ID ID this available true this semaphore new Semaphore 1 public void setAvai boolean available this available available public boolean getAvai return this available public Semaphore getSema return this semaphore public void setSema Semaphore sema this semaphore sema public int getId return this ID 哲学家类哲学家类 Philosopher java import java util concurrent Semaphore public class Philosopher implements Runnable private int ID static Semaphore room new Semaphore 4 private ChopStick leftStick private ChopStick rightStick public Philosopher int ID ChopStick cs1 ChopStick cs2 this ID ID this leftStick cs1 this rightStick cs2 public void getLeftChopStick this leftStick setAvai false public int getId return ID public void eat leftStick setAvai false rightStick setAvai false System out println 哲学家 this getId 正在用餐 public void think System out println 哲学家 this getId 正在思考 public void finishEat System out println 哲学家 this getId 用餐结束 正在思考 leftStick setAvai true rightStick setAvai true public void readyToEat System out println 哲学家 this getId 饿了准备用餐 public void cannotEat System out println 哲学家 this getId 缺少筷子 不能用餐 等待 public void run try room acquire this readyToEat if this leftStick getSema availablePermits 0 this leftStick getSema availablePermits 0 this cannotEat this leftStick getSema acquire Thread sleep 1000 1 this rightStick getSema acquire this eat Thread sleep 1000 2 this finishEat this leftStick getSema release this rightStick getSema release room release catch InterruptedException ex ex toString 测试测试 Test java import java util concurrent import java util Scanner public class Test public static void main String args Scanner input new Scanner System in menu int choice input nextInt while choice 1 if choice 0 ChopStick chopStick new ChopStick 5 for int i 0 i 5 i chopStick i new ChopStick i ExecutorService excutor Executors newFixedThreadPool 5 Philosopher ph0 new Philosopher 0 chopStick 0 chopStick 1 excutor execute new Philosopher 0 chopStick 0 chopStick 1 excutor execute new Philosopher 1 chopStick 1 chopStick 2 excutor execute new Philosopher 2 chopStick 2 chopStick 3 excutor execute new Philosopher 3 chopStick 3 chopStick 4 excutor execute new Philosopher 4 chopStick 4 chopStick 0 excutor shutdown choice input nextInt menu public static void menu System out println 0 演示 System out println 1 结束 五 运行与测试五 运行与测试 1 运行界面运行界面 2 死锁演示死锁演示 3 无死锁演示无死锁演示 六 心得体会六 心得体会 本次课程设计我总得来说花的时间不是太多 代码加起来一共不超过两百 行 我只用了一种思路来完成 思路一完成之后 我也尝试着用思路二完成 但是 AND 型信号量的问题很难解决 最后便放弃了 拿到课题之前我对哲学 家进餐问题了解的还不是很透彻 我利用网络和查询课本彻底搞懂了哲学家进 餐问题 并且得到两种解决思路 通过此次的课程设计 我想我对多线程的编 程理解更深了一点 虽然说死锁的出现几率不是非常的