作者帆子·2021-01-21 23:14

售前技术支持·国内某服务器生产商

在IBM i 上使用多线程和信号量来模拟和解决哲学家用餐问题

字数 12092阅读 1950评论 0赞 0

哲学家用餐问题，是并行计算领域的经典问题。为了简单起见，我们搞个中国版本，哲学家改吃米饭。假设有五个哲学家如下图那样围坐在一张圆桌周围，每人面前有一碗米饭，每两人之间有一根筷子。我们知道用一根筷子是无法吃饭的，所以如果某个哲学家想要吃饭，他就需要把他左手边和右手边的筷子都拿到，也就是拿到两根筷子后，才能吃上饭。

假设每位哲学家在餐桌上，要么在吃饭，要么在思考。其过程看似是，拿到两根筷子，吃一口米饭。然后放下两根筷子，进行思考。思考一段时间后，再拿起两根筷子，吃一口米饭。周而复始，直到将碗里的米饭全部吃完。

如果哲学家们互不交流，这就有可能发生死锁。比如每位哲学家都只拿到了左手边的筷子，都在等右手边的筷子，此刻所有哲学家都在等待，没有哲学家能吃上饭。这就发生了死锁。

哲学家用餐问题，很好地模拟了在并行计算领域可能遇到的资源竞争乃至死锁的情况。在这里，筷子代表着共享资源，哲学家代表着并发作业。如果没有协调机制，让多个并发作业自主地去争夺共享资源，这就很有可能会出现死锁。

我的解法，类似于网上所说到的服务生解法。也就是哲学家在每次吃饭之前，需先从服务生那里获取许可证；而在每次吃完饭后，需将许可证交还给服务生。因为我们知道，圆桌上一共只有五根筷子，最多只能提供给两位哲学家同时吃饭，也就是说，服务生那里的许可证只有两张。如果已经有两位哲学家在同时吃饭，其它的需要吃饭的哲学家就只能处于等待状态。在我看来，这种许可证机制制约了对共享资源的过度竞争，有效地防止了死锁的发生。

好了，现在就让我们用多线程和信号量来模拟和解决这个哲学家用餐问题吧。

关于多线程，请参考我先前所写的《在 IBM i 上用 C 实现多线程编程》。在这里，我们主要来谈信号量。同在 UNIX/Linux 一样，在 IBM i 上使用 C 程序，也可以非常方便地生成和使用 Unnamed Semaphore （下文以 US 来表示），并能用它来协调多个线程对共享资源的使用。期间所涉及的主要函数是如下的这几个：

1 ， int sem_init(sem_t * sem, int shared, unsigned int value);

其中， sem 是一个指针，指向内存区中一个尚未被初始化的 US 。
shared 是指示系统如何使用这个 US ， 0 代表仅能被当前作业所生成的线程使用；非 0 代表可以被其它作业所生成的线程使用。
value 是为 US 赋一个初始值。后面我们会解释 US 的 Value ，其具体含义到底是什么。
该函数的作用是初始化一个 US 。

2 ， int sem_destroy(sem_t * sem);

其中， sem 是一个指针，指向内存区中一个已经被初始化了的 US 。
该函数的作用是清除一个 US 。当一个 US 的使命完成之后，需要对它进行清除操作，以回收其所占用的内存资源。

3 ， int sem_wait(sem_t * sem);

其中， sem 是一个指针，指向内存区中一个已经被初始化了的 US 。
该函数的作用是将 US 的 Value 减 1 。该函数执行后，如果 US 的 Value 大于等于 0 ，那么当前线程将会继续执行其下一条语句；反之，如果 US 的 Value 变成小于 0 ，那么当前线程将被阻塞，直到被唤醒，才会继续执行其下一条语句。

4 ， int sema_post(sem_t * sem);

其中， sem 是一个指针，指向内存区中一个已经被初始化了的 US 。

该函数的作用是将 US 的 Value 加 1 。该函数执行前，如果 US 的 Value 小于 0 ，那么该函数将会去随机地唤醒一个正在处于被阻塞状态的线程。

由此可以看出：一个 US 的 Value 代表如下的含义：

