2

我有一个关于餐饮哲学家计划死锁的作业。我被要求制作一个名为“sections1.c”的文件，该文件存在死锁问题，在完成创建死锁后，我将复制代码并解决文件“sections2.c”中的死锁条件。我的老师让我们用 MDAT 编程。MDAT 应该像信号量和 pthread 函数一样运行，正如他在 M​​DAT 指南中给我们的那样。

void mdat_mutex_init(const char *name, pthread_mutex_t *lock,
pthread_mutexattr_t *attr);

void mdat_mutex_lock(pthread_mutex_t *lp);

void mdat_mutex_unlock(pthread_mutex_t *lp);

void mdat_sem_init(const char *name, sem_t *sem, int pshared, int value);

void mdat_sem_wait(sem_t *sp);

void mdat_sem_post(sem_t *sp);

MDAT 应该负责调度程序并通过在运行时播种当前时间来随机调度踏板。

在我不允许编辑的主文件中，函数 sectionInitGlobals 运行一次，sectionRunPhilosopher 在每个 pthread_create 中运行一次。

一个问题可能是我以前从未使用过信号量，并且使用不正确。

//  sections1.c: mutual exclusion model sections

#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include "sections.h"
#include "mdat.h"

// TODO: Declare shared variables here
int numPhils;
sem_t * sem_arr;

void sectionInitGlobals(int numPhilosophers)
{
  // TODO: Complete this function
  int i;

  char char_arr[50];

  sem_t arr[numPhilosophers];

  numPhils = numPhilosophers;

  for(i = 0; i < numPhilosophers; i++)
  {
    sprintf(char_arr,"%d", i);
    mdat_sem_init(char_arr, &arr[i], 0, 0);
  }

  sem_arr = arr;
}

void sectionRunPhilosopher(int philosopherID, int numRounds)
{
  int lChopstick = philosopherID;
  int rChopstick;

  int left;
  int right;

  int i;
  int hasEaten;
  int hasLeft;
  int hasRight;

  if(philosopherID == 0)
    rChopstick = numPhils - 1;
  else
    rChopstick = philosopherID - 1;

  for(i = 0; i < numRounds; i++)
  {
    hasEaten = 0;
    hasLeft = 0;
    hasRight = 0;

    while(hasEaten == 0)
    {
      sem_getvalue(&sem_arr[lChopstick], &left);
      if(left >= 0 || hasLeft == 1)
      {
        hasLeft = 1;
      }
      else
      {
        mdat_sem_wait(&sem_arr[lChopstick]);
      }

      sem_getvalue(&sem_arr[rChopstick], &right);
      if(right >= 0 && hasLeft != 0)
      {
        hasRight = 1;
      }
      else
      {
        mdat_sem_wait(&sem_arr[rChopstick]);
      }

      if(hasLeft != 0 && hasRight != 0)
      {
        eat();
        hasEaten = 1;
        mdat_sem_post(&sem_arr[lChopstick]);
        mdat_sem_post(&sem_arr[rChopstick]);
      }
    }

    think();
  }
}

在测试我的代码时，我可以使用我想要的任意数量的线程和轮次运行它，但是，似乎使用更多线程可以保证死锁。当我用 100 个线程运行代码时，它每次都会遇到死锁，但是如果线程越多，它发生死锁的机会就不应该减少吗？

结果：

对于 16 个线程和 10 轮，死锁有时取决于调度程序。

使用 6 个线程和 5 轮，死锁发生率为 0%。

在 100 个线程和 5 轮的情况下，死锁的发生率为 100%。

编辑：

当没有发生死锁并且程序认为发生死锁时，跟踪文件结束：

无死锁：

