模拟“五个哲学家”问题_Unix环境高级编程

时间：2021-08-24 09:18:01

实验描述

转自：http://dblab.xmu.edu.cn/blog/unix-philosopher-problem-using-files/

编制模拟“五个哲学家”问题的程序，学习和掌握并发进程同步的概念和方法。

要求：

1、程序语法，是哲学家进餐和沉思的持续时间值，缺省值为2秒。

philosopher [ -t ]

2、五个哲学家的编号为0~4，分别用五个进程独立模拟。
3、程序的输出要简洁，仅输出每个哲学家进餐和沉思的信息。例如，当编号为3的哲学家在进餐时，就打印：
philosopher 3 is eating
而当他在沉思时，则打印：
philosopher 3 is thinking
除此之外不要输出其他任何信息。
4、利用课堂已教授的知识而不使用线程或IPC机制进行同步。

实验思路

哲学家就餐问题有多种解决思路可以避免死锁的发生，《实验指导》中的思路时，哲学家一旦拿到其中的一个叉子就不放下，直到拿到另一个叉子并进餐后才把两个叉子都放下。这种思路的前提是保证哲学家中同时存在左撇子和右撇子，则不会发生死锁。

解法[编辑]

服务生解法[编辑]

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

为了演示这种解法，假设哲学家依次标号为A至E。如果A和C在吃东西，则有四只餐叉在使用中。B坐在A和C之间，所以两只餐叉都无法使用，而D和E之间有一只空余的餐叉。假设这时D想要吃东西。如果他拿起了第五只餐叉，就有可能发生死锁。相反，如果他征求服务生同意，服务生会让他等待。这样，我们就能保证下次当两把餐叉空余出来时，一定有一位哲学家可以成功的得到一对餐叉，从而避免了死锁。

资源分级解法[编辑]

另一个简单的解法是为资源（这里是餐叉）分配一个偏序或者分级的关系，并约定所有资源都按照这种顺序获取，按相反顺序释放，而且保证不会有两个无关资源同时被同一项工作所需要。在哲学家就餐问题中，资源（餐叉）按照某种规则编号为1至5，每一个工作单元（哲学家）总是先拿起左右两边编号较低的餐叉，再拿编号较高的。用完餐叉后，他总是先放下编号较高的餐叉，再放下编号较低的。在这种情况下，当四位哲学家同时拿起他们手边编号较低的餐叉时，只有编号最高的餐叉留在桌上，从而第五位哲学家就不能使用任何一只餐叉了。而且，只有一位哲学家能使用最高编号的餐叉，所以他能使用两只餐叉用餐。当他吃完后，他会先放下编号最高的餐叉，再放下编号较低的餐叉，从而让另一位哲学家拿起后边的这只开始吃东西。

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

这种方法经常是实际计算机科学问题中最实用的解法，通过为分级锁指定常量，强制获得锁的顺序，就可以解决这个问题。

Chandy/Misra解法[编辑]

1984年，K. Mani Chandy和J. Misra提出了哲学家就餐问题的另一个解法，允许任意的用户（编号P1, ..., Pn）争用任意数量的资源。与资源分级解法不同的是，这里编号可以是任意的。

  • 把筷子凑成对，让要吃的人先吃，没筷子的人得到一张换筷子券。
  • 饿了，把换筷子券交给有筷子的人，有筷子的人吃饱了会把筷子交给给券的人。有了券的人不会再得到第二张券。
  • 保证有筷子的都有得吃。

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

解法来自*：https://zh.wikipedia.org/wiki/%E5%93%B2%E5%AD%A6%E5%AE%B6%E5%B0%B1%E9%A4%90%E9%97%AE%E9%A2%98


下面的代码其实和*的解法不一样，因为代码里面先放下低编号，后高编号。但是*建议先放高编号，后低编号，

因为先放高的效率更高，不过因为放叉子是不会有死锁嘛，所以一点点效率损失问题不大。


并且也给了lock.c，实现了文件版本的lock()和unlock()，理解这个lock()的实现是关键:

  
  
    

  1. 
#include <sys/types.h>

    2. 
   
   
  2. 
#include <sys/stat.h>

    3. 
   
   
  3. 
#include <fcntl.h>

    4. 
   
   
  4. 
#include <unistd.h>

    5. 
   
   
  5. 
#include "apue.h"

    6. 
   
   
  6.  
    7. 
   
   
  7. 
