最新消息:

哲学家抢筷子吃饭的问题

java基础 yangshuai 1052浏览 0评论

前两天面试偶遇一个题目,看起来挺有意思,大致意思是:

几个哲学家(这里假定是5个)围在一张圆桌吃饭,彼此相邻的两个哲学家之间放一根筷子,规定哲学家吃饭都会先拿左边的筷子,再拿右边的筷子,都拿起来之后才可以吃饭,吃完放下两根筷子。

现在先设计代码模拟哲学家们吃饭的情景,并在后面提出解决方案,解决哲学家们同时开始吃饭时候发生的死锁现象。

首先考虑,筷子是大家争抢的资源,每两个哲学家争强一根筷子,所以可以用锁来表示,我们用 ReentryLock;

其次,每个哲学家都是独立的个体,每个人都吃自己的,还要争抢筷子,所以用线程来表示,我们用 Thread;

至于饭,他们爱吃啥吃啥把,啃桌子都行,咱们就不关心了。

现在很清楚了,代码即文字:

//定义五根筷子,因为要争抢,所以用锁来表示
private static ReentrantLock[]  sticks = new ReentrantLock[5];
//定义五个人(哲学家,单词不会,用man表示吧)来吃饭
private static Foo[] mans = new Foo[5];

static {
    for (int i = 0; i <5 ; i++) {
        sticks[i] = new ReentrantLock();
        //用i来给他们分配名字,从0号到4号
        mans[i] = new Foo(String.valueOf(i));
    }
}

public static void main(String[] args) {

    for (int i = 0; i < 5 ; i++) {
        mans[i].start();//让他们一起开始吃饭
    }
}

static class Foo extends Thread {

    public Foo(String name) {
        super(name);
    }

    @Override
    public void run() {
        int witchMan = Integer.valueOf(Thread.currentThread().getName()); //获取哲学家的名字(编号)
        ReentrantLock leftStick = sticks[witchMan]; //哲学家左手边的筷子
        //哲学家右手边的筷子,最后一个哲学家右手边与第一个哲学家左手边筷子是同一根
        ReentrantLock rightStick = sticks[witchMan >= mans.length - 1 ? 0 : witchMan + 1]; 
        System.out.println("我是哲学家[" + witchMan + "],我正在拿我左手边的筷子...");
        leftStick.lock();
        System.out.println("我是哲学家[" + witchMan + "],我拿到了左边筷子,正在拿右边筷子...");
        rightStick.lock();
        System.out.println("我是哲学家[" + witchMan + "],我拿到了右边筷子,开始吃饭...");
        try {
             Thread.sleep(10000); //模拟哲学家吃饭需要10秒钟
        } catch (InterruptedException e) {
             e.printStackTrace();
        }
        System.out.println("我是哲学家[" + witchMan + "],我吃完了饭");
        leftStick.unlock();
        rightStick.unlock();
    }
}

运行之后我们看到了下面的情景:

我是哲学家[0],我正在拿我左手边的筷子
我是哲学家[3],我正在拿我左手边的筷子
我是哲学家[4],我正在拿我左手边的筷子
我是哲学家[2],我正在拿我左手边的筷子
我是哲学家[2],我拿到了左边筷子,正在拿右边筷子
我是哲学家[1],我正在拿我左手边的筷子
我是哲学家[4],我拿到了左边筷子,正在拿右边筷子
我是哲学家[3],我拿到了左边筷子,正在拿右边筷子
我是哲学家[0],我拿到了左边筷子,正在拿右边筷子
我是哲学家[1],我拿到了左边筷子,正在拿右边筷子

很明显,他们同时拿起了左手边的筷子,然后等着自己右边的人放下自己右手边的筷子,发生死锁了!!  想想程序还真是傻,换我的话,你们先吃着。。。我打会儿牌。。

下面我们就要来解决问题了:

首先我们分析,这是个环形的死锁,只要打破一个,就可以解决死锁问题;

其次,我们注意到,必须要知道他们是不是形成了死锁,思路是 看看是不是所有人都在等着锁,是的话就是死锁了。

