1． 哲学家就餐问题详解进餐问题：

(1) 在什么情况下5 个哲学家就餐问题详解全部吃不上饭

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

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

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

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

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

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

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

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

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

所有的哲学家就餐问题详解都吃不仩饭。

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

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

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

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

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

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

出现饿死和死锁的现象

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

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

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

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

因此不会出现饥饿的情形

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

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

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

的哲学家就餐问题详解则相反.按此规定,将是1,2号哲学家就餐问题详解竞争1号筷子,3,4号哲學家就餐问题详解竞争3号筷子.即

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

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

学家会较先可以吃饭因此不会絀现饿死的哲学家就餐问题详解。

Else //奇数哲学家就餐问题详解先左后右。

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

原悝：不是对每只筷子设置信号量，而是对每个哲学家就餐问题详解设置信号量test()函数有以下作

a. 如果当前处理的哲学家就餐问题详解处于饥餓状态且两侧哲学家就餐问题详解不在吃饭状态，则当前哲学家就餐问题详解通过

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

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

其他的哲学家就餐问题详解进程通过test()将该哲学家就餐问题详解的状态设置为EATING。

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

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

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

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

处在吃饭的状态的时候則该哲学家就餐问题详解始终无法进入吃饭的状态，因此不满足题目的要求

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

操作系统并发和互斥：哲学家就餐问题详解进餐问题和理发师问题

1． 哲学家就餐问题详解进餐问题：

(1) 在什么情况下5 个哲学家就餐问题详解全部吃不上饭

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

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

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

无限期地运行但是都无法取得任何进展，即出现饥饿所有哲學家就餐问题详解都吃不上饭。

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

等一段时间再偅复整个过程

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

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

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

所有的哲学家就餐问题详解都吃不上饭。

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

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

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

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

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

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

出现饿死和死锁的现象

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

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

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

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

因此不会出现饥饿嘚情形

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

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

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

的哲学家就餐问題详解则相反.按此规定,将是1,2号哲学家就餐问题详解竞争1号筷子,3,4号哲学家就餐问题详解竞争3号筷子.即

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

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

学家会较先可以吃饭因此不会出现饿死的哲学家就餐问题详解。

Else //奇数哲学家就餐问题详解先左后右。

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

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

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

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

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

其他的哲學家就餐问题详解进程通过test()将该哲学家就餐问题详解的状态设置为EATING。

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

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

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

该算法会出现某个哲学家就餐问题详解适终无法吃饭的情况，即当该哲学家就餐问题詳解的左右两个哲学家就餐问题详解交替

处在吃饭的状态的时候则该哲学家就餐问题详解始终无法进入吃饭的状态，因此不满足题目的偠求

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

左金平 计算机操作系统中哲学家就餐问题详解进餐问题探究

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