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

本是古典何须时尚 2022-01-05 05:53 280阅读 0赞

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

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

![dinning\_phiosophers][dinning_phiosophers]

问题可以简单描述为：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_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][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

[Dining philosophers problem]: https://zh.wikipedia.org/zh-hans/%E5%93%B2%E5%AD%A6%E5%AE%B6%E5%B0%B1%E9%A4%90%E9%97%AE%E9%A2%98
[dinning_phiosophers]: /images/20211229/aa824e46f86643e6939937ebbb812828.png
[https_github.com_xiaoweicqu_dining-philosophers-problem]: 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]: 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