操原上機（三） 哲學家就餐問題的死鎖與非死鎖解法

實驗目的

了解線程/程序的死鎖概念和如何解決死鎖

實驗内容

在 windows 環境下，利用進階語言程式設計環境（限定為 VS 環境或 VC 環境）調用 CreateThread 函數哲學家就餐問題的示範。

要求：

（1）提供死鎖的解法和非死鎖的解法；

（2）有圖形界面直覺顯示哲學家取筷子，吃飯，放筷子，思考等狀态。

（3）為增強結果的随機性，各個狀态之間的維持時間采用随機時間，例如100ms-500ms 之間。

實驗過程

用C語言程式設計

思路如下圖所示：

首先，需要解決的是在windows環境下實作p操作和v操作，這一點在之前的實驗中已經模拟過了，是以不再介紹，直接上代碼：

//建立5個信号量
for(int i=0;i<5;i++){
	S[i] = CreateSemaphore(NULL ,1 ,1,name[i]);
}
//打開信号量：
HANDLE right,left;
left =OpenSemaphore(SEMAPHORE_ALL_ACCESS,FALSE,name[id]);
right=OpenSemaphore(SEMAPHORE_ALL_ACCESS,FALSE,name[(id+4)%5]);
WaitForSingleObject(left,INFINITE);	//p操作
ReleaseSemaphore(left,1,NULL);	//v操作

           

完成p v操作之後，就可以按照上圖中的僞代碼進行程式的編寫了。代碼如下：

#include <stdio.h>
#include <windows.h>
#include <time.h>

int i = 0; 
char name[5][2]={"0","1","2","3","4"};
int a[5]={1,1,1,1,1};
int random(void){
	int a=time (NULL);
	srand(a);
	return (rand()%400+100);
}
//子線程函數  
DWORD WINAPI philosopher(LPVOID lpParam){
	int id = i++;
	int time;
	HANDLE right,left;
	left =OpenSemaphore(SEMAPHORE_ALL_ACCESS,FALSE,name[id]);
	right=OpenSemaphore(SEMAPHORE_ALL_ACCESS,FALSE,name[(id+4)%5]);
	while(1){
		time = random();
		printf("哲學家%d開始思考，将思考%dms\n",id,time);
		Sleep(time);
		time = random();
		printf("哲學家%d開始休息，将休息%dms\n",id,time);
		Sleep(time);
		//p(left)
		WaitForSingleObject(left,INFINITE); 
		printf("哲學家%d取了左手邊的筷子\t%d\n",id,id);
		//p(right)
		WaitForSingleObject(right,INFINITE); 
		printf("哲學家%d取了右手邊的筷子\t%d\n",id,(id+4)%5);
		//吃飯
		time = random();
		printf("哲學家%d開始吃飯，将吃飯%dms\n",id,time);
		Sleep(time);
		//v
		ReleaseSemaphore(left,1,NULL);
		printf("哲學家%d放下左手邊的筷子\t%d\n",id,id);
		ReleaseSemaphore(right,1,NULL);
		printf("哲學家%d放下右手邊的筷子\t%d\n",id,(id+4)%5);
	}
}
int main(void){
	HANDLE S[5];
	HANDLE hThread[5];
	for(int i=0;i<5;i++){
		S[i] = CreateSemaphore(NULL ,1 ,1,name[i]);
	}
	
	for(int i=0;i<5;i++){
		hThread[i] = CreateThread(NULL,0,philosopher,NULL,0,NULL);
	} 
	WaitForMultipleObjects(5,hThread,TRUE,10000); 	//等待子線程運作 
	for(int i=0;i<5;i++){
		CloseHandle(S[i]); 
	}
}

           

如果要避免死鎖，隻需要破壞死鎖條件就可以了。這裡我們可以采用有序資源配置設定方法來破壞環路條件，進而避免死鎖。具體做法為将第0個哲學家的左筷子編号與右筷子編号互換，這樣每一個哲學家的左筷子編号都比右筷子編号大，都會先請求編号大的資源，請求到之後再請求編号小的資源，進而不可能出現每一個哲學家都占有一個資源的情況出現。是以我們隻需對原來的代碼稍做以下修改即可：

HANDLE right,left;
if(id==0){
	right =OpenSemaphore(SEMAPHORE_ALL_ACCESS,FALSE,name[id]);
	left=OpenSemaphore(SEMAPHORE_ALL_ACCESS,FALSE,name[(id+4)%5]);
}
else{
	left =OpenSemaphore(SEMAPHORE_ALL_ACCESS,FALSE,name[id]);
	right=OpenSemaphore(SEMAPHORE_ALL_ACCESS,FALSE,name[(id+4)%5]);
}