操作系統(tǒng)實驗報告

1、操作系統(tǒng)實驗報告實驗名稱：哲學家就餐問題班級：通信1202班學號：U201213584姓名：趙越指導老師：許毅平一、實驗目的1. 熟練使用VC+6.0編譯環(huán)境，調試并正確運行程序，更加熟練地利用 c語言解 決問題2. 了解哲學家就餐的基本原理，掌握死鎖的必要條件。3. 理解源程序中產(chǎn)生和防止的算法，及相關窗口操作。二、實驗原理1. 問題描述：有五個哲學家圍坐在一圓桌旁， 桌中央有一盤通心粉， 每人面前有一只空盤子， 每兩人 之間放一只筷子每個哲學家的行為是思考，感到饑餓，然后吃通心粉 . 為了吃通心粉，每 個哲學家必須拿到兩只筷子，并且每個人只能直接從自己的左邊或右邊去取筷子。 2分析問題：假

2、如所有的哲學家都同時拿起左側筷子， 看到右側筷子不可用， 又都放下左側筷子， 等 一會兒，又同時拿起左側筷子，如此這般，永遠重復。對于這種情況，即所有的程序都在無 限期地運行，但是都無法取得任何進展，即出現(xiàn)饑餓，所有哲學家都吃不上飯。規(guī)定在拿到左側的筷子后， 先檢查右面的筷子是否可用。 如果不可用， 則先放下左側筷 子，等一段時間再重復整個過程。分析： 當出現(xiàn)以下情形， 在某一個瞬間， 所有的哲學家都同時啟動這個算法，拿起左側 的筷子，而看到右側筷子不可用，又都放下左側筷子，等一會兒，又同時拿起左側筷子如此這樣永遠重復下去。 對于這種情況， 所有的程序都在運行，但卻無法取得進展，即出現(xiàn) 饑餓，

3、所有的哲學家都吃不上飯。解決死鎖問題 :為了避免死鎖，把哲學家分為三種狀態(tài)，思考，饑餓，進食，并且一次 拿到兩只筷子，否則不拿 .。僅當一個哲學家左右兩邊筷子都可用時， 才允許他拿筷子。 這樣要么一次占有兩只筷子 在吃面，然后釋放所有資源；要么不占用資源。這樣就不會導致死鎖了。由以上的分析可以得出以下結論：（1）、防止死鎖發(fā)生的分配方式：僅當一個哲學家左右兩邊的筷子都可用時，才允許他拿筷子。這樣要么一次占有兩只 筷子（所有線程需要的資源）進行下一步的吃通心粉，然后釋放所有的資源；要么不占用 資源，這樣就不可能產(chǎn)生死鎖了。（2）、產(chǎn)生死鎖的分配方式： 當筷子（資源）可用時，先分配左邊的筷子，等待

4、一會后再分配右邊的筷子，由于這個過程中，左邊的筷子一直沒有釋放，就有可能產(chǎn)生死鎖了。三、實驗過程實驗的偽代碼如下所示：1. 不發(fā)生死鎖的方式（要么一下占用兩支筷子，要么不占用）var mutexleftchopstick,mutexrightchopstick;beging:resting;waiting;p(mutexleftchopstick);p(mutexrightchopstick);GetResource(leftchopstick,rightchopstick);eating;v(mutexleftchopstick);v(mutexrightchopstick);end2. 發(fā)

5、生死鎖的方式(一旦可以占用筷子，就馬上占用)var mutexleftchopstick,mutexrightchopstick;beging:resting;waiting;p(mutexleftchopstick);GetResource(leftchopstick);p(mutexrightchopstick);GetResource(rightchopstick);eating;v(mutexleftchopstick);v(mutexrightchopstick);end與之前分析的一樣，當兩只筷子都沒被占用時才去獲取筷子，這樣就 打破了死鎖的必要條件，即不發(fā)生死鎖；而當有筷子即占用

6、，看似效率很 高，但因為資源有限，且不可搶占，很容易發(fā)生死鎖。以下即為該實驗的完整源代碼：#define WIN32_LEAN_AND_MEAN#include <stdio.h>#include <stdlib.h>#include <windows.h>#include <windowsx.h>#include <string.h>#include <math.h>#include "dining.h"HINSTANCE hInst;/ Application Instance HandleHWND