当 Value > 0 时，它代表着可用的共享资源的数量。
当 Value < 0 时，其绝对值代表着因未能获得共享资源而正处于被阻塞状态的线程的数量。
而当 Value = 0 时，它代表既没有可用的共享资源，也没有想要获得共享资源而处于阻塞状态的线程。

如果将共享资源视作供给侧，而使用共享资源的线程视作需求侧，那么：

当 Value > 0 时，代表供给大于需求。
当 Value < 0 时，代表供给小于需求。
当 Value = 0 时，代表供需平衡我们的程序非常简单。

以下是程序的设计思路：

每个线程代表一位哲学家。
五位哲学家每人都有一个唯一的编号（从第 0 号到第 4 号）。
同样地，桌子上的五根筷子也都有自己的编号（从第 0 号到第 4 号）。
哲学家的编号和他自己右手边的筷子的编号相同。
每位哲学家想要吃饭时，他总是先试图拿起他左手边的筷子，再试图拿起他右手边的筷子。只有左右手的筷子都拿到，哲学家才能吃完一口饭。吃完后立刻放下筷子思考。
每位哲学家需要独立吃完 10 口饭。

显然，桌子上的筷子是一种共享资源。因此，我们为每根筷子设置了对应的信号量 —— sema_chp[5] 。它们的初始值都是 1 。它们相当于为每根筷子都增添了一个互斥锁。一旦被人拿了，就不可以再提供给其他人使用了。

为了让哲学家逐个启动用餐，我们增设了另一个信号量 sema_dta 。当它和 Sleep(1.5) 结合时，其用意就是让这五位哲学家各自启动用餐的时间有所间隔。然而，当这个时间间隔明显小于哲学家拿到左手边筷子和拿到右手边筷子的时间间隔的时候（ Sleep(5) ），死锁的产生也就是不可避免的了。

现在就让我们看看，在没有服务生干预的情况下，我们能否模拟出一个死锁。

《 PHILOSOPHE0.C 》

#define _MULTI_THREADED
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#define  PHLSPH  5

#define checkResults(string, val) {                 \\
  if (val) {                                          \\
    printf("Failed with %d at %s", val, string);   \\
    exit(1);                                           \\
  }                                                     \\
}

char * getct(char * ct) {

  struct timeval now;
  int rc;

  rc = gettimeofday(&now, NULL);
  if (rc==0) {
    sprintf(ct, "%u.%06u", now.tv_sec, now.tv_usec);
  } else {
    sprintf(ct, "timeerror");
  }
  return(ct);
}

typedef struct {
  int   value;
} thread_parm_t;

sem_t sema_dta;
sem_t sema_chp[PHLSPH];
int   result[PHLSPH];
int   dta_value = 0;

void *threadfunc(void *parm) {

  int               i, j, k;
  char              ct[20];
  thread_parm_t     *p;
  pthread_id_np_t   thdid;

  thdid = pthread_getthreadid_np();
  p = (thread_parm_t *) parm;
  k = p->value;
  printf("线程%.8x%.8x代表第%d号哲学家\\n", thdid, k);

  if (k == 0) j=PHLSPH-1;
  else j=k-1;

  sem_wait(&sema_dta);
  printf("第%d号哲学家开动，时间是%s\\n",                   \\
           k, getct(ct));

  for (i=0; i<10; i++) {
    sem_wait(&sema_chp[j]);
    printf("第%d号哲学家拿到第%d号筷子，时间是%s\\n",     \\
           k, j, getct(ct));

    sleep(5);
    sem_wait(&sema_chp[k]);
    printf("第%d号哲学家拿到第%d号筷子，时间是%s\\n",     \\
           k, k, getct(ct));

    result[k]++;
    printf("第%d号哲学家第%d次进食，时间是%s\\n",         \\
           k, result[k], getct(ct));

    sem_post(&sema_chp[k]);
    sem_post(&sema_chp[j]);

  }

  printf("线程%.8x%.8x，第%d号哲学家用餐结束，时间是%s\\n", \\
           thdid, k, getct(ct));

}

