内容简介:在1971年,计算机科学家艾兹格·迪科斯彻提出了一个同步问题,即假设有五台计算机都试图访问五份共享的磁带驱动器。稍后,这个问题被托尼·霍尔重新表述为哲学家就餐问题。这个问题可以用来解释死結和资源耗尽。
哲学家就餐问题(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
以上所述就是小编给大家介绍的《【Android多线程】哲学家就餐问题》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
你不知道的JavaScript(中卷)
[美] Kyle Simpson / 单业、姜南 / 人民邮电出版社 / 2016-8 / 79.00元
JavaScript这门语言简单易用,很容易上手,但其语言机制复杂微妙,即使是经验丰富的JavaScript开发人员,如果没有认真学习的话也无法真正理解。本套书直面当前JavaScript开发人员不求甚解的大趋势,深入理解语言内部的机制,全面介绍了JavaScript中常被人误解和忽视的重要知识点。本书是其中卷,主要介绍了类型、语法、异步和性能。一起来看看 《你不知道的JavaScript(中卷)》 这本书的介绍吧!