转载整理自
哲学家就餐问题
哲学家进餐-多线程同步经典问题
死锁的必要条件
死锁的四个必要条件：
（1） 互斥条件：一个资源每次只能被一个进程使用。
（2） 请求并保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
（3） 不可剥夺条件: 进程已获得的资源，在末使用完之前，不能强行剥夺。
（4） 循环等待条件: 若干进程之间形成一种头尾相接的循环等待资源关系
先写一个会造成死锁的哲学家问题。当所有哲学家同时决定进餐，拿起左边筷子时候，就发生了死锁。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| public class Test {
public static void main(String[] args) {
ExecutorService exec = Executors.newCachedThreadPool();
int sum = 5;
Chopstick[] chopsticks = new Chopstick[sum];
for (int i = 0; i < sum; i++) {
chopsticks[i] = new Chopstick();
}
for (int i = 0; i < sum; i++) {
exec.execute(new Philosopher(chopsticks[i], chopsticks[(i + 1) % sum], i));
}
}
}
class Chopstick {
public Chopstick() {
}
}
class Philosopher implements Runnable {
private Chopstick left;
private Chopstick right;
int name;
public Philosopher(Chopstick left, Chopstick right, int name) {
this.left = left;
this.right = right;
this.name = name;
}
@Override
public void run() {
try {
while (true) {
Thread.sleep(1000);
synchronized (left) {
Thread.sleep(500);
System.out.println(name + " get left");
synchronized (right) {
System.out.println(name + " eat");
Thread.sleep(1000);
}
}
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
|
破坏死锁的循环等待条件
解决方案一：破坏死锁的循环等待条件。
不再按左手右手顺序拿起筷子。选择一个固定的全局顺序获取，此处给筷子添加id，根据id先获取小的再获取大的，(不用关心编号的具体规则，只要保证编号全局唯一并且可排序)，不会出现死锁情况。
该方法适合获取锁的代码写的比较集中的情况，有利于维护这个全局顺序；若规模较大的程序，使用锁的地方比较零散，各处都遵守这个顺序就变得不太实际。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| public class Test {
public static void main(String[] args) {
ExecutorService exec = Executors.newCachedThreadPool();
int sum = 5;
Chopstick[] chopsticks = new Chopstick[sum];
for (int i = 0; i < sum; i++) {
chopsticks[i] = new Chopstick(i);
}
for (int i = 0; i < sum; i++) {
exec.execute(new Philosopher(chopsticks[i], chopsticks[(i + 1) % sum], i));
}
}
}
class Chopstick {
int id;
public Chopstick(int id) {
this.id = id;
}
}
class Philosopher implements Runnable {
private Chopstick left;
private Chopstick right;
int name;
public Philosopher(Chopstick left, Chopstick right, int name) {
this.left = left.id < right.id ? left : right;
this.right = left.id > right.id ? left : right;
this.name = name;
}
@Override
public void run() {
try {
while (true) {
Thread.sleep(1000);
synchronized (left) {
System.out.println(name + " get left");
synchronized (right) {
System.out.println(name + " eat");
Thread.sleep(1000);
}
}
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
|
破坏死锁的请求与保持条件
方法二：破坏死锁的请求与保持条件，使用lock的特性，为获取锁操作设置超时时间,当一段时间获取不到所有的资源时,就释放已获得的资源,重新开始请求资源。这样不会死锁（至少不会一直死锁）
该方法避免了无尽地死锁，但也不是很好的方案，因为该方案并不能避免死锁，它只是提供了从死锁中恢复的手段，并且受到活锁现象的影响，如果所有死锁线程同时超时，它们极有可能再次陷入死锁，虽然死锁没有永远持续下去，但对资源的争夺状态却没有得到任何改善（为每个线程设置不同的超时时间可以稍好的处理这种情况）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| public class Test {
public static void main(String[] args) {
ExecutorService exec = Executors.newCachedThreadPool();
int sum = 50;
Chopstick[] chopsticks = new Chopstick[sum];
for (int i = 0; i < sum; i++) {
chopsticks[i] = new Chopstick();
}
for (int i = 0; i < sum; i++) {
exec.execute(new Philosopher(chopsticks[i], chopsticks[(i + 1) % sum], i));
}
}
}
class Chopstick extends ReentrantLock {
}
class Philosopher implements Runnable {
private ReentrantLock left, right;
int name;
public Philosopher(ReentrantLock left, ReentrantLock right, int name) {
this.left = left;
this.right = right;
this.name = name;
}
@Override
public void run() {
try {
while (true) {
Thread.sleep(1000);
left.lock();
System.out.println(name + " get left");
try {
if (right.tryLock(1000, TimeUnit.MILLISECONDS)) {
try {
System.out.println(name + " eat");
Thread.sleep(1000);
} finally {
right.unlock();
}
} else {
System.out.println(name + " has not get right chopstick,give up");
}
} finally {
left.unlock();
}
}
} catch (InterruptedException e) {
}
}
}
|
使用条件变量Condition
方法三：设置一个条件变量与锁关联。该方法只用一把锁，没有Chopstick类，将竞争从对筷子的争夺转换成了对状态的判断。仅当左右邻座都没有进餐时才可以进餐。提升了并发度。前面的方法出现情况是：只有一个哲学家进餐，其他人持有一根筷子在等待另外一根。这个方案中，当一个哲学家理论上可以进餐（邻座没有进餐）时，他就开始进餐。
思路是只使用一把锁，将竞争从对筷子的争夺转换成了对状态的判断，仅当哲学家的左右邻座都没有进餐时，才可以进餐。当一个哲学家饥饿时，首先锁住餐桌table，这样其他哲学家无法改变table状态，然后查看左右邻居是否正在进餐，如果没有，那么该哲学家开始进餐并解锁餐桌，否则调用await()以暂时解锁餐桌,等待条件满足后,再次尝试锁住餐桌table后开始进餐；当一个哲学家进餐结束并开始思考时，首先锁住餐桌将eating改为false，然后通知左右邻座可以进餐，最后解锁餐桌。如果他的左右邻居目前正在等待，那么他们将被唤醒，重新锁住餐桌，并判断是否开始进餐。
通过多次newCondition()可以获得多个Condition对象,可以通过await(),signal()等方法实现比较复杂的线程同步的功能。在这个解决方法中，当一个哲学家理论上可以进餐时，肯定就可以进餐，并发度显著提升。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| public class Test {
public static void main(String[] args) {
ExecutorService exec = Executors.newCachedThreadPool();
int sum = 5;
Philosopher[] philosophers = new Philosopher[sum];
ReentrantLock table = new ReentrantLock();
for (int i = 0; i < sum; i++) {
philosophers[i] = new Philosopher(table, i);
}
for (int i = 0; i < sum; i++) {
philosophers[i].setLeft(philosophers[(i - 1 + sum) % sum]);
philosophers[i].setRight(philosophers[(i + 1) % sum]);
}
for (int i = 0; i < sum; i++) {
exec.execute(philosophers[i]);
}
}
}
class Philosopher extends Thread {
private boolean eating;
private Philosopher left;
private Philosopher right;
private ReentrantLock table;
private Condition condition;
int name;
public Philosopher(ReentrantLock table, int name) {
eating = false;
this.table = table;
condition = table.newCondition();
this.name = name;
}
public void setLeft(Philosopher left) {
this.left = left;
}
public void setRight(Philosopher right) {
this.right = right;
}
public void think() throws InterruptedException {
table.lock();
try {
eating = false;
System.out.println(name + " 开始思考");
left.condition.signal();
right.condition.signal();
} finally {
table.unlock();
}
Thread.sleep(1000);
}
public void eat() throws InterruptedException {
table.lock();
try {
while (left.eating || right.eating)
condition.await();
System.out.println(name + " 开始吃饭");
eating = true;
} finally {
table.unlock();
}
Thread.sleep(1000);
}
public void run() {
try {
while (true) {
think();
eat();
}
} catch (InterruptedException e) {
}
}
}
|
总结
通过这一经典的问题，学习多线程并发模型的三种解决方案：
- 多把锁时，对锁设置全局唯一的顺序，按序使用锁；(破坏循环等待条件)
- 设置线程获取锁的超时时间，防止无限制的死锁；(破坏请求与保持条件)
- 使用条件变量
1
2
3
4
5
6
7
8
9
10
| ReentrantLock lock = new ReentrantLock();
Condition Condition = lock.newCondition();
lock.lock();
try {
while(!《条件为真》)
condition.await();
《使用共享资源》
} finally {
lock.unlock();
}
|
一个条件变量需要与一把锁关联，线程在开始等待条件之前必须获取这把锁，获取锁后，线程检查所等待的条件是否已经为真，如果为真，线程将继续执行, 执行完毕后并解锁。条件变量的方法会使哲学家进餐问题的并发度显著提升。