int main(int argc, char **argv) {

  int                   i=0;
  int                   rc=0;

  pthread_t             threadid[10];
  thread_parm_t         *(parm[PHLSPH]);
  pthread_attr_t        pta;

  sem_init(&sema_dta, 0, 0);
  for (i=0; i<PHLSPH; ++i) {
    result[i]=0;
    sem_init(&sema_chp[i], 0, 1);
  }

  for (i=0; i<PHLSPH; i++)
    parm[i] = malloc(sizeof(thread_parm_t));

  pthread_attr_init(&pta);
  pthread_attr_setdetachstate(&pta, PTHREAD_CREATE_JOINABLE);

  printf("Creating %d threads\\n", PHLSPH);
  for (i=0; i<PHLSPH; i++) {
    parm[i]->value = i;
    rc = pthread_create(&threadid[i], &pta,                  \\
                        threadfunc, (void *) parm[i]);
    checkResults("pthread_create()\\n", rc);
  }

  sleep(5);

  for (i=0; i<PHLSPH; i++)
    free(parm[i]);

  printf("Dinner starts\\n");
  for (i=0; i<PHLSPH; i++) {
    sem_post(&sema_dta);
    sleep(1.5);
  }

  for (i=0; i<PHLSPH; i++) {
    rc = pthread_join(threadid[i], NULL);
    checkResults("pthread_join()\\n", rc);
  }

  printf("Cleanup and show results\\n");
  pthread_attr_destroy(&pta);
  sem_destroy(&sema_dta);
  for (i=0; i<PHLSPH; i++)
    sem_destroy(&sema_chp[i]);


  printf("Main completed\\n");
  return 0;
}

让我们来运行一下。在命令行键入以下命令：

SBMJOB CMD(CALL PGM(*LIBL/PHILOSOPH0)) JOB(PHILOSOPH0) JOBD(QGPL/MULTIJOBD)

该命令将向子系统 QBATCH 提交一个支持多线程的后台作业。
我们可以通过键入 WRKACTJOB SBS(QBATCH) 来查看这个作业。

我们还可以针对该作业键入 12 这个选项，来进一步查看该后台作业所启动的那些线程以及它们的运行状态：

在这里，每一个线程代表着一位哲学家。可以看到，此刻，该作业所启动的五个线程全都处于 SEMA WAIT 状态 —— 死锁发生。

强行终止该作业，其所输出的假脱机文件（ Spool File ）的内容为：
Creating 5 threads
线程 0000000000000013 代表第 0 号哲学家
线程 0000000000000014 代表第 1 号哲学家
线程 0000000000000015 代表第 2 号哲学家
线程 0000000000000016 代表第 3 号哲学家
线程 0000000000000017 代表第 4 号哲学家
Dinner starts
第 3 号哲学家开动，时间是 1610920729.705824
第 3 号哲学家拿到第 2 号筷子，时间是 1610920729.705880
第 1 号哲学家开动，时间是 1610920730.735888
第 1 号哲学家拿到第 0 号筷子，时间是 1610920730.735928
第 2 号哲学家开动，时间是 1610920731.765976
第 2 号哲学家拿到第 1 号筷子，时间是 1610920731.766016
第 4 号哲学家开动，时间是 1610920732.796048
第 4 号哲学家拿到第 3 号筷子，时间是 1610920732.796096
第 0 号哲学家开动，时间是 1610920733.826112
第 0 号哲学家拿到第 4 号筷子，时间是 1610920733.826152

死锁的原因显而易见：每位哲学家都已经拿到了自已左手边的筷子，但他们都在等待自己右手边的筷子。结果，谁都无法吃上饭。

好了，让我们引入服务生的许可证机制。这里，我们通过增加一个信号量， sema_cct ，来实现这种机制。你可以将 sema_cct 想象成服务生手里的许可证。显然，当桌上只有五根筷子时，最多只能有两位哲学家可以同时用餐，因此 sema_cct 的初始值为 2 。现在让我们看看这五位哲学家能否顺利地把饭吃完。

《 PHILOSOPHE1.C 》

#define _MULTI_THREADED
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#define  PHLSPH  5

#define checkResults(string, val) {               \\
  if (val) {                                      \\
    printf("Failed with %d at %s", val, string);  \\
    exit(1);                                      \\
  }                                               \\
}

