哲学家就餐问题的问题解法

一个简单的解法是引入一个餐厅服务生，哲学家必须经过他的允许才能拿起餐叉。因为服务生知道哪只餐叉正在使用，所以他能够作出判断避免死锁。

为了演示这种解法，假设哲学家依次标号为A至E。如果A和C在吃东西，则有四只餐叉在使用中。B坐在A和C之间，所以两只餐叉都无法使用，而D和E之间有一只空余的餐叉。假设这时D想要吃东西。如果他拿起了第五只餐叉，就有可能发生死锁。相反，如果他征求服务生同意，服务生会让他等待。这样，我们就能保证下次当两把餐叉空余出来时，一定有一位哲学家可以成功的得到一对餐叉，从而避免了死锁。 另一个简单的解法是为资源（这里是餐叉）分配一个偏序或者分级的关系，并约定所有资源都按照这种顺序获取，按相反顺序释放，而且保证不会有两个无关资源同时被同一项工作所需要。在哲学家就餐问题中，资源（餐叉）按照某种规则编号为1至5，每一个工作单元（哲学家）总是先拿起左右两边编号较低的餐叉，再拿编号较高的。用完餐叉后，他总是先放下编号较高的餐叉，再放下编号较低的。在这种情况下，当四位哲学家同时拿起他们手边编号较低的餐叉时，只有编号最高的餐叉留在桌上，从而第五位哲学家就不能使用任何一只餐叉了。而且，只有一位哲学家能使用最高编号的餐叉，所以他能使用两只餐叉用餐。当他吃完后，他会先放下编号最高的餐叉，再放下编号较低的餐叉，从而让另一位哲学家拿起后边的这只开始吃东西。

尽管资源分级能避免死锁，但这种策略并不总是实用的，特别是当所需资源的列表并不是事先知道的时候。例如，假设一个工作单元拿着资源3和5，并决定需要资源2，则必须先要释放5，之后释放3，才能得到2，之后必须重新按顺序获取3和5。对需要访问大量数据库记录的计算机程序来说，如果需要先释放高编号的记录才能访问新的记录，那么运行效率就不会高，因此这种方法在这里并不实用。

这种方法经常是实际计算机科学问题中最实用的解法，通过为分级锁指定常量，强制获得锁的顺序，就可以解决这个问题。 1984年，K. Mani Chandy和J. Misra提出了哲学家就餐问题的另一个解法，允许任意的用户（编号P1, ..., Pn）争用任意数量的资源。与迪科斯彻的解法不同的是，这里编号可以是任意的。

1.对每一对竞争一个资源的哲学家，新拿一个餐叉，给编号较低的哲学家。每只餐叉都是“干净的”或者“脏的”。最初，所有的餐叉都是脏的。

2.当一位哲学家要使用资源（也就是要吃东西）时，他必须从与他竞争的邻居那里得到。对每只他当前没有的餐叉，他都发送一个请求。

3.当拥有餐叉的哲学家收到请求时，如果餐叉是干净的，那么他继续留着，否则就擦干净并交出餐叉。

4.当某个哲学家吃东西后，他的餐叉就变脏了。如果另一个哲学家之前请求过其中的餐叉，那他就擦干净并交出餐叉。

这个解法允许很大的并行性，适用于任意大的问题。

*** 作系统并发和互斥：哲学家进餐问题和理发师问题

1． 哲学家进餐问题：

(1) 在什么情况下5 个哲学家全部吃不上饭？

考虑两种实现的方式，如下：

A.

算法描述：

void philosopher(int i) /*i：哲学家编号，从0 到4*/

{

while (TRUE) {

think( )/*哲学家正在思考*/

take_fork(i)/*取左侧的筷子*/

take_fork((i+1) % N)/*取左侧筷子；％为取模运算*/

eat( )/*吃饭*/

put_fork(i)/*把左侧筷子放回桌子*/

put_fork((i+1) % N)/*把右侧筷子放回桌子*/

}

}

分析：假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，又都放下左侧筷子，

