E2.进程（线程）同步及死锁

《操作系统实验指南》

实验二 进程（线程）同步及死锁

一、实验目的

在多进程（线程）运行环境中，进程（线程）之间并发执行，如果对进程（线程）访问临界资源（如公共变量）的操作不加限制，就会产生“与时间有关”的错误。为防止这类错误，必须用同步机构控制进程（线程）对临界资源（公共变量）的访问。

在一个进程（线程）需要两个或两个以上的临界资源时，如果申请和推进顺序不当，会造成死锁，即多个进程（线程）因竞争临界资源而造成的一种僵局，若无外力作用，这些进程（线程）都将永远不能再向前执行。

本实验利用Windows系统提供的同步机制，来协调线程（Thread）间的并发执行，并比较各种预防死锁的措施，以加深对同步机制和死锁的理解，并学会在并发程序中引用同步机构，并预防死锁的编程方法。

二、实验要求

熟悉Windows操作系统及VC++程序设计方法

三、实验内容

设计解决哲学家就餐问题的并发线程。

假定有6个哲学家，围着圆桌交替地进行思考和进餐；每次进餐时，必须同时拿到左右两边的两只筷子才能进餐；进餐后，再放下筷子继续思考。

这是一个典型的同时需要两个资源的例子，如果申请资源顺序不当，可能会引起死锁。

本实验设计6个哲学家共享一个相同的线程Philosopher，既完成线程同步，又预防死锁发生。实验中采用了3种预防死锁的方法（摒弃‘环路等待’条件，摒弃‘请求和保持’条件，摒弃‘不剥夺’条件），要预防死锁，只采用其中的任何一种方法即可。

四、Windows及VC++并发线程同步机制程序设计简介 1、Windows线程简介

-1-

在Windows环境下，一个进程（即一个执行文件*.exe）可以同时包含多个线程，每个线程是一个分配CPU和独立执行的单位，线程可并发执行，但在访问同类临界资源的线程之间，必须采用同步机制，实现对临界资源（如公共缓冲区）的同步访问。

2、VC++并发线程设计简介 ⑴、创建线程

采用CreateThread(LPSECURITY_ATTRIBUTES lpThreadAttributes, // 线程安全属性

DWORD dwStackSize,

// 堆栈大小 // 线程启动函数 // 线程函数参数 // 线程创建属性 // 线程标识

LPTHREAD_START_ROUTINE lpStartAddress, LPVIOD lpParameter,

DWORD dwCreationFlags, LPDWORD lpThreadId);

函数可创建一个线程。

最简洁地创建线程形式为：

hThread = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE) ThreadName, NULL, 0, &ThreadID );

该形式只给出创建的线程名（ThreadName）和返回值（ThreadID），其余值皆为默认值。 ⑵、创建信号量

采用CreateSemaphore(LPSECURITY_ATTRIBUTES lpsa,

LONG lInitialCount, LONG lMaxCount,

// 安全属性 // 初始值 // 最大值 // 信号量名

LPTSTR lpszSemName);

创建一般信号量最简洁方式为：（hSemaphore为一般信号量句柄） hSemaphore = CreateSemaphore(NULL, 0, MAXCOUNT-1, NULL); 等待信号量同样采用WaitForInputIdle ()函数，可以用以下形式： WaitForSingleObject(hSemaphore, INFINITE); 发送信号量:

采用ReleaseSemaphore(HANDLE hSemaphore,

LONG lRelease,

LPLONG lplPrevious);

// 信号量句柄 // 发信号量数 // 前次信号量值

⑶、等待信号量和发送信号量

发送一般信号量最简洁方式为： ReleaseSemaphore(hSemaphore, 1, NULL); ⑷、摒弃‘环路等待’条件

使至少有一位哲学家拿筷子的顺序与其它哲学家不同。

-2-

本实验设计第0个哲学家从右边拿筷子，而其它哲学家从左边拿筷子。程序实现如下：

if (ThreadID == 0) { }

R1 = (ThreadID+1) % 6; R2 = ThreadID;

⑸、摒弃‘请求和保持’条件

使哲学家同时拿到两只筷子，否则，一只筷子也不拿。程序实现如下：

Wait(Mutex);

if ((ChopstickUsed[R1]) || (ChopstickUsed[R2])) { }

Signal(Mutex);

如果哲学家不能拿到第二只筷子，则第一只筷子也放弃掉。程序实现如下：

Wait(Mutex);

if (ChopstickUsed[R2]) { }

Signal(Mutex);

Signal(Mutex); goto ReleaseChopstick; Signal(Mutex); goto LoopAgain;

⑹、摒弃‘不剥夺’条件

-3-

HWND hWind; HDC hWDC;

void InitThreadSemaphore(void); void DrawPhilosopher(void);

