哲学家进餐问题(图文详解)
1、哲学家进餐问题描述
哲学家进餐问题说的是:有五个哲学家,他们的生活方式是交替地进行思考和进餐,哲学家们共用一张圆桌,分别坐在周围的五张椅子上,在圆桌上有五个碗和五支筷子,平时哲学家进行思考,饥饿时便试图取其左、右最靠近他的筷子,只有在他拿到两支筷子时才能进餐,该哲学家进餐完毕后,放下左右两只筷子又继续思考。这个问题是由荷兰学者Dijkstra提出的经典的同步问题之一。哲学家进餐问题是一大类并发控制问题的典型例子,涉及信号量机制、管程机制以及死锁等操作系统中关键问题的应用,在操作系统文化史上具有非常重要的地位。对该问题的剖析有助于深刻地理解计算机系统中的资源共享、进程同步机制、死锁等问题,并能熟练地将该问题的解决思想应用于生活中的控制流程。
2、哲学家进餐问题算法的基本思想
用PV操作信号量来实现这个算法,当哲学家饥饿时,只能拿左边右边的筷子,拿到2个筷子才能进餐,且不能同时拿两边的筷子,我的思想是先让哲学家去拿他左边的筷子,执行Wait方法,成功后,再去拿他右边的筷子,执行Wait方法,成功后便可进餐。进餐毕,先放下他左边的筷子,然后再放下右边的筷子,但是可能会出现最坏的一种情况,就是大家同时都拿起左边筷子,造成死锁。为防止这个情况的发生,我将5个哲学家从1到5编号,奇数号的哲学家先拿起左边的筷子,再拿起右边的筷子。偶数号的哲学家先拿起右边的筷子,再拿起左边的筷子。从而使得,只有1号和2号哲学家会同时竞争1号的筷子,3号和4四号的哲学家会同时竞争3号的筷子,即这5位哲学家会先竞争奇数号的筷子,再去竞争偶数号的筷子,最后总会有一个哲学家可以进餐成功。这样就打破了死锁的循环等待条件,从而避免了死锁的发生!
注:(实际程序中我是从0到4给哲学家和筷子编的号 程序中判断奇数偶数时用的ID+1)
3、算法实现流程图
…流程差不多就是这样(可能会画的不是特别准确,但理解大概思路就好)
4、你要的程序它来了!
注:看代码前最好对线程 和 PV操作信号量有些了解 代码总体简要说明:
用PV操作信号量来实现这个算法,init()方法初始化每个筷子信号量,创建五个哲学家进程执行start()方法,当线程调用了run()方法后,对进入该方法的哲学家进行判断,奇数号的哲学家先拿起左边的筷子,再拿起右边的筷子。偶数号的哲学家先拿起右边的筷子,再拿起左边的筷子,(拿筷子前执行Wait方法,成功后,再去拿他另一个筷子,执行Wait方法,成功后便可进餐)放筷子也按拿筷子时的左右顺序放下从而避免死锁。当run()执行到第30次后退出程序。
本人代码 PV操作信号量的详细说明:
说的通俗点就是 哲学家在使用筷子时,筷子信号量本是1但由于这位哲学家的使用使信号量-1,为0,按本人代码来看的话 下次在有人想抢这个筷子的时候 会先执行信号量-1的操作,当发现(count < 0)了 也是信号量小于0了 ,就说明这个筷子你没抢上 正有哲学家在用,他就要等待notify函数将其唤醒, 那么某时抢到这个筷子的哲学家sleep()完了 也就是吃完了 那么信号量就要加1,此时再一个判断count<=0 ?,正常来说,他用之前信号量是1,吃完饭执行PV操作后这个筷子的信号量还应该是1。但如果如果count<=0为真的话就是说 在他使用的这个筷子期间还有人想使用这个筷子 但是没抢上 所以现在要做的是PV操作这个筷子的信号量+1,可以notify他 了也就是将其唤醒。使之运行下去。
package zhexuejiajincan;
public class Main {
public static void main(String[] args) {
Init init = new Init(); // 先初始化每个筷子的信号量,该方法内用一个信号量表示一个筷子
Man man[] = new Man[5]; // 创建5个哲学家
int i;
for (i = 0; i < 5; i++) {
man[i] = new Man(i);
}
Thread[] t = new Thread[5]; // 创建5个线程
for (i = 0; i < 5; i++) {
t[i] = new Thread(man[i]); // 创建5个哲学家类型的线程
}
for (i = 0; i < 5; i++) {
t[i].start(); // 启动这五个线程!
// //因为调用线程的start方法,并不是马上启动run方法,而是进入就绪状态,由系统内部的调度方法来调用,所以运行结果不唯一
}
}
}
class PV { // PV操作类
int count = 0; // 信号量
PV() {
}
PV(int a) {
count = a; // 给每个筷子定义个信号量
}
public synchronized void Wait(int id) { // 关键字 synchronized
// 保证了此操作是一条原语,可以保证在同一时刻,只有一个线程可以执行某个方法或某个代码块,
count--; // p操作
// 若count减1后仍大于或等于0,则进程继续执行,反之则该进程被阻塞后放入等待该信号量的等待队列中,然后转线程调度。
if (count < 0) { // 等于0 :有一个进程进入了临界区
try {
System.out.println("哲学家" + id + "在思考"); // 这时候说明他身边至少有一根筷子被占用了
// 所有只能thinking 等被人吃完
// notify()后才通知他
this.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
public synchronized void Signal(int id) { // 关键字 synchronized
// 保证了此操作是一条原语,可以保证在同一时刻,只有一个线程可以执行某个方法或某个代码块,
count++; // v操作若相加后结果大于0,则进程继续执行,若相加后结果小于或等于0,则从该信号的等待队列中释放一个等待进程,然后再返回线程继续执行或转线程调度
if (count <= 0) { // 如果有进程阻塞
this.notify(); // All notify通知所有等待的线程
}
}
}
class Init {
static PV chopsticks[] = new PV[5];
// 重写了无参构造方法 从而自动new PV类 进行相应的操作。
Init() {
int i;
for (i = 0; i < 5; i++) {
chopsticks[i] = new PV(1);// 初始化信号量传入参数1表示用一个信号量表示一个筷子
System.out.println("哲学家"+i+"在思考"); //最开始所有哲学家的初始状态都在思考
}
}
}
class Man implements Runnable {// 哲学家类 //Runnable和Thread二者本身就没有本质区别,就是接口和类的区别
int ID = 0;
Man() {
}
Man(int id) {
ID = id;
}
// 重写线程的run方法
public void run() {
while (true) {
// 因为哲学家man的ID我是从0开始赋值的 故在判断奇数偶数时 我加了1
if ((ID + 1) % 2 != 0) {
// 奇数号哲学家
// 拿起左筷子
Init.chopsticks[ID].Wait(ID);
// 拿起右筷子
Init.chopsticks[(ID + 1) % 5].Wait(ID);
System.out.println("哲学家" + ID + "拿起了筷子" + ID + "和筷子"+ ((ID + 1) % 5) + "吃了起来");
try {
Thread.sleep(1000);// 1000毫秒,让当前正在执行的线程休眠(暂停执行),从而看出哲学家目前的状态
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("哲学家" + ID + "吃完了,把筷子放回了原处,开始思考");
//因为奇数哲学 先拿的左后拿的右 那么放筷子的时候也是这个顺序
Init.chopsticks[ID].Signal(ID);
Init.chopsticks[(ID + 1) % 5].Signal(ID + 1);
} else {
// 偶数号哲学家
// 请求右边的筷子
Init.chopsticks[(ID + 1) % 5].Wait(ID);
// 再请求左边的筷子
Init.chopsticks[ID].Wait(ID);
System.out.println("哲学家" + ID + "拿起了筷子" + ID + "和筷子"+ ((ID + 1) % 5) + "吃了起来");
try {
Thread.sleep(1000);// 1000毫秒,让当前正在执行的线程休眠(暂停执行),从而看出哲学家目前的状态
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("哲学家" + ID + "吃完了,把筷子放回了原处,开始思考");
//因为偶数哲学 先拿的右后拿的左 那么放筷子的时候也是这个顺序
Init.chopsticks[(ID + 1) % 5].Signal(ID + 1);
Init.chopsticks[ID].Signal(ID);
}
}
}
更多推荐
PV操作解决哲学家进餐问题(图文详解)
发布评论