обедающие философы с тупиком и голодом - PullRequest
Новая
       105

обедающие философы с тупиком и голодом

2 голосов
/ 27 мая 2020

это решение проблемы обедающих философов от geeksforgeeks с использованием семафоров: 

#include <pthread.h> 
#include <semaphore.h> 
#include <stdio.h> 
#include <unistd.h>

#define N 5 
#define THINKING 2 
#define HUNGRY 1 
#define EATING 0 
#define LEFT (phnum + 4) % N 
#define RIGHT (phnum + 1) % N 

int state[N]; 
int phil[N] = { 0, 1, 2, 3, 4 }; 

sem_t mutex; 
sem_t S[N]; 

void test(int phnum) 
{ 
    if (state[phnum] == HUNGRY 
        && state[LEFT] != EATING 
        && state[RIGHT] != EATING) { 
        // state that eating 
        state[phnum] = EATING; 

        sleep(2); 

        printf("Philosopher %d takes fork %d and %d\n", 
                    phnum + 1, LEFT + 1, phnum + 1); 

        printf("Philosopher %d is Eating\n", phnum + 1); 

        // sem_post(&S[phnum]) has no effect 
        // during takefork 
        // used to wake up hungry philosophers 
        // during putfork 
        sem_post(&S[phnum]); 
    } 
} 

// take up chopsticks 
void take_fork(int phnum) 
{ 

    sem_wait(&mutex); 

    // state that hungry 
    state[phnum] = HUNGRY; 

    printf("Philosopher %d is Hungry\n", phnum + 1); 

    // eat if neighbours are not eating 
    test(phnum); 

    sem_post(&mutex); 

    // if unable to eat wait to be signalled 
    sem_wait(&S[phnum]); 

    sleep(1); 
} 

// put down chopsticks 
void put_fork(int phnum) 
{ 

    sem_wait(&mutex); 

    // state that thinking 
    state[phnum] = THINKING; 

    printf("Philosopher %d putting fork %d and %d down\n", 
        phnum + 1, LEFT + 1, phnum + 1); 
    printf("Philosopher %d is thinking\n", phnum + 1); 

    test(LEFT); 
    test(RIGHT); 

    sem_post(&mutex); 
} 

void* philospher(void* num) 
{ 

    while (1) { 

        int* i = num; 

        sleep(1); 

        take_fork(*i); 

        sleep(0); 

        put_fork(*i); 
    } 
} 

int main() 
{ 

    int i; 
    pthread_t thread_id[N]; 

    // initialize the mutexes 
    sem_init(&mutex, 0, 1); 

    for (i = 0; i < N; i++) 

        sem_init(&S[i], 0, 0); 

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

        // create philosopher processes 
        pthread_create(&thread_id[i], NULL, 
                    philospher, &phil[i]); 

        printf("Philosopher %d is thinking\n", i + 1); 
    } 

    for (i = 0; i < N; i++) 

        pthread_join(thread_id[i], NULL); 
}

https://www.geeksforgeeks.org/dining-philosopher-problem-using-semaphores/

этот код имеет низкую вероятность тупиковой блокировки и голодание, я хочу изменить его, чтобы с большой вероятностью у него был тупик, лайвлок или голод, как я могу это сделать?

также как я могу гарантировать, что это решение не будет иметь этих проблем на 100% (если возможно)

1 Ответ

0 голосов
/ 31 мая 2020

Хорошо, во-первых, лучшее решение, которое я знаю для проблемы обедающих философов, это (из современных операционных систем - 4-е издание Таннебаума и Бос): 

#define TRUE 1
#define N 5
#define LEFT (i+N-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2

typedef int semaphore;
int state[N];
semaphore mutex = 1;
semaphore s[N];

void
philosopher(int i){
  while(TRUE){
    think();
    take_forks(i);
    eat();
    put_forks(i)
  }
}

void
take_forks(int i){
  down(&mutex);
  state[i] = HUNGRY;
  test(i);
  up(&mutex);
  down(&s[i]);
}

void
put_forks(i){
  down(&mutex);
  state[i] = THINKING;
  test(LEFT);
  test(RIGHT);
  up(&mutex);
}

void
test(int i){
  if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING){
    state[i] = EATING;
    up(&s[i]);
  }
}

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

  #define N 5

  void philosopher(int i){
    while(TRUE){
      think();
      take_fork(i);
      take_fork((i+1)%N);
      eat();
      put_fork(i);
      put_fork((i+1)%N);
    }
  }

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

...