哲学家就餐问题

问题描述

哲学家就餐问题(Dining philosophers problem)是在计算机科学中的一个经典问题,用来演示在并发计算中多线程同步(Synchronization)时产生的问题。

在1971年,著名的计算机科学家Edsger Wybe Dijkstra(艾兹格·迪科斯彻)提出了一个同步问题,即假设有五台计算机都试图访问五份共享的磁带驱动器。稍后,这个问题被托尼·霍尔重新表述为哲学家就餐问题。这个问题可以用来解释死锁和资源耗尽。

专门在Github搞了个Repo写课程代码

哲学家就餐问题可以这样表述,假设有五位哲学家围坐在一张圆形餐桌旁,做以下两件事情之一:吃饭,或者思考。吃东西的时候,他们就停止思考,思考的时候也停止吃东西。餐桌中间有一大碗意大利面,每两个哲学家之间有一只餐叉。因为用一只餐叉很难吃到意大利面,所以假设哲学家必须用两只餐叉吃东西。他们只能使用自己左右手边的那两只餐叉。哲学家就餐问题有时也用米饭和筷子而不是意大利面和餐叉来描述,因为很明显,吃米饭必须用两根筷子。

哲学家从来不交谈,这就很危险,可能产生死锁,每个哲学家都拿着左手的餐叉,永远都在等右边的餐叉(或者相反)。

即使没有死锁,也有可能发生资源耗尽。例如,假设规定当哲学家等待另一只餐叉超过五分钟后就放下自己手里的那一只餐叉,并且再等五分钟后进行下一次尝试。这个策略消除了死锁(系统总会进入到下一个状态),但仍然有可能发生“活锁”。如果五位哲学家在完全相同的时刻进入餐厅,并同时拿起左边的餐叉,那么这些哲学家就会等待五分钟,同时放下手中的餐叉,再等五分钟,又同时拿起这些餐叉。

解决办法

一、只有当哲学接的左右两只筷子均处于可用状态时,才允许他拿起筷子。这样就可以避免他们同时拿起筷子就餐,导致死锁。

实现代码

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
80
81
82
83
84
85
86
87
class Philosopher extends Thread
{
private int thinkingtimes = 0;
private int eatingtimes = 0;
int id;
static int currentid = 0;
private Forks fork;
public Philosopher(Forks fork)
{
super();
id = currentid;
currentid++;
this.fork = fork;
}
public void run()
{
while(true)
{
thinking();
fork.takeFork();
eating();
fork.putFork();
}
}
private void thinking()
{
thinkingtimes++;
System.out.println("Philosopher " + id + " : thinking start! Times : " + thinkingtimes);
try {
sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
private void eating()
{
eatingtimes++;
System.out.println("Philosopher " + id + " : eating start! Times : " + eatingtimes);
try {
sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}

class Forks
{
private boolean[] used = {false, false, false, false, false};
public synchronized void takeFork()
{
Philosopher p = (Philosopher) Thread.currentThread();
int id = p.id;
while(used[id] || used[(id + 1) % 5])
{
try {
wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
System.out.println("Philosopher " + id + " : takeFork!");
used[id] = true;
used[(id + 1) % 5] = true;
}
public synchronized void putFork()
{
Philosopher p = (Philosopher) Thread.currentThread();
int id = p.id;
System.out.println("Philosopher " + id + " : putFork!");
used[id] = false;
used[(id + 1) % 5] = false;
notifyAll();
}
}

public class DiningPhilosophers {
public static void main(String[] args)
{
Forks f = new Forks();
new Philosopher(f).start();
new Philosopher(f).start();
new Philosopher(f).start();
new Philosopher(f).start();
new Philosopher(f).start();
}
}

二、最多允许4个哲学家同时坐在桌子周围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
semaphore fork[5] = {1};
semaphore room = {4};
int i; void philosopher (int i) {
while (true) {
think();
P (room);
P (fork[i]);
P (fork [(i + 1) mod 5]);
eat();
V (fork [(i + 1) mod 5]);
V (fork[i]);
V (room);
}
} void main() {
parbegin ( philosopher (0), philosopher (1),
philosopher (2), philosopher(3), philosopher (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
void philosopher[k=0 to 4]
/* the five philosopher clients */
{
while (true) {
<think>;
get_forks(k);
/* client requests two forks via monitor */
<eat spaghetti>;
release_forks(k);
/* client releases forks via the monitor */
}
}

monitor dining_controller;
cond ForkReady[5];
boolean fork[5] = {true};
void get_forks(int pid) {
int left = pid;
int right = (++pid) % 5;
/*grant the left fork*/
if (!fork(left)
cwait(ForkReady[left]);
/* queue on condition variable */
fork(left) = false;
/*grant the right fork*/
if (!fork(right)
cwait(ForkReady(right);
/* queue on condition variable */
fork(right) = false:
}

void release_forks(int pid) {
int left = pid;
int right = (++pid) % 5;
/*release the left fork*/
if (empty(ForkReady[left])
/*no one is waiting for this fork */
fork(left) = true;
else /* awaken a process waiting on this fork */
csignal(ForkReady[left]);
/*release the right fork*/
if (empty(ForkReady[right])
/*no one is waiting for this fork */
fork(right) = true;
else /* awaken a process waiting on this fork */
csignal(ForkReady[right]);
}

四、其他解法:服务生解法 资源分级解法 Chandy/Misra解法

文章目录
  1. 1. 问题描述
  2. 2. 解决办法
    1. 2.1. 实现代码
|