内容简介：在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多线程】哲学家就餐问题》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Linux集群体系结构
Alex Vrenios / 马朝晖 / 机械工业出版社 / 2003-1 / 38.00元
本书对Linux集群体系结构的硬件环境组建与其软件开发作了深入细致的介绍。通过阅读本书，可以对Linux集群体系结构有深入的认识，掌握并了解如何设计和构造集群计算机。本书使你了解到开发项目可能遇到的问题，并掌握测试和调整分布式算法。 本书适合计算机系统集成技术人员、管理人员和计算机科研人员作为参考。一起来看看 《Linux集群体系结构》 这本书的介绍吧!
