操作系统实验报告.docx

操作系统实验报告实验名称：哲学家就餐问题 班 级：通信1202班 学 号：U201213584 姓 名：赵越 指导老师：许毅平一、实验目的1.熟练使用VC+6.0编译环境，调试并正确运行程序，更加熟练地利用c语言解决问题2.了解哲学家就餐的基本原理，掌握死锁的必要条件。3.理解源程序中产生和防止的算法，及相关窗口操作。二、实验原理1. 问题描述： 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子每个哲学家的行为是思考，感到饥饿，然后吃通心粉.为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子。2分析问题： 假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子，如此这般，永远重复。对于这种情况，即所有的程序都在无限期地运行，但是都无法取得任何进展，即出现饥饿，所有哲学家都吃不上饭。规定在拿到左侧的筷子后，先检查右面的筷子是否可用。如果不可用，则先放下左侧筷子，等一段时间再重复整个过程。分析：当出现以下情形，在某一个瞬间，所有的哲学家都同时启动这个算法，拿起左侧的筷子，而看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子如此这样永远重复下去。对于这种情况，所有的程序都在运行，但却无法取得进展，即出现饥饿，所有的哲学家都吃不上饭。解决死锁问题:为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿.。仅当一个哲学家左右两边筷子都可用时，才允许他拿筷子。这样要么一次占有两只筷子在吃面，然后释放所有资源；要么不占用资源。这样就不会导致死锁了。由以上的分析可以得出以下结论：（1）、防止死锁发生的分配方式：仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子。这样要么一次占有两只筷子（所有线程需要的资源）进行下一步的吃通心粉，然后释放所有的资源；要么不占用资源，这样就不可能产生死锁了。（2）、产生死锁的分配方式：当筷子（资源）可用时，先分配左边的筷子，等待一会后再分配右边的筷子，由于这个过程中，左边的筷子一直没有释放，就有可能产生死锁了。三、实验过程实验的伪代码如下所示：1.不发生死锁的方式（要么一下占用两支筷子，要么不占用 ）var mutexleftchopstick,mutexrightchopstick;beging: resting; waiting; p(mutexleftchopstick); p(mutexrightchopstick); GetResource(leftchopstick,rightchopstick); eating; v(mutexleftchopstick); v(mutexrightchopstick);end2.发生死锁的方式（一旦可以占用筷子，就马上占用） var mutexleftchopstick,mutexrightchopstick;beging: resting; waiting; p(mutexleftchopstick); GetResource(leftchopstick); p(mutexrightchopstick); GetResource(rightchopstick); eating; v(mutexleftchopstick); v(mutexrightchopstick);end与之前分析的一样，当两只筷子都没被占用时才去获取筷子，这样就打破了死锁的必要条件，即不发生死锁；而当有筷子即占用，看似效率很高，但因为资源有限，且不可抢占，很容易发生死锁。以下即为该实验的完整源代码：#define WIN32_LEAN_AND_MEAN#include #include #include #include #include #include #include dining.hHINSTANCE hInst;/ Application Instance HandleHWND hWndMain; / Main Window Handle HBITMAPhbmpOffscreen;LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);void RenderOffscreen(HDC hDestDC);BOOL bWaitMultiple;BOOL bFastFood;extern int gDinerState;extern int gChopstickState;extern HANDLE gchopStickPHILOSOPHERS;/ 1 chopstick between each philopher and his neighbor/*/*ROUTINE:WndProc*/*/*PURPOSE:Processes messages*/*/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_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, message, 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);intnWidth= GetSystemMetrics( SM_CXSCREEN );intnHeight= GetSystemMetrics( SM_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, hbmpOffscreen);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, CenterX - 100, CenterY - 100, CenterX + 100, CenterY + 100);/* Draw the chopsticks */dDeltaAng = 360 / PHILOSOPHERS; /筷子间的角度差for (pos = 0; pos PHILOSOPHERS; pos+)/FIXIT/* Draw the chopsticks */AngRad = (pos * dDeltaAng)/57.29577951; /转化为弧度dx = CenterX + (sin(AngRad)*60);dy = CenterY - (cos(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 plateAngRad = (pos * dDeltaAng+dDeltaAng / 2)/57.29577951; /转化为弧度dx = CenterX + (sin(AngRad) * 72);dy = CenterY - (cos(AngRad) * 72);Ellipse(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(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(AngRad)*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);LineTo(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 pen */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 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)(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;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 = MessageBox(hWndMain, 你期望使用防死锁运行模式吗?nn如果选择Yes, 程序将正常运行.n如果选择 No, 程序会进入死锁.n,Wait Mode, MB_YESNO);if (ret = IDYES)bWaitMultiple = TRUE;elsebWaitMultiple = FALSE;ret = MessageBox(hWndMain, 你期望快速进入死锁吗?nn如果选择Yes, 将更快进入死锁.n,Wait Mode, MB_YESNO);if (ret = IDYES)bFastFood = TRUE;elsebFastFood = FALSE;/ Start the threadsDiner();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) Transla