char * getct(char * ct) {

  struct timeval now;
  int rc;

  rc = gettimeofday(&now, NULL);
  if (rc==0) {
    sprintf(ct, "%u.%06u", now.tv_sec, now.tv_usec);
  } else {
    sprintf(ct, "timeerror");
  }
  return(ct);
}

typedef struct {
  int   value;
} thread_parm_t;

sem_t sema_dta;
sem_t sema_cct;
sem_t sema_chp[PHLSPH];
int   result[PHLSPH];
int   cct = PHLSPH/2;
int   dta_value = 0;

void *threadfunc(void *parm) {

  int               i, j, k;
  char              ct[20];
  thread_parm_t     *p;
  pthread_id_np_t   thdid;

  thdid = pthread_getthreadid_np();
  p = (thread_parm_t *) parm;
  k = p->value;

  printf("线程%.8x%.8x代表第%d号哲学家\\n", thdid, k);

  if (k == 0) j=PHLSPH-1;
  else j=k-1;

  sem_wait(&sema_dta);
  printf("第%d号哲学家开动，时间是%s\\n",                   \\
           k, getct(ct));

  for (i=0; i<10; i++) {
    sem_wait(&sema_cct);
    printf("第%d号哲学家获得进食许可证，时间是%s\\n",         \\
           k, getct(ct));

    sem_wait(&sema_chp[j]);
    printf("第%d号哲学家拿到第%d号筷子，时间是%s\\n",     \\
           k, j, getct(ct));

    sleep(5);
    sem_wait(&sema_chp[k]);
    printf("第%d号哲学家拿到第%d号筷子，时间是%s\\n",     \\
           k, k, getct(ct));

    result[k]++;
    printf("第%d号哲学家第%d次进食，时间是%s\\n",         \\
           k, result[k], getct(ct));

    sem_post(&sema_chp[k]);
    sem_post(&sema_chp[j]);

    sem_post(&sema_cct);
    printf("第%d号哲学家归还进食许可证，时间是%s\\n",         \\
           k, getct(ct));

  }

  printf("线程%.8x%.8x，第%d号哲学家用餐结束，时间是%s\\n", \\
           thdid, k, getct(ct));

}

int main(int argc, char **argv) {

  int                   i=0;
  int                   rc=0;

  pthread_t             threadid[10];
  thread_parm_t         *(parm[PHLSPH]);
  pthread_attr_t        pta;

  sem_init(&sema_dta, 0, 0);
  sem_init(&sema_cct, 0, cct);
  for (i=0; i<PHLSPH; ++i) {
    result[i]=0;
    sem_init(&sema_chp[i], 0, 1);
  }

  for (i=0; i<PHLSPH; i++)
    parm[i] = malloc(sizeof(thread_parm_t));

  pthread_attr_init(&pta);
  pthread_attr_setdetachstate(&pta, PTHREAD_CREATE_JOINABLE);

  printf("Creating %d threads\\n", PHLSPH);
  for (i=0; i<PHLSPH; i++) {
    parm[i]->value = i;
    rc = pthread_create(&threadid[i], &pta,                  \\
                        threadfunc, (void *) parm[i]);
    checkResults("pthread_create()\\n", rc);
  }

  sleep(5);

  printf("Dinner starts\\n");
  for (i=0; i<PHLSPH; i++) {
    sem_post(&sema_dta);
    sleep(1.5);
  }

  for (i=0; i<PHLSPH; i++) {
    rc = pthread_join(threadid[i], NULL);
    checkResults("pthread_join()\\n", rc);
  }

  printf("Cleanup\\n");
  pthread_attr_destroy(&pta);
  sem_destroy(&sema_dta);
  sem_destroy(&sema_cct);
  for (i=0; i<PHLSPH; i++)
    sem_destroy(&sema_chp[i]);


  printf("Main completed\\n");
  return 0;
}

让我们再来运行一下。通过在命令行键入以下命令：

SBMJOB CMD(CALL PGM(*LIBL/PHILOSOPH1)) JOB(PHILOSOPH1) JOBD(QGPL/MULTIJOBD)

WRKACTJOB SBS(QBATCH)

可以找到我们提交的后台作业。然后针对该作业键入 12 这个选项，可以查看其所启动的五个线程的运行状态：