THREAD: 3
SECTION: DoneRounds
MESSAGE: Thread 3 has completed
*******************************************************************************
|ID   |PROPERTY     |LOC  |SECTION      |STATUS       |WAITING ON             |
|0    |0            |19   |             |completed    |                       |
|1    |1            |19   |             |completed    |                       |
|2    |2            |19   |             |completed    |                       |
|3    |3            |19   |             |completed    |                       |
|4    |4            |19   |             |completed    |                       |
|5    |5            |19   |             |completed    |                       |
|6    |6            |19   |             |completed    |                       |
|7    |7            |19   |             |completed    |                       |
|8    |8            |19   |             |completed    |                       |
|9    |9            |19   |             |completed    |                       |
|10   |10           |19   |             |completed    |                       |
|11   |11           |19   |             |completed    |                       |
|12   |12           |19   |             |completed    |                       |
|13   |13           |19   |             |completed    |                       |
|14   |14           |19   |             |completed    |                       |
|15   |15           |19   |             |completed    |                       |
-------------------------------------------------------------------------------
|LOCK NAME                |STATUS       |WAITING THREADS                      |
|lock_a                   |unlocked     |                                     |
|lock_b                   |unlocked     |                                     |
-------------------------------------------------------------------------------
|SEMAPHORE NAME           |VALUE        |WAITING THREADS                      |
|0                        |20           |                                     |
|1                        |20           |                                     |
|2                        |20           |                                     |
|3                        |20           |                                     |
|4                        |20           |                                     |
|5                        |20           |                                     |
|6                        |20           |                                     |
|7                        |20           |                                     |
|8                        |20           |                                     |
|9                        |20           |                                     |
|10                       |20           |                                     |
|11                       |20           |                                     |
|12                       |20           |                                     |
|13                       |20           |                                     |
|14                       |20           |                                     |
|15                       |20           |                                     |
*******************************************************************************
***** Program Trace End *****

僵局：

THREAD: 13
SECTION: DoneRounds
MESSAGE: Thread 13 has completed
*******************************************************************************
|ID   |PROPERTY     |LOC  |SECTION      |STATUS       |WAITING ON             |
|0    |0            |19   |             |completed    |                       |
|1    |1            |32   |             |waiting-sem  |1                      |
|2    |2            |32   |             |waiting-sem  |2                      |
|3    |3            |38   |             |waiting-sem  |2                      |
|4    |4            |19   |             |completed    |                       |
|5    |5            |19   |             |completed    |                       |
|6    |6            |19   |             |completed    |                       |
|7    |7            |19   |             |completed    |                       |
|8    |8            |19   |             |completed    |                       |
|9    |9            |32   |             |waiting-sem  |9                      |
|10   |10           |38   |             |waiting-sem  |9                      |
|11   |11           |19   |             |completed    |                       |
|12   |12           |19   |             |completed    |                       |
|13   |13           |19   |             |completed    |                       |
|14   |14           |19   |             |completed    |                       |
|15   |15           |19   |             |completed    |                       |
-------------------------------------------------------------------------------
|LOCK NAME                |STATUS       |WAITING THREADS                      |
|lock_a                   |unlocked     |                                     |
|lock_b                   |unlocked     |                                     |
-------------------------------------------------------------------------------
|SEMAPHORE NAME           |VALUE        |WAITING THREADS                      |
|0                        |10           |                                     |
|1                        |-1           |1                                    |
|2                        |-2           |2 3                                  |
|3                        |10           |                                     |
|4                        |20           |                                     |
|5                        |20           |                                     |
|6                        |20           |                                     |
|7                        |20           |                                     |
|8                        |10           |                                     |
|9                        |-2           |9 10                                 |
|10                       |10           |                                     |
|11                       |20           |                                     |
|12                       |20           |                                     |
|13                       |20           |                                     |
|14                       |20           |                                     |
|15                       |20           |                                     |
*******************************************************************************
ERROR! VIOLATION: No ready threads to schedule - possible DEADLOCK
***** Program Trace End *****

回答后编辑

感谢mevets！最终代码：section1.c - 想要死锁

//  sections1.c: mutual exclusion model sections