//--------------------------------------------------------------------------- // DWORD FAR PASCAL InitThreadSemaphore() //

// Description:

// Window主函数 //

//---------------------------------------------------------------------------

LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam) { int wmId, wmEvent; PAINTSTRUCT ps; HDC hdc; TCHAR szHello[MAX_LOADSTRING]; LoadString(hInst, IDS_HELLO, szHello, MAX_LOADSTRING); switch (message) { case WM_CREATE: hWind = hWnd; hWDC = GetDC(hWnd); break; case WM_COMMAND: wmId = LOWORD(wParam); wmEvent = HIWORD(wParam); // Parse the menu selections: switch (wmId) { case IDM_EAT: InitThreadSemaphore(); break; case IDM_EXIT: ReleaseDC(hWnd, hWDC); DestroyWindow(hWnd); break; default: return DefWindowProc(hWnd, message, wParam, lParam);

-4-

}

break;

case WM_DESTROY: PostQuitMessage(0); break; default: return DefWindowProc(hWnd, message, wParam, lParam); }

return 0; }

case WM_PAINT: hdc = BeginPaint(hWnd, &ps); // TODO: Add any drawing code here... RECT rt; GetClientRect(hWnd, &rt);

DrawPhilosopher(); EndPaint(hWnd, &ps); break;

-5-

HANDLE Mutex; // 互斥信号量 HANDLE ChopStick[6]; // 筷子信号量 BOOL ChopstickUsed[6]; // 筷子已被其它线程申请并保持 DWORD PhilosopherID[6]; // 哲学家线程标识符 HANDLE tPhilosopher[6]; // 哲学家线程句柄 RECT PRect[6] = {{350, 100, 380, 130}, {650, 100, 680, 130}, {800, 310, 830, 340},

{650, 520, 680, 550}, {350, 520, 380, 550}, {200, 310, 230, 340}};

HBRUSH hBrush[7]; // 红、绿、蓝、黄、白色刷子

POINT CPolygon[6][4] = {{{210, 177}, {290, 217}, {284, 226}, {204, 186}}, {{510, 50}, {520, 50}, {520, 130}, {510, 130}}, {{724, 217}, {804, 177}, {810, 185}, {730, 225}}, {{730, 427}, {810, 467}, {804, 476}, {724, 436}}, {{510, 520}, {520, 520}, {520, 600}, {510, 600}}, {{204, 467}, {284, 427}, {290, 435}, {210, 475}}};

DWORD FAR PASCAL Philosopher(LPVOID); // 哲学家线程 void Wait(HANDLE); // 等待信号量 void Signal(HANDLE); // 发送信号量 void DrawChopstick(HBRUSH, int, BOOL); // 用对应颜色刷子画筷子

// 并设置/取消使用标记

void WaitTime(int);

//--------------------------------------------------------------------------- // DWORD FAR PASCAL InitThreadSemaphore() //

// Description:

// 生成哲学家线程及各种信号量和变量初始化 //

//--------------------------------------------------------------------------- void InitThreadSemaphore() { int i; hBrush[0] = CreateSolidBrush(RGB(255, 0, 0 )); hBrush[1] = CreateSolidBrush(RGB( 0, 255, 0 )); hBrush[2] = CreateSolidBrush(RGB( 0, 0, 255)); hBrush[3] = CreateSolidBrush(RGB(255, 255, 0 )); hBrush[4] = CreateSolidBrush(RGB( 0, 255, 255)); hBrush[5] = CreateSolidBrush(RGB(255, 0, 255)); hBrush[6] = CreateSolidBrush(RGB(255, 255, 255)); DrawPhilosopher();

-6-

// 红色刷子 // 绿色刷子 // 蓝色刷子 // 黄色刷子 // 青色刷子 // 棕色刷子 // 白色刷子

for (i=0; i<6; i++) ChopStick[i] = CreateSemaphore(NULL, 1, 1, NULL); // 生成筷子信号量 Mutex = CreateSemaphore(NULL, 1, 1, NULL); // 生成互斥信号量--画筷子或判断筷子是否被申请 for (i=0; i<6; i++) ChopstickUsed[i] = FALSE; // 筷子未被其它线程申请并保持 tPhilosopher[0] = CreateThread((LPSECURITY_ATTRIBUTES) NULL, // 生成哲学家0线程 0, (LPTHREAD_START_ROUTINE) Philosopher, \ 0, &PhilosopherID[0]); tPhilosopher[1] = CreateThread((LPSECURITY_ATTRIBUTES) NULL, // 生成哲学家1线程 0, (LPTHREAD_START_ROUTINE) Philosopher, \ 0, &PhilosopherID[1]); tPhilosopher[2] = CreateThread((LPSECURITY_ATTRIBUTES) NULL, // 生成哲学家2线程 0, (LPTHREAD_START_ROUTINE) Philosopher, \ 0, &PhilosopherID[2]); tPhilosopher[3] = CreateThread((LPSECURITY_ATTRIBUTES) NULL, // 生成哲学家3线程 0, (LPTHREAD_START_ROUTINE) Philosopher, \ 0, &PhilosopherID[3]); tPhilosopher[4] = CreateThread((LPSECURITY_ATTRIBUTES) NULL, // 生成哲学家4线程 0, (LPTHREAD_START_ROUTINE) Philosopher, \ 0, &PhilosopherID[4]); tPhilosopher[5] = CreateThread((LPSECURITY_ATTRIBUTES) NULL, // 生成哲学家5线程 0, (LPTHREAD_START_ROUTINE) Philosopher, \ 0, &PhilosopherID[5]); }

