操作系统课程设计课程设计报告课题:利用信号量和多线程机制实现“哲学家进餐”问题所在学院:信息工程学院班级:计科1201学号:**********名:**指导教师:***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语言中使用记录型信号量更为方便,所以本次课题我使用的是思路一。
这两行注释掉,取消至多只允许四位哲学家一起拿起左筷子的限制,就会产生死锁。
四、源代码//在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型信号量的问题很难解决,最后便放弃了。
拿到课题之前我对哲学家进餐问题了解的还不是很透彻,我利用网络和查询课本彻底搞懂了哲学家进餐问题。
并且得到两种解决思路。
通过此次的课程设计,我想我对多线程的编程理解更深了一点,虽然说死锁的出现几率不是非常的大,但是还是有可能会出现,一旦出现,程序就会锁在哪里,不能继续执行。
所以解决死锁是非常必要的。
由于我在学习java语言的时候,里面有专门降到多线程编程,这对我顺利的完成此次的课程设计有很大的帮助。
Jdk里面丰富的类库也省去了我编写线程类和信号量类的功夫。
虽然说不必考虑这些,但编写代码的时候我还是遇到了一些问题,多线程的执行和信号量的设置让我话费了一些时间。