哲学家进餐问题---操作系统经典进程同步互斥问题---详细讲解

介绍

哲学家进餐问题是操作系统中经典的进程同步和互斥问题。在这个问题中，有五位哲学家坐在圆桌旁，思考和进餐。每位哲学家之间有一把叉子，哲学家需要左右两边的叉子才能进餐。

1. 问题的描述：

   • 五位哲学家坐在圆桌旁，思考和进餐。
   • 每位哲学家之间有一把叉子。
   • 哲学家需要左右两边的叉子才能进餐。

2. 问题的分析：

   • 如果所有叉子都可用，哲学家们会交替地拿起左右两边的叉子进餐。
   • 如果某个时刻，一位哲学家左右两边的叉子都被其他哲学家占用，那么这位哲学家将无法进餐，导致死锁。

3. 解决方案：

   • 引入一个“监视器”来管理叉子的分配和释放。
   • 当一个哲学家想要进餐时，它必须先获得左右两边的叉子。如果叉子不可用，它必须等待。

分析：放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用，为了实现对筷子的互斥访问，可以用一个信号量表示筷子，由这五个信号量构成信号量数组。

记录型信号量

semaphore chopstick[5] = {1,1,1,1,1};
while(true)
{
	/*当哲学家饥饿时，总是先拿左边的筷子，再拿右边的筷子*/
	wait(chopstick[i]);
	wait(chopstick[(i+1)%5]);

	// 吃饭
 
	/*当哲学家进餐完成后，总是先放下左边的筷子，再放下右边的筷子*/
	signal(chopstick[i]);
	signal(chopstick[(i+1)%5]);
}

• 上述的代码可以保证不会有两个相邻的哲学家同时进餐，但却可能引起死锁的情况。假如五位哲学家同时饥饿而都拿起的左边的筷子，就会使五个信号量chopstick都为0，当他们试图去拿右手边的筷子时，都将无筷子而陷入无限期的等待。

为避免死锁，可以使用以下三种策略：

避免死锁策略一：

至多只允许四个哲学家同时进餐，以保证至少有一个哲学家能够进餐，最终总会释放出他所使用过的两支筷子，从而可使更多的哲学家进餐。定义信号量count，只允许4个哲学家同时进餐，这样就能保证至少有一个哲学家可以就餐。

semaphore chopstick[5]={1,1,1,1,1};
semaphore count=4; // 设置一个count，最多有四个哲学家可以进来
void philosopher(int i)
{
	while(true)
	{
		think();
		wait(count); //请求进入房间进餐 当count为0时 不能允许哲学家再进来了
		wait(chopstick[i]); //请求左手边的筷子
		wait(chopstick[(i+1)%5]); //请求右手边的筷子
		eat();
		signal(chopstick[i]); //释放左手边的筷子
		signal(chopstick[(i+1)%5]); //释放右手边的筷子
		signal(count); //离开饭桌释放信号量
	}
}

避免死锁策略二：

仅当哲学家的左右两支筷子都可用时，才允许他拿起筷子进餐。可以利用AND 型信号量机制实现，也可以利用信号量的保护机制实现。利用信号量的保护机制实现的思想是通过记录型信号量mutex对取左侧和右侧筷子的操作进行保护，使之成为一个原子操作，这样可以防止死锁的出现。描述如下：

semaphore mutex = 1; // 这个过程需要判断两根筷子是否可用，并保护起来
semaphore chopstick[5]={1,1,1,1,1};
void philosopher(int i)
{
	while(true)
	{
		/* 这个过程中可能只能由一个人在吃饭，效率低下，有五只筷子，其实是可以达到两个人同时吃饭 */
		think();
		wait(mutex); // 保护信号量
		wait(chopstick[(i+1)%5]); // 请求右手边的筷子
		wait(chopstick[i]); // 请求左手边的筷子
		signal(mutex); // 释放保护信号量
		eat();
		signal(chopstick[(i+1)%5]); // 释放右手边的筷子
		signal(chopstick[i]); // 释放左手边的筷子
	}
}

避免死锁策略三：

规定奇数号的哲学家先拿起他左边的筷子，然后再去拿他右边的筷子；而偶数号的哲学家则先拿起他右边的筷子，然后再去拿他左边的筷子。按此规定，将是1、2号哲学家竞争1号筷子，3、4号哲学家竞争3号筷子。即五个哲学家都竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一个哲学家能获得两支筷子而进餐。

semaphore chopstick[5]={1,1,1,1,1};
void philosopher(int i)
{
	while(true)
	{
		think();
		if(i%2 == 0) //偶数哲学家，先右后左。
		{
			wait (chopstick[(i + 1)%5]) ;
			wait (chopstick[i]) ;
			eat();
			signal (chopstick[(i + 1)%5]) ;
			signal (chopstick[i]) ;
		}
		else //奇数哲学家，先左后右。
		{
			wait (chopstick[i]) ;
			wait (chopstick[(i + 1)%5]) ;
			eat();
			signal (chopstick[i]) ;
			signal (chopstick[(i + 1)%5]) ;
		}
	}
}

AND型信号量

semaphore chopstick[5]={1,1,1,1,1};
do{
	//think()
	Swait(chopstick[(i+1)%5],chopstick[i]);
	//eat()
	Ssignal(chopstick[(i+1)%5],chopstick[i]);
}while(true)

首先，我们需要理解AND信号量的工作原理。AND信号量允许一个进程或线程继续执行，只有当所有关联的信号量都满足条件（即非负）时。

哲学家问题中的五个哲学家和五只筷子可以看作是五个进程和五个资源。每个哲学家在思考和进餐时都需要两只筷子，即两个资源。

为了解决这个问题，我们可以为每个哲学家设置一个AND信号量。初始时，所有信号量的值都为1，表示每只筷子都可用。当一个哲学家想要进餐时，他需要同时获取两只筷子。这可以通过使用AND信号量来实现，只有当两只筷子的信号量都为1时，该哲学家才能继续执行。

具体来说，当一个哲学家想要进餐时，他需要执行以下操作：

1. 尝试获取他左边的筷子的信号量。如果成功，进入下一步；否则，该哲学家无法进餐，需要等待。
2. 尝试获取他右边的筷子的信号量。如果成功，进入下一步；否则，该哲学家无法进餐，需要等待。
3. 如果两个信号量都成功获取，该哲学家可以拿起两只筷子并进入进餐状态。在进餐结束后，他需要释放两个信号量，表示两只筷子都可用。

通过使用AND信号量，我们可以确保在任何时候只有一个哲学家能够拿起两只筷子，从而避免死锁的发生。