void DrawPhilosopher(void) { int i; SelectObject(hWDC, hBrush[6]); for (i=0; i<6; i++) Polygon(hWDC, CPolygon[i], 4); for (i=0; i<6; i++) {

-7-

SelectObject(hWDC, hBrush[i]); Ellipse(hWDC, PRect[i].left, PRect[i].top, PRect[i].right, PRect[i].bottom); } }

//--------------------------------------------------------------------------- // DWORD FAR PASCAL Philosopher1() //

// Description:

// 哲学家线程----线程同步及预防死锁 //

//--------------------------------------------------------------------------- DWORD FAR PASCAL Philosopher(LPVOID ThreadParaStr) { int Loop, ThreadID; int R1, R2; ThreadID = atoi((char *) ThreadParaStr); Loop = 0; while (TRUE) { R1 = ThreadID; R2 = (ThreadID+1) % 6; /* // 摒弃‘环路等待’条件 if (ThreadID == 0) { R1 = (ThreadID+1) % 6; R2 = ThreadID; } */ /* // 摒弃‘请求和保持’条件 Wait(Mutex); if ((ChopstickUsed[R1]) || (ChopstickUsed[R2])) { Signal(Mutex); goto LoopAgain; } Signal(Mutex); */ Wait(ChopStick[R1]); DrawChopstick(hBrush[ThreadID], R1, TRUE); /*

-8-

// 拿到左手筷子 // 将筷子画上颜色并设置使用标志 // 摒弃‘不剥夺’条件 Wait(Mutex); if (ChopstickUsed[R2]) { Signal(Mutex); goto ReleaseChopstick; } Signal(Mutex); */ Wait(ChopStick[R2]); // 拿到右手筷子 DrawChopstick(hBrush[ThreadID], R2, TRUE); // 将筷子画上颜色并设置使用标志 WaitTime(1000*((Loop*ThreadID%5)+1)); // 吃饭 DrawChopstick(hBrush[6], R2, FALSE); // 去掉筷子颜色并取消筷子已使用标志 Signal(ChopStick[R2]);

ReleaseChopstick: DrawChopstick(hBrush[6], R1, FALSE); // 去掉筷子颜色并取消筷子已使用标志 Signal(ChopStick[R1]);

LoopAgain: WaitTime(2000*(Loop%7+1)); // 思考 if (Loop++>10000) Loop = 0; } return(0); }

//--------------------------------------------------------------------------- // DWORD FAR PASCAL Philosopher4() //

// Description: // 画筷子线程 //

//---------------------------------------------------------------------------

void DrawChopstick(HBRUSH hChopstickBrush, int ChopstickID, BOOL ChopstickUsedID) { Wait(Mutex); if (ChopstickUsedID) { ChopstickUsed[ChopstickID] = TRUE; // 设置筷子已使用标志 SelectObject(hWDC, hChopstickBrush); Polygon(hWDC, CPolygon[ChopstickID], 4); } else {

-9-

ChopstickUsed[ChopstickID] = FALSE; // 取消筷子已使用标志

SelectObject(hWDC, hChopstickBrush); Polygon(hWDC, CPolygon[ChopstickID], 4); } Signal(Mutex); }

//--------------------------------------------------------------------------- // void WaitTime() //

// Description:

// 延迟器(单位ms) //

//--------------------------------------------------------------------------- void WaitTime(int msTime) { int i; double Area, PI, r; PI = 3.14159; r = 10.12345; for (i=0; i<300 * msTime; i++) Area = PI * r * r; }

void Wait(HANDLE hSemaphore) { WaitForSingleObject(hSemaphore, INFINITE); }

void Signal(HANDLE hSemaphore) { ReleaseSemaphore(hSemaphore, 1, NULL); }

-10-

// 等待信号量

// 发送信号量

本文来源：https://www.bwwdw.com/article/5c96.html