哲学家就餐问题
标签:Java并发

问题描述:

五个哲学家(A~E)围着一张圆桌就餐,他们每个人面前都有一盘通心粉。由于通心粉很滑,所以需要两只筷子才能夹住,但每两个盘子之间只放着一只筷子,如下图。

哲学家只有两个动作:要么就餐,要么思考。而且他们之间从不交谈。
当一个哲学家饿了的时候,就拿起盘子左右两边的筷子开始就餐(不能同时拿起两只筷子)。就餐完以后,就把筷子放回盘子左右,继续思考。

由于他们之间互不交谈,所以很容易出现“死锁”:假如每个人都拿着左边的筷子,则所有人都在等右边的筷子,谁都吃不了。

我们可以规定,拿着一只筷子等待另一只筷子的时间超过五分钟就放下手中的筷子,并且再等待五分钟之后进行下一次尝试。
这个策略消除了死锁,不过还是有可能发生“活锁”:假如这五个人同时拿起左边的筷子,大家都在等另一只筷子,五分钟之后大家同时放下筷子。再过五分钟之后又同时拿起左边的筷子……

在计算机领域中,哲学家就餐问题可以抽象成资源抢占问题,筷子就是“资源”。一种常用的计算机技术就是给资源“加锁”,一个资源同时只能供一个程序或者一段代码访问。当一个程序要使用的资源被另外一个程序锁定的时候,只能等待资源被解锁。这就容易出现死锁情况,当有两个程序需要访问两个相同的资源时,如果每个程序都锁了一个资源,那么两者都在等待对方解锁另一个资源的解锁,最后谁都无法执行。


下面来看一下代码:

Chopstick

class Chopstick {
    public Chopstick() {
    }
}

Philosopher

此时的哲学家,没有加任何锁,也没有任何限制:

class Philosopher extends Thread {

    private Chopstick left;
    private Chopstick right;
    private Random random;
    public Philosopher(Chopstick left, Chopstick right) {
        this.left = left;
        this.right = right;
        random=new Random();
    }

    @Override
    public void run() {
        try {
            while (true) {
                //思考一段时间
                Thread.sleep(random.nextInt(1000));
                synchronized (left) {
                    synchronized (right) {
                        //进餐一段时间
                        Thread.sleep(random.nextInt(1000));
                        System.out.println("Philosopher " + this + " eating");
                    }
                }
            }
        }
        catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

}

DiningPhilosopher

public class DiningPhilosophers {
    public static void main(String[] args) throws InterruptedException {
        Philosopher[] philosophers=new Philosopher[5];
        Chopstick[] chopsticks=new Chopstick[5];

        for (int i = 0; i < 5; i++) {
            chopsticks[i]=new Chopstick();
        }
        for (int i = 0; i < 5; i++) {
            philosophers[i]=new Philosopher(chopsticks[i],chopsticks[(i+1)%5]);
            philosophers[i].start();
        }
        for (int i = 0; i < 5; i++) {
            philosophers[i].join();
        }
    }
}

可见这个时候如果我们开启5个线程去执行的话,那么很有可能出现死锁问题。

解决方法一

先来看一下死锁的四个条件:

死锁的四个条件:
(1) 互斥条件:一个资源每次只能被一个进程使用。
(2) 请求与保持条件:一个进程因请求资源而阻塞时,对已获得的资源保持不放。
(3) 不剥夺条件:进程已获得的资源,在末使用完之前,不能强行剥夺。
(4) 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系


我们可以给筷子编号,规定号码小的为左筷子,号码大的为右筷子(主要就是最后顺时针数的最后一个哲学家,它的左筷子要和第一个哲学家公用),这样我们就有了最大的一个筷子来打破循环等待的死锁条件。

这个时候的哲学家代码为:

Philosopher

class Philosopher extends Thread {
    private Chopstick first, second;
    private Random random;

    public Philosopher(Chopstick left, Chopstick right) {
        if(left.getId() < right.getId()) {
            first = left; second = right;
        } else {
            first = right; second = left;
        }
        random = new Random();
    }

    @Override
    public void run() {
        try {
            while(true) {
                Thread.sleep(random.nextInt(1000));     // Think for a while
                synchronized(first) {                   // Grab first chopstick
                    synchronized(second) {                // Grab second chopstick
                        Thread.sleep(random.nextInt(1000)); // Eat for a while
                        System.out.println("Philosopher " + this + " eating");
                    }
                }
            }
        } catch(InterruptedException e) {}
    }
}

解决方法二

构建两个ReentrantLock,这样在获取不到锁的时候释放锁,为获取锁操作设置超时时间。这样不会死锁(至少不会无尽的死锁),破坏死锁的请求与保持条件

Philosopher

class Philosopher extends Thread {
    private ReentrantLock leftChopstick;
    private ReentrantLock rightChopstick;

    private Random random;

    public Philosopher(ReentrantLock leftChopstick,ReentrantLock rightChopstick){
        this.leftChopstick=leftChopstick;
        this.rightChopstick=rightChopstick;
        random=new Random();
    }

    @Override
    public void run() {
        try {
            while (true){
//                思考
                Thread.sleep(random.nextInt(1000));
                leftChopstick.lock();
                try {
                    if (rightChopstick.tryLock(1000, TimeUnit.MILLISECONDS)){
                        try {
                            Thread.sleep(1000);
                            System.out.println("Philosopher " + this + " eating");
                        } finally {
                            rightChopstick.unlock();
                        }
                    }else {
                        System.out.println("Philosopher " + this + " timed out");
                    }
                }finally {
                    leftChopstick.unlock();
                }
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

这样在获取到左筷子的时候,如果超时没有获取到右筷子,则释放左筷子,让其他哲学家进餐。

参考链接:哲学家就餐问题与死锁总结

  • 5 min read

CONTRIBUTORS


  • 5 min read