使用信号量解决哲学家就餐僵局

Question

我正在尝试使用 C 中的信号量来解决哲学家就餐问题。下面是我的代码。在代码中，每根筷子都由一个信号量表示。每个哲学家都是一个过程。我使用的概念是在任何给定时间最多可以有 4 根筷子处于“拿起”状态，以避免死锁。这就是为什么我将 dt 设置为 4。请告诉我下面的代码是否正确以及逻辑是否合理

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sched.h>
#include <signal.h>
#include <sys/wait.h>
#include <time.h>
#include <semaphore.h>
#define STACKSIZE 10000
#define NUMPROCS 5
#define ROUNDS 10

sem_t dt,c1,c2,c3,c4,c5;

int child (void * philNum) {
    int* phil1 = (int *)philNum;
    int phil = *phil1;
    int i = 0 ;

    for ( ; i < ROUNDS ; i ++ ) {
        switch(phil){

            case 1:
                sem_wait(&dt);
                sem_wait(&c1);
                sem_wait(&c5);
            case 2:
                sem_wait(&dt);
                sem_wait(&c1);
                sem_wait(&c2);
            case 3:
                sem_wait(&dt);
                sem_wait(&c3);
                sem_wait(&c2);
            case 4:
                sem_wait(&dt);
                sem_wait(&c4);
                sem_wait(&c3);
            case 5:
                sem_wait(&dt);
                sem_wait(&c4);
                sem_wait(&c5);
            default:
                perror(NULL);
                exit(1);
        }

        // Start of critical section -- 
        int sleeptime = rand()%20000 ;
        if ( sleeptime > 10000 ) usleep(sleeptime) ;

        // exit protocol here
        switch(phil){

            case 1:
                sem_post(&dt);
                sem_post(&c1);
                sem_post(&c5);
            case 2:
                sem_post(&dt);
                sem_post(&c1);
                sem_post(&c2);
            case 3:
                sem_post(&dt);
                sem_post(&c3);
                sem_post(&c2);
            case 4:
                sem_post(&dt);
                sem_post(&c4);
                sem_post(&c3);
            case 5:
                sem_post(&dt);
                sem_post(&c4);
                sem_post(&c5);
            default:
                perror(NULL);
                exit(1);
        }

    }
    return 0 ;
}

int main ( int argc, char ** argv ) {
    int i, num ;
    int *pt= (int *)malloc(sizeof(int));
    void * p ;
    srand(time(NULL));
    sem_init(&c1,1,1);
    sem_init(&c2,1,1);
    sem_init(&c3,1,1);
    sem_init(&c4,1,1);
    sem_init(&c5,1,1);
    sem_init(&dt,1,4); //only 4 chopsticks can be picked up at a time. 5th one has to wait anyways as he cant eat with one chopstick
    for ( i = 0 ; i < NUMPROCS ; i ++ ) {
        p = malloc(STACKSIZE) ;
        if ( p == NULL ) {
            printf("Error allocating memory\n") ;
            exit(1) ;
        }
        *pt = i+1;

        int c = clone(child,p+STACKSIZE-1,CLONE_VM|SIGCHLD,(void *)pt,NULL) ;
        if ( c < 0 ) {
            perror(NULL) ;
            exit(1) ;
        }
    }
    for ( ; i > 0 ; i -- ) wait(NULL) ;

    return 0 ;
}

Answer 1

你的案子正在败诉。

Answer 2

我在这里看到一个问题（但它与您正在处理的问题的并行性并不真正相关）：

srand(time(NULL));

在您的 clone 调用之前。基本上，进程的每个克隆都将具有相同的随机种子。因此，任何对 rand 的调用，假设它们以相同的顺序发生，都将产生相同的结果“随机”数。

您可能应该做的是使随机种子依赖于进程 ID，并在克隆出各个进程后进行初始化。这样你就会得到你所期望的随机行为。

至于整个算法的正确性......你尝试过运行它吗？