多线程之死锁，哲学家就餐问题的实现

1.死锁是什么

死锁是这样一种情形：多个线程同时被阻塞，它们中的一个或者全部都在等待某个资源被释放。由于线程被无限期地阻塞，因此程序不可能正常终止。

2.哲学家就餐问题

有五个哲学家，他们的生活方式是交替地进行思考和进餐。他们共用一张圆桌，分别坐在五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐完毕，放下筷子又继续思考。

 

为了进一步阐述死锁的形成, 很多资料上也会谈论到 "哲学家就餐问题".

解决办法一，哲学家要进餐时，要么同时拿起两支筷子，要么一支筷子都不拿．

package thread4;import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;//解决办法一，哲学家要进餐时，要么同时拿起两支筷子，要么一支筷子都不拿．
class Philosopher {//哲学家编号public int id;public Philosopher(int id) {this.id = id;}//思考public void thinking() throws InterruptedException {System.out.println("我是哲学家" + this.id + "号，我正在思考！");Thread.sleep(1000);}//吃饭public void eating() throws InterruptedException {System.out.println("我是哲学家" + this.id + "号，我正在吃饭！");Thread.sleep(1000);}//拿筷子public void takeUp(Chopsticks chopsticksLeft, Chopsticks chopsticksRight) throws InterruptedException {synchronized (Test3.locker) {if (chopsticksLeft.used || chopsticksRight.used) {Test3.locker.wait();}}chopsticksLeft.used = true;chopsticksRight.used = true;System.out.println("我是哲学家" + this.id + "号，我拿到俩只筷子！");}//放筷子public void putDown(Chopsticks chopsticksLeft, Chopsticks chopsticksRight) {synchronized (Test3.locker) {chopsticksLeft.used = false;chopsticksRight.used = false;System.out.println("我是哲学家" + this.id + "号，我吃完了！");Test3.locker.notify();}}
}//筷子
class Chopsticks {//筷子编号public int id;//筷子状态public boolean used;public Chopsticks(int id, boolean used) {this.id = id;this.used = used;}
}public class Test3 {public static Object locker = new Object();public static void main(String[] args) {Philosopher philosopher1 = new Philosopher(1);Philosopher philosopher2 = new Philosopher(2);Philosopher philosopher3 = new Philosopher(3);Philosopher philosopher4 = new Philosopher(4);Philosopher philosopher5 = new Philosopher(5);Chopsticks chopsticks1 = new Chopsticks(1, false);Chopsticks chopsticks2 = new Chopsticks(2, false);Chopsticks chopsticks3 = new Chopsticks(3, false);Chopsticks chopsticks4 = new Chopsticks(4, false);Chopsticks chopsticks5 = new Chopsticks(5, false);ExecutorService pool = Executors.newFixedThreadPool(5);pool.submit(new Runnable() {@Overridepublic void run() {try {philosopher1.thinking();philosopher1.takeUp(chopsticks1, chopsticks2);philosopher1.eating();philosopher1.putDown(chopsticks1, chopsticks2);} catch (InterruptedException e) {throw new RuntimeException(e);}}});pool.submit(new Runnable() {@Overridepublic void run() {try {philosopher2.thinking();philosopher2.takeUp(chopsticks2, chopsticks3);philosopher2.eating();philosopher2.putDown(chopsticks2, chopsticks3);} catch (InterruptedException e) {throw new RuntimeException(e);}}});pool.submit(new Runnable() {@Overridepublic void run() {try {philosopher3.thinking();philosopher3.takeUp(chopsticks3, chopsticks4);philosopher3.eating();philosopher3.putDown(chopsticks3, chopsticks4);} catch (InterruptedException e) {throw new RuntimeException(e);}}});pool.submit(new Runnable() {@Overridepublic void run() {try {philosopher4.thinking();philosopher4.takeUp(chopsticks4, chopsticks5);philosopher4.eating();philosopher4.putDown(chopsticks4, chopsticks5);} catch (InterruptedException e) {throw new RuntimeException(e);}}});pool.submit(new Runnable() {@Overridepublic void run() {try {philosopher5.thinking();philosopher5.takeUp(chopsticks5, chopsticks1);philosopher5.eating();philosopher5.putDown(chopsticks5, chopsticks1);} catch (InterruptedException e) {throw new RuntimeException(e);}}});pool.shutdown();}
}

解决办法二，给筷子编号，哲学家将要进餐时，要先从小号（左边）的开始拿．