还是老规矩,代码即解释,如下:

private final static int MAN_TOTAL = 5;
//定义五根筷子,因为要争抢,所以用锁来表示
private static ReentrantLock[] sticks = new ReentrantLock[MAN_TOTAL];
//定义五个人(哲学家,单词不会)来吃饭
private static Foo[] mans = new Foo[MAN_TOTAL];

static {
    for (int i = 0; i < MAN_TOTAL; i++) {
        sticks[i] = new ReentrantLock(true);//公平锁
        mans[i] = new Foo(String.valueOf(i));//用i来给他们分配名字,从0号到4号
    }
}

public static void main(String[] args) {

    for (int i = 0; i < MAN_TOTAL; i++) {
        mans[i].start();//让他们一起开始吃饭
    }

    try {
        Thread.sleep(1000);
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
    System.out.println(getTimeString() + " 我是饭店老板,我看看他们开始吃了没");
    interruptDead();

}

/**
 *
 */
public static void interruptDead() {
    int eatingManCount = 0;//完成人数
    int finishedManCount = 0;
    for (Foo man : mans) {
        int witchMan = Integer.valueOf(man.getName()); //获取哲学家的名字(编号)
        ReentrantLock leftStick = sticks[witchMan];    //哲学家左手边的筷子
        ReentrantLock rightStick = sticks[witchMan >= mans.length - 1 ? 0 : witchMan + 1];  //哲学家右手边的筷子
        if (!leftStick.hasQueuedThread(man) && !rightStick.hasQueuedThread(man)) {          //这位哲学家既没有等左手筷子,也没有在等右手筷子,那他肯定在吃饭啊
            System.out.println(getTimeString() + " 我是饭店老板,看到哲学家[" + witchMan + "]正在吃饭");
            eatingManCount++;
        }
        if (!man.isAlive()) {           //如果他吃完饭这个线程就该挂了
            finishedManCount++;
        }
    }
    //如果还有人没吃完,而且没有正在吃饭的人,那就是发生死锁了!!
    if (finishedManCount < MAN_TOTAL && eatingManCount < 1) {
        System.out.println(getTimeString() + " 我是饭店老板,看到他们抢筷子抢的不可开交,根本无心吃饭!!");
        mans[0].interrupt(); //让它先放下筷子,这样他右边的就可能吃饭了
    }
}

public static String getTimeString() {
    return new SimpleDateFormat("mm:ss").format(new Date());//请不要太较真
}

static class Foo extends Thread {

    public Foo(String name) {
        super(name);
    }

    private boolean finished = false;

    @Override
    public void run() {
        while (!finished) { //上次没吃成就再来
            int witchMan = Integer.valueOf(Thread.currentThread().getName());                            //获取哲学家的名字(编号)
            ReentrantLock leftStick = sticks[witchMan];                                                  //哲学家左手边的筷子
            ReentrantLock rightStick = sticks[witchMan >= mans.length - 1 ? 0 : witchMan + 1];           //哲学家右手边的筷子,最后一个哲学家右手边与第一个哲学家左手边筷子是同一根
            try {
                System.out.println(getTimeString() + " 我是哲学家[" + witchMan + "],我正在拿我左手边的筷子...");
                leftStick.lockInterruptibly();//可以被中断的锁,代表这位哲学家左边的筷子被命令放下
                System.out.println(getTimeString() + " 我是哲学家[" + witchMan + "],我拿到了左边筷子,正在拿右边筷子...");
                rightStick.lockInterruptibly();
                System.out.println(getTimeString() + " 我是哲学家[" + witchMan + "],我拿到了右边筷子,开始吃饭...");
                Thread.sleep(10000);        //模拟哲学家吃饭需要10秒钟
                finished = true;            //设置这位的饭吃完了
                System.out.println(getTimeString() + " 我是哲学家[" + witchMan + "],我吃完了饭");
            } catch (InterruptedException e) {
                System.out.println(getTimeString() + " 我是哲学家[" + witchMan + "],我被迫放下了手中的筷子,但是老子不甘心,敢跟我比手速吗,你贏了你先吃!");//之所以用公平锁是为了防止锁偏向,一直是这家伙抢到
            } finally {
                if (leftStick.isHeldByCurrentThread()) {
                    System.out.println(getTimeString() + " 我是哲学家[" + witchMan + "],我完事了,放下左手的筷子");
                    leftStick.unlock();
                }
                if (rightStick.isHeldByCurrentThread()) {
                    System.out.println(getTimeString() + " 我是哲学家[" + witchMan + "],我也放下右边筷子");
                    rightStick.unlock();
                }
            }
        }
    }
}

下面是故事日志:

11:35 我是哲学家[4],我正在拿我左手边的筷子...
11:35 我是哲学家[0],我正在拿我左手边的筷子...
11:35 我是哲学家[3],我正在拿我左手边的筷子...
11:35 我是哲学家[2],我正在拿我左手边的筷子...
11:35 我是哲学家[4],我拿到了左边筷子,正在拿右边筷子...
11:35 我是哲学家[1],我正在拿我左手边的筷子...
11:35 我是哲学家[2],我拿到了左边筷子,正在拿右边筷子...
11:35 我是哲学家[3],我拿到了左边筷子,正在拿右边筷子...
11:35 我是哲学家[0],我拿到了左边筷子,正在拿右边筷子...
11:35 我是哲学家[1],我拿到了左边筷子,正在拿右边筷子...
11:36 我是饭店老板,我看看他们开始吃了没
11:36 我是饭店老板,看到他们抢筷子抢的不可开交,根本无心吃饭!!
11:36 我是哲学家[0],我被迫放下了手中的筷子,但是老子不甘心,敢跟我比手速吗,你贏了你先吃!
11:36 我是哲学家[0],我完事了,放下左手的筷子
11:36 我是哲学家[0],我正在拿我左手边的筷子...
11:36 我是哲学家[4],我拿到了右边筷子,开始吃饭...
11:46 我是哲学家[4],我吃完了饭
11:46 我是哲学家[4],我完事了,放下左手的筷子
11:46 我是哲学家[4],我也放下右边筷子
11:46 我是哲学家[3],我拿到了右边筷子,开始吃饭...
11:46 我是哲学家[0],我拿到了左边筷子,正在拿右边筷子...
11:56 我是哲学家[3],我吃完了饭
11:56 我是哲学家[3],我完事了,放下左手的筷子
11:56 我是哲学家[3],我也放下右边筷子
11:56 我是哲学家[2],我拿到了右边筷子,开始吃饭...
12:06 我是哲学家[2],我吃完了饭
12:06 我是哲学家[2],我完事了,放下左手的筷子
12:06 我是哲学家[2],我也放下右边筷子
12:06 我是哲学家[1],我拿到了右边筷子,开始吃饭...
12:16 我是哲学家[1],我吃完了饭
12:16 我是哲学家[1],我完事了,放下左手的筷子
12:16 我是哲学家[1],我也放下右边筷子
12:16 我是哲学家[0],我拿到了右边筷子,开始吃饭...
12:26 我是哲学家[0],我吃完了饭
12:26 我是哲学家[0],我完事了,放下左手的筷子
12:26 我是哲学家[0],我也放下右边筷子

我们很容易看到,首先发生了死锁,然后哲学家0 被迫放下了自己左边的筷子,这时候哲学家4抢到了他放下的筷子,也就是4右手的筷子,然后他就开始吃。他吃完了,放下自己左右手的筷子,然后他左边的哲学家3就可以吃饭了,右边的筷子则还给哲学家0的左手,苦逼的哲学家0只能等2也吃完自己才 吃。

这样是解决了问题,但是我们发现他们所有人在傻傻的看一个人吃,不知道换你还吃不吃的下去。。。。那么我们怎么实现让一拨人先吃,另一拨人先去打牌呢??卖个关子,自己想吧。O(∩_∩)O哈哈~

最后想说的是共用筷子是不卫生的!!!

转载请注明:心阳之家 » 哲学家抢筷子吃饭的问题

发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址