Dining philosophers problem


哲学家就餐问题。这是由计算机科学家Dijkstra提出的经典死锁场景。原版的故事里有五个哲学家(不过我们写的程序可以有N个哲学家),这些哲学家们只做两件事--思考和吃饭,他们思考的时候不需要任何共享资源,但是吃饭的时候就必须使用餐具,而餐桌上的餐具是有限的,原版的故事里,餐具是叉子,吃饭的时候要用两把叉子把面条从碗里捞出来。很显然把叉子换成筷子会更合理,所以:一个哲学家需要两根筷子才能吃饭。现在引入问题的关键:这些哲学家很穷,只买得起五根筷子。他们坐成一圈,两个人的中间放一根筷子。哲学家吃饭的时候必须同时得到左手边和右手边的筷子。如果他身边的任何一位正在使用筷子,那他只有等着。
废话不多说,上代码

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

#define NUM 5
pthread_mutex_t chop1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t chop2 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t chop3 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t chop4 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t chop5 = PTHREAD_MUTEX_INITIALIZER;

void *philo_working(void *id) {
	int left_id[5] = {4, 0, 1, 2, 3};
	int right_id[5] = {0, 1, 2, 3, 4};
	while (1) {
		int philo_id = *((int*)(id));
		sleep(rand()%10);
		pthread_mutex_t chops[5] = {chop1, chop2, chop3, chop4, chop5};
		pthread_mutex_lock(&(chops[left_id[philo_id]]));
		printf("Philosopher %c fetches chopstick %d\n", (char)(philo_id+'A'), left_id[philo_id]+1);
		pthread_mutex_lock(&(chops[right_id[philo_id]]));
		printf("Philosopher %c fetches chopstick %d\n", (char)(philo_id+'A'), right_id[philo_id]+1);
		sleep(rand()%10);
		pthread_mutex_unlock(&(chops[right_id[philo_id]]));
		pthread_mutex_unlock(&(chops[left_id[philo_id]]));
		printf("Philosopher %c release chopsticks %d %d\n", (char)(philo_id+'A'), left_id[philo_id]+1, right_id[philo_id]+1);
	}
}

int main() {
	pthread_t philos[NUM];
	int counter[NUM] = {0, 1, 2, 3, 4};
	pthread_create(&(philos[counter[0]]), NULL, philo_working, counter);
	pthread_create(&(philos[counter[1]]), NULL, philo_working, counter+1);
	pthread_create(&(philos[counter[2]]), NULL, philo_working, counter+2);
	pthread_create(&(philos[counter[3]]), NULL, philo_working, counter+3);
	pthread_create(&(philos[counter[4]]), NULL, philo_working, counter+4);

	pthread_join(philos[counter[0]], NULL);
	pthread_join(philos[counter[1]], NULL);
	pthread_join(philos[counter[2]], NULL);
	pthread_join(philos[counter[3]], NULL);
	pthread_join(philos[counter[4]], NULL);
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s