等一会儿，又同时拿起左侧筷子，如此这般，永远重复。对于这种情况，即所有的程序都在

无限期地运行，但是都无法取得任何进展，即出现饥饿，所有哲学家都吃不上饭。

B．

算法描述：

规定在拿到左侧的筷子后，先检查右面的筷子是否可用。如果不可用，则先放下左侧筷子，

等一段时间再重复整个过程。

分析：当出现以下情形，在某一个瞬间，所有的哲学家都同时启动这个算法，拿起左侧的筷

子，而看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子……如此

这样永远重复下去。对于这种情况，所有的程序都在运行，但却无法取得进展，即出现饥饿，

所有的哲学家都吃不上饭。

(2) 描述一种没有人饿死（永远拿不到筷子）算法。

考虑了四种实现的方式（A、B、C、D）：

A．原理：至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释

放出他所使用过的两支筷子,从而可使更多的哲学家进餐。以下将room 作为信号量，只允

许4 个哲学家同时进入餐厅就餐，这样就能保证至少有一个哲学家可以就餐，而申请进入

餐厅的哲学家进入room 的等待队列，根据FIFO 的原则，总会进入到餐厅就餐，因此不会

出现饿死和死锁的现象。

伪码：

semaphore chopstick[5]={1，1，1，1，1}

semaphore room=4

void philosopher(int i)

{

while(true)

{

think()

wait(room)//请求进入房间进餐

wait(chopstick[i])//请求左手边的筷子

wait(chopstick[(i+1)%5])//请求右手边的筷子

eat()

signal(chopstick[(i+1)%5])//释放右手边的筷子

signal(chopstick[i])//释放左手边的筷子

signal(room)//退出房间释放信号量room

}

}

B．原理：仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。

方法1：利用AND 型信号量机制实现：根据课程讲述，在一个原语中，将一段代码同时需

要的多个临界资源，要么全部分配给它，要么一个都不分配，因此不会出现死锁的情形。当

某些资源不够时阻塞调用进程由于等待队列的存在，使得对资源的请求满足FIFO 的要求，

因此不会出现饥饿的情形。

伪码：

semaphore chopstick[5]={1，1，1，1，1}

void philosopher(int I)

{

while(true)

{

think()

Swait(chopstick[(I+1)]%5,chopstick[I])

eat()

Ssignal(chopstick[(I+1)]%5,chopstick[I])

}

}

方法2：利用信号量的保护机制实现。通过信号量mutex对eat（）之前的取左侧和右侧筷

子的 *** 作进行保护，使之成为一个原子 *** 作，这样可以防止死锁的出现。

伪码：

semaphore mutex = 1

semaphore chopstick[5]={1，1，1，1，1}

void philosopher(int I)

{

while(true)

{

think()

wait(mutex)

wait(chopstick[(I+1)]%5)

wait(chopstick[I])

signal(mutex)

eat()

signal(chopstick[(I+1)]%5)

signal(chopstick[I])

}

}

C． 原理：规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子而偶数号

的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即

五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获

得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，根FIFO原则，则先申请的哲

学家会较先可以吃饭，因此不会出现饿死的哲学家。

伪码：

semaphore chopstick[5]={1，1，1，1，1}

void philosopher(int i)

