[LeetCode] 1226. 哲学家进餐(Medium)Java语言题解

1.题目相关

①题目及示例

Alt text
Alt text

②相关标签

  • 多线程

③题目地址


2.解题方法

  • 哲学家进餐问题有死锁和资源耗尽的风险:每个哲学家同时拿着左边的筷子,永远都在等右边的筷子。
  • 所以本题的重点在于如何避免死锁,我们采用两种常用的解决方法:
    1. 改变一个哲学家拿叉子的顺序
    2. 餐票策略

①synchronized 关键字 + 改变一个哲学家拿叉子的顺序

  • 改变一个哲学家拿叉子的顺序:要想发生死锁,必须所有人同时拿起左边的筷子,但是如果这时有一个哲学家先拿右边再拿左边,就不会发生死锁。即避免发生环路,属于避免策略。
  • 使用 synchronized 关键字对拿起的筷子加锁

②lock + 改变一个哲学家拿叉子的顺序

  • 改变一个哲学家拿叉子的顺序:要想发生死锁,必须所有人同时拿起左边的筷子,但是如果这时有一个哲学家先拿右边再拿左边,就不会发生死锁。即避免发生环路,属于避免策略。
  • 使用 lock 对拿起的筷子加锁

③synchronized 关键字 + 信号量 + 餐票策略

  • 餐票策略:要求必须拿到餐票才能吃饭,而我们为了避免死锁,总共只发三张餐票,这样可以避免五个人同时准备吃饭的情况,也属于避免策略。
  • 使用 synchronized 关键字对拿起的筷子加锁
  • 使用信号量模拟餐票

④lock + 信号量 + 餐票策略

  • 餐票策略:要求必须拿到餐票才能吃饭,而我们为了避免死锁,总共只发三张餐票,这样可以避免五个人同时准备吃饭的情况,也属于避免策略。
  • 使用 lock 对拿起的筷子加锁
  • 使用信号量模拟餐票

3.代码详解

①synchronized 关键字 + 改变一个哲学家拿叉子的顺序

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
// 1.synchronized+改变一个哲学家拿叉子的顺序来避免死锁
class DiningPhilosophers {
private Object[] locks = new Object[5];

public DiningPhilosophers() {
for (int i = 0; i < 5; i++) {
locks[i] = new Object();
}
}

public void wantsToEat(int philosopher,
Runnable pickLeftFork,
Runnable pickRightFork,
Runnable eat,
Runnable putLeftFork,
Runnable putRightFork) throws InterruptedException {
// 改变0号哲学家拿叉子的顺序
int leftForkNumber = philosopher == 0? (philosopher + 1) % 5: philosopher;
int rightForkNumber = philosopher == 0? philosopher: (philosopher + 1) % 5;
synchronized (locks[leftForkNumber]) {
synchronized (locks[rightForkNumber]) {
pickLeftFork.run();
pickRightFork.run();
eat.run();
putLeftFork.run();
putRightFork.run();
}
}
}
}

②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
// 2.lock+改变一个哲学家拿叉子的顺序来避免死锁
class DiningPhilosophers {
private Lock[] locks = {new ReentrantLock(), new ReentrantLock(), new ReentrantLock(), new ReentrantLock(), new ReentrantLock()};

public DiningPhilosophers() {
}

public void wantsToEat(int philosopher,
Runnable pickLeftFork,
Runnable pickRightFork,
Runnable eat,
Runnable putLeftFork,
Runnable putRightFork) throws InterruptedException {
// 改变0号哲学家拿叉子的顺序
int leftForkNumber = philosopher == 0? (philosopher + 1) % 5: philosopher;
int rightForkNumber = philosopher == 0? philosopher: (philosopher + 1) % 5;
locks[leftForkNumber].lock();
locks[rightForkNumber].lock();
pickLeftFork.run();
pickRightFork.run();
eat.run();
putLeftFork.run();
putRightFork.run();
locks[rightForkNumber].unlock();
locks[leftForkNumber].unlock();
}
}

③synchronized 关键字 + 信号量 + 餐票策略

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
// 3.synchronized+信号量+餐票策略来避免死锁
class DiningPhilosophers {
private Object[] locks = new Object[5];
private Semaphore limit = new Semaphore(3);

public DiningPhilosophers() {
for (int i = 0; i < 5; i++) {
locks[i] = new Object();
}
}

public void wantsToEat(int philosopher,
Runnable pickLeftFork,
Runnable pickRightFork,
Runnable eat,
Runnable putLeftFork,
Runnable putRightFork) throws InterruptedException {
int leftForkNumber = philosopher;
int rightForkNumber = (philosopher + 1) % 5;
// 规定最多有三个哲学家同时拿起叉子
limit.acquire();
synchronized (locks[leftForkNumber]) {
synchronized (locks[rightForkNumber]) {
pickLeftFork.run();
pickRightFork.run();
eat.run();
putLeftFork.run();
putRightFork.run();
}
}
limit.release();
}
}

④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
// 4.lock+信号量+餐票策略来避免死锁
class DiningPhilosophers {
private Lock[] locks = {new ReentrantLock(), new ReentrantLock(), new ReentrantLock(), new ReentrantLock(), new ReentrantLock()};
private Semaphore limit = new Semaphore(3);

public DiningPhilosophers() {
}

public void wantsToEat(int philosopher,
Runnable pickLeftFork,
Runnable pickRightFork,
Runnable eat,
Runnable putLeftFork,
Runnable putRightFork) throws InterruptedException {
int leftForkNumber = philosopher;
int rightForkNumber = (philosopher + 1) % 5;
// 规定最多有三个哲学家同时拿起叉子
limit.acquire();
locks[leftForkNumber].lock();
locks[rightForkNumber].lock();
pickLeftFork.run();
pickRightFork.run();
eat.run();
putLeftFork.run();
putRightFork.run();
locks[rightForkNumber].unlock();
locks[leftForkNumber].unlock();
limit.release();
}
}

附录

0%