void initlock(const char *lockfile)

    8. 
   
   
  8. {
    9. 
   
   
  9. 
 int i;

    10. 
   
   
  10.  
    11. 
   
   
  11. 
 unlink(lockfile);

    12. 
   
   
  12. }
    13. 
   
   
  13.  
    14. 
   
   
  14. 
void lock(const char *lockfile)

    15. 
   
   
  15. {
    16. 
   
   
  16. 
 int fd;

    17. 
   
   
  17. 
 while ( (fd = open(lockfile, O_RDONLY | O_CREAT | O_EXCL, FILE_MODE)) < 0)

    18. 
   
   
  18. 
 sleep(1);

    19. 
   
   
  19. 
 close(fd);

    20. 
   
   
  20. }
    21. 
   
   
  21.  
    22. 
   
   
  22. 
void unlock(const char *lockfile)

    23. 
   
   
  23. {
    24. 
   
   
  24. 
 unlink(lockfile);

    25. 
   
   
  25. }
    26.
C 语言

lock(): 同时指定open()的 O_CREAT 和 O_EXCL 位，可用于判断文件是否存在(书中第48页)。fd<0表示文件已存在，于是sleep1秒，然后继续尝试。如果文件不存在，则创建文件，创建后，别人则无法再创建该文件。通过这样的方式来模拟lock，即该叉子(文件)已被某哲学家(进程)使用(创建)，在叉子未放下(未删除)前，其他人不能使用(创建)。对应的unlock()就是删除该文件。

可以通过下图来进一步了解该lock：

模拟“五个哲学家”问题_Unix环境高级编程文件版的lock实现

实验的大部分代码，《实验指导》中已经给出。

  
  
    

  1. // 定义5个文件，分别表示5个叉子。其文件名可以按如下方式说明：
    2. 
   
   
  2. 
static char* forks[5] = {“fork0“, “fork1“, “fork2“, “fork3“, “fork4“};

    3. 
   
   
  3.  
    4. 
   
   
  4. // 哲学家的行为可以用如下函数描述：
    5. 
   
   
  5. 
void philosopher(int i)

    6. 
   
   
  6. {
    7. 
   
   
  7. 
 while(1) {

    8. 
   
   
  8. 
 thinking(i, nsecs); // 哲学家i思考nsecs秒

    9. 
   
   
  9. 
 takeFork(i); // 哲学家i拿起叉子

    10. 
   
   
  10. 
 eating(i, nsecs); // 哲学家i进餐nsecs秒

    11. 
   
   
  11. 
 putFork(i); // 哲学家i放下叉子

    12. 
   
   
  12. 
 }

    13. 
   
   
  13. }
    14. 
   
   
  14.  
    15. 
   
   
  15. // 在主程序里，可以用下面的程序段生成5个哲学家进程：
    16. 
   
   
  16. 
#define N 5

    17. 
   
   
  17. 
for(i = 0; i < N; i++) {

    18. 
   
   
  18. 
 pid = fork();

    19. 
   
   
  19. 
 if( pid == 0 )

    20. 
   
   
  20. 
 philosopher(i)；

    21. 
   
   
  21. 
 // …………………

    22. 
   
   
  22. }
    23. 
   
   
  23. 
wait(NULL); /* 注意，如果父进程不等待子进程的结束，那么需要终止程序运行时，就只能从控制台删除在后台运行的哲学家进程 */

    24. 
   
   
  24.  
    25. 
   
   
  25. // 拿起叉子可以如此定义：
    26. 
   
   
  26. 
void takeFork(i)

    27. 
   
   
  27. {
    28. 
   
   
  28. 
 if( i == N - 1 ) {

    29. 
   
   
  29. 
 lock( forks[0] );

    30. 
   
   
  30. 
 lock( forks[i] );

    31. 
   
   
  31. 
 }

    32. 
   
   
  32. 
 else {

    33. 
   
   
  33. 
 lock( fork[i] );

    34. 
   
   
  34. 
 lock( fork[i + 1] );

    35. 
   
   
  35. 
 }

    36. 
   
   
  36. }
    37. 
   
   
  37.  
    38. 
   
   
  38. // 放下叉子可以如此定义：
    39. 
   
   
  39. 
void putFork(i)

    40. 
   
   
  40. {
    41. 
   
   
  41. 
 if( i == N - 1 ) {

    42. 
   
   
  42. 
 unlock( forks[0] );

    43. 
   
   
  43. 
 unlock( forks[i] );

    44. 
   
   
  44. 
 }

    45. 
   
   
  45. 
 else {

    46. 
   
   
  46. 
 unlock( fork[i] );

    47. 
   
   
  47. 
 unlock( fork[i + 1] );

    48. 
   
   
  48. 
 }

    49. 
   
   
  49. }
    50.