{

while(true)

{

think()

if(i%2 == 0) //偶数哲学家，先右后左。

{

wait (chopstick[ i + 1 ] mod 5)

wait (chopstick[ i])

eat()

signal (chopstick[ i + 1 ] mod 5)

signal (chopstick[ i])

}

Else //奇数哲学家，先左后右。

{

wait (chopstick[ i])

wait (chopstick[ i + 1 ] mod 5)

eat()

signal (chopstick[ i])

signal (chopstick[ i + 1 ] mod 5)

}

}

D．利用管程机制实现（最终该实现是失败的，见以下分析）：

原理：不是对每只筷子设置信号量，而是对每个哲学家设置信号量。test()函数有以下作

用：

a. 如果当前处理的哲学家处于饥饿状态且两侧哲学家不在吃饭状态，则当前哲学家通过

test()函数试图进入吃饭状态。

b. 如果通过test()进入吃饭状态不成功，那么当前哲学家就在该信号量阻塞等待，直到

其他的哲学家进程通过test()将该哲学家的状态设置为EATING。

c. 当一个哲学家进程调用put_forks()放下筷子的时候，会通过test()测试它的邻居，

如果邻居处于饥饿状态，且该邻居的邻居不在吃饭状态，则该邻居进入吃饭状态。

由上所述,该算法不会出现死锁，因为一个哲学家只有在两个邻座都不在进餐时，才允

许转换到进餐状态。

该算法会出现某个哲学家适终无法吃饭的情况，即当该哲学家的左右两个哲学家交替

处在吃饭的状态的时候，则该哲学家始终无法进入吃饭的状态，因此不满足题目的要求。

但是该算法能够实现对于任意多位哲学家的情况都能获得最大的并行度，因此具有重要

的意义。

伪码：

#define N 5 /* 哲学家人数*/

#define LEFT (i-1+N)%N /* i的左邻号码 */

#define RIGHT (i+1)%N /* i的右邻号码 */

typedef enum { THINKING, HUNGRY, EATING } phil_state/*哲学家状态*/

monitor dp /*管程*/

{

phil_state state[N]

semaphore mutex =1

semaphore s[N]/*每个哲学家一个信号量，初始值为0*/

void test(int i)

{

if ( state[i] == HUNGRY &&state[LEFT(i)] != EATING &&

state[RIGHT(i)] != EATING )

{

state[i] = EATING

V(s[i])

}

}

void get_forks(int i)

{

P(mutex)

state[i] = HUNGRY

test(i)/*试图得到两支筷子*/

V(mutex)

P(s[i])/*得不到筷子则阻塞*/

}

void put_forks(int i)

{

P(mutex)

state[i]= THINKING

test(LEFT(i))/*看左邻是否进餐*/

test(RIGHT(i))/*看右邻是否进餐*/

V(mutex)

}

}

哲学家进程如下：

void philosopher(int process)

{

while(true)

{

think()

get_forks(process)

eat()

put_forks(process)

}

}

2.理发师问题：一个理发店有一个入口和一个出口。理发店内有一个可站5 位顾客的站席

区、4 个单人沙发、3 个理发师及其专用理发工具、一个收银台。新来的顾客坐在沙发上等

待；没有空沙发时，可在站席区等待；站席区满时，只能在入口外等待。理发师可从事理

发、收银和休息三种活动。理发店的活动满足下列条件：

1）休息的理发师是坐地自己专用的理发椅上，不会占用顾客的沙发；

2）处理休息状态的理发师可为在沙发上等待时间最长的顾客理发；

3）理发时间长短由理发师决定；

4）在站席区等待时间最长的顾客可坐到空闲的理发上；

5）任何时刻最多只能有一个理发师在收银。

试用信号量机制或管程机制实现理发师进程和顾客进程。

原理：

(1)customer 进程：

首先检查站席区是否已满（stand_capacity）,若满选择离开，否则进入站席区，即进入

理发店。在站席区等待沙发的空位（信号量sofa），如果沙发已满，则进入阻塞等待队列，

直到出现空位，在站席区中等待时间最长的顾客离开站席区（stand_capacity）。坐到沙

发上，等待理发椅(barber_chair)，如果理发椅已满，则进入阻塞等待队列，直到出现

空位，在沙发上等待时间最长的顾客离开沙发（释放信号量sofa）。坐到理发椅上，释放

准备好的信号（customer_ready），获得该理发师的编号（0~1 的数字）。等待理发师理

发结束（finished[barber_number]）。在离开理发椅之前付款（payment），等待收据

(receipt)，离开理发椅（leave_barberchair）。最后离开理发店。

这里需要注意几点：

a) 首先是几个需要进行互斥处理的地方，主要包括:进入站席区、进入沙发、进入理发椅

和付款几个地方。

b) 通过barber_chair 保证一个理发椅上最多只有一名顾客。但这也不够，因为单凭