package thread4;import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;class Philosopher {//哲学家编号public int id;public Philosopher(int id) {this.id = id;}//思考public void thinking() throws InterruptedException {System.out.println("我是哲学家" + this.id + "号，我正在思考！");Thread.sleep(1000);}//吃饭public void eating() throws InterruptedException {System.out.println("我是哲学家" + this.id + "号，我正在吃饭！");Thread.sleep(1000);}//拿筷子public void takeUp(Chopsticks chopsticksMin, Chopsticks chopsticksMax) throws InterruptedException {synchronized (Test4.locker) {//先尝试拿小号筷子，失败则进入等待状态，并释放锁if (!chopsticksMin.used) {//false能拿，true不能拿别人占用的了所以 是!chopsticksMin.usedchopsticksMin.used = true;if (!chopsticksMax.used) {chopsticksMax.used = true;} else {Test4.locker.wait();}} else {Test4.locker.wait();}}}//放筷子public void putDown(Chopsticks chopsticksMin, Chopsticks chopsticksMax) {synchronized (Test4.locker) {chopsticksMin.used = false;chopsticksMax.used = false;System.out.println("我是哲学家" + this.id + "号，我吃完了！");Test4.locker.notify();}}
}//筷子
class Chopsticks {//筷子编号public int id;//筷子状态public boolean used;public Chopsticks(int id, boolean used) {this.id = id;this.used = used;}
}public class Test4 {public static Object locker = new Object();public static void main(String[] args) {Philosopher philosopher1 = new Philosopher(1);Philosopher philosopher2 = new Philosopher(2);Philosopher philosopher3 = new Philosopher(3);Philosopher philosopher4 = new Philosopher(4);Philosopher philosopher5 = new Philosopher(5);Chopsticks chopsticks1 = new Chopsticks(1, false);Chopsticks chopsticks2 = new Chopsticks(2, false);Chopsticks chopsticks3 = new Chopsticks(3, false);Chopsticks chopsticks4 = new Chopsticks(4, false);Chopsticks chopsticks5 = new Chopsticks(5, false);ExecutorService pool = Executors.newFixedThreadPool(5);pool.submit(new Runnable() {@Overridepublic void run() {try {philosopher1.thinking();philosopher1.takeUp(chopsticks1, chopsticks2);philosopher1.eating();philosopher1.putDown(chopsticks1, chopsticks2);} catch (InterruptedException e) {throw new RuntimeException(e);}}});pool.submit(new Runnable() {@Overridepublic void run() {try {philosopher2.thinking();philosopher2.takeUp(chopsticks2, chopsticks3);philosopher2.eating();philosopher2.putDown(chopsticks2, chopsticks3);} catch (InterruptedException e) {throw new RuntimeException(e);}}});pool.submit(new Runnable() {@Overridepublic void run() {try {philosopher3.thinking();philosopher3.takeUp(chopsticks3, chopsticks4);philosopher3.eating();philosopher3.putDown(chopsticks3, chopsticks4);} catch (InterruptedException e) {throw new RuntimeException(e);}}});pool.submit(new Runnable() {@Overridepublic void run() {try {philosopher4.thinking();philosopher4.takeUp(chopsticks4, chopsticks5);philosopher4.eating();philosopher4.putDown(chopsticks4, chopsticks5);} catch (InterruptedException e) {throw new RuntimeException(e);}}});pool.submit(new Runnable() {@Overridepublic void run() {try {philosopher5.thinking();philosopher5.takeUp(chopsticks5, chopsticks1);philosopher5.eating();philosopher5.putDown(chopsticks5, chopsticks1);} catch (InterruptedException e) {throw new RuntimeException(e);}}});pool.shutdown();}
}

3.如何避免死锁

死锁产生的四个必要条件

• 互斥使用，即当资源被一个线程使用(占有)时，别的线程不能使用
• 不可抢占，资源请求者不能强制从资源占有者手中夺取资源，资源只能由资源占有者主动释放。
• 请求和保持，即当资源请求者在请求其他的资源的同时保持对原有资源的占有。
• 循环等待，即存在一个等待队列：P1占有P2的资源，P2占有P3的资源，P3占有P1的资源。这样就形成了一个等待环路

当上述四个条件都成立的时候，便形成死锁。当然，死锁的情况下如果打破上述任何一个条件，便可让死锁消失。其中最容易破坏的就是 "循环等待".

破坏循环等待

最常用的一种死锁阻止技术就是锁排序. 假设有 N 个线程尝试获取 M 把锁, 就可以针对 M 把锁进行编号(1, 2, 3...M).N 个线程尝试获取锁的时候, 都按照固定的按编号由小到大顺序来获取锁. 这样就可以避免环路等待.

属于理论上的破除死锁的方法.但是这样的方法,并不实用.
更实用的方法,就是尽量避免锁嵌套.(不要在一个加锁的代码中,再去加其他锁...)

可能产生环路等待的代码:

package thread4;public class Test2 {public static void main(String[] args) {Object locker1 = new Object();Object locker2 = new Object();Thread thread1 = new Thread() {@Overridepublic void run() {synchronized (locker1) {synchronized (locker2) {}}}};thread1.start();Thread thread2 = new Thread() {@Overridepublic void run() {synchronized (locker2) {synchronized (locker1) {}}}};thread2.start();}
}

约定好先获取 lock1, 再获取 lock2 , 就不会环路等待（锁排序）

package thread4;public class Test2 {public static void main(String[] args) {Object locker1 = new Object();Object locker2 = new Object();Thread thread1 = new Thread() {@Overridepublic void run() {synchronized (locker1) {synchronized (locker2) {}}}};thread1.start();Thread thread2 = new Thread() {@Overridepublic void run() {synchronized (locker1) {synchronized (locker2) {}}}};thread2.start();}
}