#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include "sections.h"
#include "mdat.h"

// TODO: Declare shared variables here
int numPhils;
sem_t * sem_arr;

void sectionInitGlobals(int numPhilosophers)
{
  // TODO: Complete this function
  int i;

  char char_arr[50];

  sem_t arr[numPhilosophers];

  numPhils = numPhilosophers;

  for(i = 0; i < numPhilosophers; i++)
  {
    sprintf(char_arr,"%d", i);
    mdat_sem_init(char_arr, &arr[i], 0, 1);
  }

  sem_arr = arr;
}

void sectionRunPhilosopher(int philosopherID, int numRounds)
{
  int lChop = philosopherID;
  int rChop;

  int i;

  if(philosopherID == 0)
    rChop = numPhils - 1;
  else
    rChop = philosopherID - 1;

  for(i = 0; i < numRounds; i++)
  {
    mdat_sem_wait(&sem_arr[lChop]);
    mdat_sem_wait(&sem_arr[rChop]);
    eat();
    mdat_sem_post(&sem_arr[rChop]);
    mdat_sem_post(&sem_arr[lChop]);

    think();
  }
}

section2.c - 不想死锁

//  sections1.c: mutual exclusion model sections

#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include "sections.h"
#include "mdat.h"

// TODO: Declare shared variables here
int numPhils;
sem_t * sem_arr;

void sectionInitGlobals(int numPhilosophers)
{
  // TODO: Complete this function
  int i;

  char char_arr[50];

  sem_t arr[numPhilosophers];

  numPhils = numPhilosophers;

  for(i = 0; i < numPhilosophers; i++)
  {
    sprintf(char_arr,"%d", i);
    mdat_sem_init(char_arr, &arr[i], 0, 1);
  }

  sem_arr = arr;
}

void sectionRunPhilosopher(int philosopherID, int numRounds)
{
  int lChop = philosopherID;
  int rChop;

  int i;

  if(philosopherID == 0)
    rChop = numPhils - 1;
  else
    rChop = philosopherID - 1;

  for(i = 0; i < numRounds; i++)
  {
    if(philosopherID != numPhils - 1)
    {
      mdat_sem_wait(&sem_arr[lChop]);
      mdat_sem_wait(&sem_arr[rChop]);
      eat();
      mdat_sem_post(&sem_arr[rChop]);
      mdat_sem_post(&sem_arr[lChop]);
    }
    else
    {
      mdat_sem_wait(&sem_arr[rChop]);
      mdat_sem_wait(&sem_arr[lChop]);
      eat();
      mdat_sem_post(&sem_arr[lChop]);
      mdat_sem_post(&sem_arr[rChop]);
    }

    think();
  }
}
4

1 回答 1

2

经典的哲学家就餐问题有 N 个哲学家和 N 个叉子；但每个人需要 2 把叉子吃。给定的分叉信号量的最大值可能为 1 [可用]，最小值为 -1（一个有分叉，一个正在等待分叉）。你的叉子有 10 和 20 的值吗？

在你的逻辑中，你检查信号量的值，如果它 >= 0，你说你“拥有它”，然后继续检查另一个；但你没有。在您等待它之前，您没有信号量。在 eat()ing 之后，你向他们两个发帖，即使你可能从来没有等过他们中的任何一个。这就是为什么你对信号量有非常高的价值。

其次，当sem_get_value返回时，信号量的值可能已经改变。这是一个常见的同步问题，所以很常见它有一个名字：TOCTOU（检查时间到使用时间）。您需要使用基于操作做出决策的机制，而不仅仅是检查状态。

第三，您将其更改为有效地坐在一个循环中：

  sem_wait(left);
  sem_wait(right);
  eat();
  sem_post(right);
  sem_post(left);

您将遇到一个完全不同的同步问题，这就是餐饮哲学家要说明的问题。狩猎快乐！

于 2019-05-15T00:50:35.157 回答