C 语言

上面的代码基本无需修改，只要再补充输入参数的检验、think()、eating()就可以了，这个实验重在理解，理解了就非常简单了（代码都给得这么细了…）

比较重要的是 takeFork() ，前面说了哲学家一旦拿到其中的一个叉子就不放下，直到拿到另一个叉子并进餐后才把两个叉子都放下。这种思路的前提是保证哲学家中同时存在左撇子和右撇子，上面给出的代码，其实就是人为将第N个哲学家（编号N-1）设为右撇子，其他人是左撇子。你自己在图上画个圈表示哲学家跟叉子，都编上号，你就明白了。

还有一个点是僵尸进程，主程序中使用了 wait(NULL) 来避免僵尸进程的发生，为何？自己翻书吧…

使用 ps au 可以查看当前用户运行的程序，如运行 ./philosopher 时，新开一个终端并运行 ps au，如下图，可以看到有6个 philosopher 进程（1个主进程，5个子进程），当结束 ./philosopher 后，再运行 ps au 将不会看到 philosopher 进程，否则就是产生了僵尸进程。

模拟“五个哲学家”问题_Unix环境高级编程使用ps au来查看运行的程序

最后，程序每次运行的结果都不太一样。例如一开始五个哲学家都进入思考状态，这五条状态的输出顺序不固定，你跑程序时就会发现这一点了，Why？还是自己翻书去吧… 有一点需要注意的是，执行 sleep(1) 时，进程并不会精准的休眠1秒，知道这点有助于你理解程序的运行。

题外话

做实验时有给同学讲解了下，主要是讲了 lock() 的实现和左右撇子的问题，但从实验过程来看，一些同学对 fork() 还是不够了解，比如 fork() 创建的子进程，子进程是从哪里执行的这些都还不是很了解：

使用 fork() 创建子进程后，子进程是从 fork() 的位置继续执行。所以上面给的程序中，子进程实际上是会继续执行主程序里的 for 循环的（若是完整的执行流程，philosopher() 会运行 31 次）。但因为 philopher() 中是 while(1) 循环，因此每个子进程中就一直各自在不断执行一个philosopher()，即可以模拟5个哲学家。

所以还是建议做实验前好好看下书中相关内容，真的，对 fork() 都不太了解的话，实验一的简单 shell 你是怎么做的？这样你确定你期末上机考试能过么… 做这些实验还是得多思考，多翻书的，要真正明白整个实验所涉及的知识点。

实验讲解PPT

把PPT放出来好了(已转成PDF): UNIX实验四讲解PPT下载

完整代码

代码编译时要将 lock.c 一起编译：

  
  
    

  1. gcc philosopher.c error2e.c lock.c -o philosopher
    2.
Shell 命令

代码中的结果输出顺带输出了当前时间，只是方便查看结果，实验并不要求，提交代码时也不该输出时间，请自行删去。

  
  
    

  1. 
#include "apue.h"

    2. 
   
   
  2. 
#include "time.h"

    3. 
   
   
  3.  
    4. 
   
   
  4. 
#define N 5

    5. 
   
   
  5. 
static char* forks[N] = {"fork0", "fork1", "fork2", "fork3", "fork4"};

    6. 
   
   
  6. 
static int nsecs = 2;

    7. 
   
   
  7.  
    8. 
   
   
  8. /* 显示时间，方便查看结果，提交时应删除 */
    9. 
   
   
  9. 
static char now[80];

    10. 
   
   
  10. 
char* getTime() {

    11. 
   
   
  11. 
 time_t tim;

    12. 
   
   
  12. 
 struct tm *at;

    13. 
   
   
  13. 
 time(&tim);

    14. 
   
   
  14. 
 at=localtime(&tim);

    15. 
   
   
  15. 
 strftime(now, 79, "%H:%M:%S", at);

    16. 
   
   
  16. 
 return now;

    17. 
   
   
  17. }
    18. 
   
   
  18.  
    19. 
   
   
  19. /*
    20. 
   
   
  20.  * 拿叉子的定义
    21. 
   
   
  21.  * 如果哲学家中同时存在左撇子和右撇子，则哲学家问题有解
    22. 
   
   
  22.  */
    23. 
   
   
  23. 
