哲学家就餐问题的实验课程思路拓展

2018-05-13杨珊

实验科学与技术 2018年2期

杨珊

(电子科技大学信息与软件学院，四川成都 610000)

在1965年，文献[1]中Dijkstra将一个同步问题称为哲学家就餐的同步问题。

在软件工程专业的操作系统实验课程中，哲学家就餐问题是学生掌握信号量使用的第一步尝试，同样也是一次重要的实验项目，目的是加强学生在互斥量信号量等同步及互斥机制的实践训练。

操作系统这门课程具有概念多、算法多、内容抽象且广泛等特点，实验效果反馈显示学生自主完成该实验项目具有一定难度。因此本文将主要通过同步问题内容分解、算法实现思路、死锁解决方案3大内容来提高学生对实验学习的达成度及动手能力。首先本文将通过对哲学家就餐问题的详细分解加深加强对该同步问题的理解；进而实现一种并发量较大的算法思路，目的是为了拓宽学生的知识面，使其从多种角度学习理解操作系统的同步问题，延展解决思路；最后讨论死锁的产生原因及预防的一种方案，锻炼学生对于解决死锁问题的思考能力。参与本门实验课程的学生亦可将本文作为实验指导内容。

1 经典操作系统同步问题

哲学家就餐问题描述[2－3]为:一共有5个哲学家和5把叉子，每人面前一盘通心粉 (需要两把叉子才能拿起)，大家围绕桌子，进行思考与进食的活动。

哲学家的活动方式为:要么放下左右手刀叉进行思考，要么拿起刀叉开始吃饭(刀叉拿起时，必须拿两把，而且只能左右手依次拿，先左手拿左边，后右手拿右边，或者先右手拿右边，后左边拿左边)。即只有思考和进餐两种交替状态。

哲学家面临的问题为:哲学家需要统一思考逻辑，同时能够保证以下两个条件:

1)他们至少有人且尽可能两个人能同时拿到两把叉子开始吃饭；

2)不会发生 “死锁”和 “饥饿”的状态。

哲学家进餐和思考的时机是随机的，不能指定哲学家们进餐顺序。同时要保证不会出现死锁和饥饿[3]这两种让 “进餐”无法继续的状态。

2 哲学家就餐问题解决思路

我们将哲学家问题抽象为进程或线程对资源访问的互斥及同步问题，此处我们使用线程函数来描述一位哲学家的行为。

关系分析:5名哲学家 (线程)对5只叉子的访问特征为占有之后，其他邻居不可以访问，因此是互斥关系。由于哲学家线程行为是一致的，所以如何定义哲学家对资源的获取是每个算法的核心思想。通常哲学家线程的进餐及思考流程如图1所示。

图1 哲学家就餐线程流程图

3 K.Mani Chandy/J.Misra算法

本文讨论的是由K.Mani Chandy和J.Misra在1984年提出的一种哲学家就餐算法的实现，主要原理旨在增加哲学家获取叉子的时候，竞争者之间的 “交流”，使得线程没有盲目地去抢夺资源。

文献[4－5]中解法思路为原解法，允许哲学家数量为P1，P2，…，PN，此处仍旧讨论5位哲学家的情况。

1)每一对竞争同一资源的哲学家，新拿一个叉子，分给编号较低的哲学家。刚开始的时候，把每只叉子(F)依次分给编号较小的哲学家 (A，B，C，D，E)，即有 A－F1，B－F2，C－F3，DF4，E－F5，并把筷子都定义为“脏的”。

2)当某位哲学家要使用筷子的时候，他缺哪只叉子，就向拥有那只叉子的哲学家发送一个请求。

3)当拥有叉子的哲学家收到请求时，如果叉子是脏的，就把叉子擦干净并交出去；否则就继续留着。

4)当哲学家拥有两只干净的叉子时，就可以就餐了，吃完以后叉子就变成脏的了。如果有哲学家之前请求过其中一只叉子，则把叉子擦干净并交出去。

首先算法定义叉子是属于某位哲学家的，并且永远都在某位哲学家手上，只有该哲学家同意，筷子才可以交出去。这种哲学家之间 “交流”的算法思想和传统解决方法有极大的差别。

其中，哲学家手上的叉子状态有两种，一种是 “干净的”，一种是 “脏的”。在整个哲学家吃饭和休息 (思考)的过程中，叉子只有在某个哲学家准备开始到吃饭行为结束期间是干净的，如图2所示。

图2 筷子状态变化示意图

图2的例子详细地解释了本算法的重要规则。本例中有5位哲学家参与进餐过程，叉子是依次分给编号较小的哲学家，即有A－F1，B－F2，C－F3，D－F4，E－F5，根据算法规则，叉子的状态在一开始的时候都是 “脏的”。如图3所示，给出了哲学家就餐开始到某个时间点的过程中，A、B、C 3位哲学家对叉子进行竞争分配、交出叉子或进餐的过程。

最先需要进餐的B将手上的叉子F2擦干净，同时向A请求叉子F1，A的叉子F1是 “脏的”，所以擦干净交给B。此时C需要进餐，向B请求叉子F2，但是叉子F2此时是 “干净的”，所以B留在手上。最后B进餐结束，叉子F1与叉子F2都变为 “脏的”，此时C的请求得到响应，拿到叉子F2。

图3 哲学家A、B、C竞争进餐过程

这种算法可以解决大规模的并发问题 (哲学家数量可以为Pn)，也能避免饿死问题。但是，不能完全避免死锁现象 (当每个哲学家拿到一只干净叉子的时候，则陷入了死锁)[6]。

4 算法实现具体描述

本文接下来将讨论算法的实现思路，主要描述两个重要函数的实现思路。

函数philo://主要的哲学家线程程序

