トークンを使用した哲学者の規制

次のリストは、トークンシステムを使用する修正バージョンの食事する哲学者プログラムを示します。このソリューションには 4 つのトークン (食事する人数より 1 少ない) が組み入れられ、したがって同時に 4 人の哲学者しか食事できません。このバージョンのプログラムは din_philo_fix1.c と呼ばれます。

     1  /*
     2   * Copyright (c) 2006, 2010, Oracle and/or its affiliates. All Rights Reserved.
     3   * @(#)din_philo_fix1.c 1.3 (Oracle) 10/03/26
     4   */
     5
     6  #include <pthread.h>
     7  #include <stdio.h>
     8  #include <unistd.h>
     9  #include <stdlib.h>
    10  #include <errno.h>
    11  #include <assert.h>
    12
    13  #define PHILOS 5
    14  #define DELAY 5000
    15  #define FOOD 100
    16
    17  void *philosopher (void *id);
    18  void grab_chopstick (int,
    19                       int,
    20                       char *);
    21  void down_chopsticks (int,
    22                        int);
    23  int food_on_table ();
    24  void get_token ();
    25  void return_token ();
    26
    27  pthread_mutex_t chopstick[PHILOS];
    28  pthread_t philo[PHILOS];
    29  pthread_mutex_t food_lock;
    30  pthread_mutex_t num_can_eat_lock;
    31  int sleep_seconds = 0;
    32  uint32_t num_can_eat = PHILOS - 1;
    33
    34
    35  int
    36  main (int argn,
    37        char **argv)
    38  {
    39      int i;
    40
    41      pthread_mutex_init (&food_lock, NULL);
    42      pthread_mutex_init (&num_can_eat_lock, NULL);
    43      for (i = 0; i < PHILOS; i++)
    44          pthread_mutex_init (&chopstick[i], NULL);
    45      for (i = 0; i < PHILOS; i++)
    46          pthread_create (&philo[i], NULL, philosopher, (void *)i);
    47      for (i = 0; i < PHILOS; i++)
    48          pthread_join (philo[i], NULL);
    49      return 0;
    50  }
    51
    52  void *
    53  philosopher (void *num)
    54  {
    55      int id;
    56      int i, left_chopstick, right_chopstick, f;
    57
    58      id = (int)num;
    59      printf ("Philosopher %d is done thinking and now ready to eat.\n", id);
    60      right_chopstick = id;
    61      left_chopstick = id + 1;
    62
    63      /* Wrap around the chopsticks. */
    64      if (left_chopstick == PHILOS)
    65          left_chopstick = 0;
    66
    67      while (f = food_on_table ()) {
    68          get_token ();
    69
    70          grab_chopstick (id, right_chopstick, "right ");
    71          grab_chopstick (id, left_chopstick, "left");
    72
    73          printf ("Philosopher %d: eating.\n", id);
    74          usleep (DELAY * (FOOD - f + 1));
    75          down_chopsticks (left_chopstick, right_chopstick);
    76
    77          return_token ();
    78      }
    79
    80      printf ("Philosopher %d is done eating.\n", id);
    81      return (NULL);
    82  }
    83
    84  int
    85  food_on_table ()
    86  {
    87      static int food = FOOD;
    88      int myfood;
    89
    90      pthread_mutex_lock (&food_lock);
    91      if (food > 0) {
    92          food--;
    93      }
    94      myfood = food;
    95      pthread_mutex_unlock (&food_lock);
    96      return myfood;
    97  }
    98
    99  void
   100  grab_chopstick (int phil,
   101                  int c,
   102                  char *hand)
   103  {
   104      pthread_mutex_lock (&chopstick[c]);
   105      printf ("Philosopher %d: got %s chopstick %d\n", phil, hand, c);
   106  }
   107
   108
   109
   110  void
   111  down_chopsticks (int c1,
   112                   int c2)
   113  {
   114      pthread_mutex_unlock (&chopstick[c1]);
   115      pthread_mutex_unlock (&chopstick[c2]);
   116  }
   117
   118
   119  void
   120  get_token ()
   121  {
   122      int successful = 0;
   123
   124      while (!successful) {
   125          pthread_mutex_lock (&num_can_eat_lock);
   126          if (num_can_eat > 0) {
   127              num_can_eat--;
   128              successful = 1;
   129          }
   130          else {
   131              successful = 0;
   132          }
   133          pthread_mutex_unlock (&num_can_eat_lock);
   134      }
   135  }
   136
   137  void
   138  return_token ()
   139  {
   140      pthread_mutex_lock (&num_can_eat_lock);
   141      num_can_eat++;
   142      pthread_mutex_unlock (&num_can_eat_lock);
   143  }

この修正バージョンの食事する哲学者プログラムをコンパイルし、複数回それを実行してみます。トークンのシステムは、箸を使用して食事しようとする人の人数を制限し、これによって実デッドロックおよび潜在的デッドロックを回避します。

コンパイルするには、次のコマンドを使用します。

% cc -g -o din_philo_fix1 din_philo_fix1.c

実験結果を収集する

% collect -r deadlock -o din_philo_fix1.1.er din_philo_fix1 

誤検知レポート

トークンのシステムを使用するときでも、スレッドアナライザは、まったく存在していない場合にもこの実装の潜在的デッドロックを報告します。これが誤検知です。潜在的デッドロックについて詳しく説明した次のスクリーンショットを見てください。

図 3-5  潜在的デッドロックの誤検知レポート

チェーンの最初のスレッド (スレッド #2) を選択し、「デュアルソース」ビューをクリックして、スレッド #2 がアドレス 0x216a8 でロックを保持していたソースコード位置と、アドレス 0x216c0 でロックを要求したソースコードでの位置を確認します。次の図には、スレッド #2 の「デュアルソース」ビューが示されています。

図 3-6  誤検知の潜在的デッドロックのソース

din_philo_fix1.c の get_token() 関数は、while ループを使用してスレッドを同期します。スレッドは、トークンの取得に成功するまで、while ループ外に出ません (これは、num_can_eat が 0 より大きいときに起こります)。while ループは同時に食事する人を 4 人に制限します。ただし、while ループによって実装された同期は、スレッドアナライザには認識されません。スレッドアナライザは、5 人の哲学者全員が同時に箸を掴んで食事しようとしていると想定しているので、潜在的デッドロックを報告します。次のセクションでは、スレッドアナライザが認識する同期を使用することによって、同時に食事する人の人数を制限する方法について詳しく説明します。