Тупики в Си с семафорами - PullRequest
Новая
       49

Тупики в Си с семафорами

2 голосов
/ 15 мая 2019

У меня есть задание о взаимоблокировках для программы «Обедающие философы».Меня просят создать файл с именем "section1.c", в котором есть проблема взаимоблокировки, и после завершения создания взаимоблокировки я должен скопировать код и устранить условие взаимоблокировки в файле "section2.c".Мой учитель ведет программу с MDAT.MDAT должен работать точно так же, как семафоры и функции pthread, как он дал нам это в руководстве по MDAT. 

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();
  }
}

1 Ответ

1 голос
/ 15 мая 2019

У классической задачи Обеденных Философов есть N философов и N вилок; но каждому нужно 2 вилки, чтобы поесть. Заданный семафор разветвления может иметь максимальное значение 1 [доступно] и минимальное значение -1 (один имеет разветвление, другой ожидает на разветвлении). Ваши вилки имеют значения 10 и 20?

В вашей логике вы проверяете значение семафора, и если оно> = 0, вы говорите, что оно у вас есть, затем переходите к проверке другого; но у тебя его нет. У вас нет семафора, пока вы не наберете wait . После того, как вы съели (), вы отправляете сообщения обоим, даже если вы никогда не ожидали ни одного из них. Вот почему у вас безумно высокие значения для семафоров.

Во-вторых, ко времени возврата sem_get_value значение семафора могло измениться. Это распространенная проблема синхронизации, поэтому она часто имеет название: TOCTOU (время проверки - время использования). Вам нужно использовать механизмы, в которых вы принимаете решения, основанные на действиях, а не просто проверяете статус.

В-третьих, вы изменяете это, чтобы эффективно сидеть в цикле: 

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

У вас будет совершенно другая проблема с синхронизацией, которую призвана проиллюстрировать Обедающая философия. Удачной охоты!

...