【Android多线程】哲学家就餐问题

哲学家就餐问题（Dining philosophers problem） 是经典的用来演示在并发计算中多线程同步的问题。 

在1971年，计算机科学家艾兹格·迪科斯彻提出了一个同步问题，即假设有五台计算机都试图访问五份共享的磁带驱动器。稍后，这个问题被托尼·霍尔重新表述为哲学家就餐问题。这个问题可以用来解释死結和资源耗尽。

问题可以简单描述为：5位哲学家围绕一个餐桌就左，餐桌上有5支（不是5双）筷子。哲学家会“思考”或者“就餐”，“就餐”需要拿起他身边的两双筷子，进餐结束后会放回筷子。

同步和死锁

我们使用对象内置锁，即关键字synchronized来表示哲学家企图拿起筷子就餐的过程，用餐结束后通过释放锁（即退出程序块）来放回筷子。简单的代码如下：

public class Philosopher extends Thread {
    private static final String TAG = "Philosopher";
    private String name;
    private Chopstick left;
    private Chopstick right;
    private Random random;

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

    @Override
    public void run() {
        try {
            while (true) {
                // Think for a while.
                Thread.sleep(random.nextInt(1000));
                Log.i(TAG, name + " finished thinking.");
                // Grab the left chopstick.
                Log.i(TAG, name + " tried to grab chopstick " + left.id);
                synchronized (left) {
                    Log.i(TAG, name + " grabbed chopstick " + left.id);
                    Log.i(TAG, name + " tried to grab chopstick " + left.id);
                    // Grab the right chopstick.
                    synchronized (right) {
                        Log.i(TAG, name + " grabbed chopstick " + right.id);
                        // Eat for while.
                        Thread.sleep(random.nextInt(1000));
                        Log.i(TAG, name + " finished eating.");
                    }
                }
            }
        } catch (InterruptedException e) {
            // do nothing
        }
    }

    static final class Chopstick {
        int id;
        public Chopstick(int id) {
            this.id = id;
        }
    }
}

这样的竞争就可能导致死锁（但实际情况下，程序可能会运行很久很久。。。）。从log很容看书死锁的原因：

16787-16838 I/Philosopher: #4 grabbed chopstick 4
16787-16838 I/Philosopher: #4 tried to grab chopstick 5
16787-16837 I/Philosopher: #3 grabbed chopstick 3
16787-16837 I/Philosopher: #3 tried to grab chopstick 4
16787-16837 I/Philosopher: #2 grabbed chopstick 2
16787-16837 I/Philosopher: #2 tried to grab chopstick 3
16787-16837 I/Philosopher: #5 grabbed chopstick 5
16787-16837 I/Philosopher: #2 tried to grab chopstick 1
16787-16835 I/Philosopher: #1 grabbed chopstick 1
16787-16835 I/Philosopher: #1 grabbed chopstick 2

每个哲学家都拿了自己左边的筷子，并且尝试去拿右边的筷子。每个哲学家都很执拗，不会放下手中的筷子。。。

一个简单的策略可以避开这种“环”的锁：总按照一个全局固定的规则来请求锁。如上面的日志中，如果每个哲学家都先拿ID更小的筷子，在拿ID更大的筷子，就不会有问题。也就是Philosopher #5 不会先拿到筷子5，这样Philosopher #4就可以先拿到并且放下筷子，解锁Philosopher #3，一次类推。。。

可以更改Philosopher的构造函数，通过筷子ID来设置请求顺序：

public Philosopher(String name, Chopstick left, Chopstick right) {
        this.name = name;
        if (left.id < right.id) {
            this.left = left;
            this.right = right;
        } else {
            this.left = right;
            this.right = left;
        }
        random = new Random();
    }

如果Chopstick对象没有属性id，也可以使用对象散列值，不过有一定概率（非常小）会遇到散列冲突，即不同的对象有一样的散列值：

public Philosopher(String name, Chopstick left, Chopstick right) {
        this.name = name;
        if (System.identityHashCode(left) < System.identityHashCode(right)) {
            this.left = left;
            this.right = right;
        } else  {
            this.left = right;
            this.right = left;
        }
        random = new Random();
    }

重入锁

重入锁ReetrantLock虽然在一定程序上与内置锁是等价的，但它提供了超时的设置，使得我们可以避免程序“无限期”死锁。

public class Philosopher extends Thread {
    private static final String TAG = "Philosopher";
    private String name;
    private Chopstick left;
    private Chopstick right;
    private Random random;

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

