哲学家就餐问题OpenMP解决
程序员文章站
2024-02-26 11:02:10
...
1 问题描述:
假设有五位哲学家围坐在一张圆形餐桌旁,每两个哲学家之间有一只筷子。因为用一根筷子很难吃东西,规定哲学家必须用两根筷子吃东西。
2 分析
以下程序使用三种解决方案实现:semaphore, noorder, nodeadlock
/**
* Using OpenMP and C to realize dinning philosopher problem.
*
* Three mode of solution function are provided:
* semaphore, noorder, nodeadlock
*
* gcc -g -Wall -fopenmp -o philosophers mp_dinning_philosopher.c
* ./philosophers semaphore 10
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <omp.h>
#include <semaphore.h>
#include <time.h>
#define MSG_MAX 200
int thread_count;
void* Order(void);
void* NoOrder(void);
void* NoDeadLock(void);
void* Usage(char* prog_name);
sem_t* semaphores;
int main(int argc, char *argv[]){
long thread;
void (*dine_func)();
char* func_name;
pthread_t* thread_handles;
/* Get dinning mode */
func_name = argv[1];
/* Get number of threads. */
thread_count = strtol(argv[2], NULL, 10);
/* Allocate memory for pthread instance. */
thread_handles = malloc(thread_count*sizeof(pthread_t));
/* Allocate memory for semaphores. */
semaphores = malloc(thread_count*sizeof(sem_t));
if (strcmp(func_name, "semaphore")==0){
*(int*)&dine_func=(int)Order;
/* Initialize semaphores to 0 (locked) except last one. */
for (thread = 0; thread < thread_count-1; thread++)
sem_init(&semaphores[thread], 0, 0);
sem_init(&semaphores[thread], 0, 1);
}else if (strcmp(func_name, "noorder")==0){
*(int*)&dine_func=(int)NoOrder;
/* Initialize all semaphores to 1 (unlocked). */
for (thread = 0; thread < thread_count; thread++)
sem_init(&semaphores[thread], 0, 1);
}else if (strcmp(func_name, "nodeadlock")==0){
*(int*)&dine_func=(int)NoDeadLock;
/* Initialize all semaphores to 1 (unlocked). */
for (thread = 0; thread < thread_count; thread++)
sem_init(&semaphores[thread], 0, 1);
}else
Usage(argv[0]);
# pragma omp parallel num_threads(thread_count)
(*dine_func)();
/* Destroy semaphores. */
for (thread = 0; thread < thread_count; thread++)
sem_destroy(&semaphores[thread]);
free(semaphores);
free(thread_handles);
return 0;
}
/*--------------------------------------------------------------------
* Function: Order
* Purpose: Philosophers dinning in order.
*/
void* Order(void){
int my_rank = omp_get_thread_num();
int thread_count = omp_get_num_threads();
int fork_r = my_rank;
int fork_l = (my_rank+thread_count-1)%thread_count;
char* my_msg = malloc(MSG_MAX * sizeof(char));
sem_wait(&semaphores[fork_l]);
sprintf(my_msg, "Philosopher %d: I get fork %d and fork %d.\n", my_rank, fork_l, fork_r);
printf("%s\n", my_msg);
sem_post(&semaphores[fork_r]);
return NULL;
}
/*--------------------------------------------------------------------
* Function: NoOrder
* Purpose: Philosophers dinning in random (may exist deadlock).
*/
void* NoOrder(void){
int my_rank = omp_get_thread_num();
int thread_count = omp_get_num_threads();
int fork_r = my_rank;
int fork_l = (my_rank+thread_count-1)%thread_count;
char* my_msg = malloc(MSG_MAX * sizeof(char));
sem_wait(&semaphores[fork_r]);
sem_wait(&semaphores[fork_l]);
sprintf(my_msg, "Philosopher %d: I get fork %d and fork %d.\n", my_rank, fork_l, fork_r);
printf("%s\n", my_msg);
sem_post(&semaphores[fork_r]);
sem_post(&semaphores[fork_l]);
return NULL;
}
/*--------------------------------------------------------------------
* Function: NoDeadLock
* Purpose: Philosophers dinning in random (no deadlock).
*/
void* NoDeadLock(void){
int my_rank = omp_get_thread_num();
int thread_count = omp_get_num_threads();
int fork_r = (my_rank+1)%thread_count;
int fork_m = my_rank;
int fork_l = (my_rank+thread_count-1)%thread_count;
char* my_msg = malloc(MSG_MAX * sizeof(char));
sem_wait(&semaphores[fork_m]);
int value_r = sem_trywait(&semaphores[fork_r]);
int value_l = sem_trywait(&semaphores[fork_l]);
sprintf(my_msg, "Philosopher %d: I get fork %d and fork %d.\n", my_rank, fork_l, fork_m);
printf("%s\n", my_msg);
if(value_r==0)sem_post(&semaphores[fork_r]);
if(value_l==0)sem_post(&semaphores[fork_l]);
sem_post(&semaphores[fork_m]);
return NULL;
}
/*--------------------------------------------------------------------
* Function: Usage
* Purpose: Print command line for function and terminate
* In arg: prog_name
*/
void* Usage(char* prog_name){
fprintf(stderr, "usage: %s <mode of dinning> <number of threads>\n", prog_name);
exit(0);
}/* exit */