欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

哲学家就餐问题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 */

相关标签: 并行程序