void takeFork(int i) {

    24. 
   
   
  24. 
 if(i == N-1) { // 人为设定第N-1位哲学家是右撇子

    25. 
   
   
  25. 
 lock(forks[0]);

    26. 
   
   
  26. 
 lock(forks[i]);

    27. 
   
   
  27. 
 } else { // 其他是左撇子

    28. 
   
   
  28. 
 lock(forks[i]);

    29. 
   
   
  29. 
 lock(forks[i+1]);

    30. 
   
   
  30. 
 }

    31. 
   
   
  31. }
    32. 
   
   
  32.  
    33. 
   
   
  33. /* 放下叉子 */
    34. 
   
   
  34. 
void putFork(int i) {

    35. 
   
   
  35. 
 if(i == N-1) {

    36. 
   
   
  36. 
 unlock(forks[0]);

    37. 
   
   
  37. 
 unlock(forks[i]);

    38. 
   
   
  38. 
 }

    39. 
   
   
  39. 
 else {

    40. 
   
   
  40. 
 unlock(forks[i]);

    41. 
   
   
  41. 
 unlock(forks[i+1]);

    42. 
   
   
  42. 
 }

    43. 
   
   
  43. }
    44. 
   
   
  44.  
    45. 
   
   
  45. 
void thinking(int i, int nsecs) {

    46. 
   
   
  46. 
 printf("philosopher %d is thinking\t%s\n", i, getTime());

    47. 
   
   
  47. 
 sleep(nsecs);

    48. 
   
   
  48. }
    49. 
   
   
  49.  
    50. 
   
   
  50. 
void eating(int i, int nsecs) {

    51. 
   
   
  51. 
 printf("philosopher %d is eating\t\t%s\n", i, getTime());

    52. 
   
   
  52. 
 sleep(nsecs);

    53. 
   
   
  53. }
    54. 
   
   
  54.  
    55. 
   
   
  55. /* 哲学家行为 */
    56. 
   
   
  56. 
void philosopher(int i) {

    57. 
   
   
  57. 
 while(1) {

    58. 
   
   
  58. 
 thinking(i, nsecs); // 哲学家i思考nsecs秒

    59. 
   
   
  59. 
 takeFork(i); // 哲学家i拿起叉子

    60. 
   
   
  60. 
 eating(i, nsecs); // 哲学家i进餐nsecs秒

    61. 
   
   
  61. 
 putFork(i); // 哲学家i放下叉子

    62. 
   
   
  62. 
 }

    63. 
   
   
  63. }
    64. 
   
   
  64.  
    65. 
   
   
  65. 
int main(int argc, char * argv[]) {

    66. 
   
   
  66. 
 int i;

    67. 
   
   
  67. 
 pid_t pid;

    68. 
   
   
  68.  
    69. 
   
   
  69. 
 /* 初始化叉子 */

    70. 
   
   
  70. 
 for(i = 0; i < N; i++) {

    71. 
   
   
  71. 
 initlock(forks[i]);

    72. 
   
   
  72. 
 }

    73. 
   
   
  73.  
    74. 
   
   
  74. 
 /* 处理输入 */

    75. 
   
   
  75. 
 if(argc == 3 && strcmp(argv[1], "-t") == 0) {

    76. 
   
   
  76. 
 nsecs = atoi(argv[2]);

    77. 
   
   
  77. 
 // if (!nsecs) err_quit("usage: philosopher [ -t <time> ]");

    78. 
   
   
  78. 
 } else if (argc != 1) {

    79. 
   
   
  79. 
 err_quit("usage: philosopher [ -t <time> ]");

    80. 
   
   
  80. 
 }

    81. 
   
   
  81.  
    82. 
   
   
  82. 
 /* 创建五个子进程来模拟五个哲学家 */

    83. 
   
   
  83. 
 for(i = 0; i < N; i++) {

    84. 
   
   
  84. 
 pid = fork();

    85. 
   
   
  85. 
 if (pid == 0) {

    86. 
   
   
  86. 
 philosopher(i);

    87. 
   
   
  87. 
 } else if (pid < 0) {

    88. 
   
   
  88. 
 err_quit("fork error");

    89. 
   
   
  89. 
 }

    90. 
   
   
  90. 
 }

    91. 
   
   
  91.  
    92. 
   
   
  92. 
 wait(NULL); /* 注意，如果父进程不等待子进程的结束，*/

    93. 
   
   
  93. 
 /* 那么需要终止程序运行时，就只能从控制台删除在后台运行的哲学家进程 */

    94. 
   
   
  94. }
    95.
标签：

相关文章