baber_chair 无法保证一名顾客离开理发椅之前，另一位顾客不会坐到该理发椅上，

因此增加信号量leave_barberchair，让顾客离开理发椅后，释放该信号，而理发

师接收到该信号后才释放barber_chair 等待下一位顾客。

c) 在理发的过程中，需要保证是自己理发完毕，才能够进行下面的付款、离开理发椅的活

动。这个机制是通过customer 进程获得给他理发的理发师编号来实现的，这样，当

该编号的理发师释放对应的finished[i]信号的时候，该顾客才理发完毕。

d) 理发师是通过mutex 信号量保证他们每个人同时只进行一项 *** 作（理发或者收款）。

e) 为了保证该顾客理发完毕后马上可以付款离开，就应该保证给该顾客理发的理发师在理

发完毕后马上到收银台进入收款 *** 作而不是给下一位顾客服务。在伪码中由以下机制实

现：即顾客在释放离开理发椅的信号前，发出付款的信号。这样该理发师得不到顾客的

离开理发椅的信号，不能进入下一个循环为下一名顾客服务，而只能进入收款台的收款

*** 作。直到顾客接到收据后，才释放离开理发椅的信号，离开理发椅，让理发师释放该

理发椅的信号，让下一位等待的顾客坐到理发椅上。

(2)barber 进程

首先将该理发师的编号压入队列，供顾客提取。等待顾客坐到理发椅坐好(信号量

customer_ready)，开始理发，理发结束后释放结束信号（finished[i]）。等待顾客

离开理发椅（leave_barberchair）（期间去收银台进行收款活动），释放理发椅空闲信

号(barber_chair)，等待下一位顾客坐上来。

(3)cash（收银台）进程

等待顾客付款(payment),执行收款 *** 作，收款 *** 作结束，给付收据（receipt）。

信号量总表：

信号量 wait signal

stand_capacity 顾客等待进入理发店 顾客离开站席区

sofa 顾客等待坐到沙发 顾客离开沙发

barber_chair 顾客等待空理发椅 理发师释放空理发椅

customer_ready 理发师等待，直到一个顾客坐

到理发椅

顾客坐到理发椅上，给理发师

发出信号

mutex 等待理发师空闲，执行理发或

收款 *** 作

理发师执行理发或收款结束，

进入空闲状态

mutex1 执行入队或出队等待 入队或出队结束，释放信号

finished[i] 顾客等待对应编号理发师理

发结束

理发师理发结束，释放信号

leave_barberchair 理发师等待顾客离开理发椅 顾客付款完毕得到收据，离开

理发椅释放信号

payment 收银员等待顾客付款 顾客付款，发出信号

receipt 顾客等待收银员收、开具收据收银员收款结束、开具收据，

释放信号

伪码：

semaphore stand_capacity=5

semaphore sofa=4

semaphore barber_chair=3

semaphore customer_ready=0

semaphore mutex=3

semaphore mutex1=1

semaphore finished[3]={0,0,0}

semaphore leave_barberchair=0

semaphore payment=0

semaphore receipt=0

void customer()

{

int barber_number

wait(stand_capacity)//等待进入理发店

enter_room()//进入理发店

wait(sofa)//等待沙发

leave_stand_section()//离开站席区

signal(stand_capacity)

sit_on_sofa()//坐在沙发上

wait(barber_chair)//等待理发椅

get_up_sofa()//离开沙发

signal(sofa)

wait(mutex1)

sit_on_barberchair()//坐到理发椅上

signal(customer_ready)

barber_number=dequeue()//得到理发师编号

signal(mutex1)

wait(finished[barber_number])//等待理发结束

pay()//付款

signal(payment)//付款

wait(receipt)//等待收据

get_up_barberchair()//离开理发椅

signal(leave_barberchair)//发出离开理发椅信号

exit_shop()//了离开理发店

}

void barber(int i)

{

while(true)

{

wait(mutex1)

enqueue(i)//将该理发师的编号加入队列

signal(mutex1)

wait(customer_ready)//等待顾客准备好

wait(mutex)

cut_hair()//理发

signal(mutex)

signal(finished[i])//理发结束

wait(leave_barberchair)//等待顾客离开理发椅信号

signal(barber_chair)//释放barber_chair 信号

}

}