    @Override
    public void run() {
        try {
            while (true) {
                // Think for a while.
                Thread.sleep(random.nextInt(1000));
                Log.i(TAG, name + " finished thinking.");
                // Grab the left chopstick.
                Log.i(TAG, name + " tried to grab chopstick " + left.id);
                try {
                    left.grab();
                    Log.i(TAG, name + " grabbed chopstick " + left.id);
                    Log.i(TAG, name + " tried to grab chopstick " + left.id);
                    if (right.tryGrab()) {
                        // Grab the right chopstick.
                        Log.i(TAG, name + " grabbed chopstick " + right.id);
                        try {
                            // Eat for while.
                            Thread.sleep(random.nextInt(1000));
                            Log.i(TAG, name + " finished eating.");
                        } finally {
                            right.putDown();
                        }
                    }
                } finally {
                    left.putDown();
                }
            }
        } catch (InterruptedException e) {
            // do nothing
        }
    }

    static final class Chopstick {
        int id;
        ReentrantLock lock;
        public Chopstick(int id) {
            this.id = id;
            lock = new ReentrantLock();
        }

        public void grab() {
            lock.lock();
        }

        public boolean tryGrab() throws InterruptedException {
           return lock.tryLock(1000, TimeUnit.MILLISECONDS);
        }

        public void putDown() {
            lock.unlock();
        }
    }
}

条件变量

条件变量Condition实现了“等待某件事情发生”，使得我们可以实现“等待其他哲学家就餐完成”的逻辑。

条件变量需要与锁关联使用，并且在等待条件之前需要先获取锁。获取锁之后，判断条件是否为真来进行后续动作，否则就通过await()原地等待。对于我们的需求，每个哲学家要判断旁边的哲学家是否“没有就餐”，否则就进行等待，直到有其他哲学家就餐完成，即其他线程通过调用singal()或者singalAll()，await()会回复运行并重新判断。注意此时条件“旁边的哲学家都没有正在就餐”不一定为帧，因为可能左边的哲学家已经通知就餐结束，但右边的哲学家仍在就餐，所以需要重新进行判断。

public class Philosopher extends Thread {
    private static final String TAG = "Philosopher";
    private final String name;
    private final Condition condition;
    private final Random random;
    private boolean eatting;

    private Philosopher left;
    private Philosopher right;
    private ReentrantLock table;

    public Philosopher(String name) {
        this.name = name;
        table = new ReentrantLock();
        condition = table.newCondition();
        random = new Random();
    }

    public void setLeft(Philosopher3 philosopher) {
        left = philosopher;
    }

    public void setRight(Philosopher3 philosopher) {
        right = philosopher;
    }

    @Override
    public void run() {
        try {
            while (true) {
                think();
                eat();
            }
        } catch (InterruptedException e) {
            // do nothing
        }
    }

    private void think() throws InterruptedException {
        table.lock();
        try {
            eatting = false;
            left.condition.signal();
            right.condition.signal();
        } finally {
            table.unlock();
        }
        Thread.sleep(random.nextInt(1000));
        Log.i(TAG, name + " finished thinking.");
    }

    private void eat() throws InterruptedException {
        table.lock();
        try {
            Log.i(TAG, name + " tried to grab chopstick from " + left.name + " and " + right.name);
            while (left.eatting || right.eatting) {
                condition.wait();
            }
            Log.i(TAG, name + " grabbed chopsticks.");
            eatting = true;
        } finally {
            table.unlock();
        }
        Thread.sleep(random.nextInt(1000));
        Log.i(TAG, name + " finished eating.");
    }
}

新的实现中只有一个锁table，且每个哲学家不在直接关心筷子，而是关心其他的哲学家对象。每个哲学家就餐完成后会通知旁边的哲学家，这样正在等待的哲学家就有可以重新尝试拿起筷子。

这样做的好处不仅是使得我们的哲学家看上去更为“绅士”，更能有效的避免资源浪费：如果旁边的哲学家正在就餐，就等待且不拿起筷子，这样也就不会出现一个哲学家拿着一个筷子等待另一个筷子的情况。

代码下载： https://github.com/xiaoweicqu/dining-philosophers-problem

参考资料

• 维基百科： https://zh.wikipedia.org/wiki/%E5%93%B2%E5%AD%A6%E5%AE%B6%E5%B0%B1%E9%A4%90%E9%97%AE%E9%A2%98
• Paul Butcher: Seven Concurrency Models in Seven Weeks