7、 hWndMain;/ Main Window HandleHBITMAP hbmpOffscreen;LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM); void RenderOffscreen(HDC hDestDC);BOOL bWaitMultiple;BOOL bFastFood;extern int gDinerState;extern int gChopstickState;extern HANDLE gchopStickPHILOSOPHER/S/ 1; chopstick between each philopher a

8、nd his neighbor*/*/*/*/* ROUTINE: WndProc/*/* PURPOSE: Processes messagesI*/LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)PAINTSTRUCT ps;HDC hdc;switch (message)case WM_COMMAND: switch (wParam) case CM_EXIT:PostMessage(hWndMain, WM_CLOSE, 0, 0L); break; break;case WM

9、_FORCE_REPAINT: MSG msg;InvalidateRect(hWndMain, NULL, TRUE); while (PeekMessage(&msg, hWndMain, WM_FORCE_REPAINT,WM_FORCE_REPAINT,TRUE) break;case WM_PAINT:hdc = BeginPaint(hWndMain, &ps);RenderOffscreen(hdc);EndPaint(hWndMain, &ps); break;case WM_CLOSE:return DefWindowProc(hWndMain, me

10、ssage, wParam, lParam);case WM_DESTROY:PostQuitMessage(0); break;default:return DefWindowProc(hWnd, message, wParam, lParam);return (0);BOOL CreateOffscreen()HWND hwndScreen = GetDesktopWindow();HDC hdc= GetDC(hwndScreen);int nWidth = GetSystemMetrics( SM_CXSCREEN );int nHeight = GetSystemMetrics( S

11、M_CYSCREEN );hbmpOffscreen = CreateCompatibleBitmap( hdc, nWidth, nHeight );ReleaseDC(hwndScreen, hdc);if ( !hbmpOffscreen )return FALSE;elsereturn TRUE;void RenderOffscreen(HDC hDestDC)HDC hdc= hDestDC; / CreateCompatibleDC(hWndMain);int err=GetLastError();HBITMAP hOldBitmap = SelectObject(hdc, hbm

12、pOffscreen);RECT rect;HPEN hPen; double dx, dy, px, py, AngRad, dDeltaAng; int pos, p1;long CenterX, CenterY;hPen = SelectObject(hdc, CreatePen(PS_SOLID, 3, 0L);GetClientRect(hWndMain, &rect);/* Draw the table */CenterX = (rect.right- rect.left)/2;CenterY = (rect.bottom- rect.top)/2;Ellipse(hdc,

13、 CenterX- 100, CenterY- 100, CenterX + 100, CenterY + 100);/* Draw the chopsticks */ dDeltaAng = 360 / PHILOSOPHERS; / 筷子間的角度差 for (pos = 0; pos < PHILOSOPHERS; pos+/+/F)IXIT /* Draw the chopsticks */ AngRad = (pos * dDeltaAng)/57.29577951; / 轉化為弧度 dx = CenterX + (sin(AngRad)*60);dy = CenterY- (c

14、os(AngRad)*60); MoveToEx(hdc, (int)dx, (int)dy, NULL);dx = CenterX + (sin(AngRad)*85); dy = CenterY- (cos(AngRad)*85); LineTo(hdc, (int)dx, (int)dy);/Draw the plate弧度AngRad = (pos * dDeltaAng+dDeltaAng / 2)/57.29577951; / 轉化為 dx = CenterX + (sin(AngRad) * 72);dy = CenterY- (cos(AngRad) * 72);Ellipse

15、(hdc, (int)dx-12, (int)dy-12, (int)dx+12, (int)dy+12); /* delete the black pen */ DeleteObject(SelectObject(hdc, hPen);/* Draw the philosophers */ for(pos = 0; pos < PHILOSOPHERS; pos+) /* select a pen for each philosopher */ switch (gDinerStatepos)case RESTING:hPen = SelectObject(hdc, CreatePen(

16、PS_SOLID, 3, RGB(0, 255, 0); break;case WAITING:case EATING:hPen = SelectObject(hdc, CreatePen(PS_SOLID, 3, RGB(255, 0, 0); break;default:hPen = SelectObject(hdc, CreatePen(PS_SOLID, 3, 0L);AngRad = (pos * dDeltaAng) + dDeltaAng / 2)/57.29577951; px = CenterX + (sin(AngRad)*150);py = CenterY- (cos(A

17、ngRad)*150);/* Draw the Philosopher */Ellipse(hdc, (int)px-25, (int)py-25, (int)px+25, (int)py+25);/Draw the left armif (gChopstickStatepos = pos)MoveToEx(hdc, (int)px, (int)py, NULL);AngRad = (pos * dDeltaAng)/57.29577951; /轉/ 化為弧度 dx = CenterX + (sin(AngRad)*85);dy = CenterY- (cos(AngRad)*85);Line

18、To(hdc, (int)dx, (int)dy);/Draw the right armp1 = pos + 1;if (p1 = PHILOSOPHERS)p1 = 0;if (gChopstickStatep1 = pos)MoveToEx(hdc, (int)px, (int)py, NULL);AngRad = (p1 * dDeltaAng)/57.29577951;dx = CenterX + (sin(AngRad)*85);dy = CenterY- (cos(AngRad)*85);LineTo(hdc, (int)dx, (int)dy);/* Delete the pe

19、n */DeleteObject(SelectObject(hdc, hPen); /for posBitBlt( hDestDC,rect.left, rect.top, rect.right - rect.left, rect.bottom -rect.top, hdc, rect.left, rect.top, SRCCOPY);GetLastError();SelectObject(hdc, hOldBitmap);/ DeleteDC(hWndMain, hdc);*/* ROUTINE: InitApplication /*/*/* PURPOSE: Initialize the

20、application*/*/BOOL InitApplication(HINSTANCE hInstance)WNDCLASS wc;wc.style = CS_HREDRAW | CS_VREDRAW;wc.lpfnWndProc = WndProc;wc.cbClsExtra = 0;wc.cbWndExtra = 0;wc.hInstance = hInstance;wc.hIcon = LoadIcon(NULL, IDI_APPLICATION);wc.hCursor = LoadCursor(NULL, IDC_ARROW);wc.hbrBackground = (HBRUSH)

21、(COLOR_WINDOW+1); wc.lpszMenuName = "din"wc.lpszClassName = "dinWClass"RegisterClass(&wc);return TRUE; /*/*/*/*/* ROUTINE: InitInstance/*/* PURPOSE: Saves instance handle and creates main window /*/BOOL InitInstance(HINSTANCE hInstance, int nCmdShow) int ret;hInst = hInstance

22、;hWndMain = CreateWindow( "dinWClass", "Dining Philosopher", WS_OVERLAPPEDWINDOW, CW_USEDEFAULT, CW_USEDEFAULT, 450, 450, NULL, NULL, hInstance, NULL );if (!hWndMain)return FALSE;ShowWindow(hWndMain, nCmdShow);UpdateWindow(hWndMain);if (!CreateOffscreen()PostQuitMessage(1);ret =

23、MessageBox(hWndMain, "你期望使用防死鎖運行模式嗎 ?nn" "如果選擇 Yes, 程序將正常運行 .n" " 如果選擇 No, 程序會進入死鎖 .n", "Wait Mode", MB_YESNO);if (ret = IDYES)bWaitMultiple = TRUE;elsebWaitMultiple = FALSE;ret = MessageBox(hWndMain, "你期望快速進入死鎖嗎 ?nn" "如果選擇 Yes, 將更快進入死鎖 .n"

24、, "Wait Mode", MB_YESNO);if (ret = IDYES) bFastFood = TRUE;else bFastFood = FALSE;/ Start the threads Diner();return TRUE; */*/*/* FUNCTION: WinMain/* /* PURPOSE: Calls initialization function, processes message loop*/*/int PASCAL WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow)MSG msg;int i;if (!hPrevInstance)if (!InitApplication(hInstance) return (FALSE);if (!InitInstance(hInstance, nCmdShow) return (FALSE);while (GetMessage(&msg, NULL, 0, 0)TranslateMessage(&msg);DispatchMessage(&msg);/ Clear the tablefor (i