void cash() //收银

{

while(true)

{

wait(payment)//等待顾客付款

wait(mutex)//原子 *** 作

get_pay()//接受付款

give_receipt()//给顾客收据

signal(mutex)

signal(receipt)//收银完毕，释放信号

}

}

分析：

在分析该问题过程中，出现若干问题，是参阅相关资料后才认识到这些问题的隐蔽性和严重

性的,主要包括：

（1）在顾客进程，如果是在释放leave_barberchair 信号之后进行付款动作的话，很

容易造成没有收银员为其收款的情形， 原因是： 为该顾客理发的理发师收到

leave_barberchair 信号后，释放barber_chair 信号，另外一名顾客坐到理发椅上，

该理发师有可能为这另外一名顾客理发，而没有为刚理完发的顾客收款。为解决这个问题，

就是采取在释放leave_barberchair 信号之前，完成付款 *** 作。这样该理发师无法进入

下一轮循环为另外顾客服务，只能到收银台收款。

（2）本算法是通过给理发师编号的方式，当顾客坐到某理发椅上也同时获得理发师的编号，

如此，当该理发师理发结束，释放信号，顾客只有接收到为其理发的理发师的理发结束信号

才会进行付款等 *** 作。这样实现，是为避免这样的错误，即：如果仅用一个finished 信

号量的话，很容易出现别的理发师理发完毕释放了finished 信号，把正在理发的这位顾

客赶去付款,而已经理完发的顾客却被阻塞在理发椅上的情形。当然也可以为顾客进行编

号，让理发师获取他理发的顾客的编号，但这样就会限制顾客的数量，因为finished[]

数组不能是无限的。而为理发师编号，则只需要三个元素即可。

3.参考文献：

左金平 计算机 *** 作系统中哲学家进餐问题探究。

参考教材 *** 作系统—内核与设计原理

其他网络资源

哲学家就餐问题

1965年，Dijkstra提出并解决了一个他称之为哲学家就餐的同步问题。从那时起，每个发明新的同步原语的人都希望通过解决哲学家就餐问题来 展示其同步原语的精妙之处。这个问题可以简单地描述如下：五个哲学家围坐在一张圆桌周围，每个哲学家面前都有一盘通心粉。由于通心粉很滑，所以需要两把叉 子才能夹住。相邻两个盘子之间放有一把叉子，餐桌如图2-44所示。

哲学家的生活中有两种交替活动时段：即吃饭和思考（这只是一种抽象，即对哲学家而言其他活动都无关紧要）。当一个哲学家觉得饿了时，他就试图分两次 去取其左边和右边的叉子，每次拿一把，但不分次序。如果成功地得到了两把叉子，就开始吃饭，吃完后放下叉子继续思考。关键问题是：能为每一个哲学家写一段 描述其行为的程序，且决不会死锁吗？（要求拿两把叉子是人为规定的，我们也可以将意大利面条换成中国菜，用米饭代替通心粉，用筷子代替叉子。）

图2-45给出了一种直观的解法。过程take_fork将一直等到所指定的叉子可用，然后将其取用。不过，这种显然的解法是错误的。如果五位哲学家同时拿起左面的叉子，就没有人能够拿到他们右面的叉子，于是发生死锁。

我们可以将这个程序修改一下，这样在拿到左叉后，程序要查看右面的叉子是否可用。如果不可用，则该哲学家先放下左叉，等一段时间，再重复整个过程。 但这种解法也是错误的，尽管与前一种原因不同。可能在某一个瞬间，所有的哲学家都同时开始这个算法，拿起其左叉，看到右叉不可用，又都放下左叉，等一会 儿，又同时拿起左叉，如此这样永远重复下去。对于这种情况，所有的程序都在不停地运行，但都无法取得进展，就称为饥饿（starvation）。（即使问 题不发生在意大利餐馆或中国餐馆，也被称为饥饿。）

---