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

操作系統(tǒng)課程設(shè)計生產(chǎn)者和消費(fèi)者問題系 院：計算機(jī)科學(xué)系學(xué)生姓名：吳偉學(xué) 號：0734130101專 業(yè)：軟件工程年 級：0701B完成日期：2009年11月指導(dǎo)教師：劉栓一、課程設(shè)計的性質(zhì)與任務(wù)1、生產(chǎn)者-消費(fèi)者問題是很經(jīng)典很具有代表性的進(jìn)程同步問題，計算機(jī)中的很多同步問題都可抽象為生產(chǎn)者-消費(fèi)者問題，通過本實(shí)驗(yàn)的練習(xí)，希望能加深學(xué)生對進(jìn)程同步問題的認(rèn)識與理解。2、熟悉VC的使用，培養(yǎng)和提高學(xué)生的分析問題、解決問題的能力。二、課程設(shè)計的內(nèi)容及其要求1 實(shí)驗(yàn)內(nèi)容以生產(chǎn)者/消費(fèi)者模型為依據(jù)，在Windows 2000環(huán)境下創(chuàng)建一個控制臺進(jìn)程，在該進(jìn)程中創(chuàng)建n個線程模擬生產(chǎn)者和消費(fèi)者，實(shí)現(xiàn)進(jìn)程(線程)的同步與互斥。2 實(shí)驗(yàn)要求l 學(xué)習(xí)并理解生產(chǎn)者/消費(fèi)者模型及其同步/互斥規(guī)則；l 學(xué)習(xí)了解Windows同步對象及其特性；l 熟悉實(shí)驗(yàn)環(huán)境，掌握相關(guān)API的使用方法；l 設(shè)計程序，實(shí)現(xiàn)生產(chǎn)者/消費(fèi)者進(jìn)程(線程)的同步與互斥；l 提交實(shí)驗(yàn)報告。三、課程設(shè)計的時間安排課程設(shè)計時間 8課時四、課程設(shè)計的實(shí)驗(yàn)環(huán)境本實(shí)驗(yàn)是在winxpVC6.0環(huán)境下實(shí)現(xiàn)的，利用Windows SDK編制實(shí)例程序。所以試驗(yàn)需要在windows下安裝VC后進(jìn)行。VC是一個集成開發(fā)環(huán)境，其中包含了Windows SDK所有工具和定義；所以安裝了VC后就不用特意安裝SDK了。五、正文1、 實(shí)驗(yàn)程序的結(jié)構(gòu)圖（流程圖）；開始ProduceWait BufferWait ProductsConsume結(jié)束While produceWhile consume2、數(shù)據(jù)結(jié)構(gòu)及信號量定義的說明；(1) CreateThreadl 功能創(chuàng)建一個在調(diào)用進(jìn)程的地址空間中執(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定義一個給進(jìn)程傳遞參數(shù)的指針。dwCreationFlags定義控制線程創(chuàng)建的附加標(biāo)志。lpThread保存線程標(biāo)志符(32位)(2) CreateMutexl 功能創(chuàng)建一個命名或匿名的互斥量對象l 格式HANDLE CreateMutex(LPSECURITY_ATTRIBUTES lpMutexAttributes,BOOL bInitialOwner,LPCTSTR lpName);l 參數(shù)說明lpMutexAttributes必須取值NULL。bInitialOwner指示當(dāng)前線程是否馬上擁有該互斥量(即馬上加鎖)。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保存信號量當(dāng)前值。(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ū)對象的所有權(quán)l(xiāng) 格式VOID enterCriticalSection(LPCRITICAL_SECTION lpCriticalSection);l 參數(shù)說明lpCriticalSection指向臨界區(qū)對象的指針。(9) LeaveCriticalSectionl 功能釋放指定臨界區(qū)對象的所有權(quán)l(xiāng) 格式VOID LeaveCriticalSection(LPCRITICAL_SECTION lpCriticalSection);l 參數(shù)說明lpCriticalSection指向臨界區(qū)對象的指針。3、實(shí)驗(yàn)的步驟；(1) 打開VC，選擇菜單項(xiàng)file-new,選擇projects選項(xiàng)卡并建立一個名為 R_WP1的win32 console applicatoin工程；創(chuàng)建時注意指定創(chuàng)建該工程的目錄；(2) 在工程中創(chuàng)建源文件 R_WP1.cpp：選擇菜單項(xiàng)project-add to project-files，在選擇框中輸入自己想要創(chuàng)建的文件名，這里是 R_WP1.cpp；在接下來詢問是否創(chuàng)建新文件時回答yes；然后通過Workspace-FileView-Source Files打開該文件，在其中編輯源文件并保存.(3) 通過調(diào)用菜單命令項(xiàng)build-build all進(jìn)行編譯連接,可以在指定的工程目錄下得到debug- R_WP1.exe程序，然后把給定的test.txt文件存入該debug目錄下，就可以在控制臺進(jìn)入該debug目錄運(yùn)行程序了。需要強(qiáng)調(diào)的是在創(chuàng)建數(shù)據(jù)文件時，由于涉及到文件格式問題，最好在記事本中手工逐個輸入數(shù)據(jù)，而不要拷貝粘貼數(shù)據(jù)。4、 主要算法創(chuàng)建生產(chǎn)者和消費(fèi)者線程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);/確認(rèn)有空緩沖區(qū)可供生產(chǎn)，同時將空位置數(shù)empty減1；用于生產(chǎn)者和消費(fèi)者的同步；wait_for_semaphore= WaitForSingleObject(empty_semaphore,-1);/互斥訪問下一個可用于生產(chǎn)的空臨界區(qū)，實(shí)現(xiàn)寫寫互斥；wait_for_mutex = WaitForSingleObject(h_mutex,-1);int ProducePos = FindProducePosition(); ReleaseMutex(h_mutex);/生產(chǎn)者在獲得自己的空位置并做上標(biāo)記后，以下的寫操作在生產(chǎn)者之間可以并發(fā)；/核心生產(chǎn)步驟中，程序?qū)⑸a(chǎn)者的ID作為產(chǎn)品編號放入，方便消費(fèi)者識別;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ū)可以被多個消費(fèi)者使用，實(shí)現(xiàn)讀寫同步；ReleaseSemaphore(h_Semaphorem_serial,n_Thread,NULL);消費(fèi)者進(jìn)程void Consume(void * p)/局部變量聲明；DWORDwait_for_semaphore,m_delay;intm_serial,m_requestNum; /消費(fèi)者的序列號和請求的數(shù)目；intm_thread_requestMAX_THREAD_NUM;/本消費(fèi)線程的請求隊列； /提取本線程的信息到本地；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)進(jìn)行所需產(chǎn)品的消費(fèi)for(i =0;ithread_requesti =-1; if(!IfInOtherRequest(m_thread_requesti)Buffer_CriticalBufferPos = -1; /標(biāo)記緩沖區(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、實(shí)驗(yàn)運(yùn)行圖；6、實(shí)驗(yàn)結(jié)果分析；只有在生產(chǎn)者生產(chǎn)了產(chǎn)品并將產(chǎn)品存放到緩沖池中消費(fèi)者才能去消費(fèi)，當(dāng)緩沖池為空時消費(fèi)者不能消費(fèi)六、 結(jié)論（應(yīng)當(dāng)準(zhǔn)確、完整、明確精練；也可以在結(jié)論或討論中提出建議、設(shè)想、尚待解決問題等。）七、 參考文獻(xiàn)【1】湯子瀛等.計算機(jī)操作系統(tǒng).西安電子科技大學(xué)出版社.2007年2月【2】張堯?qū)W等編著，計算機(jī)操作系統(tǒng)教程，清華出版社。2002.2【3】嚴(yán)蔚敏，吳偉民編著，數(shù)據(jù)結(jié)構(gòu)，清華大學(xué)出版社。2002【4】陳向群編著，操作系統(tǒng)教程，北京大學(xué)出版社，2001.07【5】鄭莉等編著，C+語言設(shè)計。北京：清華大學(xué)出版社.2000八、 指導(dǎo)教師評語 簽名： 年 月 日課程設(shè)計成績附：課程設(shè)計源代碼：#include#include#include#include#include/定義常量；/此程序允許的最大臨界區(qū)數(shù)；#define MAX_BUFFER_NUM10/秒到微秒的乘法因子；#define INTE_PER_SEC 1000/本程序允許的生產(chǎn)和消費(fèi)線程的總數(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í)際的線程的數(shù)目；DWORDn_Buffer_or_Critical; /實(shí)際的緩沖區(qū)或者臨界區(qū)的數(shù)目；HANDLEh_SemaphoreMAX_THREAD_NUM; /生產(chǎn)者允許消費(fèi)者開始消費(fèi)的信號量；/生產(chǎn)消費(fèi)及輔助函數(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);/提取每個線程的信息到相應(yīng)數(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+; /回顯獲得的線程信息，便于確認(rèn)正確性；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號來為相應(yīng)生產(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)者和消費(fèi)者線程；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;/確認(rèn)是否還有對同一產(chǎn)品的消費(fèi)請求未執(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;/找出當(dāng)前可以進(jìn)行產(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;/找出當(dāng)前所需生產(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);/確認(rèn)有空緩沖區(qū)可供生產(chǎn)，同時將空位置數(shù)empty減1；用于生產(chǎn)者和消費(fèi)者的同步；wait_for_semaphore= WaitForSingleObject(empty_semaphore,-1);/互斥訪問下一個可用于生產(chǎn)的空臨界區(qū)，實(shí)現(xiàn)寫寫互斥；wait_for_mutex = WaitForSingleObject(h_mutex,-1);int ProducePos = FindProducePosition(); ReleaseMutex(h_mutex);/生產(chǎn)者在獲得自己的空位置并做上標(biāo)記后，以下的寫操作在生產(chǎn)者之間可以并發(fā)；/核心生產(chǎn)步驟中，程序?qū)⑸a(chǎn)者的ID作為產(chǎn)品編號放入，方便消費(fèi)者識別;printf(Producer %2d begin to produce at position %2d.n,m_serial,ProducePos);Buffer_CriticalProducePos = m_serial;printf(Producer %2d finish p