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

操作系统课程设计

操作系统课程设计
课程设计报告
课题：利用信号量和多线程机制实现“哲学家进餐”问题

所在学院： 信息工程学院
班 级： 计科1201
学 号： 121404114
姓 名： 魏 祥
指导教师： 徐向英

2015年1月 1日
2 / 13

目录

一、课程设计目标 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型信号量的问题很难解决，最后便放弃了。拿到课题之前我对哲学家进餐问题了解的还不是很透彻，我利用网络和查询课本彻底搞懂了哲学家进餐问题。并且得到两种解决思路。通过此次的课程设计，我想我对多线程的编程理解更深了一点，虽然说死锁的出现几率不是非常的大，但是还是有可能会出现，一旦出现，程序就会锁在哪里，不能继续执行。所以解决死锁是非常必要的。
由于我在学习java语言的时候，里面有专门降到多线程编程，这对我顺利的完成此次的课程设计有很大的帮助。Jdk里面丰富的类库也省去了我编写线程类和信号量类的功夫。虽然说不必考虑这些，但编写代码的时候我还是遇到了一些问题，多线程的执行和信号量的设置让我话费了一些时间。
总的说，这次课程设计，我只用了一种法案解决了哲学家进餐问题，这让我有点不满意。但独自完成课程设计的感觉还是很畅快的。也让我对多线程，信号量的理解更深了。