刚刚读完《Linux C 一站式编程》,所以就把最后一个练习题答案发出来,作为纪念。

题目

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

假设哲学家编号 A、B、C、D、E,筷子编号 1、2、3、4、5,如图:

thread.philosopher

分析

哲学家就餐问题(Dining philosophers problem)是在计算机科学中的一个经典问题,用来演示在并发计算中多线程同步(Synchronization)时产生的问题。这个问题可以用来解释死結和资源耗尽。

我们使用五个互斥锁 mutex 来表示五根筷子,五个哲学家就是五个单独的线程,思考rand()%10秒,然后先拿左手边的筷子再拿右手边的筷子(筷子这种资源可以用mutex表示),有任何一边拿不到就一直等着,全拿到就吃饭rand()%10秒,然后放下筷子。

代码

#include "bin.h"

#define THINK sleep(rand() % 10)
#define DINING sleep(rand() % 10)

struct arg {
	char id;
	pthread_mutex_t *left, *right;
	int l, r;
};

pthread_mutex_t chopstick1, chopstick2, chopstick3, chopstick4, chopstick5;

void Pthread_create(pthread_t *thread, void *(* func)(void *),
		struct arg *chopsticks);
void *philosopher(void *chopsticks);

int main()
{
	pthread_t A, B, C, D, E;
	pthread_mutex_init(&chopstick1, NULL);
	pthread_mutex_init(&chopstick2, NULL);
	pthread_mutex_init(&chopstick3, NULL);
	pthread_mutex_init(&chopstick4, NULL);
	pthread_mutex_init(&chopstick5, NULL);
	struct arg As = {'A', chopstick5, chopstick1, 5, 1},
		   Bs = {'B', &chopstick1, &chopstick2, 1, 2},
		   Cs = {'C', &chopstick2, &chopstick3, 2, 3},
		   Ds = {'D', &chopstick3, &chopstick4, 3, 4},
		   Es = {'E', &chopstick4, &chopstick5, 4, 5};

	Pthread_create(&A, philosopher, &As);
	Pthread_create(&B, philosopher, &Bs);
	Pthread_create(&C, philosopher, &Cs);
	Pthread_create(&D, philosopher, &Ds);
	Pthread_create(&E, philosopher, &Es);

	while (1)
            ;

	return 0;
}

void Pthread_create(pthread_t *tid, void *(* func)(void *),
		struct arg *chopsticks)
{
	if (pthread_create(tid, NULL, func, (void *) chopsticks) != 0)
		perror("pthread_create error");
}

void *philosopher(void *chopsticks)
{
	struct arg *chops = (struct arg *) chopsticks;

    pthread_detach(pthread_self());
	srand(time(0));
	while (1) {
		THINK;

		pthread_mutex_lock(chops->left);
		printf("Philosopher %c fecthes chopstick %d\n", chops->id, chops->l);
		pthread_mutex_lock(chops->right);
		printf("Philosopher %c fecthes chopstick %d\n", chops->id, chops->r);

		DINING;

		pthread_mutex_unlock(chops->left);
		pthread_mutex_unlock(chops->right);
		printf("Philosopher %c releases chopsticks %d %d\n",
				chops->id, chops->l, chops->r);
	}
}

必要的头文件我已经放在 bin.h 里面了。

运行结果大概是这样的:

Philosopher A fecthes chopstick 5
Philosopher A fecthes chopstick 1
Philosopher A releases chopsticks 5 1
Philosopher B fecthes chopstick 1
Philosopher B fecthes chopstick 2
Philosopher B releases chopsticks 1 2
Philosopher C fecthes chopstick 2
Philosopher D fecthes chopstick 3
Philosopher E fecthes chopstick 4
Philosopher E fecthes chopstick 5
Philosopher E releases chopsticks 4 5
Philosopher D fecthes chopstick 4
Philosopher A fecthes chopstick 5
Philosopher A fecthes chopstick 1
Philosopher A releases chopsticks 5 1
Philosopher B fecthes chopstick 1
Philosopher D releases chopsticks 3 4
Philosopher C fecthes chopstick 3
Philosopher E fecthes chopstick 4
Philosopher E fecthes chopstick 5
Philosopher E releases chopsticks 4 5
Philosopher A fecthes chopstick 5
Philosopher E fecthes chopstick 4
Philosopher C releases chopsticks 2 3
Philosopher B fecthes chopstick 2
Philosopher D fecthes chopstick 3
Philosopher B releases chopsticks 1 2
Philosopher A fecthes chopstick 1
^C

看起来一切正常,但是,我把思考和就餐用时都调小之后,也就是把两个宏定义中的 10 变成 1:

Philosopher B fecthes chopstick 1
Philosopher D fecthes chopstick 3
Philosopher E fecthes chopstick 4
Philosopher C fecthes chopstick 2
Philosopher A fecthes chopstick 5

然后就没反应了,显然,死锁!每个线程都在等另一个线程释放资源。

解法

可以让每个哲学家,在只有可以同时得到两个筷子的时候,才开始就餐,否则就等待,这样可以完全避免死锁问题。

#include "bin.h"

#define THINK sleep(rand() % 1)
#define DINING sleep(rand() % 1)

...

int released_chops[5];

int main()
{
	...
}

...

void *philosopher(void *chopsticks)
{
	struct arg *chops = (struct arg *) chopsticks;

	srand(time(0));
	while (1) {
		THINK;

		while (1) {
			if (released_chops[chops->l - 1] || released_chops[chops->r - 1]) {
				sleep(1);
			} else {
				released_chops[chops->l - 1] = released_chops[chops->r - 1] = 1;
				pthread_mutex_lock(chops->left);
				pthread_mutex_lock(chops->right);
				printf("Philosopher %c fecthes chopsticks %d %d\n",
					chops->id, chops->l, chops->r);
				break;
			}
		}

		DINING;

		released_chops[chops->l - 1] = released_chops[chops->r - 1] = 0;
		pthread_mutex_unlock(chops->left);
		pthread_mutex_unlock(chops->right);
		printf("Philosopher %c releases chopsticks %d %d\n",
				chops->id, chops->l, chops->r);
	}
}

设置了一个数组,每个元素表示一个筷子是否可用(0 可用,1 不可用)。

结果:

Philosopher B fecthes chopsticks 1 2
Philosopher D fecthes chopsticks 3 4
Philosopher D releases chopsticks 3 4
Philosopher E fecthes chopsticks 4 5
Philosopher E releases chopsticks 4 5
Philosopher E fecthes chopsticks 4 5
Philosopher B releases chopsticks 1 2
Philosopher C fecthes chopsticks 2 3
Philosopher C releases chopsticks 2 3
Philosopher B fecthes chopsticks 1 2
Philosopher E releases chopsticks 4 5
Philosopher D fecthes chopsticks 3 4
Philosopher D releases chopsticks 3 4
Philosopher B releases chopsticks 1 2
Philosopher B fecthes chopsticks 1 2
Philosopher E fecthes chopsticks 4 5
Philosopher B releases chopsticks 1 2
Philosopher C fecthes chopsticks 2 3
Philosopher E releases chopsticks 4 5
Philosopher A fecthes chopsticks 5 1
Philosopher A releases chopsticks 5 1
...

非常好,但这并不是最好的解法,因为必须轮询筷子是否可用,会影响并发性,所以我们也有其他的解决办法。
比如:Dining philosophers problem - wiki