{

while(无限){

while(左叉子不在手上或者右叉子不在手上)

{

getchopfromneighbor(左叉子)；

//对没有的叉子进行请求

getchopfromneighbor(右叉子)；

}

//进入互斥区

pthread＿mutex＿lock(＆g＿mtx)；

确认两个叉子都在手上则吃饭3秒；

将两把叉子状态设置为DIRTY

pthread＿mutex＿unlock(＆g＿mtx)；

sleep(随机数秒)；

}

函数Philo结束

函数getchopfromneighbor(chokid)

//判断是否让邻居交出叉子

{

if Philo[chokid]＝＝请求者

Status[chokid]＝CLEAN；

if Philo[chokid]！＝请求者

{

pthread＿mutex＿lock(＆g＿mtx)；

if(需判断叉子＝＝DIRTY)

{ Philo[chokid] ＝请求者

Status[chokid] ＝CLEAN；}

pthread＿mutex＿unlock(＆g＿mtx)；

}

函数Philo是主要的哲学家线程函数，包括了哲学家的所有行为流程，主要有吃饭行为和思考行为。吃饭行为在获取到叉子之后进入互斥区开始进餐，使用互斥主要是为了保证吃饭行为的原子性；思考行为主要是sleep函数，线程阻塞数秒。

5 死锁原因及解决思路

在前文算法介绍处提到，根据此思路实现的算法有时会出现死锁，即5位哲学家都拿到了干净的叉子 (哲学家请求资源的顺序的一致)[7]。

在上述流程描述中，哲学家在得到一只叉子之后，设为 “干净的”，此时如果每位哲学家依次获得一只干净叉子，程序会进入死锁状态。

因此，实现了以上思路的代码后，在运行多次的情况下有可能会出现如图4所示的结果。

图4中5位哲学家同时拿到右手干净的叉子而未进入进餐，出现死锁状态。对于解决哲学家进餐的死锁问题[8－11]，有许多人已经提出了以下的思路:

1)保证拿起左右叉子操作的原子性；

2)奇数、偶数哲学家拿叉子顺序不同；

3)采用异步操作来让权等待；

4)通过条件变量和信号量的结合使用。

如在计算机局域网的实际应用中，为了避免死锁，人们尝试将等待的时间设为随机时间 (在哲学家问题里描述为 “如果哲学家在拿不到右边叉子时等待一段随机时间，而不是等待相同的时间”[12])。如果两台计算机同时发送数据包，则每台计算机等待随机时间之后再进行尝试。

结合这几条思路研究此处死锁出现的条件，可得知是由于所有哲学家同一时间 (间隔极短)请求同方向的叉子而导致死锁。因此在考虑请求叉子时，使用随机数加入随机请求左右叉子的判断 (拿叉子顺序不同)，则能以极大概率避免了死锁的发生。

将上面的philo函数中while循环段的示意代码做一些修改，如下:

while(左叉子不在手上或者右叉子不在手上){

初始化一个随机数；if随机数%2＝1

则getchopfromneighbor(左叉子)；if随机数%2＝＝0

则getchopfromneighbor(右叉子)；}此种避免死锁的方法和上述解决思路2中奇数、偶数哲学家拿叉子顺序不同的原理一致，在实验过程中可以根据此思路来完成死锁避免的具体实现。

以上程序提供源码下载，供读者研究参考，死锁的解决方法在源码中已经隐藏，读者可以尝试多次运行得到死锁状态，再尝试解决死锁问题。

源码地址如下:http://download.csdn.net/detail/forsaking/9906530。

6 结束语

哲学家进餐问题是一个经典的操作系统同步问题。作为操作系统实验课的一个小型实验项目，哲学家进餐实验具有一定的难度。通过本文介绍的K.Mani Chandy/J.Misra哲学家就餐算法内容和相关实现过程及对死锁的解决方法，可以延展学生解决该同步问题的思路，帮助学生提高分析问题的能力。学生在采用本文算法进行实践后，可以帮助其提高学习效果。

1)加深对死锁的理解，从实例中体会死锁对程序的影响及产生死锁的具体原因；体会解决死锁思路的不同方式，解决死锁可能只需要一行代码。

2)在不使用信号量的情况下，使用本文的算法解决多线程之间的通信，理解信号量的解决问题的最根本原始思路。

3)拓宽学生的思考领域，从其他维度分析解决项目问题的能力。

此外，如何加强学生实验研究的主动性，自主构建多元解决方案，仍是今后需要不断探索研究的内容。

[1]窦金凤，曹家宝，郭忠文，等.计算机操作系统哲学家进餐问题的教学探讨[J].计算机教育，2009(14):86－88.

[2]贾玉珍，王祥雒.哲学家进餐问题的一种解决方案[J].电脑知识与技术，2006(14):163－164.

[3]张磊，马军.描述短时资源混杂占用型任务调度的数学模型与算法[C]//中国计算机学会理论计算机科学专业委员会.2005年全国理论计算机科学学术年会论文集.北京:中国计算机学会理论计算机科学专业委员会，2005.

[4]左金平.计算机操作系统中哲学家进餐问题探究[J].晋中学院学报，2004，21(4):343－344.

[5]JENNIFER L W，NANCY A.Lynch a modular drinking philosophers algorithm[J]. Distributed Computing，1993，6(4):233－244.

[6]CHANDY K M，MISRA J.Parallel program design:a foundation[J].Addison－Wesley Longman，1988，16(11):1313－1334.

[7]王继伟，王安，汪树勋.一个经典进程同步问题的几种解法[J].甘肃科技，2007，23(1):60－62.

[8]孙时光，张晋.解决哲学家进餐问题陷入死锁状态的系统改造方案分析[J].辽宁大学学报 (自然科学版)，2013，40(3):210－212.