在五个线程之中，总有一到两个处于运行状态，并且所有的线程都能顺利运行完毕。

以下是作业正常结束后所生成的假脱机文件的内容：
Creating 5 threads
线程 0000000000000024 代表第 0 号哲学家
线程 0000000000000025 代表第 1 号哲学家
线程 0000000000000026 代表第 2 号哲学家
线程 0000000000000027 代表第 3 号哲学家
线程 0000000000000028 代表第 4 号哲学家
Dinner starts
第 4 号哲学家开动，时间是 1610923100.056784
第 4 号哲学家获得进食许可证，时间是 1610923100.056840
第 4 号哲学家拿到第 3 号筷子，时间是 1610923100.056848
第 3 号哲学家开动，时间是 1610923101.086840
第 3 号哲学家获得进食许可证，时间是 1610923101.086880
第 3 号哲学家拿到第 2 号筷子，时间是 1610923101.086888
第 0 号哲学家开动，时间是 1610923102.116904
第 1 号哲学家开动，时间是 1610923103.146968
第 2 号哲学家开动，时间是 1610923104.177032

。。。。。。

第 4 号哲学家第 10 次进食，时间是 1610923216.782728
第 4 号哲学家归还进食许可证，时间是 1610923216.782736
线程 0000000000000028 ，第 4 号哲学家用餐结束，时间是 1610923216.782744
第 1 号哲学家获得进食许可证，时间是 1610923216.782744
第 1 号哲学家拿到第 0 号筷子，时间是 1610923216.782768
第 3 号哲学家拿到第 3 号筷子，时间是 1610923220.748240
第 3 号哲学家第 10 次进食，时间是 1610923220.748288
第 3 号哲学家归还进食许可证，时间是 1610923220.748304
线程 0000000000000027 ，第 3 号哲学家用餐结束，时间是 1610923220.748312
第 0 号哲学家获得进食许可证，时间是 1610923220.748312
第 0 号哲学家拿到第 4 号筷子，时间是 1610923220.748336
第 1 号哲学家拿到第 1 号筷子，时间是 1610923221.812832
第 1 号哲学家第 10 次进食，时间是 1610923221.812864
第 1 号哲学家归还进食许可证，时间是 1610923221.812880
第 2 号哲学家获得进食许可证，时间是 1610923221.812880
线程 0000000000000025 ，第 1 号哲学家用餐结束，时间是 1610923221.812888
第 2 号哲学家拿到第 1 号筷子，时间是 1610923221.812896
第 0 号哲学家拿到第 0 号筷子，时间是 1610923225.778400
第 0 号哲学家第 10 次进食，时间是 1610923225.778440
第 0 号哲学家归还进食许可证，时间是 1610923225.778448
线程 0000000000000024 ，第 0 号哲学家用餐结束，时间是 1610923225.778456
第 2 号哲学家拿到第 2 号筷子，时间是 1610923226.842984
第 2 号哲学家第 10 次进食，时间是 1610923226.843024
第 2 号哲学家归还进食许可证，时间是 1610923226.843032
线程 0000000000000026 ，第 2 号哲学家用餐结束，时间是 1610923226.843040
Cleanup
Main completed

至此，我们通过使用信号量，成功地模拟和解决了哲学家用餐问题。只有理解了信号量当前值所代表供给和需求的含义，了解了涉及信号量的相关函数，才能正确而有效地利用好这一工具。

参考网站：

1，Knowledge Center – IBM i Programming - Multithreaded Applications
https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_73/rzahw/rzahwovepo.htm

2，Knowledge Center – Pthread APIs
https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_73/apis/rzah4mst.htm

3，Knowledge Center – Interprocess Communication APIs
https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_73/apis/unix3.htm

4，Knowledge Center - Synchronization techniques among threads
https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_73/rzahw/rzahwsynco.htm

哲学家用餐问题 IBM i 信号量多线程

著作权归作者所有

如果觉得我的文章对您有用，请点赞。您的支持将鼓励我继续创作！

添加新评论0 条评论

Ctrl+Enter 发表

匿名评论

在IBM i 上使用多线程和信号量来模拟和解决哲学家用餐问题

添加新评论0 条评论

作者其他文章

相关文章

相关问题