操作系統(tǒng)生產(chǎn)者與消費者課程設計.doc

操作系統(tǒng)課程設計生產(chǎn)者和消費者問題系 院：計算機科學系學生姓名：吳偉學 號：0734130101專 業(yè)：軟件工程年 級：0701B完成日期：2009年11月指導教師：劉栓一、課程設計的性質(zhì)與任務1、生產(chǎn)者-消費者問題是很經(jīng)典很具有代表性的進程同步問題，計算機中的很多同步問題都可抽象為生產(chǎn)者-消費者問題，通過本實驗的練習，希望能加深學生對進程同步問題的認識與理解。2、熟悉VC的使用，培養(yǎng)和提高學生的分析問題、解決問題的能力。二、課程設計的內(nèi)容及其要求1 實驗內(nèi)容以生產(chǎn)者/消費者模型為依據(jù)，在Windows 2000環(huán)境下創(chuàng)建一個控制臺進程，在該進程中創(chuàng)建n個線程模擬生產(chǎn)者和消費者，實現(xiàn)進程(線程)的同步與互斥。2 實驗要求l 學習并理解生產(chǎn)者/消費者模型及其同步/互斥規(guī)則；l 學習了解Windows同步對象及其特性；l 熟悉實驗環(huán)境，掌握相關API的使用方法；l 設計程序，實現(xiàn)生產(chǎn)者/消費者進程(線程)的同步與互斥；l 提交實驗報告。三、課程設計的時間安排課程設計時間 8課時四、課程設計的實驗環(huán)境本實驗是在winxpVC6.0環(huán)境下實現(xiàn)的，利用Windows SDK編制實例程序。所以試驗需要在windows下安裝VC后進行。VC是一個集成開發(fā)環(huán)境，其中包含了Windows SDK所有工具和定義；所以安裝了VC后就不用特意安裝SDK了。五、正文1、 實驗程序的結(jié)構(gòu)圖（流程圖）；開始ProduceWait BufferWait ProductsConsume結(jié)束While produceWhile consume2、數(shù)據(jù)結(jié)構(gòu)及信號量定義的說明；(1) CreateThreadl 功能創(chuàng)建一個在調(diào)用進程的地址空間中執(zhí)行的線程l 格式HANDLE CreateThread( LPSECURITY_ATTRIBUTES lpThreadAttributes,DWORD dwStackSize,LPTHREAD_START_ROUTINE lpStartAddress,LPVOID lpParamiter,DWORD dwCreationFlags,Lpdword lpThread );l 參數(shù)說明lpThreadAttributes指向一個LPSECURITY_ATTRIBUTES(新線程的安全性描述符)。dwStackSize定義原始堆棧大小。lpStartAddress指向使用LPTHRAED_START_ROUTINE類型定義的函數(shù)。lpParamiter定義一個給進程傳遞參數(shù)的指針。dwCreationFlags定義控制線程創(chuàng)建的附加標志。lpThread保存線程標志符(32位)(2) CreateMutexl 功能創(chuàng)建一個命名或匿名的互斥量對象l 格式HANDLE CreateMutex(LPSECURITY_ATTRIBUTES lpMutexAttributes,BOOL bInitialOwner,LPCTSTR lpName);l 參數(shù)說明lpMutexAttributes必須取值NULL。bInitialOwner指示當前線程是否馬上擁有該互斥量(即馬上加鎖)。lpName互斥量名稱。(3) CreateSemaphorel 功能創(chuàng)建一個命名或匿名的信號量對象l 格式HANDLE CreateSemaphore(LPSECURITY_ATTRIBUTES lpSemaphoreAttributes, LONG lInitialCount, LONG lMaximumCount, LPCTSTR lpName );l 參數(shù)說明lpSemaphoreAttributes必須取值NULL。lInitialCount信號量的初始值。該值大于0，但小于lMaximumCount指定的最大值。lMaximumCount信號量的最大值。lpName信號量名稱。(4) WaitForSingleObjectl 功能使程序處于等待狀態(tài)，直到信號量hHandle出現(xiàn)(即其值大于等于1)或超過規(guī)定的等待時間l 格式DWORD WaitForSingleObject(HANDLE hHandle, DWORD dwMilliseconds);l 參數(shù)說明hHandle信號量指針。dwMilliseconds等待的最長時間(INFINITE為無限等待)。(5) ReleaseSemaphorel 功能對指定信號量加上一個指定大小的量。成功執(zhí)行則返回非0值l 格式BOOL ReleaseSemaphore(HANDLE hSemaphore,LONG lReleaseCount,LPLONG lppreviousCount );l 參數(shù)說明hSemaphore信號量指針。lReleaseCount信號量的增量。lppreviousCount保存信號量當前值。(6) ReleaseMutexl 功能打開互斥鎖，即把互斥量加1。成功調(diào)用則返回0l 格式BOOL ReleaseMutex(HANDLE hMutex);l 參數(shù)說明hMutex互斥量指針。(7) InitializeCriticalSectionl 功能初始化臨界區(qū)對象l 格式VOID InitializeCriticalSection(LPCRITICAL_SECTION lpCriticalSection);l 參數(shù)說明lpCriticalSection指向臨界區(qū)對象的指針。(8) EnterCriticalSectionl 功能等待指定臨界區(qū)對象的所有權l(xiāng) 格式VOID enterCriticalSection(LPCRITICAL_SECTION lpCriticalSection);l 參數(shù)說明lpCriticalSection指向臨界區(qū)對象的指針。(9) LeaveCriticalSectionl 功能釋放指定臨界區(qū)對象的所有權l(xiāng) 格式VOID LeaveCriticalSection(LPCRITICAL_SECTION lpCriticalSection);l 參數(shù)說明lpCriticalSection指向臨界區(qū)對象的指針。3、實驗的步驟；(1) 打開VC，選擇菜單項file-new,選擇projects選項卡并建立一個名為 R_WP1的win32 console applicatoin工程；創(chuàng)建時注意指定創(chuàng)建該工程的目錄；(2) 在工程中創(chuàng)建源文件 R_WP1.cpp：選擇菜單項project-add to project-files，在選擇框中輸入自己想要創(chuàng)建的文件名，這里是 R_WP1.cpp；在接下來詢問是否創(chuàng)建新文件時回答yes；然后通過Workspace-FileView-Source Files打開該文件，在其中編輯源文件并保存.(3) 通過調(diào)用菜單命令項build-build all進行編譯連接,可以在指定的工程目錄下得到debug- R_WP1.exe程序，然后把給定的test.txt文件存入該debug目錄下，就可以在控制臺進入該debug目錄運行程序了。需要強調(diào)的是在創(chuàng)建數(shù)據(jù)文件時，由于涉及到文件格式問題，最好在記事本中手工逐個輸入數(shù)據(jù)，而不要拷貝粘貼數(shù)據(jù)。4、 主要算法創(chuàng)建生產(chǎn)者和消費者線程for(i =0;iserial;m_delay = (DWORD)(ThreadInfo*)(p)-delay *INTE_PER_SEC);Sleep(m_delay);/開始請求生產(chǎn)printf(Producer %2d sends the produce require.n,m_serial);/確認有空緩沖區(qū)可供生產(chǎn)，同時將空位置數(shù)empty減1；用于生產(chǎn)者和消費者的同步；wait_for_semaphore= WaitForSingleObject(empty_semaphore,-1);/互斥訪問下一個可用于生產(chǎn)的空臨界區(qū)，實現(xiàn)寫寫互斥；wait_for_mutex = WaitForSingleObject(h_mutex,-1);int ProducePos = FindProducePosition(); ReleaseMutex(h_mutex);/生產(chǎn)者在獲得自己的空位置并做上標記后，以下的寫操作在生產(chǎn)者之間可以并發(fā)；/核心生產(chǎn)步驟中，程序?qū)⑸a(chǎn)者的ID作為產(chǎn)品編號放入，方便消費者識別;printf(Producer %2d begin to produce at position %2d.n,m_serial,ProducePos);Buffer_CriticalProducePos = m_serial;printf(Producer %2d finish producing :n ,m_serial);printf( position %2d :%3d n ,ProducePos,Buffer_CriticalProducePos);/使生產(chǎn)者寫的緩沖區(qū)可以被多個消費者使用，實現(xiàn)讀寫同步；ReleaseSemaphore(h_Semaphorem_serial,n_Thread,NULL);消費者進程void Consume(void * p)/局部變量聲明；DWORDwait_for_semaphore,m_delay;intm_serial,m_requestNum; /消費者的序列號和請求的數(shù)目；intm_thread_requestMAX_THREAD_NUM;/本消費線程的請求隊列； /提取本線程的信息到本地；m_serial = (ThreadInfo*)(p)-serial;m_delay = (DWORD)(ThreadInfo*)(p)-delay *INTE_PER_SEC);m_requestNum = (ThreadInfo *)(p)-n_request;for (int i = 0;ithread_requesti;Sleep(m_delay);/循環(huán)進行所需產(chǎn)品的消費for(i =0;ithread_requesti =-1; if(!IfInOtherRequest(m_thread_requesti)Buffer_CriticalBufferPos = -1; /標記緩沖區(qū)為空；printf(Consumer%2d finish consuming %2d:n ,m_serial,m_thread_requesti);printf( position %2d :%3d n ,BufferPos,Buffer_CriticalBufferPos);ReleaseSemaphore(empty_semaphore,1,NULL); elseprintf(Consumer %2d finish consuming product %2dn ,m_serial,m_thread_requesti); /離開臨界區(qū) LeaveCriticalSection(&PC_CriticalBufferPos); 5、實驗運行圖；6、實驗結(jié)果分析；只有在生產(chǎn)者生產(chǎn)了產(chǎn)品并將產(chǎn)品存放到緩沖池中消費者才能去消費，當緩沖池為空時消費者不能消費六、 結(jié)論（應當準確、完整、明確精練；也可以在結(jié)論或討論中提出建議、設想、尚待解決問題等。）七、 參考文獻【1】湯子瀛等.計算機操作系統(tǒng).西安電子科技大學出版社.2007年2月【2】張堯?qū)W等編著，計算機操作系統(tǒng)教程，清華出版社。2002.2【3】嚴蔚敏，吳偉民編著，數(shù)據(jù)結(jié)構(gòu)，清華大學出版社。2002【4】陳向群編著，操作系統(tǒng)教程，北京大學出版社，2001.07【5】鄭莉等編著，C+語言設計。北京：清華大學出版社.2000八、 指導教師評語 簽名： 年 月 日課程設計成績附：課程設計源代碼：#include#include#include#include#include/定義常量；/此程序允許的最大臨界區(qū)數(shù)；#define MAX_BUFFER_NUM10/秒到微秒的乘法因子；#define INTE_PER_SEC 1000/本程序允許的生產(chǎn)和消費線程的總數(shù)；#define MAX_THREAD_NUM 64/定義一個結(jié)構(gòu)，記錄在測試文件中指定的每一個線程的參數(shù)struct ThreadInfointserial;/線程序列號charentity; /是P還是Cdoubledelay;/線程延遲intthread_requestMAX_THREAD_NUM; /線程請求隊列intn_request;/請求個數(shù);/全局變量的定義/臨界區(qū)對象的聲明,用于管理緩沖區(qū)的互斥訪問；CRITICAL_SECTIONPC_CriticalMAX_BUFFER_NUM;int Buffer_CriticalMAX_BUFFER_NUM; /緩沖區(qū)聲明，用于存放產(chǎn)品；HANDLE h_ThreadMAX_THREAD_NUM; /用于存儲每個線程句柄的數(shù)組；ThreadInfoThread_InfoMAX_THREAD_NUM; /線程信息數(shù)組；HANDLEempty_semaphore; /一個信號量；HANDLEh_mutex; /一個互斥量；DWORDn_Thread = 0; /實際的線程的數(shù)目；DWORDn_Buffer_or_Critical; /實際的緩沖區(qū)或者臨界區(qū)的數(shù)目；HANDLEh_SemaphoreMAX_THREAD_NUM; /生產(chǎn)者允許消費者開始消費的信號量；/生產(chǎn)消費及輔助函數(shù)的聲明void Produce(void *p);void Consume(void *p);bool IfInOtherRequest(int);int FindProducePositon();int FindBufferPosition(int);int main(void)/聲明所需變量；DWORDwait_for_all;ifstreaminFile;/初始化緩沖區(qū)；for(int i=0;i MAX_BUFFER_NUM;i+)Buffer_Criticali = -1;/初始化每個線程的請求隊列；for(int j=0;jMAX_THREAD_NUM;j+)for(int k=0;kMAX_THREAD_NUM;k+)Thread_Infoj.thread_requestk = -1;Thread_Infoj.n_request = 0;/初始化臨界區(qū)；for(i =0;i n_Buffer_or_Critical;inFile.get();printf(輸入文件是:n);/回顯獲得的緩沖區(qū)的數(shù)目信息；printf(%d n,(int) n_Buffer_or_Critical);/提取每個線程的信息到相應數(shù)據(jù)結(jié)構(gòu)中；while(inFile)inFile Thread_Infon_Thread.serial;inFile Thread_Infon_Thread.entity;inFile Thread_Infon_Thread.delay;char c;inFile.get(c);while(c!=n& !inFile.eof() inFile Thread_Infon_Thread.thread_requestThread_Infon_Thread.n_request+; inFile.get(c);n_Thread+; /回顯獲得的線程信息，便于確認正確性；for(j=0;j(int) n_Thread;j+)int Temp_serial = Thread_Infoj.serial;char Temp_entity = Thread_Infoj.entity;double Temp_delay = Thread_Infoj.delay;printf( n thread%2d %c %f ,Temp_serial,Temp_entity,Temp_delay);int Temp_request = Thread_Infoj.n_request;for(int k=0;kTemp_request;k+)printf( %d , Thread_Infoj.thread_requestk);coutendl;printf(nn); /創(chuàng)建在模擬過程中幾個必要的信號量empty_semaphore=CreateSemaphore(NULL,n_Buffer_or_Critical,n_Buffer_or_Critical, semaphore_for_empty);h_mutex= CreateMutex(NULL,FALSE,mutex_for_update);/下面這個循環(huán)用線程的ID號來為相應生產(chǎn)線程的產(chǎn)品讀寫時所/使用的同步信號量命名；for(j=0;j(int)n_Thread;j+) std:string lp =semaphore_for_produce_;int temp =j;while(temp)char c = (char)(temp%10);lp+=c;temp/=10;h_Semaphorej+1=CreateSemaphore(NULL,0,n_Thread,lp.c_str();/創(chuàng)建生產(chǎn)者和消費者線程；for(i =0;i (int) n_Thread;i+)if(Thread_Infoi.entity =P)h_Threadi= CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(Produce),&(Thread_Infoi),0,NULL);else h_Threadi=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(Consume),&(Thread_Infoi),0,NULL);/主程序等待各個線程的動作結(jié)束；wait_for_all = WaitForMultipleObjects(n_Thread,h_Thread,TRUE,-1);printf( n nALL Producer and consumer have finished their work. n);getch();return 0;/確認是否還有對同一產(chǎn)品的消費請求未執(zhí)行；bool IfInOtherRequest(int req)for(int i=0;in_Thread;i+)for(int j=0;jThread_Infoi.n_request;j+)if(Thread_Infoi.thread_requestj = req)return TRUE;return FALSE;/找出當前可以進行產(chǎn)品生產(chǎn)的空緩沖區(qū)位置；intFindProducePosition()int EmptyPosition;for (int i =0;in_Buffer_or_Critical;i+)if(Buffer_Criticali = -1)EmptyPosition = i;/用下面這個特殊值表示本緩沖區(qū)正處于被寫狀態(tài)；Buffer_Criticali = -2;break;return EmptyPosition;/找出當前所需生產(chǎn)者生產(chǎn)的產(chǎn)品的位置；int FindBufferPosition(int ProPos)int TempPos;for (int i =0 ;iserial;m_delay = (DWORD)(ThreadInfo*)(p)-delay *INTE_PER_SEC);Sleep(m_delay);/開始請求生產(chǎn)printf(Producer %2d sends the produce require.n,m_serial);/確認有空緩沖區(qū)可供生產(chǎn)，同時將空位置數(shù)empty減1；用于生產(chǎn)者和消費者的同步；wait_for_semaphore= WaitForSingleObject(empty_semaphore,-1);/互斥訪問下一個可用于生產(chǎn)的空臨界區(qū)，實現(xiàn)寫寫互斥；wait_for_mutex = WaitForSingleObject(h_mutex,-1);int ProducePos = FindProducePosition(); ReleaseMutex(h_mutex);/生產(chǎn)者在獲得自己的空位置并做上標記后，以下的寫操作在生產(chǎn)者之間可以并發(fā)；/核心生產(chǎn)步驟中，程序?qū)⑸a(chǎn)者的ID作為產(chǎn)品編號放入，方便消費者識別;printf(Producer %2d begin to produce at position %2d.n,m_serial,ProducePos);Buffer_CriticalProducePos = m_serial;printf(Producer %2d finish p