0

私は、教授がセマフォを使用してダイニング哲学者の問題を解決するための解決策を求めている課題に取り組んでいます。

これまでの私のコードは次のとおりです。

#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <semaphore.h>

#define MAX_THINKING_TIME 1500  /* maximum thinking time in milliseconds */
#define MIN_THINKING_TIME 1000  /* minimum thinking time in milliseconds */
#define MAX_EATING_TIME   1000  /* maximum eating time in milliseconds */
#define MIN_EATING_TIME   750   /* minimum eating time in milliseconds */

/*
 * Macros to encapsulate the POSIX semaphore functions.
 */
#define semaphore_create(s,v)   sem_init( &s, 0, v )
#define semaphore_wait(s)           sem_wait( &s )
#define semaphore_signal(s)         sem_post( &s )
#define semaphore_release(s)    sem_destroy( &s )
typedef sem_t semaphore;

// Each chopstick is represented by a semaphore (shared between all processes).
semaphore *chopstick;

int NUM_PHILOSOPHERS; /* number of philosophers */
int NUM_REPETITIONS;  /* number of cycles */

/*
 * Generating a random number within a range.
 */
unsigned int randr(unsigned int min, unsigned int max)
{
    double scaled = (double)rand()/RAND_MAX;
    return (max - min +1) * scaled + min;
}

/*
 * To pick up his chopsticks, a philosopher does a semaphore wait on each.
 * Alternating order prevents deadlock.
 */
void pickup_chopsticks(int index)
{
    if(index % 2 == 0) /* Even number: Left, then right */
    {
        semaphore_wait(chopstick[(index+1) % NUM_PHILOSOPHERS]);
        printf("Philosopher #%d: I am picking up the left chopstick!\n", index+1);
        semaphore_wait(chopstick[index]);
        printf("Philosopher #%d: I am picking up the right chopstick!\n", index+1);
    }
    else /* Odd number: Right, then left */
    {
        semaphore_wait(chopstick[index]);
        printf("Philosopher #%d: I am picking up the right chopstick!\n", index+1);
        semaphore_wait(chopstick[(index+1) % NUM_PHILOSOPHERS]);
        printf("Philosopher #%d: I am picking up the left chopstick!\n", index+1);
    }
}

/*
 * To drop his chopsticks, a philosopher does a semaphore signal on each.
 * Order does not matter.
 */
void drop_chopsticks(int index)
{
    printf("Philosopher #%d: I am dropping the right chopstick!\n", index+1);
    semaphore_signal(chopstick[index]);
    printf("Philosopher #%d: I am dropping the left chopstick!\n", index+1);
    semaphore_signal(chopstick[(index+1) % NUM_PHILOSOPHERS]);
}

/*
 * Simulate a philosopher - endlessly cycling between eating and thinking
 * until his "life" is over.
 */
void start_philosopher(int index)
{
    int i; // A counter.

    for(i = 0; i < NUM_REPETITIONS; i++)
    {
        /* Hungry */
        printf("Philosopher #%d (Cycle #%d): I am hungry!\n", index+1, i+1);
        pickup_chopsticks(index);

        /* Eating */
        printf("Philosopher #%d (Cycle #%d): I am eating!\n", index+1, i+1);
        usleep(1000 * randr(MIN_EATING_TIME, MAX_EATING_TIME));
        drop_chopsticks(index);

        /* Thinking */
        printf("Philosopher #%d (Cycle #%d): I am thinking!\n", index+1, i+1);
        usleep(1000 * randr(MIN_THINKING_TIME, MAX_THINKING_TIME));
    }

    printf("Philosopher #%d: I am dead!\n", index+1);
    exit(0);
}

/*
 * The main function.
 */
int main(int argc, char *argv[])
{

    // If the input arguments are not 2 elements, display a message and return.
    if(argc != 3)
    {
        printf("You have to insert arguments in the form:\n");
        printf("Number_of_Philosopher Number_of_repeats\n");
        return -1;
    }

    // Set value of NUM_PHILOSOPHERS and NUM_REPETITIONS from the user input.
    NUM_PHILOSOPHERS = atoi(argv[1]);
    NUM_REPETITIONS  = atoi(argv[2]);
    int i; // A counter.

    // Allocate memory for the semaphores.
    chopstick = malloc(NUM_PHILOSOPHERS * sizeof(semaphore));

    // Create semaphores to represent "one user at a time" chopsticks.
    for(i = 0; i < NUM_PHILOSOPHERS; i++)
        semaphore_create(chopstick[i], 1);

    // Create n processes for n philosophers
    for(i = 0; i < NUM_PHILOSOPHERS; i++)
    {
        if(fork() == 0) start_philosopher(i);
        else wait();
    }
    // Release semaphore resources.
    for(i = 0; i < NUM_PHILOSOPHERS; i++)
        semaphore_release(chopstick[i]);

    // Free the memory.
    free(chopstick);

    return 0;
}

実行すると、次のようになりました。

$ ./run 2 2
Philosopher #1 (Cycle #1): I am hungry!
Philosopher #1: I am picking up the left chopstick!
Philosopher #1: I am picking up the right chopstick!
Philosopher #1 (Cycle #1): I am eating!
Philosopher #1: I am dropping the right chopstick!
Philosopher #1: I am dropping the left chopstick!
Philosopher #1 (Cycle #1): I am thinking!
Philosopher #1 (Cycle #2): I am hungry!
Philosopher #1: I am picking up the left chopstick!
Philosopher #1: I am picking up the right chopstick!
Philosopher #1 (Cycle #2): I am eating!
Philosopher #1: I am dropping the right chopstick!
Philosopher #1: I am dropping the left chopstick!
Philosopher #1 (Cycle #2): I am thinking!
Philosopher #1: I am dead!
Philosopher #2 (Cycle #1): I am hungry!
^Z
[6]+  Stopped                 ./run 2 2

ご覧のとおり、次の 2 つの問題があります。

  • プロセス n+1 は、プロセス n が完了しない限り実行されません。
  • プログラムを実行する前のテストでは、2 番目の哲学者が箸を持ち上げるように要求しているときに、プログラムが動かなくなりました。どうやらセマフォに信号が送られておらず、哲学者が信号を待っているようです。

プログラムを修正するのを手伝ってくれませんか?

4

2 に答える 2

1

問題 (1) は、fork を実行するループの外に wait() を移動することで解決されます。

問題 (2) は、mmap() を使用して MAP_SHARED フラグを使用してメモリを割り当て、sem_init 呼び出しに sem_init(&s, 1, v) オプションを使用することで解決されます。 2 番目のオプションは、それがイントラプロセス用であることを意味します (つまり、fork を使用する子でなくても、同じ pid にあります)。

chopstick = mmap(0, NUM_PHILOSOPHERS * sizeof(semaphore), PROT_READ | PROT_WRITE, MAP_SHARED | MAP_ANONYMOUS, -1, 0);
于 2011-11-25T18:21:54.160 に答える
1

新しいプロセスをフォークするループでは、新しい親プロセス ( fork0 以外を返す) で、新しいプロセスが終了するのを待ちます。をドロップして、ループの外elseで呼び出します。wait

于 2011-11-25T18:16:16.533 に答える